« Of mice and graduate students | Main | Partial function application in F#, part 2: a technique for simplicity »

June 06, 2011

Partial function application in F#, part 1: the basics

Partial function application is an important technique in functional languages like F#, but it tends to get blank stares when I try to explain it to C# and Java programmers. I don’t know if I’ll have any more luck putting it in writing, but here goes all the same.

First, the how

When you first see it, partial application seems like a weird and confusing quirk of the language.  It isn’t until you see it in action that it makes sense.  However, before I can show you it in action, I need to briefly show you how to do it.

Here’s a function of two arguments in F#:

> let incby x y = x + y;;
val incby : int -> int –> int

We can apply this to two values, and everything works just like you’d expect:

> incby 2 3;;
val it : int = 5

But, rather unexpectedly, we can also apply it to one value, and instead of getting a compiler error, we get something back:

> incby 2;;
val it : (int -> int) = <fun:it@6>

That response like looks a bit like line noise, but it’s easy to understand by comparing it to the response in the ‘normal’ case.  val it : int = 5 means the result was a value which F# Interactive has called it, of type int and value 5.  So val it : (int –> int) = <fun:it@6> should mean that the result was a value which F# Interactive has again called it, of type (int –> int) and value <fun:it@6>.

What is type (int –> int)?  The arrow is F#’s notation for ‘function from a to b.’  So int –> int is a function that takes an integer and returns an integer, like Func<int, int> in C#.  So the response implies that incby 2 returned a function which we can apply to an integer:

> it 3;;
val it : int = 5

And indeed it did!

By not passing enough arguments, we have partially applied the incby function, and got another function back.

Let’s see that again in C#

Functions that return functions tend to make people’s heads spin, so let’s drop back to a more familiar language and take another look.  Here’s the incby function in C#:

public int IncBy(int x, int y) { return x + y; }

Obviously, IncBy takes two arguments:

IncBy(2, 3);
// returns 5
IncBy(2);
// compiler error

But we can imagine overloading IncBy with a single-argument version.

public Func<int, int> IncBy(int x) { return y => IncBy(x, y); }

You can imagine how we could use this overload:

IncBy(2, 3);
// calls 2-argument overload, returns 5
IncBy(2);
// calls 1-argument overload, returns Func<int, int>
IncBy(2)(3);
// calls 1-argument overload, which returns a Func<int, int>
// that Func then calls 2-argument overload, which returns 5

(You may still not be able to imagine why we would use this overload, but I’ll get to that, I promise.)

Let’s walk through the last line there, to try to make it clear what’s going on when we use the 1-argument overload.

When we call IncBy(2), it calls the 1-argument overload with an argument of 2.  This substitutes 2 for x in the lambda, and returns the resulting lambda, which is now y => IncBy(2, y).  We now pass 3 into that lambda.  This substitutes 3 for y in the lambda, leaving us with a call to IncBy(2, 3).  This is the 2-argument overload, so all the function madness ends here and we are back to the sane and simple world of adding two integers and getting an integer back.

Partial application is like the crazy overload

The two forms of IncBy in C# correspond to ‘full’ and partial application in F#.  The big difference is that in C# we had to create the 1-argument overload explicitly, whereas in F# we didn’t: F# saw that we were trying to use the 1-argument overload, and automatically created it for us.

You can see that if we were overloading a lot of functions in this way, the F# automatic ‘overloads’ would save us a lot of repetitive boilerplate code.  But that just invites the question, why on earth would you need these crazy function-returning overloads?  Why does F# think they’re important enough that the compiler should go to the trouble of detecting them and working them out for you?  Now that we’ve seen a bit of the how and the what, the next part will take a step back and try to show you a bit of the motivation.

June 6, 2011 in Software | Permalink

TrackBack

TrackBack URL for this entry:
http://www.typepad.com/services/trackback/6a00d8341c5c9b53ef014e88ec5d09970d

Listed below are links to weblogs that reference Partial function application in F#, part 1: the basics:

Comments

Great explanation Ivan!

Posted by: Nick at Jun 8, 2011 3:36:57 AM