Christopher Bennage is an the dev lead on the patterns & practices team at Microsoft. Christopher began programming on his Texas Instrument in elementary school, but fell in love with computers with the advent of the Commodore Amiga. More recently he's been attracted to client technologies like XAML, HTML5, and JavaScript. In his free time, Christopher is usually very distracted by a dozen different, competing creative ideas. He lives in Kirkland, WA with his wife, Sandra, and their three children. Christopher is a DZone MVB and is not an employee of DZone and has posted 40 posts at DZone. You can read more from them at their website. View Full User Profile

What is Functional Programming? Part 2, Currying

10.30.2011
| 5902 views |
  • submit to reddit

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…

References
Published at DZone with permission of Christopher Bennage, author and DZone MVB. (source)

(Note: Opinions expressed in this article and its replies are the opinions of their respective authors and not those of DZone, Inc.)

Comments

Robert Craft replied on Thu, 2012/01/26 - 5:35am

FunctionalProgramming is when functions, not objects or procedures, are the fundamental building blocks of a program. Functions in this sense, not to be confused with CeeLanguage functions which are just procedures, are analogous to mathematical equations: they declare a relationship between two or more entities. FunctionalProgramming, however, is not about mathematics but about abstraction and reducing complexity: as such, it provides a powerful paradigm in which to tackle complex, real-world programming tasks.

Spring Framework

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.