« Partial function application in F#, part 4: underlying concepts | Main | Partial function application in F#: index »

June 20, 2011

Partial function application in F#, part 5: design considerations

I showed earlier in this series how important and idiomatic partial function application is in F#.  Although you can always replace a partial application by a lambda, partial application is much more concise and readable.

So when you design a function in F#, it’s worth bearing in mind how it might be partially applied.  I’ve ducked this issue throughout this series by using a very simple example which doesn’t really have any design choices about it, but real functions don’t have that luxury.

A simple predicate

Suppose we want to create a divisibleby function, which takes two arguments and returns whether one is divisible by the other.  There are two ways we could write this function:

let divisibleby value factor = (value % factor = 0)
let divisibleby factor value = (value % factor = 0)

Obviously, these are the same except for whether we put the value we’re testing first or last in the argument list.  Which should we prefer?  You might instinctively go for the first one because the arguments appear in the same order as they do in the English sentence ‘value is divisible by factor.’  But take a look at what happens when you try to use that as a predicate in a filter expression.

let evens = List.filter (fun x –> divisibleby x 2) ints

Lambdarrific!  By contrast, here’s how the predicate looks if we write divisibleby the other way around, with the factor first.

let evens = List.filter (divisibleby 2) ints

We can use partial application, and all the lambda noise goes away.  The resulting expression is shorter, less noisy and more readable.  Clearly if we want to use our divisibleby function in predicates, we should be writing it the second way, testee last.

A simple mapping

The List.map (LINQ Select) function provides another example.  Suppose we want to subtract 1 from every member of a list:

List.map (subtract 1) ints

How should we design the subtract function?  We want subtract 1 to result in subtracting 1 from its argument:

(subtract 1) y = y – 1

So, counterintuitively, we should design subtract to take its subtrahend first and its minuend second:

let subtract x y = y – x

Of course, this could be very confusing to use in a non-partial form because it reverses the order of the subtraction operator!  A user writing subtract 5 2 would probably expect a result of 3, not -3.  So this is a case where it might be better to stick to using a lambda in the List.map call.

The pipeline operator

F#’s pipeline operator, |>, is a nice way to make long chains of operations more readable.  The pipeline operator just flips function application around:

let (|>) x f = f x

Partial application means we can use the pipeline operator even with multi-argument functions:

23 |> subtract 17;;
val it : int = 6

A more realistic example of this performs a LINQ-like query by composing List functions in a pipeline:

ints |> List.filter (divisibleby 2)
     |> List.map (subtract 1)

Notice that this example depends on partial application in two ways.  Not only are we partially applying the divisibleby and subtract functions to create our filter predicate and mapping function, but we are also partially applying the List.filter and List.map functions themselves.

Looking at list functions

F#’s list functions provide another case study in function design.  Both List.filter and List.map take two arguments, and in both cases the filter or map function appears first, and the list to apply it to appears last.  Similarly, List.fold (the equivalent to the LINQ Aggregate operator) puts the accumulator function first, the seed second and the list to aggregate over last.

This isn’t an accident.  It’s precisely so that you can partially apply these functions.

The F# designers had two choices for the design of List.filter:

let filter predicate list = ...  // actual
let filter list predicate = ...  // hypothetical

The implementation is the same, of course, so that doesn’t help decide between them.  But we can compare the meaning of the partially applied versions.

In the actual version, we can write List.filter predicate – for example, List.filter isEven – and get a function that we can apply to lists.  This seems like it will give us useful functions: for example, List.filter isEven gives us a function that we can apply to a list to choose its even members.

In the hypothetical version, the partial application is List.filter list.  So we can write something like List.filter ints and get a function that we can apply to predicates.  In this version, List.filter ints takes a predicate, and returns all the elements of ints for which that predicate is true.  This isn’t necessarily useless, but it’s kind of obscure, and more critically it is evidently a function of predicates, not of lists.  If it is useful, it belongs in a Predicate module, not in a List module.

Just tell me the rules already

It’s impossible to lay down a firm set of rules on how to design F# functions.  The two versions of List.filter above are functionally equivalent: the F# designers were able to choose between them because they knew that users were much more likely to be choosing a predicate and then passing different lists through it than to be choosing a list and trying different predicates against it.  If you have a scenario where you have a fixed list and predicates coming in from the outside, then List.filter is the wrong design for you: you need a function which works the same as List.filter but reverses the arguments.  (Needless to say, it’s trivial to write such a function: let trueIn list f = List.filter f list.)  The ‘right’ design depends on how you’ll be applying the function.

Still, here’s my rule of thumb:

The thing you want to apply the function to should be the last argument.

This rule is, on the face of it, nonsense.  The function takes multiple arguments, and you apply it to all of them.

But actually, a lot of the time it turns out that there’s one thing you want to apply the function to, and the other arguments are the extra information you need in order to apply the function.  In the divisibleby example, I wanted to know if value was divisible by something.  Of course, I had to say what that ‘something’ was; but it was the divisibility of value that I was interested in.  And it turned out that putting value in the last place was the best choice.  Similarly, in the subtract function, I wanted to subtract something from a minuend; I had to say what the subtrahend was, but the minuend was what it got applied to.  And in List.filter, I wanted to filter things from a list; I had to say what criterion I wanted to use, but it was still the list that was being filtered.

Of course, this rule doesn’t help you to organise arguments other than the last, so what should you do if you have a function of three or more arguments?  The rule of thumb is a bit more nebulous here, but here’s a stab at it:

Is there a particular argument (or set of arguments) which, if you pin it down, still gives you something useful?  If so, put it at the front.

For a case study, let’s look at List.fold.  This is roughly equivalent to the LINQ Aggregate operator: you give it a function, a seed and a list, and it applies the function to each member of the list in turn, starting with the seed.  For example, List.fold (+) 0 list gives you the sum of the elements of list.

Obviously, the list argument is what List.fold is applied to, so that should be last.  But why choose the actual List.fold (+) 0 list rather than the hypothetical List.fold 0 (+) list?  Well, what is the meaning of the actual partial application List.fold (+)?  It is a ‘sum from’ function – a sum operation starting with whatever seed it gets given.  Contrast this with the meaning of the hypothetical partial application List.fold 0.  It’s hard to find a meaning for this other than ‘aggregate using a seed of 0.’  Partially applying List.fold with the accumulation function gives us something more useful and meaningful than partially applying List.fold with the seed.  So the accumulation function should go first, the list to accumulate over should go last, and by default the seed has to go in the middle.

These rules of thumb leave a lot of room for interpretation and judgment, and so they should.  Design depends on context and usage.  In part three we saw partial application being used to precompute a parse tree.  In that example, was I applying the function to the formula text, or to the evaluation environment?  Both perspectives are meaningful, and I put the formula text first and the evaluation environment last more for practical performance reasons than for conceptual reasons.

Ultimately, you’ll be guided by how you find yourself applying the function in practice.  If you find yourself repeatedly writing lambda expressions that could be avoided by pushing a parameter to the front, then that’s a big hint.  If you don’t, then either your design is already right, or it’s not enough of a problem to worry about.  Ship it.

June 20, 2011 in Software | Permalink

TrackBack

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

Listed below are links to weblogs that reference Partial function application in F#, part 5: design considerations:

Comments

Please publish a book about programming, your explanation is one of the best I've ever seen.

Posted by: ypcheng at Feb 1, 2012 5:57:36 PM

It's possible to define an operator to avoid you to create a lambda when you need inversed currying:

> let isDivisibleBy x y = (x%y=0);;
> let (==) f y = fun x -> f x y;;
> [3; 4] |> List.filter (isDivisibleBy == 2);;

val it : int list = [4]

Posted by: FremyCompany at Sep 29, 2012 11:43:19 PM

This was a fun experiment trying to work out the argument order issue for arbitrary long functions:

let ( f a b;
let ( f a b c;
let ( f a b c d;

let sum5 a b c d e = a+b+c+d+e;
let sum5s = sum5 Seq.find (isDivisibleBy sum5s

If someone find less ugly, I'm inderested ;-)

Posted by: FremyCompany at Sep 30, 2012 4:59:59 AM