currying functions (idea)

Currying is a very common little technique in functional programming languages such as Haskell that allow functions to return functions. (That is allow higher-order functions to be written.)

I will now attempt to explain it, here using Haskell for the examples.

First a very simple function

Here's a function, succ, that adds one on to it's input:

    succ :: int -> int
    succ x = x + 1

The 'int -> int' bit says that this is a function mapping an int to an int. To apply this function you can do 'succ 1' for example, which results in 2.

Now what if you wish a function that takes more than one input? The traditional way is....

Using a Cartesian product for the domain

Here's a function that adds two numbers together:

    add :: (int, int) -> int
    add (x,y) = x + y

This says that 'add' is a function mapping a Cartesian product of two ints to another int. Applying add to the ordered pair (x,y) results in x+y. ('x+y' being the rule of the function.)

To call the function, you would do something like:

    add (2,3)

Which (obviously enough) evaluates to 5.

Note that the brackets must be there as the function expects an ordered pair for input.

This is all well and good, except when you wish to do a function call something like:

    foo0( foo1( foo2(2,4,5), foo(3) ) )

Okay, not a terribly good example, but you get the point -- there are lots of annoying parentheses about the place. One of the more mundane uses of currying is simply to reduce the number of parentheses needed.

So how does currying work?

Here's the add function again, this time done using currying:

    add :: int -> (int -> int)
    add a b = a + b

Now to call the function you would do:

    add 2 3

Let's step back a moment; what does the signature of this new add function mean?

'int -> (int -> int)' says that the function takes a single int, and returns a function mapping an int to an int.

This works as follows:

First the 'add 2' bit is evalutated. This returns a function, which we'll name 'add2' for simplicity. Essentially this function has the definition:

    add2 :: int -> int
    add2 y = 2 + y

So now you're left with 'add2 3' to evaluate, which of course gives 5.

So in general....

Even if you don't understand the above waffle, just remember this. Given a function definition such as:

    foo :: int -> int -> int -> int

The type after the last arrow is what the function (eventually) returns when fully evalutated.