June 19, 2011

Partial function application in F#, part 4: underlying concepts

In previous parts, I discussed what partial application means and why it’s so important in F# programming.  Because partial application is so idiomatic, it’s important to design your own functions to play nicely with partial application, and that means you need to have some idea of the conceptual model that underlies it.

A closer look at F# functions

Here’s a dead simple F# function, declared in F# Interactive.

> let inc x = x + 1;;
val inc : int –> int

F# Interactive’s response tells us that inc is a function from int to int.  It represents this using the arrow notation.  That is, a –> b is a type meaning ‘function which takes an a and returns a b.’  It’s roughly equivalent to Func<T, TResult> in C#:

Func<int, int> inc = x => x + 1;

So far so good.  Now obviously F# also allows us to declare functions of more than one argument.  In previous parts I used a trivial example I called incby.  Let’s review its declaration and its type:

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

As you can see, incby takes two integers, x and y, and returns another integer.  So it’s a function from int and int to int.

But look closely at the way F# Interactive represents this function of two arguments.  That notation looks really ambiguous, because you could also read it as:

int –> (int –> int)

which would mean ‘takes an int and returns an int –> int,’ i.e. a function of one argument which returns another function.

So what is the int –> int –> int function type?  “Function which takes two int arguments and returns an int’ or ‘function which takes one int argument and returns an int –> int function’?

A difference that makes no difference is no difference

It turns out that this difference is no difference.  int –> int –> int is unambiguous, because the two readings are conceptually the same.  Partial application is the realisation of this.

Recall that partial application means that you can provide incby with only one argument instead of its full complement of two:

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

Look at the first line again.  It’s natural to think of this as applying incby to 2 and 3.  But it’s also correct to think of it as evaluating (incby 2) and applying that to 3:

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

It even turns out that if we specifically write a single-argument form of incby, we can apply it to two arguments using exactly the same syntax:

> let incbyc x = fun y -> x + y;;
val incbyc : int -> int –> int
> incby2 2;;
val it : (int -> int) = <fun:it@11-1>
> incbyc 2 3;;      // Same calling syntax as incby
val it : int = 5    // Same result

At the F# language level, we just can’t tell the difference between incby and incbyc.  They have the same type, and we can apply them in the same way, and in both cases we can apply them to one or two arguments and get the same result.

One way to think of this is that partial application resolves the ambiguity of the a –> b –> c type, by allowing an a –> b –> c to be used interchangeably with an a –> (b –> c).  Another way to think of it is that the a –> b –> c type unambiguously means a –> (b –> c), and that the multiple-argument syntax we used in incby is just a handy way to avoid writing and thinking about the fiddly lambda we see in incbyc.

Which is the right way to think of it?  Mathematically and conceptually, the second way is correct.  Pragmatically, however, it’s often easier to think the first way.  Lots of functions have more than two arguments, and trying to think of these all the time as functions that return functions that return functions that return functions will just make your brain turn to custard.

Let’s see that again in C#

It’s instructive to compare F#’s ‘ambiguity’ – though, as we’ve seen, ‘unification’ would be a better word – with the C# equivalent.  C# represents functions of multiple arguments quite differently from functions which return functions.

Func<int, int, int> incby = (x, y) => x + y;
Func<int, Func<int, int> incbyc = x => (y => x + y);

In C#, the two versions have completely different types.  Similarly, they are applied in different ways:

int sum = incby(2, 3);
int sumc = incbyc(2)(3);
// shorthand for
// Func<int, int> temp = incbyc(2);
// int sumc = temp(3)

F#’s trick is to always pretend that you wrote the second version, but provide a syntax for doing so that looks like the first version.

Enter the mathematicians

The trick of always pretending that the programmer wrote the second version is called currying.  It’s an important technique to understand if you’re interested in the conceptual underpinnings of functional programming, but I’m not going to go into it any further here.  Suffice it to say that it’s basically no more than the trick of interpreting (x, y) => something as being equivalent to x => (y => something) – and similarly of course for further arguments.  In short, exactly what we’ve already seen F# doing automatically and what we were able to do explicitly in C#.

Does F# really do this?

So does F# really curry all your multi-argument functions to single-argument functions full of chains of lambdas?  No, it doesn’t.  The easiest way to see this is to call a multi-argument F# function from C#: you’ll see that you have to use the C# multiple argument syntax, not the C# repeated application syntax.

// In FSharpTest module
let incby x y = x + y

// In C#
var sum = FSharpTest.incby(2, 3);  // Not incby(2)(3)

The way F# really implements partial application at the compiler level is more like what I described in the first part of this series: when the F# compiler sees you using a function in a partial way, it generates a private function which represents the partially-applied form.  You can see how this works by compiling some F# code that performs partial application, then opening the compiled assembly in a C# decompiler such as Reflector.

What does all this mean for me?

If you find the mathematical and conceptual underpinnings a bit intimidating, don’t worry about it too much.  You can pretty much get away with thinking about F# function signatures and application the ‘pragmatic’ way, and in fact you’ll be closer to the implementation reality than people who think about them the ‘mathematical’ way.  The important thing to understand is that there are two ways of reading a function type like a –> b –> c –> d, and that you can read it whichever way is more convenient for the job at hand.  F# doesn’t force you to make a choice the way C# does.

Nevertheless, it’s useful to have an appreciation for the meaning of the intermediate partial forms of a function, even if that’s not how they’re represented in the compiled code.  We’ll see why when we talk about what partial application means for designing F# functions.

June 19, 2011 in Software | Permalink | Comments (2) | TrackBack (0)

June 08, 2011

Partial function application in F#, part 3: precomputing partial results

In previous parts we saw that partially applying a function was a bit like creating a lambda to call that function.  So far we’ve mostly used this as a convenience for calling LINQ-like functions.  In this part we’ll look at it in a different context – precomputing partial results.

The expression engine

Suppose you’re writing a simple data analysis or reporting tool which operates over a data set.  Users can enter formulae and the tool evaluates these formulae for each record in the data set – a bit like computed columns in a database.  For example, maybe the input data contains a field named Age.  Then the user could write 65 – Age and assign this to a field named YearsUntilRetirement.

Using the F# tools fslex and fsyacc, it’s fairly easy to build a parser that translates the user text to an abstract syntax tree (AST), and a set of evaluation functions to walk such a tree and perform the calculations.  You can then put this behind a handy evaluate function which hides all the implementation from the caller.

The one wrinkle – and it’s an important one – is that evaluating an AST requires not only the AST itself, but also the values of the fields to which the user formula refers.  In the 65 – Age example, the evaluator needs to be able to get the Age value for the record being processed.  We’ll call this an evaluation environment.  So the evaluate function looks something like this:

let evaluate text environment =
  let ast = parse text       // parse is private
  evalAst ast environment    // evalAst is private

That is, evaluate and evalAst takes two arguments, the formula string and the evaluation environment object.

Performance sucks

The evaluate function works fine for small data sets.  But if you feed it a lot of records, you’ll notice that it feels a bit… well… sluggish.

It’s not hard to see why.  For every record, evaluate is taking the string expression, parsing it, and then evaluating the parsed AST in the provided environment.  And it turns out that parsing formulae is hard work.

Let them eat AST

Parsing the same formulae for every record is redundant. The only thing that varies from record to record is the environment: the same formula always results in the same AST.

This suggests one way to solve the performance problem: make the parse and evalAst functions public.  Then the consumer can run parse once, store the resulting AST, and feed it back into evalAst as required.  Sorted, right?

A functional solution

This works, but at the expense of requiring the consumer to know about parsers and ASTs.  The consumer isn’t really interested in the parsing process and its intermediate results.  The consumer just wants a way to get the result of a formula for a particular environment.

A way to get one value from another?  That sounds like a function!  Specifically, it sounds like a function from environments to results.

Without further ado, let’s write that function:

let makeEval text =
  let ast = parse text
  evalAst ast

makeEval starts out the same as evaluate, but because it doesn’t have an environment argument, it can’t finish the job.  Instead, it partially applies the evalAst function.  Partial application leaves us with something still waiting for an environment, and ready to return a result when it gets one – that is, a function from environments to results, just as we needed.

let f = makeEval "65 - Age"  // can cache this for reuse
let result = f  env

Like the previous fix, this solves the performance problem.  When you call makeEval, F# precomputes the AST, doing all the hard work of parsing, and returns you a function with that precomputed AST all tucked up inside.  When you apply that function, it uses the precomputed AST, so it doesn’t pay the parsing overhead again.

Spelling it out

This may be confusing, so I’ll rewrite makeEval in a more C#-like idiom:

let makeEval text =
  let ast = parse text
  fun env –> evalAst ast env

This makes it clearer that makeEval returns a function, and exactly what that function does, at the expense of some noise.

Finding the right partial results to precompute

What if we didn’t control the expression engine?  Could we still take advantage of precomputing by partially applying evaluate?

let f = evaluate "65 – Age"
let result = f env

evaluate "65 – Age" does return a function from environments to results, so this superficially seems attractive.  Alas, it is fools’ gold.  The only thing precomputed by evaluate "65 – Age" is the string "65 – Age", which is no saving at all!  Partial application doesn’t look inside evaluate to see if there’s anything it could precompute – all it does is bundle up the arguments it has in the form of a lambda.  The above is equivalent to:

let f = fun env –> evaluate "65 – Age" env

It’s now obvious that the full evaluate function, including the repetitive parsing, would run each time the lambda was called.  The makeEval function works only because it precomputes the AST: it relies on partially applying evalAst rather than partially applying evaluate.


Precomputing partial results is a handy technique in any language, and will work in any language where you can capture those partial results and provide an easy way to reuse them.  Lambdas are a particularly convenient way to provide a function with precomputed state, and what we’ve seen here is basically partial application as a shorthand for lambdas.

I hope that after this part and the previous one, partial application doesn’t seem quite as intimidating or obscure as it seemed after the first part.  In the next part, I’ll return to the underlying concepts and implementation.

June 8, 2011 in Software | Permalink | Comments (0) | TrackBack (0)

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


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 | Comments (0) | TrackBack (0)

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
// 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
// calls 1-argument overload, returns Func<int, int>
// 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 | Comments (1) | TrackBack (0)

May 21, 2011

Of mice and graduate students

Reading Amy Stewart’s Wicked Bugs and was greatly taken with this tale of the deadly Asian giant hornet:

After the larvae have finished their meal [of dead insects], the adults tap on their heads, which prompts the larvae to offer up a “kiss” consisting of a few drops of clear liquid.  The adults drink this liquid, using it as a source of fuel.  The Japanese scientists harvested the clear liquid, one drop at a time, from larvae they found in over eighty hornets’ nests.  In the laboratory they demonstrated that both mice and graduate students showed reduced fatigue and an increased ability to turn fat into energy after drinking the juice.

Stewart does not specify whether they tested it on the mice or graduate students first.

Say what you like about category theory not having any practical applications, at least my supervisor never made me drink hornet barf.

May 21, 2011 in Science | Permalink | Comments (1) | TrackBack (0)

April 24, 2011

The speeding conundrum: solved at last

The helpful gnomes at Land Transport New Zealand have been posting signs up and down SH2 in dramatic black and yellow with the legend “Too Fast?  Slow Down.”

Those last two words are crucial.  Most people know how to check their speed.  But what to do about it?  Without guidance, forced to guess, I would probably stick my arse out the driver’s window, jam a clown wig on my coccyx and a bugle between my cheeks, and fart the Marseillaise.

And where would this leave me?

Still going too fast, only now I’d have to steer with my teeth.

So three cheers for the advice to “slow down.”  To LTNZ, two small words; to me, hundreds of dollars in saved bugle cleaning fees.

April 24, 2011 | Permalink | Comments (0) | TrackBack (0)

The book in the bubble

Fascinating analysis of how automated pricing and a positive feedback loop led a pair of Amazon vendors to price an out-of-print book about flies at two million dollars – rising over just ten days to more than twenty three million dollars.

Plus, as the author notes, $3.99 shipping.

April 24, 2011 in Books, Web | Permalink | Comments (0) | TrackBack (0)

April 17, 2011

The blackout

So, turning your Twitter avatar black inexplicably failed to have any effect.

What’s the next part of the plan?

April 17, 2011 in Current Affairs, Web | Permalink | Comments (2) | TrackBack (0)

March 18, 2011

F# party at the old Trask place

I’ve been posting a bunch of stuff about F# over at my employer’s site, so for those who are interested, here’s the links:

First class functions in F#, parts 1, 2, 3, 4 and of course the oh-yes-I-guess-I-should-have-mentioned part 0

Functions versus member methods in F#

Object expressions in F#

Recursive iterators in F#

March 18, 2011 in Software | Permalink | Comments (0) | TrackBack (0)

March 16, 2011

Things I never knew I ought to worry about


Yes, that does promise ‘nuclear free catnip.’

Although judging by the exposed skin and peculiar shedding on the tail of the cat on the packet, I am less than convinced.

March 16, 2011 | Permalink | Comments (1) | TrackBack (0)