Next: Induction (20 points) Up: CS212 Preliminary Exam I Previous: Analysis of Algorithms (30

Higher-Order Functions (10 points)

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 <function>)
       (method ((f <function>))
         (method (x)
           (method (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 <function>) ((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 <function>) ((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)

(define (uncurry <function>)
  (method ((f <function>))
    (method (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.

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

Next: Induction (20 points) Up: CS212 Preliminary Exam I Previous: Analysis of Algorithms (30