F# and first-class functions, part 3: partial function application

We ended the previous instalment with a bit of a mystery. To recap, we were using the List.filter and List.map functions — F#’s equivalents of the LINQ Where and Select operators — to create new functions in point-free style:

let except f = List.filter (not << f)

The mystery was that List.filter, like Where, doesn’t take just a predicate: it takes a predicate and a list:

let numerics = List.filter isNumeric someList

So how come calling List.filter with only a predicate doesn’t cause a compiler error?

Tonight we’re gonna program like it’s 1929

List.filter is a bit complicated, so let’s step back and look at a simpler function:

let add x y = x + y

If we look at the type of this function in Intellisense or in F# Interactive, it looks a bit funny. We defined add to take two ints and returns an int. Now F# represents “returns” by the symbol “->” (the same as in F# lambda expressions), so we’d expect the type of add to be displayed as (int, int) -> int or some similar syntax.

What we actually see is something completely different and weird:

val add : int -> int -> int

That looks like a function which takes an int and returns a function from int to int:

               int -> (int -> int)
// Takes an int ^          ^ Returns an int -> int

But that’s crazy talk. Isn’t it? I mean, if we call add with just a single int, that’s obviously invalid, it’ll give us a compiler error, not–

> let inconceivable = add 1;;
val inconceivable : (int -> int)    // You keep using that word. I do not think it means what you think it means.

So add really does work like a function that takes an int and returns a function from int to int. So when we write the normal version, e.g. add 123 456, it’s as if F# did the add 123 to create an anonymous function that adds 123 to things, and then applied that anonymous function to 456. It doesn’t, of course, because that would be awfully inefficient, but that’s an optimisation.

That is, even though it probably isn’t really, in F# you can always think of a function of n arguments as a function of one argument that returns a function of n-1 arguments.

To the mighty bearded ones of computer science, this trick is known as currying, after its inventor, Moses Schoenfinkel.

Creating functions by partial application

Why do F# and other functional programming languages do this weird currying trick? As we’ve seen, currying allows programmers to supply a subset of the required arguments and get a function out, and this turns out to be a terribly convenient way of creating new functions. Let’s go back to the except function:

let except f = List.filter (not << f)          // List.filter takes a predicate
let numerics = List.filter isNumeric someList  // List.filter takes a predicate and a list

It should be a lot clearer now what’s going on. Here’s the signature of List.filter:

> List.filter;;
val it : (('a -> bool) -> 'a list -> 'a list) = <fun:clo@5>

List.filter doesn’t take a predicate and a list after all. It takes a predicate (‘a -> bool), and returns a function that takes a list (‘a list -> ‘a list). In numerics, we immediately applied that function to someList, so it looked like filter was taking a predicate and a list to a list. But in except, we captured the function generated by that first step, and returned that as the result of the except function.

In general, partially applying a function gives us a way to create new functions. Partially applying the add function creates new functions from integers. Partially applying the List.filter function, or other higher-order functions such as List.map, creates new functions from existing functions.

Partial application, precomputing and performance

An interesting side issue with partial application is when you can precompute some internal state used by the function. Consider an expression evaluator, which takes a string expression and evaluates it in the context of an environment which provides values for variables:

let evalFormula ast env =  // ast is the parsed expression AST
  // ... body omitted -- basically recursing down the tree ...
let parse s =  // parse creates an AST from a source string
  let lexbuff = Lexing.from_string s
  Parser.start Lexer.tokenize lexbuff  // magic incantations -- don't worry about how this works!
let eval s env =
  evalFormula (parse s) env

Now suppose you’re going to need to evaluate the same expression with a bunch of different variable assignments. The expression doesn’t change, so it would be a waste of time to call eval for each set of variable assignments — it would parse the same expression string every time and generate the same AST each time. By partially applying evalFormula, we can create a function that has already performed the parse, and can be fed different environments in which to evaluate that parsed expression:

let makeEval s =
  evalFormula (parse s)

When we call makeEval, it parses the expression string. It then partially applies evalFormula to the result of the parsing and returns the resulting function. We can now call that resulting function as many times as we like, passing in different environments. In this example I’m calling makeEval and the resulting evaluator from from C#:

var f = Evaluator.makeEval(expressionText);  // parse happens here
foreach (var variableAssignment in allVariableAssignments)
{
  var result = f.Invoke(variableAssignment);  // runs efficiently on parsed AST
  // do something with result
}

A quick test shows that this is significantly faster than using eval and parsing the expression every time.

Return to the valley of C# and Visual Basic

There’s nothing here you couldn’t do in C# or Visual Basic, of course. For example, the F# except function translates pretty easily into C#:

public static Func<IEnumerable<T>, IEnumerable<T>> Except<T>(IEnumerable<T> source, Func<T, bool> predicate)
{
  return source.Where(x => !predicate(x));
}

Of course, the entire F# declaration and implementation of except is only one character longer than just the return type of the C# definition, but that’s why we have ergonomic keyboards, right? Right! We can even capture the general concept of partial application in C#:

public static Func<T2, TResult> PartiallyApply<T1, T2, TResult>(Func<T1, T2, TResult> f, T1 val1)
{
  return val2 => f(val1, val2);
}
 
// Usage:
var inconceivable = PartiallyApply(Add, 1);

I don’t think this is as convenient or readable as F#’s built-in support for partial application (particularly when you have to deal with functional cases and overloaded methods, as you would if you wanted to write Except using PartiallyApply), and of course you would need to write overloads of PartiallyApply for every combination of total and provided argument counts. But it’s certainly doable.

Using first-class functions to do the heavy lifting

The simplicity of working with functions in F# makes it easy to assemble low-level functions like List.filter, List.map and so on along with domain methods into convenient little utility functions. As I said before, it’s not that F# allows you to do anything that you can’t do in C# or Visual Basic: rather, it’s that it makes it so much more natural that it becomes idiomatic. So I don’t feel too embarrassed about using examples that are pretty small and simple. Small and simple doesn’t mean useless!

That said, as you need to do more sophisticated things with functions, the simplicity of working with functions in F# starts to pay back more and more. In the final instalment, I’ll talk about a project I’m working on which has made considerable use of first-class functions, and try to show you how F# has made it easy for me to pull common logic and boilerplate code up into higher-order functions that I’ve been able to apply across the project.

Tagged as F#

5 Responses to “F# and first-class functions, part 3: partial function application”

  • Great point on using partial application or closures to enhance performance by transparently doing extra work up front.

    It occurs to me that you could easily refactor an existing function to improve performance in this way without changing any other code in your app. A very cool trick for a demo :).

  • [...] a technique called partial function application, and we’ll look at this in more detail in the next instalment. Add your comments Posted by Ivan Towlson on 12 October 2010 3 Responses to “F# and [...]

  • [...] F# and first-class functions, parts one, two, three and [...]

  • Sorry for nitpicking:
    РIf currying was named after its inventor, and its inventor was Moses Sch̦nfinkel, then it should be called schoenfinkeling.
    РThe Wikipedia page you cite on Mr Sch̦nfinkel indicates that currying was invented by one Gottlob Frege and wrongfully attributed to Mr Sch̦nfinkel by Mr Curry.

  • [...] Partial application reduces the amount of lambda noise in the code, and can also be useful in creating new functions by specialising existing ones. You can read more about partial application in this series and (more concisely) in this article. [...]

  • Leave a Reply

Archives

Join our mailer

You should join our newsletter! Sent monthly:

Back to Top