Grokking Applicatives

Applicatives are perhaps the less well-known sibling of the monad, but are equally important and solve a different, but related problem. Once you've discovered them you'll find they're a useful tool for writing code where we don't care about the order of the computations.

In this post we're going to grok applicatives by "discovering" them through a worked example.

Small F# primer

Skip this if you've got basic familiarity with F#.

It should be easy enough to follow along if you've not used F# before, you'll just need to understand the following bits:

• F# has a Result<T, E> type. It represents the result of a computation that might fail. It has a Ok case constructor which contains a value of type T and a Error case constructor which contains an error value of type E.
• We can pattern match on a Result like so:

match aResult with
| Ok x -> // expression based on the good value x
| Error e -> // expression based on the error value e

The Scenario

Let's say we've been asked to write a function that validates a credit card, which is modelled like this.

type CreditCard =
    { Number: string
      Expiry: string
      Cvv: string }

The function we need to implement is

let validateCreditCard (creditCard: CreditCard): Result<CreditCard, string>

Happily, someone else has already written some functions for validating a credit card number, expiry and CVV. They look like this.

let validateNumber number: Result<string, string> =
    if String.length number > 16 then
        Error "A credit card number must be less than 16 characters"
    else
        Ok number

let validateExpiry expiry: Result<string, string> =
    // Some validation checks for an expiry

let validateCvv cvv: Result<string, string> =
   // Some validation checks for a CVV

The details of the validation checks aren't crucial here, I've just shown a basic example for the card number, but in reality they’d be more complex. The main thing to take note of is that each function takes an unvalidated string and returns a Result<string, string> which indicates whether or not the value is valid. If the value is invalid then it will return a string containing the error message.

Our first attempt

What luck! All we've got to do is compose these functions somehow to validate a credit card instance. Let's give it a go!

let validateCreditCard card =
    let validatedNumber = validateNumber card.Number
    let validatedExpiry = validateExpiry card.Expiry
    let validatedCvv = validateCvv card.Cvv

    { Number = validatedNumber
      Expiry = validatedExpiry
      Cvv = validatedCvv }

Hmmm, that doesn't compile. The problem is that we're trying to pass Result<string, string> to the fields of the CreditCard at the end, but the fields of CreditCard have type string.

I spy, with my little eye, something beginning with M 👀

Seeing as we've now Grokked Monads we might notice that we could solve our problem using monads. Each validation functions takes a string and lifts it up to a Result<string, string> and we seemingly want to chain several of these functions together. We saw in 'Grokking Monads' that we can use bind for exactly this type of chaining. For reference, bind for a Result would look like this.

let bind f result =
    match result with
    | Ok x -> f x
    | Error e -> Error e

So let's try and write validateCreditCard as a chain using bind.

let validateCard card =
    validateNumber card.Number
    |> bind (validateExpiry card.Expiry)
    |> bind (validateCvv card.Cvv)
    |> fun number expiry cvv ->
        { Number = number
          Expiry = expiry
          Cvv = cvv }

Looks neat, but it still doesn't compile!

The calls to bind expect a function that take as input the validated value from the previous computation. In the first case it would be the validated number being passed to the validateExpiry function. However, validateExpiry doesn't need the validated number as input, it needs the unvalidated expiry, but we do need to keep track of that validated number somehow until the end so that we can use it to build the valid CreditCard instance.

It is possible to remedy these points by accumulating these intermediate validation results as we go.

let validateCard card =
    validateNumber card.Number
    |> bind
        (fun number ->
            validateExpiry card.Expiry
            |> Result.map (fun expiry -> number, expiry))
    |> bind
        (fun (number, expiry) ->
            validateCvv card.Cvv
            |> Result.map
                (fun cvv ->
                    { Number = number
                      Expiry = expiry
                      Cvv = cvv }))

Yikes! 😱 Pretty messy and definitely more confusing than we'd like. At each stage we have to create a lambda that takes as input the validated values from the previous step, validates one more piece of data and then accumulates it all in a tuple until we finally have all of the bits to build the whole CreditCard.

Our simple validation task has been lost in a sea of lambdas and intermediate tuple objects. Imagine the mess if we had even more fields on the CreditCard that required validation. What we need is a solution that avoids us having to create so many intermediate objects.

Applicatives to the rescue 🦸

Another way to accumulate values is through partial application. This allows us to take a function of n arguments and return a function of n - 1 arguments. For example let's define a function called createCreditCard that works with plain string inputs.

let createCreditCard number expiry cvv =
    { Number = number
      Expiry = expiry
      Cvv = cvv }

We can progressively accumulate the values by applying them to the function.

let number = "1234"
let numberApplied = createCreditCard number

numberApplied is a function with the signature string -> string -> CreditCard or to name those parameters expiry -> cvv -> CreditCard. So we've been able to "store" the number for later without having to create an intermediate tuple.

So let's invent a function called apply that makes use of partial application but for values that are wrapped in some other structure such as Result and put it before each argument like this.

let validateCreditCard card: Result<CreditCard, string> =
    Ok (createCreditCard)
    |> apply (validateNumber card.Number)
    |> apply (validateExpiry card.Expiry)
    |> apply (validateCvv card.Cvv)

You might be wondering why we need to wrap createCreditCard in Ok. That's because this function is going to return Result<CreditCard, string>, therefore apply must return Result. This means that in order to chain them together it must also accept a Result as input. Therefore we need to just initially "lift" the createCardFunction up into a Result to kick off the chain with the right type.

It might seem strange to have a Result of a function, but remember that we're going to be using partial application to gradually accumulate the state after each call to apply. So really what we're doing here is starting with an empty container that is Ok and progressively filling it with data, checking at each step whether the new data is Ok or not.

As usual we can let the types guide us in writing this function. At each stage of the chain what we need to do is take two arguments. The first is a Result<T, E> and the second is a Result<(T -> V), E>. We want to try and unwrap both the value of type T and the function of type T -> V and if they're both Ok, we can apply the value to the function.

The type T -> V might look like a function of only one argument, but there's nothing to say that V can't be another function itself. So whilst this might look like it only works when the function input has a single argument, in fact it works for functions of any number of arguments, providing that the first argument matches the type of value contained in the Result we wish to apply.

So apply should have the signature Result<T, E> -> Result<(T -> V), E> -> Result<V, E>, but we'll see that with just that, rather abstract, information it's quite straight forward to implement.

let apply a f =
    match f, a with
    | Ok g, Ok x -> g x |> Ok
    | Error e, Ok _ -> e |> Error
    | Ok _, Error e -> e |> Error
    | Error e1, Error _ -> e1 |> Error

Basically, all we can really do is pattern match on both the function f and the argument a and then do the case analysis, which gives us four cases to scrutinise. In the first case both values are Ok so we simply unwrap them both and apply the value to the function and then repackage in Ok. In all of the other cases we have at least one error so we return that. The final case is interesting because we have two errors, we decide to just keep the first one here.

Testing it out

Let's test the apply function in the FSharp repl to make sure it behaves correctly. It will also help us improve our understanding.

> Ok (createCreditCard) 
-    |> apply ((Ok "1234"): Result<string, string>) 
-    |> apply (Ok "08/19") 
-    |> apply (Ok "123")

val it : Result<CreditCard,string> = Ok { Number = "1234"
                                          Expiry = "08/19"
                                          Cvv = "123" }

Looks good, if all the inputs are valid then we get a valid CreditCard. Let's see what happens when one of the inputs is bad.

> Ok (createCreditCard) 
-    |> apply (Ok "1234") 
-    |> apply (Ok "08/19") 
-    |> apply (Error "Invalid CVV")

val it : Result<CreditCard,string> = Error "Invalid CVV"

Excellent, just as we'd hoped. Finally, what if we have multiple bad inputs.

> Ok (createCreditCard) 
-    |> apply (Error "Invalid card number") 
-    |> apply (Ok "08/19") 
-    |> apply (Error "Invalid CVV")

val it : Result<CreditCard,string> = Error "Invalid card number"

Again it's what we'd designed for. Here it's failed on the first bad input. Many of you might rightly be wondering whether this is desirable, surely it would be better to return all the errors. In the next post we'll see how we can do that.

You just discovered applicatives 👏

The apply function is what makes something applicative. Hopefully by seeing the problem that they solve you understand them more deeply and intuitively than by just staring at the type signature of apply and reading about the applicative laws.

Applicatives are similar to monads in that they provide a means to combine the outputs of several computations, but applicatives are useful when those computations are independent, whereas with monads we take the result of one and use it as the input of another.

A bit more tidy up 🧹

If you don't like the fact that you have to wrap the createCreditCard function in Ok, then we can get rid of this. If you've ready Grokking Functors then you'll see that map can be defined for Result to make it a functor. We know that map takes a function and calls it the contents of the Result if it's Ok. So we can actually use this to kick off the chain like so.

let validateCard card =
    (validateNumber card.Number)
    |> Result.map createCreditCard
    |> apply (validateExpiry card.Expiry)
    |> apply (validateCvv card.Cvv)

That's a little awkward though because the flow seems to be all mixed up with the createCreditCard function in the middle of the 3 arguments. To remedy this it's quite common to define an <!> infix operator for map, which then reads .

let validateCard card =
    createCreditCard 
    <!> validateNumber card.Number
    |> apply (validateExpiry card.Expiry)
    |> apply (validateCvv card.Cvv)

Finally, it's common to also use <*> for apply which gives us this.

let validateCard card =
    createCreditCard 
    <!> validateNumber card.Number
    <*> validateExpiry card.Expiry
    <*> validateCvv card.Cvv

Don't be put off by this if you find it confusing, they're just symbols. Grokking applicatives is about understanding how apply works and what problems it solves, not about this slightly esoteric syntax. I only point it out here as it's fairly common to see them used in this way.

Spotting Applicatives in the wild 🐗

Any time you find yourself needing to call a function with several arguments, but the values you have to hand are wrapped in something like a Result then applicatives are likely to help you solve the problem.

More types than just Result can be made applicative too, all we have to do is define the appropriate apply function for it. For example we could define it for option. As we hinted at above, there might be more than one way to implement such a function too, so make sure you've chosen the one with the semantics you need.

Test yourself 🧑‍🏫

See if you can write apply for the option type. The answers are below, no peeking until you've had a go first!

Option solution

let applyOpt a f =
    match f, a with
    | Some g, Some x -> g x |> Some
    | None, _
    | _, None -> None

This is just like for Result but because we have no additional information in the None case we can just combine all the patterns that contain at least one None into a single expression that returns None.

What did we learn? 🧑‍🎓

By defining an apply function we were able to apply arguments that were wrapped in a Result to a function expecting regular string arguments. We saw how doing this allowed us to use partial application as a means of progressively accumulating data and this effectively allowed us to write our code in a very similar style to how we'd have written it if we didn't have to deal with invalid inputs.

Comments

[Kirk Shillingford]

I love this series so much! Your explanations are great! Applicatives were always the least intuitive for me, at least in terms of use case and setup. Thank you for your efforts!

[Matt Thornton]

Thanks 👍 Glad to hear that. I found a lot of the articles on fp were lacking the intuition and I’ve always found it easier to learn myself when I’ve got a concrete problem to apply it to. Also writing these have really helped me iron out the details in my head.