Beautiful folds in F# (3 Part Series)
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 3tuple 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^{1}. But unlike the functors we've seen previously, calling <!>
is just the first step in defining a compound computation. If we use a multiargument 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 n1 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 (oneargument) mapping functions, applicatives extend that approach to work with multiargument mapping functions. The applicative pattern has three characteristics:^{2}
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 thecompose
function, 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
composableCombiner
function. Since that name is a mouthful, let's instead call itlift
going forward.^{4} In general,lift f <*> x
must produce the same result asf <!> x
, which is exactly what we saw in our example. I don't thinklift
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
// <null>
// <null>
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!

We've used
<!>
as an infix abbreviation for themap
function to mirror Haskell's<$>
infix abbreviation for the Functor typeclass'sfmap
method.<$>
itself isn't a legal infix identifier in F#.) ↩ 
There are several additional laws that an applicative must follow, but I'm not going into them here. See this article for details. ↩

Haskell usually uses the name
ap
orapply
as synonyms for<*>
. ↩ 
Haskell calls the lifting function
pure
orreturn
, but both of those are reserved words in F#. ↩
Beautiful folds in F# (3 Part Series)
Discussion
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.Thanks! Yeah, I really should make it a series. Good suggestion.