F# and first-class functions, part 1: the composition operator

One of the things people tout about functional programming languages like F# is that they treat functions as first-class values. That is, you can pass functions around just like any other value, perform operations on them just like any other value, and so on.

To a C# programmer, this initially doesn’t sound like a big deal. C# has delegate types, which allow you to pass functions around, perform operations on them, and so on. But C# has very few primitives for actually working with functions. If you’re doing much work with functions, then a functional language such as F# really does pay for itself. In this series, I’m going to mention a few F# features that make higher-order functions just that bit more concise, starting off with F#’s composition operators.

Composing functions in C#

Suppose I’ve got a list that contains error and non-error values (come on, you remember Visual Basic variants), and I want to find the first error. It’s pretty easy in both C# and F#:

values.Find(IsError);  // C#
List.tryFind isError values  // F#

But what if I want to find the first non-error? Well, of course, I could write an IsNonError helper method. But that feels a bit superfluous, a bit of bloat in the API, and I’d have to start sprouting IsNonNumeric and IsNonString and IsNotMissing methods if I had the same issue with other predicates. Combinatoric explosions are rarely good. Fortunately, C# lets us work around this using lambda expressions or anonymous methods, and F# has the equivalent:

values.Find(v => !IsError(v));  // C#
List.tryFind (fun v -> not (isError v)) values  // F# in a C# style

This is okay, but it’s a bit verbose. In order to compose the ! (not) and IsError methods, we’ve had to stop talking about predicates and start talking about values. Wouldn’t it be nice if we could just compose the methods directly?

values.Find(!IsError);  // invalid C#
List.tryFind (not isError) values  // invalid F#

These don’t work because ! and not want to operate on boolean values, not functions. In C#, this leaves us stuffed: the only way to describe how to compose functions is to spell out their action on a value.

The F# composition operators

In F#, however, we can use the composition operator to combine the functions without having to introduce a value for them to act on:

List.tryFind (isError >> not) values  // F#

The >> operator means “the function you get from first doing the thing on the left, then doing the thing on the right.” In our example, that’s the function you get from doing isError, then doing a not on the result of that. In other words, a function that tests if one of our variants is not an error value — just what we needed!

There’s still one little niggle, though, because the natural English order for what we’re describing here is “not isError” rather than “isError not.” Enter the F# reverse composition operator:

List.tryFind (not << isError) values  // F#

This does exactly the same thing as isError >> not was doing, it just allows us to write and — more importantly — read it in a different order.

As a mnemonic, the arrows describe the flow of data through the sequence of composed functions. In the first fragment, each list element will be fed through the chain of functions from left to right: isError will run on the list element, then not will run on the output of isError. In the second fragment, each list element will be fed through the chain from right to left. Which order is more natural depends on the chain of functions — a processing pipeline reads more naturally from left to right (the >> operator) whereas the boolean not reads more naturally from right to left (the << operator).

But you could do that in C# as well!

I certainly could! Let’s give it a go:

public static Func<T, R> Compose<T, TInt, R>(Func<T, TInt> f, Func<TInt, R> g)
{
  return o => f(g(o));
}
 
// Usage:
var composed = Compose(Square, Cube);

Hah, so much for C# not supporting function operations. That was easy! Let’s feed it back into the original example:

values.Find(Compose(!, IsError));  // suck on that, F# fan-- wait, what do you mean, "compiler error"?

Not only is the C# Compose method harder to read (consider Compose(Subtract, Divide) — quick, does the subtraction or division happen first?), it doesn’t work, because ! isn’t a function in C#. We could write Compose(b => !b, IsError), of course, but it’s just too depressing.

Where are we?

F#’s composition operators, << and >>, make it easy to stick functions together in a processing or filtering pipeline without having to write a whole new function every time you want to create a new combination. They’re easy to read and avoid the extraneous verbiage of C# lambdas.

The composition operators are a simple example of a way to define a new function in terms of existing functions alone, without having to introduce a formal argument and write the boilerplate of how the functions combine around that formal argument. While you can do this in C#, having it in the language makes for a very concise style. In fact, this is such an important idiom that it has its own name: point-free style. In the next instalment, we’ll look at how point-free style encourages and facilitates abstraction.

Tagged as F#

10 Responses to “F# and first-class functions, part 1: the composition operator”

  • Good points that make F# sound interesting, but there are oodles of ways to handle this specific case of builtin operators, and given the fixed quantity of builtins to deal with, not *that* egregious to consider.

    public static Func Not(Func f)
    {
    return o => !f(o); //not compiled
    }

    or

    public static class Compose
    {
    public static Func Not(Func f);

    public static Func Two(Func f, Func g);
    }

  • well, all my template args got lost, but you can likely guess.

  • Thomas – I was thinking the exact same thing!

    values.Find(Not(IsError(v)) just seems a lot easier to read and trivial to write.

    Now, this article obviously showed a very simple example, so I’m sure there is a more robust example that makes F# more interesting. I have a hard time believing MS would have invested in a new language and bundled it with VS2010 unless it did something cool.

    I just can’t see it because I’m looking through OOP-colored glasses. :-D

  • but compare that to the composite function:
    f << g
    You don't have to know the details of the Compose method, you don't have to explicitly write the implementations.
    I may have to look into this. Too bad my company doesn't support .NET 4 :(

  • Parrotlover77: You are right, this is a very simple example — and as Thomas notes it’s not too egregious to replicate in C#, though I still find the F# version easier to read because it makes the order of composition easier (subjective, granted). Where F# starts to score is when you start to deal with more complex compositions, in particular when partial application hoves into view. I’m hoping to get round to posting about this in the next few days. That said, you and Thomas will still be able to counter that you can do the same things in C# using closures, and you’ll be right — I’m just using a lot of this stuff on a current project and finding F# makes it a lot simpler to read and write. But your mileage may vary!

  • Codeslinger M: You don’t need .NET 4 — there’s a free download of F# for .NET 2.0-3.5, and I believe it contains integration into Visual Studio 2008. There’s a link at http://msdn.microsoft.com/en-us/fsharp/default.aspx.

  • […] Date()).getTime() F# and first-class functions, part 2: point-free style Tagged as F#In the previous instalment, we saw that F# provided composition operators to allow you to concisely build up anonymous […]

  • Awesome, thanks Ivan!

  • […] to tackle in C#. Give it a try — you might be surprised!Previous entries in this series:Part 1: composition operatorsPart 2: point-free stylePart 3: partial function application Add your comments Posted by Ivan […]

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

  • Leave a Reply

Archives

Join our mailer

You should join our newsletter! Sent monthly:

Back to Top