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))