« May 2011 | Main | July 2011 »

June 29, 2011

It has been one of those days

So to cheer myself up here is a picture of a cat ‘helping’ to install LightSpeed 4.

June 29, 2011 | Permalink | Comments (0) | TrackBack

June 26, 2011

Sunday cats in air guitar competitions blogging

Silver medal in the ‘being a rock god while lying under a desk and stopping me getting on with my work’ category.

June 26, 2011 | Permalink | Comments (0) | TrackBack

June 21, 2011

Reservoir mogs

By way of apology to everybody who thought Partial Function Application was an experimental German rock band of the 1970s.

reservoir-mogs

They don’t normally look this purposeful.

June 21, 2011 | Permalink | Comments (2) | TrackBack

June 20, 2011

Partial function application in F#: index

This post just provides links to the various bits of the ‘partial function application’ series.

  • Part 1 describes the syntax and meaning of partially applying a function.
  • Part 2 shows how partial application results in code that is simpler and more readable than lambda expressions.
  • Part 3 looks at another use case for partial application, precomputing partial results.
  • Part 4 discusses the underlying concepts.
  • Part 5 examines how the partial application idiom affects the design of your own functions.

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

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

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

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.

Conclusion

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

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

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