Going from Curry-0, 1, 2, to ...n

Question

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?

Answer 1

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

Answer 2

I recommend you to write the following function instead:

;; create `num` nested lambdas, where the body applies `func` to
;; `args-so-far` along with the arguments of those nested lambdas
(define (curry-n* func num args-so-far)
  ...)

Here's its usage:

(define (sub-4 a b c d)
  (- a b c d))

(curry-n* sub-4 0 (list 10 1 2 3)) 
;=> should evaluate to 10 - 1 - 2 - 3 = 4

(curry-n* sub-4 1 (list 10 1 2)) 
;=> should evaluate to a procedure that accepts x, 
;   and returns 10 - 1 - 2 - x = 7 - x

(curry-n* sub-4 2 (list 10 1)) 
;=> should evaluate to a procedure that accepts x, 
;   and returns a procedure that accepts y, 
;   and returns 10 - 1 - x - y = 9 - x - y

For the base case (num = 0), you will want to use the function apply.

Once you have curry-n*, you can then create curry-n which invokes curry-n* as a helper function.

---

Once you have the solution, you will notice that it is not quite efficient. You can revise curry-n* to flip args-fo-far around, so that its usage is like this:

(define (sub-4 a b c d)
  (- a b c d))

(curry-n* sub-4 0 (list 3 2 1 10)) 
;=> should evaluate to 4

(curry-n* sub-4 1 (list 2 1 10)) 
;=> should evaluate to a procedure that accepts x, 
;   and returns 7 - x

(curry-n* sub-4 2 (list 1 10)) 
;=> should evaluate to a procedure that accepts x, 
;   and returns a procedure that accepts y, 
;   and returns 9 - x - y

Answer 3

The other answers may be a bit more efficient as they accumulate a concrete list of parameters, or fancier because they allow you to take multiple arguments at once, but in my opinion it is a better learning exercise, and simpler, to just write a basic function that takes one argument at a time with no need for an accumulator.

(define (curry n f)
  (cond ((= n 1) f)
        (else (lambda (x)
                (curry (- n 1)
                       (lambda args
                          (apply f (cons x args))))))))

 > (((curry 2 +) 5) 4)
=> 9

Instead of accumulating parameters, we just create a new lambda that expects fewer parameters each time, and curry that. It behaves very much like the generalization of your attempts for fixed n. It's the same basic approach as rawrex's (perfectly reasonable) answer, but without the fancy facility to handle args in larger chunks.