Saturday, October 30, 2010

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 1:

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

No comments:

Post a Comment