Beautiful folds in F# (3 Part Series)
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
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>
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
module Computation = let map mapping computation = mapping <!> computation
So our computation type is actually a functor, because we can "map" a function over it1. 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.
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:2
The applicative must also be a functor. Our example satisfies this requirement through the
The applicative must provide a way to apply arguments one at a time, via a
<*>function. Our example satisfies this requirement through the
composefunction, of which
<*>is the infix version.3
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
composableCombinerfunction. Since that name is a mouthful, let's instead call it
liftgoing forward.4 In general,
lift f <*> xmust produce the same result as
f <!> x, which is exactly what we saw in our example. I don't think
liftis 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 // <null> // <null>
Using applicative syntax, we can multiply
Option<int>s using plain integer multiplication. That's pretty cool!
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!
Haskell usually uses the name
applyas synonyms for
Haskell calls the lifting function
return, but both of those are reserved words in F#. ↩