Function Currying in Scheme

Jeffrey A. Meunier
University of Connecticut
jeffm@cse.uconn.edu

December 7, 1995
Revised March 15, 1997

Abstract

A method for generalized function currying in Scheme is given. Function currying is the process of partially, or incrementally, supplying arguments to a function. Curried functions are delayed functions expecting the remainder of the arguments to be supplied. Once all the arguments are supplied, the function evaluates normally. A good working knowledge of Scheme is assumed.

All code examples were written using PC Scheme version 4.02, although no architecture-specific functions were used.

1 Currying in Functional Languages

Functional languages such as Haskell and ML enjoy the benefits of function currying. Currying is the incomplete application of arguments to a function. For example, in Haskell we could write the function mult which takes two integers and returns their product

        mult :: Int -> Int -> Int
        mult x y = x * y

Evaluating mult 2 6 would yield 12, as expected. To curry a function, one needs only to leave off one or more of the rightmost arguments. (Argument application must occur in a left-to-right order.) Evaluating mult 2 would yield the curried function (mult 2), which is a function of arity 1 (meaning it expects 1 argument). An argument can be applied to this function by evaluating (mult 2) 6, for instance. The inclusion of parentheses is important because it distinguishes the application of one argument to a curried function from the application of two arguments to a non-curried function.

Functions can be built of curried functions as

        double = mult 2

(or equivalently)

        double = (*) 2

where (*) is the prefix application of the infix multiplication operator. The expression (2 *) is equivalent to (*) 2, but prefix operators are better for understanding function currying. Evaluating double 6 then yields 12.

2 Partial Argument Application in Scheme

The concept of partial argument application is not new to Scheme users. This is nothing more than returning a lambda abstraction from a function, with lexically-bound free variables. The previous example can easily be coded in Scheme as

        (define (mult y) (lambda (x) (* y x)))

The free variable y in the lambda function becomes statically bound to the argument to (mult y). Evaluating (mult n) returns the lambda abstraction

        (lambda (x) (* n x))

and allows one to create constant multiplier functions. Then

        (define (double x) ((mult 2) x))

would create a doubler, similar to the one described in Haskell above.

3 Generalized Explicit Currying in Scheme

The Scheme example above is rather specific to the function upon which partial argument application is occurring, namely mult. It is easy, though, to create a generalized function currier:

        (define (curry fun . args)
          (lambda x
            (apply fun (append args x))))

This function takes a function and some number of arguments (0 or more) to be applied to that function as arguments, and returns a function expecting more arguments. When the curried function is evaluated with arguments, a complete argument list is created from both the original partial argument list and the new completing argument list (using append), and the original function is evaluated with the new argument list (using apply).

The doubler could then be built using the curry function

        (define double (curry * 2))
        => DOUBLE
        (double 6)
        => 12

Curried functions can be built of other curried functions, as in

        (define lister1 (curry list 'args))
        (define lister2 (curry lister1 'one))
        (define lister3 (curry lister2 'two))

Evaluating each of the functions would yield

        (lister1 'foo)     =>     (args foo)
        (lister2 'bar)     =>     (args one bar)
        (lister3 'baz)     =>     (args one two baz)

Since the original function of the curried function (which is list) can accept multiple arguments, the curried function can also accept multiple arguments

        (define lister4 (curry list 'foo 'bar 'baz))
        (lister4 'qux 'quux)     =>     (foo bar baz qux quux)

4 Implicit Currying in Scheme

A drawback of the explicit method of currying described above is that it is explicit. To curry a function one must use the curry function. One must also know when all the arguments are present, then supply them without using the curry function. It would be better if a function, when called with some number of arguments, automatically determines if it needs more arguments or if it has all its arguments and can evluate itself, just like in Haskell. The c-lambda macro, given below, accomplishes just that.

        (macro c-lambda
          (lambda (e)
            (let* ((params (cadr e))
                   (expr (caddr e))
                   (lp (length params)))
              (lambda args
                (let ((la (length args)))
                  (cond ((< la lp)
                         (let ((params$ (%c-diff args params))
                               (expr$ `((lambda ,(%c-isect args params)
                                                ,expr)
                                        ,@(%c-quote-all args))))
                           (eval `(c-lambda ,params$ ,expr$))))
                        ((= la lp)
                         (eval `((lambda ,params ,expr) 
                                ,@(%c-quote-all args))))
                        (else
                          (error `(error ,expr called with ,la
                                         arguments expected ,lp)))))))))

Three support functions are needed for c-lambda. They are

        ;- return those elements of list y that do not have corresponding 
        ;- elements in list x (simple set difference operation)
        (define %c-diff
          (named-lambda (%c-r x y)
            (if (null? x)
                y
                (%c-r (cdr x) (cdr y)))))

        ;- return those elements of list y that have corresponding
        ;- elements in list x (simple set intersection)
        (define %c-isect
          (named-lambda (%c-b x y)
            (if (null? x) 
                () 
                (cons (car y) (%c-b (cdr x) (cdr y))))))

        ;- return x with each element quoted
        (define (%c-quote-all x)
          (map (lambda (y) (list 'quote y)) x))

c-lambda is used in the same way that the standard lambda special form is used.

A good example of one of the uses of function currying is with the assoc function. assoc expects the item being sought as the first argument, then the list to search as the second argument. The function becomes more useful, though, when the parameters are reversed and the function is curriable, defined as follows with c-lambda:

        (define assoc-r
          (c-lambda (lst item)
            (assoc item lst)))

Evaluating assoc-r with the arguments of a list and an item in the list (in that order) yields a pair just like the standard assoc function would

        (assoc-r '((a 1) (b 2) (c 3)) 'b)
        => (b 3)

However, evaluating this function with just the list yields an important result:

        (assoc-r '((a 1) (b 2) (c 3)))  ;- omit item being sought
        =>

The result is a function waiting for the final argument. This result can then be bound to a name and used as a function

        (define lookup (assoc-r '((a 1) (b 2) (c 3))))
        => LOOKUP
        (lookup 'a)
        => (a 1)
        (lookup 'b)
        => (b 2)
        (map lookup '(c b a))
        => ((c 3) (b 2) (a 1))

Note that since map requires a function of arity 1 as an argument (and as it turns out, one of the most common uses of the lambda function is as an argument to the map function), a curried function can be used as that argument. It is no longer necessary to create a lambda function just to perform a simple operation such as binding a free variable in an expression.

From here it is rather straightforward to create a c-define special form, so that curriable functions can be defined more easily:

        (macro c-define
          (lambda (e)
            (let ((name (caadr e))
                  (params (cdadr e))
                  (expr (caddr e))
                  (env (environment-parent (the-environment))))
              (eval
                `(set! (access ,name ,env) (c-lambda ,params ,expr)))
              (list 'quote name))))

Now the assoc-r function can be defined as

        (c-define (assoc-r lst item)
          (assoc item lst))

Not only does this create a parameter-reversed function, but the function is curriable. It is equivalent to the assoc-r function defined above using c-lambda.

5 Conclusion

The code overhead associated with creating curried functions in Scheme is far outweighed by those functions' utility, and furthermore, Scheme's potential for allowing elegant code to be written is augmented by this feature. However, the use of curried functions is not something to which one becomes quickly accustomed, so its initial benefit is difficult to gauge by the casual Scheme user.