Following up from a previous question I asked about writing a curry function, How to create a make-curry function like racket has, I've started writing the fixed case for 0, 1, 2 -- they are very similar to Church Numerals which is pretty neat. Here is what I have so far:
(define (curry-0 func)
func)
(define hello (begin (display "Hello!") (newline)))
(curry-0 hello)
; Hello!
(define (curry-1 func)
(lambda (x)
(func x )))
((curry-1 -) 2)
; -2
(define (curry-2 func)
(lambda (x)
(lambda (y)
(func x y))))
(((curry-2 +) 2) 3)
5
The pattern seems to be:
(define curry-n func
(lambda (x1)
(lambda (x2)
...
(lambda (xn)
(func x1 x2 ... xn)
However, I'm having some trouble 'building up' the n-nested lambda expression. I suppose I could build a nested lambda with something like:
(define (curry-n num func)
(if (num > 0)
(lambda (?) (curry-n (- num 1) func))))
But I'm not sure how I would 'bind' the variables to each lambda function and also how I would end up passing those same variables (in order) to the (func x1 x2 ... xn) function.
This is incorrect but I've started along the lines of...
(define (curry-n num func)
(if (> num 0)
; but lambda won't accept a number, possible to string-format?
(curry-n (- num 1) (lambda (num)))))
How could this be done?
using a loop
You need some sort of loop to collect each arg from the lambda -
(define (curry-n num f)
(let loop
((n num)
(args null))
(lambda ((arg null))
(cond ((= n 0)
(apply f (reverse args)))
((= n 1)
(apply f (reverse (cons arg args))))
(else
(loop (- n 1) (cons arg args)))))))
curry should always return a procedure, so you can see loop will always return a lambda, even for the num = 0 case. Each arg is cons'd onto args, creating a reversed list of arguments. This is why we reverse the args before applying the user-supplied procedure, f.
It works like this -
(define (hello)
(println "hello world"))
((curry-n 0 hello))
"hello world"
((((curry-n 3 +) 10) 20) 30)
60
using delimited continuations
In the spirit of sharing learning exercises, take some time to review this example using delimited continuations -
(require racket/control)
(define (curry-3 f)
(reset (f (shift k k) (shift k k) (shift k k))))
(define (hello a b c)
(printf "hello world ~a ~a ~a\n" a b c))
((((curry-3 hello) 10) 20) 30)
hello world 10 20 30
To get curry-n all we need to do is build a list of n continuations!
(require racket/control)
(define (curry-n n f)
(reset (apply f (build-list n (lambda (_) (shift k k))))))
And it works just like our first one -
(define (hello a b c)
(printf "hello world ~a ~a ~a\n" a b c))
((((curry-n 3 hello) 10) 20) 30)
"hello world 10 20 30"
((((((curry-n 5 +) 10) 20) 30) 40) 50)
150
You can visualize the process as working something like this, where each __ is a "hole" to fill -
(f __ __ __)
\
\_ (lambda (x)
(f x __ __))
\
\_ (lambda (y)
(f x y __))
\
\_ (lambda (z)
(f x y z))
The only difference is there are n holes to fill, so we build a list of n holes and apply -
(build-list 3 (lambda (_) (shift k k)))
(list __
\
\_ (lambda (x)
(list x __
\
\_ (lambda (y)
(list x y __
\
\_ (lambda (z)
(list x y z))
(apply f (list x y z)
scheme
I didn't notice you were doing this work in Scheme. We can define build-list -
(define (build-list n f)
(let loop
((m 0))
(if (>= m n)
'()
(cons (f m) (loop (+ m 1))))))
And we can use Olivier Danvy's original implementation of shift/reset,
(define-syntax reset
(syntax-rules ()
((_ ?e) (reset-thunk (lambda () ?e)))))
(define-syntax shift
(syntax-rules ()
((_ ?k ?e) (call/ct (lambda (?k) ?e)))))
(define *meta-continuation*
(lambda (v)
(error "You forgot the top-level reset...")))
(define abort
(lambda (v)
(*meta-continuation* v)))
(define reset-thunk
(lambda (t)
(let ((mc *meta-continuation*))
(call-with-current-continuation
(lambda (k)
(begin
(set! *meta-continuation* (lambda (v)
(begin
(set! *meta-continuation* mc)
(k v))))
(abort (t))))))))
(define call/ct
(lambda (f)
(call-with-current-continuation
(lambda (k)
(abort (f (lambda (v)
(reset (k v)))))))))
Our curry-n can stay the same -
(define (curry-n n f)
(reset (apply f (build-list n (lambda (_) (shift k k))))))
((((((curry-n 5 +) 10) 20) 30) 40) 50)
150