What is Currying?

Currying is like a kind of incremental binding of function arguments. Let’s define a simple function which takes 5 arguments:

In a language where currying is supported, f is a function which takes one argument (a) and returns a function which takes 4 arguments. This means that f(5) is the following function:

We could emulate this behavior the following way:

Now, f(1) returns the function g(b, c, d, e) which, for all b, c, d and e, behaves exactly like f(1, b, c, d, e). Since g is a function, it should support currying as well. Then what we really want is this:

So what is f? It’s a function which takes an argument a and returns another function g which “remembers” that argument. The same way, g is a function which takes an argument b and returns another function h which “remembers” that argument. Basically, h is the function obtained from f by binding the first two arguments to a and b, respectively. Note that the last line of the code above is equivalent to this:

I know what you’re thinking: we aren’t done yet! Here’s the final version in all its glory:

That’s currying for you!

But what about f(1, 2, 3, 4, 5)? Ops… f doesn’t take 5 arguments anymore

Well, there are some functional languages (Haskell, for instance) where function application is indicated by juxtaposition. For instance, f(a, b, c, d, e) would be expressed like this:

Does that mean that f is a function which takes 5 arguments? Nope. Like in the example above, f is a function which takes an argument and returns a function which takes an argument, and so on… Let’s see it this way: the space (‘ ‘) is an operator that applies the right operand to the left operand (a function). The space is left-associative, meaning that the expression above is grouped this way:

If you don’t like the operator space, let’s use some other operator:

The operator ‘<-‘ passes its right operand to its left operand, which is a function. Indeed, these are functions:

• f
• f<-a
• (f<-a)<-b
• ((f<-a)<-b)<-c
• (((f<-a)<-b)<-c)<-d

We can remove the brackets, of course:

What am I trying to say? Simply that classic currying is better left to languages which use juxtaposition to pass arguments to functions.

Why currying?

Simple enough: it’s an easy way to get specialized functions from more general functions. Here are a few simple examples:

• times3 = myMul(3)
  • Usage:
    listTimes3 = map(times3, list)          # evaluates myMul(3, x) for all x in list
• printErrMsg = printMsg(“Error”)
  printWrnMsg = printMsg(“Warning”)
  • Usage:
    printErrMsg(“Divide by Zero!”)
    printWrnMsg(“You should save your document.”)
• lexicSort = mySort(lexicCmp)
  • Usage:
    lexicSort(listOfStrings)

Currying VS partial application

Partial application is partial binding:

Looks familiar?

Is that currying? Not quite. It’s more like manual currying:

Is currying right for us?

We said that, in Haskell, we can write

while, in Python, we would have to write

I don’t know about you, but I prefer this one:

We should also keep in mind that Python has keyword argument, so this should also be allowed:

Is that real currying? It depends on whom you ask. But if you like it and find it useful, who cares?

Incremental binding

So let’s call it incremental binding because we can bind arguments in any order we like and how many arguments we feel like at once. Let’s pretend we have implemented a magical function called cur. Here’s a simple function we can use to test cur:

Now let’s create a curried version of that function:

Now we would like to be able to write the following (and get the expected result, of course!):

The lines that print to the screen are marked with the double arrow ‘<====’.

The first line binds the argument a to 1 and save this less-free (i.e. more-bounded) function in c1. Now we have two currying-able functions: f and c1.

Here comes the interesting part: the second line binds b to 4 and d to 4, while c remains unbounded. Basically, at each step we can bind some positional arguments and some keyword arguments. If we have bound 2 arguments so far, then the 3rd argument will be the next positional argument to be bound. Indeed, line 3 binds c to 3 and then binds the two keyword arguments f and e (the order doesn’t matter, as you can see). Note that I talk of positional arguments and keyword arguments, but here positional and keyword don’t describe the arguments but the way the arguments are bound.

Note how line 4 forces the evaluation.

But… shouldn’t the evaluation be automatic? I would say no and here’s why.

As you may know, a function is called Referentially Transparent if its behavior depends on its arguments alone. This means that a function without arguments is a constant: it behaves the same way every time. Since functions don’t have side effects in pure functional languages, “to behave” is not the most appropriate verb: I should have said that a constant function always returns the same value. Now let’s look at c3 in the previous example. Is that a function? In a pure functional language the answer would be no: it’s a constant. But that means we can’t evaluate a function more than once. As you can see, func has side effects: it prints to the screen! Why shouldn’t we be able to call c3 more than once? So, manual evaluation is really a feature! Learning from other languages is a good think but trying to emulate the same exact behavior at all cost is a mistake.

The last two lines in the example above show another binding starting from c2.

Here’s our second example:

What is curr? It’s a variant of cur which lets you rebind arguments by keyword. In the example above, we first bind e to 5 and then rebind it to 10. Note that, even if that’s a one-line statement, we’re binding in 3 different steps. Finally, we forces the evaluation with ‘()’.

But I can feel some of you still want automatic evaluation (Why???). Ok, me too. So how about this:

You see how nicely default-valued arguments are handled? In the example above, 6 arguments are enough to force the evaluation, but we can also define all 7 of them (if we’re quick enough!). If we feel like it, we could even use some reflection to find out the number of non default-valued arguments (or at least I think so: I’ve been programming in Python for just 3 days and I haven’t looked at reflection yet). I don’t feel like it, but it’s simple to write a little wrapper around cur and curr.

Are we sure that our (still imaginary) cur works like expected? Let’s try something more convoluted:

What does it do? It prints the first 64 non negative integers in base two. Here’s the exact output:

Was it really necessary to cut and paste all that? Probably not… I could’ve written it by hand.

Here’s the code again (that’s what long unneeded listings do to your articles):

Our printTree is a function which takes a function func and an optional level which defaults to -1. There are 3 cases:

• level is –1:
  • we didn’t call ourselves, so someone has just called us and passed to us (we hope so) a “normal” function;
  • we call ourselves recursively, but this time the way we like: with a curried version of func and with level 0. That’s better.
• level is 6:
  • we called ourselves recursively many times and we’re finally at level 6;
  • our (very own private) func should have the first 6 arguments already bounded;
  • we bind the last argument gto something that won’t show up on the screen: the empty string(if you’re wondering why I disregard the last argument this way, you should try to include a monotonous 128-line output in one of your articles!);
  • we evaluate func and print a number on the screen!
• level is between 0 and 5 (limits included):
  • our func is a function which have the first level arguments bound and the remaining arguments unbound;
  • we can’t evalute func: we need more arguments;
  • we control the argument x in position level;
  • we bound x to 0 and let another instance of printTree handle the remaining arguments;
  • we now bound x to 1 and call yet another instance of printTree.

If you hate recursion, you can very well skip this example and go to the last one which is… ops… recursive as well:

It prints this:

Why did I use recursion? Because I was so caught up in implementing cur that I forgot Python has loop constructs

Beginners shouldn’t have too much of a problem with this example and I’m getting a little bored myself, so let’s proceed!

Wonderful, but how do we implement cur???

Let’s proceed a step at a time.

We might implement a function which remembers the arguments it has received so far:

The last line prints “1 2 3 4”.

Our function asks to receive an arbitrary number of arguments packed in the local array args and then there are two cases:

1. if len(args) is non-zero, we have received some arguments from the caller so we append them to our global array myArgs;
2. if len(args) is zero, the caller wants to force the evaluation so we act as if we were called with all the arguments in myArgs from the start.

Any objections? Like

1. Why aren’t we writingg = f(1,2)but justf(1,2)?
2. What aboutf(1,2)(3,4)()?
3. What if we want two different bindings of f at the same time?

Objection 2 is easy to deal with:

We just needed to add return f so now f(1, 2) returns f and so on…

What about objection 3? That is strictly related the first objection: we don’t need assignments because we are allowing a single global binding per function and that defeats the purpose of having currying. The solution is easy: let’s give each partially bounded f its private myArgs.

We can do that by wrapping myArgs and f inside another function so that myArgs is not shared anymore:

The last two lines print “1 2 3 4” and “10 20 30 40”, respectively. We did it!

Let’s try something a little different:

It prints “1 1 1” and… ops… “1 1 1 2 2”. That’s right: functions a and b behave exactly like our old f with its global myArgs. It’s true that myArgs isn’t global anymore, but while a and b receive two different myArgs, every successive use of a will use that same array. So the last line adds 2, 2 to a’s myArgs which already contains 1, 1, 1. The second line is just there for symmetry

How do we solve this problem? Hmm… more recursion!!! … Nope… that wouldn’t work. How about less recursion?

Let’s look at the code again: “a = g(1)” returns an f-type (so to speak) function so the next “a(1, 1)” doesn’t work correctly (we’ve just postponed the problem we were facing from the start with f). And if a itself returned “g(1, 1, 1)”? It’d be as if the caller had performed a single binding by calling g. History would be forgotten and totally irrelevant. Every binding would look like the first and only binding!

Before proceeding, we should get rid of another flaw. Look at this example:

This prints “1 1 1 2 2”. Our old f, here referred to by a, still likes to remember things it shouldn’t. We can solve both problems at the same time:

Now, g gives each f its arguments and no f can change them in any way. When f receives more arguments (args), it creates and returns a new version of f which includes all the arguments seen so far. As you can see, the new f is created by calling g one more time at line 6.

We can do even better:

The argument args was already a local variable of g (in a sense), so why create another local variable myArgs? Also, we don’t need nonlocal because we won’t modify myArgs: we’ll just read it.

We still miss a step: I hope you won’t code any single function by hand like that! We should implement cur as a curried version of a general function. That’s easy enough:

Now we can include keyword arguments:

Final Version

Now you should be able to understand the final version, which has some additional features. Here’s the entire code (examples included):

That’s all!

Please feel free to let me know what you think by leaving a comment!

Source : http://mtomassoli.wordpress.com/2012/03/18/currying-in-python/