From www@deja.com Fri Sep 1 17:55:09 2000 Message-Id: <200009020055.TAA10960@x68.deja.com> From: oleg@pobox.com Subject: Re: Currying and Uncurrying in Scheme Date: Sat, 02 Sep 2000 00:55:21 GMT Reply-To: oleg@pobox.com Newsgroups: comp.lang.scheme References: <85wvgxsvrh.fsf@lambda.cs.hut.fi> X-Article-Creation-Date: Sat Sep 02 00:55:21 2000 GMT X-comment: added more examples Status: OR Before we consider relationships between curry, uncurry, and fold [see below] let's first look into the problem you reported, how can we fix it, and how can we formally _prove_ that the fix indeed works. In article <85wvgxsvrh.fsf@lambda.cs.hut.fi> (Timo Lilja) wrote: > > I wonder if there's a way to write similar uncurry function, > but I can't figure it out. > > This is what I had in mind: > > (define (uncurry-1 f) > (lambda (x . rest) > (apply (f x) rest))) > > (define (uncurry f n) > ((repeated uncurry-1 n) f)) > > But this doesn't work because uncurry-1 isn't working correctly. > When I try to eval the following expression MzScheme prints: > > > ((uncurry (lambda (a) (lambda (b) (lambda (c) (- a b c)))) 3) 5 2 1) > #: expects 1 argument, given 0 Let's consider what happens when you ((uncurry f 2) 5 6) where f is (lambda (a) (lambda (b) (+ a b))) => ( (uncurry-1 (uncurry-1 f)) 5 6 ) => ( (lambda (x . rest) (apply ((uncurry-1 f) x) rest)) 5 6) => (apply ((uncurry-1 f) 5) '(6)) => (apply ((lambda (x . rest) (apply (f x) rest)) 5) '(6)) => (apply (apply (f 5) '()) '(6)) => (apply (apply (lambda (b) (+ 5 b)) '()) '(6)) and we see the problem: function (lambda (b) (+ 5 b)) that requires one argument is applied to an empty list (which denotes zero arguments). The error is even more apparent when n = 1: ((uncurry (lambda (x) (- x)) 1) 42) =eventually reduces to=> (apply -42 '()) Here's the solution. The key is to split the argument list backwards (that is, into the last cell and the prefix list) (define (uncurry-1 f) (lambda (x . rest) (let* ((args (cons x rest)) (args-rev (reverse args)) (last-arg (car args-rev)) (first-args (reverse (cdr args-rev)))) ((if (null? first-args) f (apply f first-args)) last-arg)))) Then we have ((uncurry-1 f) x) => (f x) ((uncurry-1 (uncurry-1 f)) (append rest (list x))) => ( (apply (uncurry-1 f) rest) x ) These two reductions will let us prove that ((uncurry-1 (uncurry-1 ... (lambda (x) (lambda (y) body))...)) a1 a2 ... an) reduces to ((lambda (x y ...) body) a1 a2 ... an) The proof is rather trivial (by induction in the number of uncurrying operations). The following shows the relationship between curry, uncurry and fold: ; (uncurry f a1 a2 ...an) => (((f a1) a2) ... an) (define (uncurry f . arglist) (if (null? arglist) f (apply uncurry (f (car arglist)) (cdr arglist)))) We can notice that the pattern of the iteration is the same as that of fold: (define (fold kons knil lis1) (let lp ((lis lis1) (ans knil)) (if (null? lis) ans (lp (cdr lis) (kons (car lis) ans))))) See SRFI-1 for details. This makes definition of uncurry particularly elegant: (define (rev-apply-1 arg f) (f arg)) (define (uncurry f . arglist) (fold rev-apply-1 f arglist)) (uncurry (lambda (a) (lambda (b) (lambda (c) (+ a b c)))) 5 2 1) => 8 (uncurry (lambda (a) (lambda (b) (lambda (c) (< a b c)))) 5 7 9) #t Let's revisit currying. Let's define a form lambda-curried so that: ; (lambda-curried (a1 a2 ... an) body) => ; (lambda (a1) (lambda (a2) .... (lambda (an) body))) (define-macro (lambda-curried bindings . body) (define (fold-right kons knil lis1) (let recur ((lis lis1)) (if (null? lis) knil (let ((head (car lis))) (kons head (recur (cdr lis))))))) (if (null? bindings) `(lambda () ,@body) (fold-right (lambda (arg curr-body) `(lambda (,arg) ,curr-body)) (cons 'begin body) bindings))) (pp (lambda-curried (x y z) (+ x y z))) => (lambda (x) (lambda (y) (lambda (z) (+ x y z)))) Gambit's pp procedure can print out closures. Another example: multiplying a diagonal matrix diag(1 2 3) by a square matrix ((4 5 6) (7 8 9) (10 11 12)): (map map (map (lambda-curried (a b) (* a b)) '(1 2 3)) '((4 5 6) (7 8 9) (10 11 12))) => ((4 5 6) (14 16 18) (30 33 36))