In my last post, I provided a list of concepts that I found to be characteristic of functional languages. We’ve talked bout the first three so far.

• First Class Functions
• Higher Order Functions
• Pure Functions
• Currying or Partial Application
• Recursion
• Pattern Matching
• Memoization

Currying

Updated based on some feedback from Matthew Podwysocki.

Let’s begin with the term “partial application”. This is application in the sense of “applying a function”. Based on my reading thus far, I am inferring that the term “apply” means to resolve the result of a function with a certain set of arguments. Thus, partial application is resolving the result of a function with only a partial set of arguments. The result will be another function that requires fewer arguments that the original function.

In light of this, currying is the act of structuring a function so that it can be partially applied.

Ok, that’s a pretty naive definition. Here’s what wikipedia says:

“[Currying] is the technique of transforming a function that takes multiple arguments in such a way that it can be called as a chain of functions each with a single argument.” - en.wikipedia.org/wiki/Currying

In the book Real World Functional Programming: With Examples in F# and C# by Tomas Petricek and Jon Skeet (a book that I found immensely helpful), the authors define currying specifically as the act of converting a function with multiple arguments into a function that takes the first argument and returns a function taking the next argument (p140). This definition clarified my reading of the wikipedia definition.

Let’s consider an example based on these definitions. Recall our add function (in C#) from the last post:

Func<int, int, int> add = (i, j) => i + j;

We can convert this into:

Func<int, Func<int,int>> add_c = i => j => i + j;

That might be hard to read, so I’ll break it down a bit.

add_c is a function that takes an integer and returns another function. That means add_c is a higher order function. The returned function takes an integer and returns an integer.

If we define Tx as Func<int,int> then would could define add_c as as having the type Func<int,Tx>. Remember that the final parameter is the return type.

In regards to the nested lambda expressions that define add_c, realize that the expression j => i + j is the actual returned function.

If we were to invoke these functions to add 3 and 4, it would look like this:

var sum = add(3,4);
var sum = add_c(3)(4);

The expression, add_c(3), actually returns a function. We invoke it (or apply it) immediately providing 4 as an argument. We could partially apply it like this:

var add3 = add_c(3); // no second set of parentheses

or with the type made explicit:

Func<int,int> add3 = add_c(3);

So now, our curried function is partially applied and we can reuse this function as needed. To complete our task of adding 3 and 4 (which I guess would be fully applying the function):

var sum = add3(4);

The type signature can get ugly quickly in C#, not to mention those crazy nested lambda expressions. Also, we could not curry our original add function without rewriting it. Even though we are able to express these functional concepts in C#, they are not elegant.

Introducing A Bit of F#

F# has a cleaner syntax and functions are more, um, curriable by default. We could express our add function in F# like this:

let add (i,j) = i + j

This is very much equivalent to our original C# add function. However, a more natural way in F# would be this:

let add_c i j = i + j

This might seems like a trivial difference, but it is not. To fully understand it, we need to look at the way F# defines the signatures of these two functions.

In F#, the type for add is

int * int -> int

The –> indicate that something is returned. Specifically, something with the type designated after the –>. In this case, an integer. Now the thing to the left of the arrow is what is passed into the function. What isn’t obvious though is that int * int is a single thing. That is, it is a single value comprised of two integers. That’s what the * means. It’s a way of separating the constituents of a single value. This single thing is called a tuple. We won’t dig deep into it yet, but the important thing to understand is that add takes a single value (a tuple consisting of two integers) and returns an integer.

This signature is actually a lot like Func<int,int,int>. (Nitpickers: Yes, we could get very exact and use the new Tuple<T1,T2> in .NET 4.0. However, it doesn’t make much of a difference practically.)

Now, let’s move on to add_c. The signature for it is

int -> int -> int

Look back at the wikipedia definition for currying. In particular consider “a chain of functions each with a single argument”.

Okay, now compare this to the C# definition of add_c with the nested lambdas:

i => j => i + j

There are oddly similar, aren’t they?

Now I said to interpret the –> as meaning that whatever comes after it is returned and that whatever comes before is the input. If that is so, then we can understand

int -> int –> int

as meaning that the function takes a single integer and then returns a function with a signature of

int –> int

Are you thoroughly confused? Don’t be ashamed. It takes time to sink in.

What this means is that our F# version of add_c really does have the same type that we expressed in C#. That is Func<int, Func<int,int>>. However, it’s easier on the eyes (and fingers).

Ultimately, this means that the natural way of writing functions in F# makes them very easy to curry.

Now why is this helpful? Well, we can talk about that later.

Continue on to Recursion…