Higher-Order Functions

The following function (named after the famed Mathematician Haskel B. Curry) takes a function f of two arguments and returns a new function which, when given an argument x returns a function which, when given an argument y, returns the application of f to x and y.

     (define (curry f)
       (lambda (x)
         (lambda (y) (f x y))))

For instance, (((curry +) 3) 4) returns (+ 3 4) = 7. Currying is useful for turning 2-argument functions into one argument functions that can be used many more times in conjunction with a given constant. For instance, we can define the increment function as follows:

     (define incr ((curry +) 1))

     (incr 3) --> 4
     (incr 41) --> 42

As another example, we can define the function that appends the list '(1 2 3 4) to the front of any other list as:

     (define append-stuff ((curry append) '(1 2 3 4))

     (append-stuff '(5 6)) --> '(1 2 3 4 5 6)
     (append-stuff '(9 10 11)) --> '(1 2 3 4 9 10 11)

a.

Define a function uncurry with the property that, if f is a function of two arguments, then:

((uncurry (curry f)) x y) = (f x y)

b.

Use the substitution model to prove that for all f, x and y (of the appropriate types),

((uncurry (curry f)) x y) = (f x y)

Show all of the steps.

Solution

Return to CS 212 Prelim 1 - Spring 1998