Functional Programming: Currying vs Partial Application

As functional programming becomes popular, many developers, including me, are curious to find out what is the fuss about Scala and Clojure. After playing with functional programming for a while, I came across concepts called currying and partial application. Unfortunately, these two concepts are not properly explained in either books or on-line resources ^2-4. The concepts are very simple once we understand them. Let's start with the formal definition of Curry ¹:

Given a function f of type f:(A x B) -> C , then currying it makes a function curry(f): A -> (B -> C) . That is, curry(f) takes an argument of type A and returns a function of type B -> C .

I will be using Scheme to demonstrate this concept. A simple non-curry subtract function will look like this:

(define (subtract a b)
  (- a b))

(subtract 10 2)
;Value: 8

Going back to the first part of the definition, i.e. f:(A x B) -> C, the subtract function takes two arguments and produces value 8.

After we curry the subtract function, we have the following:

(define (subtract a)
 (lambda (b)
   (- a b)))

((subtract 10) 2)  ;; extra parenthesis is used to invoke the returned function
;Value: 8

From the second part of the definition, i.e. curry(f): A -> (B -> C), the subtract function takes one argument, a, and returns a function, lambda, which takes another argument, b. The lambda function will be evaluated and returns 8.

Partial Application is just an application of curry function. Instead of returning a function with only one argument, a function with multiple arguments is returned. Consider a simple calculator below:

(define (make-calculator a)
(lambda (operation b)
(cond ((eq? operation 'add) (+ a b))
      ((eq? operation 'subtract) (- a b))
      (else (error "Unknown operation"
                   operation)))))

(define cal (make-calculator 10)) ;; returns a function with two arguments

(cal 'add 5)
;Value: 15

After sifting through the on-line resources ^1-4, I found wikipedia has the best explanation of curry and partial application. In practice, people use the terms curry and partial application interchangeably because partial application is just an application of curry. But, it is important to know the distinction.

Resources:

1. Wikipedia
2. What is currying
3. Currying vs. Partial Application
4. Partial Application != Currying

Amazon's biased coin toss problem

I was at CodeMash conference last week. Amazon.com was one of the vendors at the conference. They were recruiting people at the conference. They posted all kinds of brain teaser problems for the attendees to solve. One of the problems drew my attention and I have been obsessed with it for a few days. Here is the problem:

You are given a randomFlip() that returns true 50% of the time. Implements a biasedFlip() that returns true 31.416% of the time using randomFlip().

I have taken probability courses in high school and college. All the probability problems I came across involved calculating probabilities for certain number of coins or dices. The above problem is new to me. I applied all my probability knowledge but got nowhere. So, I turned to google and found this solution. The solution is a bit confusing because it is used to break a three or more way tie, or create a probability distribution other than 50-50. We need to create a probability distribution other than 50-50 for our problem. I was stuck again because I don't understand some of the steps. Again, I turned to Internet. This time, I turned to Dr. Math for help. It is a great site to search for Math solution or ask a question. After getting some clarifications from Dr. Math, I managed to construct the following steps for our problem:

Step 1: The probability for each outcome is 31.416%.

Step 2: The intervals are [0, 0.31416) and [0.31416, 1).

Step 3: Convert 0.31416 to binary decimal.

0.31416 * 2 = 0.62832
0.62832 * 2 = 1.25664
0.25664 * 2 = 0.51328
0.51328 * 2 = 1.02656
0.02656 * 2 = 0.05312
0.05312 * 2 = 0.10624
0.10624 * 2 = 0.21248
0.21248 * 2 = 0.42496
0.42496 * 2 = 0.84992
0.84992 * 2 = 1.69984
0.69984 * 2 = 1.39968
0.39968 * 2 = 0.79936
0.79936 * 2 = 1.59872
0.59872 * 2 = 1.19744
0.19744 * 2 = 0.39488
0.39488 * 2 = 0.78976
0.78976 * 2 = 1.57952

From the above, the binary decimal for 0.31416 is 0.01010000011011001.

Step 4: true = 1; false = 0

Step 5: Call randomFlip() and record each result.

Step 6: Convert the sequence of true and false to a binary decimal according to step 4.

Step 7: Will be illustrated by below code.

The following code illustrates how to create a biased flip program:

public boolean biasedFlip() {
       String binaryProbabilityInString = "01010000011011001";    // binary decimal for 0.31416
      
       for (int i=0; i<binaryProbabilityInString.length(); i++) {
           boolean isTrue = randomFlip();
           if (isTrue && binaryProbabilityInString.charAt(i) == '1') {
               continue;
           } else if (!isTrue && binaryProbabilityInString.charAt(i) == '0') {
               continue;
           } else if (!isTrue && binaryProbabilityInString.charAt(i) == '1') {
               return true;    // when the probability of the toss is < 0.31416
           } else if (isTrue && binaryProbabilityInString.charAt(i) == '0') {
               return false;    // when the probability of the toss is > 0.0.31416
           }
       }
       return true;
   }

randomFlip() is trivial and we will skip that. It returns true 50% of the time. Let's assume that true = 1 and false = 0. In biasedFlip(), we loop through each bit of 0.31416. If the randomFlip() returns true (1) and the bit is “1” or randomFlip() returns false (0) and the bit is “0”, we call randomFlip() again. If randomFlip() returns false (0) and the bit is 1, it means the probability of next and future coin flip will be less than 0.31416. For example, if the first two flips return 00 (represents 0.00 in binary decimal form), the decimal value will be less than 0.01 (first two bits of 0.31416). We are sure that the probability of next and future flip will be in [0, 0.31416) interval. So, there is no need for us to flip the coin any further and we are done. On the other hand, if randomFlip() returns true (1) and the bit is 0, it means the probability of next and future coin flip will be greater than 0.31416. For example, if the first flip returns 1 (represents 0.1 in binary decimal form), 0.1 will be greater than 0.01 (first two bits of 0.31416). We are sure that the probability of next and future flip will be in [0.31416, 1) interval. As a result, there is no need for us to flip the coin any further and we are done.

The probability problem is interesting and challenging. I learned a lot by working through the problem. It is a popular interview question asked by companies like Amazon and Facebook but there are not many solutions on the Web. In my opinion, this is a lousy interview question. People who do not work with probability a lot won't come across this kind of problem. However, it is a good programming exercise and I enjoyed it.

Update: I sent an email to the author of "How to Simulate a Biased Coin Toss With a Fair Coin" to get some clarifications on the steps and he updated the article with some examples.