TIL: Partial application and currying aren't the same

Up to yesterday, I thought that currying was the same as partial function application. They're not, as I learned from some web research (e.g. 1, 2, 3). But the concepts are similar, probably that's where the misunderstanding comes from.

Curiously, Racket's curry function (from racket/function) is a hybrid that supports both partial application and currying. Check the curry documentation to see how.

5 Likes

The way I like to think about it is, partial application is the simple and intuitive thing that everyone understands -- you want to pre-apply the function to some arguments and then apply it to the rest later.

Currying is a mathematical result that a function of N arguments can be expressed as N functions of 1 argument. Naively, if you tried to call this curried function with N arguments, that would be an error -- because the curried function expects one argument. But in some sense, the curried function is the "smallest building block" of partial application -- intuitively, we feel that it should be possible to do partial application using this building block. And in fact, it's easy to write a thin wrapper around the curried function that can accept any number of arguments at a time, and take care of applying the curried function to the arguments individually until a result is obtained. It would be fine to call this new, wrapped, function with N arguments.

So curried function + thin "applier" wrapper can model partial application in all cases, but partial application could also be done without any use of a curried function. E.g. try writing a function (partial f . args) to do this - all you need is a lambda! But the curried version of partial application is preferable because, if you don't supply enough arguments, it will always give you back another function that expects the remainder.

3 Likes

I've always thought of currying as a degenerate case of partial application. When using PA you're taking function f of arity N and generating a function g of arity N-M that is a lambda around f with M arguments encoded in the body of g. Currying is simply syntactic sugar for iterating PA with M=1 until you end up with a function of one argument. It's no different in type from writing (define (f a) a) instead of (define f (lambda (a) a)).

(define (f a b c) (list a b c))
(f 7 8 9) ; => '(7 8 9)                                                                                       

; partial application                                                                                         
(define (g b c) (f 7 b c))  ; => (lambda (b c) (f 7 b c))                                                     
(g 8 9) ; => '(7 8 9)                                                                                         

; manually iterated partial application                                                                       
(define (h c) (g 8 c)) ; => (lambda (c) (g 8 c))                                                              
(h 9) ; => '(7 8 9)                                                                                           

; currying.  x, y, and z are equivalent                                                                       
(define x (curry f 7 8))       
(define y (lambda (c) (g 8 c))) 
(define z (lambda (c)
            ((lambda (b c)
               ((lambda (a b c)
                  (list a b c))
	          7 b c))
             8 c)))

(x 9)  ; => '(7 8 9)
(y 9)  ; => '(7 8 9)
(z 9)  ; => '(7 8 9)


EDIT: I originally said that partial application involves taking a function of N arguments and returning a function of N-1. This is incorrect, since you can partially apply multiple arguments at a time. Corrected it to say "...function of N arguments and return a function of N-M arguments with M arguments encoded in the body."

3 Likes

That's a great way of looking at it. In some sense, partial application is "inverse" of currying, and, as you showed, you can use partial application in a way that looks almost identical to currying on the outside!

Thinking of partial application as Fn -> Fn-1 -- that is, accepting a n-argument function and giving you back an n-1 arity function with one arg pre-applied -- as you suggested, is a great insight, and one that makes the analogy with currying much more clear. Since this accepts a function and gives you back a function, it's just a function itself, which we can call ρ. By iterating this process, we can go from Fn -> Fn-1 -> ... -> F1, and each of these arrows is just ρ. Now, we know that currying takes in a function of n arguments and gives us a function of 1 argument. In other words, currying is a function (let's call it γ) which does Fn -> F1. Since each of the arrows in the partial application sequence is simply ρ which is a function, we can define a composed function which goes from Fn all the way to F1, that is, ρ* : Fn -> F1. Now the question is:

Are these two the same?

That is, is ρ* the same as γ? They have the same signatures Fn -> F1, and they are given the same input function f. But in fact, the output function is quite different in the two cases. Let's call the result of partial application fp and the result of currying fc. In the case of fp, it accepts one argument and gives us the result of the original n-ary function. On the other hand, for fc, it accepts one argument and gives us a function. If we keep iterating this currying process, we get a sequence like this: fc -> f2 -> f3 -> ... -> fn (here the subscript is just an index and doesn't indicate arity as it did earlier with capital F -- and each of these functions is 1-ary!). At this point, calling fn with an argument would produce the final result of the original n-ary function. Here, we have another sequence of functions -- just like we did earlier "on the other end" with partial application, and just as we did there, we can define a composed function fc* here, that is, fc* is a function fc -> fn. This is very handwavy at this point, since we haven't really explained how any of these functions work. But still, we can safely guess that the function fc* is going to be one that accepts N-1 arguments, in order to apply each of the currying steps, and we know that it produces a function that accepts 1 argument, fn. In other words, given only the sequence of curried functions, we can define a new function that accepts n-1 arguments and gives us a function that accepts 1 argument, which, when called, gives the final result. This sounds familiar, in fact, with a little tightening up of the math (computer scientists / mathematicians on here, help! :)), I bet it is identical to ρ, i.e. partial application.

What does this tell us? I'm actually a bit lost myself, so I'm not sure. Has all this reasoning been a pointless tautology of some kind? Who knows! Maybe you do. But I get the sense that the symmetry of sequences on opposite ends of this process for partial application vs currying tells us that these two processes are in some way inverse and yet isomorphic in some way. Maybe they can each model the other, which would explain our intuition of them as being similar. :waves hands furiously: I hope this has been at least "partially" edifying, or that it ... curries favor with somebody.

Maybe this is a stupid argument, but let's see where it goes; it is a Friday.

I like to think of functions in terms of expressions with holes. Obviously, this side-steps a bunch of terminology about how we fill those holes, and conflates functions with a slew of other machinery, but for argument's sake, we assume that our hole-expression (function) is incomplete (as yet to be fully applied) until all of the holes have been plugged.

So, with some tendency to triviality, there is no need to appeal to the formalisms of partial vs. curried functions, because in either case, they cannot be fully realized until all of their holes are plugged. This shifts the argument away from the head of the function, to its body.

It also helps us to side-step the (problem?) of keywords. By this, I am pointing vaguely to the fact that a function with keywords (either partially applied or curried) can be made to plug its holes in different orderings, depending on the precise sequence of applications one assumes. I have never looked at the implementation of keywords, per se, perhaps these are simply more layers of machinery to the head of the function, but I digress.

This brings to light, I think, an important assumption that we make implicitly: time exists.

In a world without time, currying and partial application are the same (and correspond roughly to a sequence of states wherein successively more holes are plugged) up to their completion, but in a world where time exists, like ours, the two are only the same in as far as they can be made to produce the same result (without holes).

Is the limit (over time) of an expression, the same as the value it approaches at that limit? In some sense, yes, in some sense, no. It depends on whether you consider time to be a factor or not, to my mind.

Interestingly, the featured presentation by Abelson and Sussman mentions duels in the first section of the presentation, in particular eval/apply. Perhaps this speaks to the intuition elaborated in the thread?