Introduction

In the previous post, we introduced Functors, and observed a symmetry between operating with unaugmented functions on unaugmented and augmented values.

In this post, we’ll talk about how to augment functions as well, and then operate with them on augmented values.

Simple Addition

Let’s consider addition:

We know how to do addition with unaugmented values in F#

let seven = 3 + 4

But what happens when we want to add augmented values? Clearly, the following will not work

let howEvenDoesThisWork = (Some 3) + (Some 4)

Of course, we could write some form of magic operator in Maybe to handle addition, but this approach has two severe limitations:

1. We would have to write a similar function for every other function that operates on unaugmented values - subtraction, multiplication and everything else. Clearly this is painful.
2. We would have to replicate this effort for every other functor. This is exponentially more painful, and perhaps would prevent us from embarking down the road of using these structures in the first place… (Maybe this is why these approaches are not commonplace with other languages?)

Clearly we need a nicer way to apply existing functions.

Part of the reason this is a problem is because (+) takes two arguments. If it had just taken one argument, we could use Map to allow Maybe to operate on the internally stored raw value with any old properly-typed function! Now that we have two arguments, we need to support partial application, and that is going to mess things up for us. Basically, what we need is some way to “lift” a function into the Maybe context in a general way so we can support partial application.

In F#, partial application is the normal way to operate on functions with more than one argument. This automatically happens with anonymous lambdas but let’s get explicit here so we can see what’s going on

// (+) takes two arguments
// (+) : int -> int -> int

// partially applying the first argument results in a lambda taking the remaining arguments. We'll name this lambda for clarity.
// addThree : int -> int
let addThree = 3 |> (+) 

// finally, applying the last argument results in the result
// seven : int
let seven = addThree 4

We have already encountered Map. So far, we have written it as:

// map : F<'a> -> ('a -> 'b) -> F<'b>

We could flip the arguments without any change to its behaviour

// map : ('a -> 'b) -> F<'a> -> F<'b>

If we squint a little, we can see Map as a function that takes a function of type ('a -> 'b), and returns a function of type (F<'a> -> F<'b>). One might say that Maybe.Map lifts a function f into the Maybe context. The lifted function is surely partially applicable, so perhaps we only need to use Map for the (+) as well!

// addThree_m : Maybe<int -> int>
let addThree_m = (Some 3) <|> (+)

But, alas, this is not quite sufficient, because there’s no way to apply a function of type Maybe<int -> int> onto the second argument. Therefore, we need to extend Maybe to give us this functionality.

type Maybe<'t> with
    member this.Apply<'r> (f : Maybe<'t -> 'r>) =
        match f with
        | Some op -> this.Map op
        | None -> Maybe<'r>.None

This function applies a value of type Maybe<'t> to a function of type Maybe<'t -> 'r>, and returns a Maybe<'r>. Now we have the building blocks in place to do this:

Let’s give this an infix form too!

let (<*>) (mf : Maybe<'a ->'b>) (ma : Maybe<'a>) = ma.Apply mf

// addThree_m : Maybe<int -> int>
let addThree_m = (Some 3) <|> (+)

// seven_m : Maybe<int>
let seven_m = addThree_m <*> (Some 4)

which allows us to write

let seven   =       3       +            4
let seven_m = (Some 3) <|> (+) <*> (Some 4)

This is indeed quite elegant, although the bit of operator soup in the middle might seem somewhat irritating.

Let’s clean things up one more step by providing an operation to just lift something into the Maybe context without actually mapping over a value:

type Maybe<'t> with
    static member Pure (t : 't) : Maybe<'t> =
        Some t

We can now write something that should contrast very well indeed with our traditional function operations:

let mplus = Maybe<_>.Pure (+)

let seven   =   (+)           3            4
let seven_m = mplus <*> (Some 3) <*> (Some 4)

This is really very elegant indeed. It is very satisfying to get a visual similarity between partial application of unaugmented functions on unaugmented values, and partial application of augmented functions on augmented values.

Terminology

This structure is still a Functor, but the two new methods Pure and Apply, which allow for a nice way to incorporate partial application within the functor’s context make it a special kind of functor called an Applicative Functor, or sometimes just an Applicative

In fact, in may usage scenarios, we may never actually use the Map method explicitly, because, (and this is fun to work out),

// x <|> f = pure f <*> x

Summary

We have come a long way. We started with functions and function application, chaining and composition; types, type composition and augmentation; functors and mapping; and now applicatives and (partial) application.

We had to put a fair bit of effort into arcane terminology, and do some mathematical gymnastics to get here.

Now, whilst all of this may be of academic interest, what does it have to do with real-world programming? In other words, why does knowing any of this help us in any practical way?

The next post addresses specifically this question. Read on!