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?

as shown, `(curry-0 hello)` couldn't have produced that output, `; Hello!`. only `((curry-0 hello))` could do that. — Will Ness, Jun 17 '21 at 07:36
also, this has nothing to do with Church encoding, except the functions being nested lambdas taking one argument at a time. i.e. "curried". — Will Ness, Jun 18 '21 at 18:33

amalloy · Answer 1 · 2021-06-17T07:00:59.043

2

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.

edited Jun 17 '21 at 07:00

answered Jun 17 '21 at 05:40

amalloy

89,153
8
140
205

how fun! i love the simplicity of this compared to my `loop` answer. in the spirit of sharing learning exercises i added another technique which exposes each argument as a continuation :D – Mulan Jun 17 '21 at 06:02
@amalloy -- that's really neat, thank you. Could you explain how this part here works -- `(lambda args (apply f (cons x args)))` ? – David542 Jun 17 '21 at 21:19
What part do you not understand? – amalloy Jun 17 '21 at 22:29
@amalloy basically why is it `(apply f (cons x args))` instead of just `(apply f args)` ? What does the `x` represent here? – David542 Jun 18 '21 at 00:04
The point is that each lambda captures a single argument. We go from a 5-argument function to a 4-argument function with one argument "baked in", then to a 3-argument function with two baked in...and so on until we get to just a one-argument function with 4 baked in. – amalloy Jun 18 '21 at 04:22

Mulan · Accepted Answer · 2021-06-17T15:38:02.050

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)

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)

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)

ha, that's pretty neat. Can you explain the `reset` and the whole `shift k k` thing? Is that sort of like vim where you do something like `nmap k ...` ? — David542, Jun 17 '21 at 20:41
also, what does `(let loop ((n num) (args null))` do? I've only seen a `let` used something like `(let ((a 1) (b 2)) ...)` — David542, Jun 17 '21 at 21:35
That is a [named let](https://docs.racket-lang.org/guide/let.html#%28part._.Named_let%29). `let loop ((a 1) (b2)) )` is the same as `(define (loop a b) ) (loop 1 2)` — Mulan, Jun 18 '21 at 16:01
`shift` and `reset` are control operators. The [wikipedia page](https://en.wikipedia.org/wiki/Delimited_continuation) offers a fairly approachable explanation. Given `(* 2 (reset (+ 1 (shift k ...))))`, `k` or whatever you decide to name it, represents the continuation up to the `reset` boundary. Here you can think of `k` as `(lambda (x) (+ 1 x)`. Applying `k` would resume the computation with its argument, ie `(k 5)` would result in `(* 2 (+ 1 5))`. With our program, `(reset (myfunc (shift k k))` builds a continuation like `(lambda (x) (myfunc x)`. — Mulan, Jun 18 '21 at 16:11
The interesting thing is you can decide not to apply the continuation `(* 2 (reset (+ 1 (shift k 3))))` results in `(* 2 3)`. This is because the `(+ 1 ...)` portion represented by `k` is not applied and instead `3` is returned. Another interesting thing is you can apply `k` multiple times, `(* 2 (reset (+ 1 (shift k (k (k (k 5)))))))` results in `(* 2 (+ 1 (+ 1 (+ 1 5))))` as the `(+ 1 ...)`. The wikipedia page contains other powerful demonstrations. — Mulan, Jun 18 '21 at 16:18

Sorawee Porncharoenwase · Answer 3 · 2021-06-17T05:08:27.790

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

what's the function though, all you have is `...` ? – David542 Jun 17 '21 at 20:40 — David542, Jun 17 '21 at 20:40
That's an exercise for you to do. – Sorawee Porncharoenwase Jun 18 '21 at 02:08 — Sorawee Porncharoenwase, Jun 18 '21 at 02:08

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

3 Answers3

Linked