Beautiful folds in F# - Part 3: Applicatives

Improved syntax

The composableCombiner function that we ended up with last time works fine, but doesn't seem quite right. It creates a computation that returns the given "combiner" function, but the rest of what it does is a total waste:

let composableCombiner combiner =
    (fun () item -> ()),   // step function ignores inputs
    (),
    (fun () -> combiner)   // extract function ignores inputs

We can improve this by using the result of an actual computation as the first argument to combiner directly, instead:

let (<!>) combiner (step, init, extract) =
    step, init, (extract >> combiner)

This approach leverages partial function application, just as before. Given a combiner of type 'a -> 'b -> 'c -> ..., the infix function <!> converts a computation that returns a result of type 'a, into a computation that returns a result of type 'b -> 'c -> ..., which is exactly what we need for the next computation in the chain. This eliminates the need for composableCombiner, so instead of writing this:

(composableCombiner toMean) <*> composableSum <*> composableLength

We can define the same composite computation more simply, like this:

toMean <!> composableSum <*> composableLength

Note how similar this version is to normal function invocation:

toMean sum length

Sweet!

Functor

Now that we have a concise, elegant syntax for composing computations, let's take a step back and examine what we've created. In particular, take a close look at the <!> function. It takes a function and the definition of a computation and applies the given function to the computation to create a new computation. Its type signature looks something like this:

('a -> 'b) -> Computation<'a> -> Computation<'b>

Where Computation<'t> is our standard 3-tuple computation definition whose "extract" function returns a 't. Interestingly, this is exactly the signature needed for a functor's map function:

module Computation =
    let map mapping computation =
        mapping <!> computation

So our computation type is actually a functor, because we can "map" a function over it¹. But unlike the functors we've seen previously, calling <!> is just the first step in defining a compound computation. If we use a multi-argument mapping function (which we've been calling a "combiner" to this point), the first argument is bound and we get back a computation that is ready for n-1 additional arguments via partial function application.

Applicative

The pattern we've employed here is called "applicative", because it gives us a powerful way to apply arguments to a function. While functors work well with unary (one-argument) mapping functions, applicatives extend that approach to work with multi-argument mapping functions. The applicative pattern has three characteristics:²

• The applicative must also be a functor. Our example satisfies this requirement through the <!> function.

• The applicative must provide a way to apply arguments one at a time, via a <*> function. Our example satisfies this requirement through the compose function, of which <*> is the infix version.³

• The applicative must provide a way to create an instance directly from any given value. This process is referred to as "lifting" the value into the applicative. We provided this via the reviled composableCombiner function. Since that name is a mouthful, let's instead call it lift going forward.⁴ In general, lift f <*> x must produce the same result as f <!> x, which is exactly what we saw in our example. I don't think lift is used much for applicatives in practice (because it's wasteful), but it does serve a role logically.

As a quick example, we can see that Option is an applicative:

let (<!>) = Option.map   // Option is a functor

let lift x = Some x      // not used, but still conceptually important

let (<*>) fOpt xOpt =
    match fOpt, xOpt with
        | Some f, Some x -> Some (f x)
        | _ -> None

Which we can try out like this:

let mult = (*)
mult <!> Some 3 <*> Some 4 |> printfn "%A"
mult <!> None   <*> Some 4 |> printfn "%A"
mult <!> Some 3 <*> None   |> printfn "%A"

// output:
// Some 12
// None
// None

Using applicative syntax, we can multiply Option<int>s using plain integer multiplication. That's pretty cool!

Beautiful folds

To wrap things up, I just want to mention that the use of applicative computations to process a sequence in a single pass is actually called a "beautiful fold". (I didn't make the name up, honest.) I've borrowed the idea from Haskell (e.g. here), but it works just fine in F# and is useful in both languages due to the properties of lazy streams.

So what are the takeaways here? We've encountered two important ideas:

• We extended the functor pattern to a more general "applicative" pattern, which can be used in multiple contexts.

• We've identified a specific context in which applicatives are useful in F#: beautiful folds.

It's been a long journey, but hopefully worthwhile. If you made it this far, thanks for participating!

---

1. We've used <!> as an infix abbreviation for the map function to mirror Haskell's <$> infix abbreviation for the Functor typeclass's fmap method. <$> itself isn't a legal infix identifier in F#.) ↩

2. There are several additional laws that an applicative must follow, but I'm not going into them here. See this article for details. ↩

3. Haskell usually uses the name ap or apply as synonyms for <*>. ↩

4. Haskell calls the lifting function pure or return, but both of those are reserved words in F#. ↩

Comments

[Matt Eland]

You really should use the series: tag in the v1 editor or series feature in the v2 editor and put these all in a series for navigation purposes. Great series and I love seeing the F# love.

[Brian Berns]

Thanks! Yeah, I really should make it a series. Good suggestion.