« Partial function application in F#, part 1: the basics | Main | Partial function application in F#, part 3: precomputing partial results »

June 07, 2011

Partial function application in F#, part 2: a technique for simplicity

In the previous part, I showed that if you didn’t supply enough arguments to a F# function, you didn’t get an error like you would in C#, but instead got back… another function.  No doubt, this seemed like a weird, abstruse behaviour.  ‘Functions that return functions’ tend to make people’s heads spin.

In practice, though, far from introducing complication and abstraction, partial application is a simplifying idiom, enabling cleaner, more readable code.  Let’s see how.

Mapping and filtering with functions

You’re probably familiar with performing set-based operations like mapping and filtering in C# using LINQ.  For example, you can use Select to perform mapping, or Where to perform filtering. Each takes a function which gets applied to each element of the sequence.

var squares = ints.Select(Square);

F# generally doesn’t use the LINQ operators, but has equivalent operators in the List and Seq modules.  F#’s equivalent of Select is called map, and its equivalent of Where is filter.  Here’s how the C# statement above might translate into F#.

let squares = List.map square ints

Lambdas

Since the mapping or filtering function gets applied to each element of the sequence, it has to be a function of one argument.  Unfortunately, the map or filter function we want to apply might need more than one argument.

Imagine we want to use our incby function from the previous part in a mapping expression.  We can’t do this directly, because the mapping function has to take one argument, but incby takes two arguments.

Fortunately, we can get around this using lambdas.  Again, the F# syntax for lambdas is slightly different from C#, but it’s still easy to understand.  Here’s how we can use incby to map each element to its successor.

var successors = ints.Select(x => IncBy(1, x));
let successors = List.map (fun x –> incby 1 x) ints

Lambdas are nice, but they could be nicer

This is okay, but is starting to look a little messy.  Lambdas require us to provide parameters on the left, then to cite those parameters on the right, and the actual meat of the mapping has to compete with the noise.  Below, I’ve highlighted in blue the important bit of the expression, and the lambda plumbing in red:

var successors = ints.Select(x => IncBy(1, x));
let successors = List.map (fun x –> incby 1 x) ints

In both cases, the meat of the expression is incby and 1.  If we could write just those bits, it would save us having to write the lambda boilerplate.

Replacing lambdas with partially applied functions

The reason we had to drag in lambdas was that List.map requires a function of one argument to apply to each element of the sequence, but incby is a function of two arguments.

Well, what do we get if we just write incby 1 in F#, leaving out the second argument?  We saw that in the previous post: we get a function of one argument.  And that’s exactly what List.map needs!

> let successors = List.map (incby 1) ints;;
val successors : int list = [2; 3; 4]

By partially applying incby, we have got the mapping function we need, without typing all that lambda boilerplate.

Obviously we can apply the same technique in a filter:

let divisibleby n x = (x % n = 0)
let evens = List.filter (divisibleby 2) ints

And so on for all the LINQ-type operators.

Pause for breath

At this stage you may be feeling lost in all the ‘functions returning functions which then get passed to other functions’ craziness.

Don’t panic.  Let’s take a look at the expression we just wrote:

List.map (incby 1) ints

Think about how you’d read and understand this if you’d never even heard of partial application.  I’d read it something like “map ‘increment by one’ over ints.”  Conversely, if I decided I needed to map an ‘increment by one’ function over ints, the expression above is a much more direct translation of that into code than the lambda version.  incby 1 is as direct a translation of the description ‘increment by one’ as you could hope for, even if it doesn’t entirely register that incby is being given the ‘wrong’ number of arguments or that it’s returning a function.

So somehow, despite all the craziness going on under the surface, what we see at the point of use is simpler code, code that is a more natural translation of a problem statement, code that is easier to understand just by reading it.

So don’t let the head-spinning abstractions of the implementation confuse you.  When you come to use it, partial application actually turns out to be pretty intuitive.  In some cases, the usage can be so intuitive you may not even realise it’s happening.

Composing expressions…

C#’s extension methods provide a really nice way of composing LINQ expressions.

ints.Where(x => IsDivisibleBy(3, x))
    .Select(x => IncBy(1, x));

The code flow reflects the flow of data through the operators - -first through the Where, then through the Select.  If you write the same thing in normal function(arguments) style, it would seem inside out:

List.map (incby 1) (List.filter (divisibleby 3) ints)

You have to read this from right to left to get the clarity of the C# version.  To deal with this, F# provides the pipeline operator, which just allows you to put the argument before the function:

3 |> square  // equivalent to square 3

With pipeline, you can chain expressions together in ‘flow of data’ order just like C# extension methods:

ints |> List.filter (divisibleby 3)
     |> List.map (incby 1)

Now it’s nice and clear and readable again.

…is another example of partial application

Does your spidey sense tingle when you look at the List.filter and List.map calls in the pipeline example?  I hope it doesn’t.  I hope you just think, “Yes, I see what’s going on there, you’re passing ints through a filter and then a map, duh.”

But take another look.  List.filter and List.map are functions that take two arguments, the filter/map function and the list to apply it to.  But in the pipeline, they appear with only one argument, the filter/map function.

Now does your spidey sense tingle?

If you know a bit about how LINQ works, you may think the compiler is transforming the pipeline syntax into the normal function(arguments) syntax, the same way the C# compiler transforms the extension method syntax into the normal function(arguments) syntax.  But actually the pipeline operator can be defined as a normal infix operator, like + or *:

let (|>) x f = f x

(The brackets around the name just mean ‘infix.’)

For example, if you write 3 |> square, then x is 3 and f is square.  So, logically, if you write ints |> List.map (incby 1), then x is ints, and f is List.map (incby 1).  So the pipeline is partially applying List.map to (incby 1), giving rise to a new anonymous function, and then applying that anonymous function to ints.

If you were to think about this in detail, you would probably lose track of it in short order.  I know I would.  We’re partially applying a function to a function (itself the result of partial application!) in order to get another function, in order to apply that function to some arguments.  Did I miss any?  I honestly can’t tell.

But as you’ve seen, the syntax is natural and readable enough that you may not even have noticed it until I pointed it out.

ints |> List.filter (divisibleby 3)
     |> List.map (incby 1)

“Take ints, filter for ‘divisible by three,’ and map ‘increment by one’ over it.”  No teetering mental stacks required.

A simplifying technique

In this part, we’ve seen how partial application simplifies using higher-order functions like List.map.  Higher-order functions are pervasive in F#, just as they are in LINQ, and being able to use partial application syntax instead of lambdas is extremely convenient.

In fact, we’ve seen that partial application makes it possible to create simplifying idioms like the pipeline (|>) operator entirely in user code, without having to wait for compiler support as we did for C# extension methods.  If we didn’t have partial application, List.map and List.filter would have been a bit noisy, but pipelines would be unusable!

Most important, I hope you’ve seen that you don’t need to hold together a teetering mental stack of higher-order functions in order to make use of partial application.  A lot of the time, it will be an almost transparent shorthand for lambda notation; occasionally, as in the pipeline example, it will be so transparent that you hardly realise it’s there.

In the next part, I’ll show you how partial application can be handy even when you’re not working with higher-order functions.

June 7, 2011 in Software | Permalink

TrackBack

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

Listed below are links to weblogs that reference Partial function application in F#, part 2: a technique for simplicity:

Comments