Beautiful folds in F# - Part 3: Applicatives
Tags: fsharp, dotnet, functional
Published: 2020-01-22 04:31:16

# 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:

```fsharp
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:

```fsharp
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:

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

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

```fsharp
toMean <!> composableSum <*> composableLength
```

Note how similar this version is to normal function invocation:

```fsharp
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:

```fsharp
('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](https://dev.to/shimmer/functors-in-f-2fd7)'s `map` function:

```fsharp
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 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:[^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 the `compose` 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 it `lift` going forward.[^4] 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:

```fsharp
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:

```fsharp
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](http://squing.blogspot.com/2008/11/beautiful-folding.html)), 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](https://wiki.haskell.org/Functor)'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](https://en.wikibooks.org/wiki/Haskell/Applicative_functors#Applicative_functor_laws) 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#.