Beginner: Curried functions in Scheme

Question

I'm using the SICP lectures and text to learn about Scheme on my own. I am looking at an exercise that says "An application of an expression E is an expression of the form (E E1,...En). This includes the case n=0, corresponding to an expression (E). A Curried application of E is either an application of E or an application of a Curried application of E."

(Edit: I corrected the above quote ... I'd originally misquoted the definition.)

The task is to define a Curried application of the procedure which evaluates to 3 for

(define foo1
    (lambda (x)
        (* x x)))

I really don't understand the idea here, and reading the Wikipedia entry on Curriying didn't really help.

Can anyone help with a more lucid explanation of what's being asked for here?

Actually even giving me the answer to this problem would be helpful, since there are five more to solve after this one. ... I just am not getting the basic idea.

Addition: Even after Brian Campbell's lengthy explanation, I'm still somewhat lost.

Is (foo1 (sqrt 3))) considered an application of foo, and therefore a curried application of foo?

Seems too simple, but maybe...

Typing (((foo1 2 )) 2) into DrScheme gives the following error (which I kind of expected)

procedure application: expected procedure, given: 4 (no arguments)

After re-reading What is Currying? I understand I can also re-define foo1 to be:

(define (foo1 a)
    (lambda (b)
        (* a b)))

So then I can type

((foo1 3 ) 4)

12

But this doesn't really get me any closer to producing 3 as an output, and it seems like this isn't really currying the original foo1, it's just re-defining it.

Damn, 20 years of C programming hasn't prepared me for this. :-) :-)

You have an unbalanced double quote. Where does your quote end? — Svante, Mar 29 '09 at 12:28
I've updated my answer with some clarifications and answers to your edits. Try not to think about other definitions of Currying you see; this exercise is not talking about defining a Curried function, but instead applying a Curried function. — Brian Campbell, Mar 29 '09 at 17:55
Please do let me know if my edited answer has helped! Since you are trying to learn this, I'm trying to give you enough information for you to solve the problem without solving it myself; if you'd like me to expand on my explanation at all, I'm certainly willing to. — Brian Campbell, Mar 30 '09 at 14:50
@Brian: Your answer has definitely helped. Thanks for cheering me on. I decided to go back and re-read the earlier portions of the book, up to 1.3, as you suggested, and it's a side project, not full time, so the going is slow. — Leonard, Mar 30 '09 at 19:11
I think the thing that's catching you up is actually the simplicity of what they are asking. They are not asking you to define any curried functions here, they are just defining a simple concept, curried function application, and asking you to use that definition to apply some functions they provide — Brian Campbell, Mar 30 '09 at 19:46

Brian Campbell · Answer 1 · 2009-03-29T17:51:33.713

Hm, this problem is fairly confusingly phrased, compared to the usually much more clear style of the books. Actually, it looks like you might be misquoting the problem set, if you're getting the problem set from here; that could be contributing to your confusion.

I'll break the definition down for you, with some examples that might help you figure out what's going on.

An application of an expression E is an expression of the form (E E1 ... En).

Here's an example of an application:

(foo 1 2)      ; This is an application of foo
(bar 1)        ; This is an application of bar

This includes the case n=0, corresponding to an expression (E).

(baz)          ; This is an application of baz

A Curried application of E is either an application of E or an application of a Curried application of E...........

This is the one that you misquoted; above is the definition from the problem set that I found online.

There are two halves to this definition. Starting with the first:

A Curried application of E is either an application of E

(foo 1 2)       ; (1) A Curried application of foo, since it is an application of foo
(bar 1)         ; (2) A Curried application of bar, since it is an application of bar
(baz)           ; (3) A Curried application of baz, since it is an application of baz

or an application of a Curried application of E

((foo 1 2) 3)   ; (4) A Curried application of foo, since it is an application of (1)
((bar 1))       ; (5) A Curried application of bar, since it is an application of (2)
((baz) 1 2)     ; (6) A Curried application of baz, since it is an application of (3)
(((foo 1 2) 3)) ; A Curried application of foo, since it is an application of (4)
(((bar 1)) 2)   ; A Curried application of bar, since it is an application of (5)
                ; etc...

Does that give you the help you need to get started?

edit: Yes, (foo1 (sqrt 3)) is a Curried application of foo1; it is that simple. This is not a very good question, since in many implementations you'll actually get 2.9999999999999996 or something like that; it's not possible to have a value that will return exactly 3, unless your Scheme has some sort of representation of exact algebraic numbers.

Your second example is indeed an error. foo1 returns an integer, which is not valid to apply. It is only some of the later examples for which the recursive case, of an application of an application of the function, are valid. Take a look at foo3, for example.

edit 2: I just checked in SICP, and it looks like the concepts here aren't explained until section 1.3, while this assignment only mentions section 1.1. I would recommend trying to read through section 1.3 if you haven't yet.

I appreciate your lengthy answer, but confess I'm still fairly puzzled. I edited the question to reflect my current state of confusion :-) — Leonard, Mar 29 '09 at 17:29

score 4 · Answer 2 · edited May 23 '17 at 12:23

4

See What is 'Currying'?

Currying takes a function and provides a new function accepting a single argument, and returning the specified function with its first argument set to that argument.

edited May 23 '17 at 12:23

Community

1
1

answered Mar 29 '09 at 07:06

Eugene Yokota

94,654
45
215
319

Thanks. I had read that question before posting, but I re-read it now, and it made more sense the second time. – Leonard Mar 29 '09 at 18:00

score 3 · Answer 3 · edited Aug 22 '14 at 15:08

3

I don't think James' curry function is correct - there's a syntax error when I try it in my scheme interpreter.

Here's an implementation of "curry" that I use all the time:

> (define curry (lambda (f . c) (lambda x (apply f (append c x)))))
> ((curry list 5 4) 3 2)
(5 4 3 2)

Notice, it also works for currying more than one argument to a function.

There's also a macro someone has written that let's you write functions that implicitly curry for you when you call them with insufficient arguments: http://www.engr.uconn.edu/~jeffm/Papers/curry.html

edited Aug 22 '14 at 15:08

ceving

21,900
13
104
178

answered Jun 26 '09 at 11:20

Paul Hollingsworth

13,124
12
51
68

+1. I prefer your function, even if I typed mine in properly yours works better. And I should have checked my functions worked, sorry. – James Brooks Jun 28 '09 at 10:22

GoZoner · Answer 4 · 2014-02-15T20:08:28.283

Most of the answers you've gotten are examples of 'partial evaluation'. To do true currying in Scheme you need syntactic help. Like such:

(define-syntax curry
  (syntax-rules ()
    ((_ (a) body ...) 
     (lambda (a) body ...))
    ((_ (a b ...) body ...)
     (lambda (a) (curry (b ...) body ...)))))

Which you then use as:

> (define adding-n3 (curry (a b c) (+ a b c)))
> (define adding-n2-to-100 (adding-n3 100))
> ((adding-n2-to-100) 1) 10)
111

> (adding-n3 1)
#<procedure>

> ((adding-n3 1) 10)
#<procedure>

score 2 · Answer 5 · edited Mar 05 '13 at 15:13

I think you are confusing yourself too much. Currying a function takes a function of type F(a1,a2,...aN) and turns it into F(a1) which returns a function that takes a2, (which returns a function that takes a3 ... etc.)

So if you have:

(define F (lambda (a b) (+ a b)))
(F 1 2) ;; ==> 3

you can curry it to make something that acts like the following:

(define F (lambda (a) (lambda (b) (+ a b))))
((F 1) 2) ;; ==> 3

in the case of your specific question, it seems very confusing.

(foo1 (sqrt 3))

seems to be suitable. I would recommend leaving it for now and reading more of the book.

you can actually make a function that does a simple curry for you:

(define (curry f x) (lambda (y) (apply f (cons x y))))
(curry = 0) ;; a function that returns true if input is zero

Thank you for the `((F 1) 2)` part. Helped me figure out currying! — Gaʀʀʏ, Aug 29 '12 at 20:02

score 0 · Answer 6 · answered Mar 04 '13 at 17:51

Depending on your Scheme implementation, there might be some utilities to be able to recover from errors/exceptions, for example, in Chicken Scheme, there is condition-case.

(condition-case (func)
    ((exn) (print "error")))

We can define a function which take a function of an arbitrary number of elements and return the curryed form :

(define curry
    (lambda (func . args)
        (condition-case (apply func args)
           ((exn)
               (lambda plus
                   (apply curry func (append args plus)))))]))))

This is a bit ugly, because if you use too many argument one time, you'll never get the final result, but this turn any function into the curryed form.

Beginner: Curried functions in Scheme

6 Answers6