Matt Thornton

Posted on Mar 16, 2021 • Edited on Mar 31, 2021

Grokking Monads

#fsharp #functional #programming #grokking

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

Small F# primer

We'll be using F#, but it should be easy enough to follow along if you've not used it before. You'll only need to understand the following bits.

F# has an option type. It represents either the presence of Some value or its absence through a None value. It is typically used instead of null to indicate missing values.
Pattern matching on an option type looks like:

match anOptionalValue with
| Some x -> // expression when the value exists
| None -> // expression when the value doesn't exist.

F# has a pipe operator which is denoted as |>. It is an infix operator that applies the value on the left hand side to the function on the right. For example if toLower takes a string and converts it to lowercase then "ABC |> toLower would output "abc".

The scenario

Let's say we're writing some code that needs to charge a user's credit card. If the user exists and they have a credit card saved in their profile we can charge it, otherwise we'll have to signal that nothing happened.

The data model in F#

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

type User = 
    { Id: UserId
      CreditCard: CreditCard option }

Notice that the CreditCard field in the User record is an option, because it could be missing.

We want to write a chargeUserCard function with the following signature

double -> UserId -> TransactionId option

It should take an amount of type double, a UserId and return Some TransactionId if the user's card was successfully charged, otherwise None to indicate the card was not charged.

Our first implementation

Let's try and implement chargeUserCard. We'll first define a couple of helper functions that we'll stub out for looking up the user and actually charging a card.

let chargeCard (amount: double) (card: CreditCard): TransactionId option =
    // synchronously charges the card and returns 
    // Some TransactionId if successful, otherwise None

let lookupUser (userId: UserId): User option =
    // synchronously lookup a user that might not exist

let chargeUserCard (amount: double) (userId: UserId): TransactionId option =
    let user = lookupUser userId
    match user with
    | Some u ->
        match u.CreditCard with
        | Some cc -> chargeCard amount cc
        | None -> None
    | None -> None

It's done, but it's a bit messy. The double pattern match isn't the clearest code to read. It's probably manageable in this simple example, but wouldn't be if there was a third, or fourth nested match. We could solve that by factoring out some functions, but there's another issue. Notice the fact that in both the None cases we return None. This looks innocent because the default value is simple and it's only repeated twice, but we should be able to do better than this.

What we really want is to be able to say, "if at any point we can't proceed because some data is missing, then stop and return None".

Our desired implementation

For a moment, let's imagine the data is always present and we have no options to deal with. Let's call this chargeUserCardSafe and it would look like this.

let chargeUserCardSafe (amount: double) (userId: UserId): TransactionId =
    let user = lookupUser userId
    let creditCard = u.CreditCard
    chargeCard amount creditCard

Notice how it now returns a TransactionId rather than TransactionId option because it can never fail.

It would be great if we could write code that looked like this, even in the presence of missing data. To make that work though we're going to need to put something in between each of those lines to make the types line up and glue them together.

Refactoring towards a cleaner implementation

How should that piece of glue behave? Well, it should terminate the computation if the value in the previous step was None, otherwise it should unwrap the value from the Some and supply it to the next line. In effect, doing the pattern matching that we first wrote above.

Let's see if we can factor out the pattern match then. First we'll start by rewriting the function that can't fail in a pipeline fashion so we can more easily inject our new function in between the steps later.

// This helper is just here so we can easily chain all the steps
let getCreditCard (user: User): CreditCard option =
    u.CreditCard

let chargeUserCardSafe (amount: double) (userId: UserId): TransactionId = 
    userId 
    |> lookupUser 
    |> getCreditCard 
    |> chargeCard amount

All we've done here is turn it into a series of steps that are composed with the pipe operator.

Now if we allow lookupUser and lookupCreditCard to return option again then it will no longer compile. The problem is that we can't write

userId |> lookupUser |> getCreditCard

because lookupUser returns User option and we're trying to pipe that into a function that's expecting a plain ol' User.

So we're faced with two choices to get this to compile.

Write a function of type User option -> User that unwraps the option so it can be piped. This means throwing away some information by ignoring the None case. An imperative programmer might solve this by throwing an exception. But functional programming is supposed to give us safety, so we don't want to do that here.
Transform the function on the right hand side of the pipe so that it can accept a User option instead of just a User. So what we need to do is write a higher-order function. That is, something that takes a function as input and transforms it into another function.

We know this higher order function should have the type (User -> CreditCard option) -> (User option -> CreditCard option).
So let's write it by just following the types. We'll call it liftGetCreditCard, because it "lifts" the getCreditCard function up to work with option inputs rather than plain inputs.

let liftGetCreditCard getCreditCard (user: User option): CreditCard option =
    match user with
    | Some u -> u |> getCreditCard
    | None -> None

Nice, now we're getting closer to the chargeUserCard function we wanted. It now becomes.

let chargeUserCard (amount: double) (userId: UserId): TransactionId option = 
    userId 
    |> lookupUser 
    |> liftGetCreditCard getCreditCard 
    |> chargeCard double

By partially applying getCreditCard to liftGetCreditCard we created a function whose signature was User option -> CreditCard option which is what we wanted.

Well not quite, we've now got the same problem, just further down the chain. chargeCard is expecting a CreditCard, but we're trying to pass it a CreditCard option. No problem, let's just apply the same trick again.

let liftGetCreditCard getCreditCard (user: User option): CreditCard option =
    match user with
    | Some u -> u |> getCreditCard
    | None -> None

let liftChargeCard chargeCard (card: CreditCard option): TransactionId option =
    match card with
    | Some cc -> cc |> chargeCard
    | None -> None

let chargeUserCard (amount: double) (userId: UserId): TransactionId option = 
    userId 
    |> lookupUser 
    |> liftGetCreditCard getCreditCard 
    |> liftChargeCard (chargeCard amount)

On the verge of discovery 🗺

Notice how those two lift... functions are very similar. Also notice how they don't depend much on the type of the first argument. So long as it's a function from the value contained inside the option to another optional value. Let's see if we can write a single version to satisfy both then, which we can do by renaming the first argument to f (for function) and removing most of the type hints, because F# will then infer the generics for us.

let lift f x =
    match x with
    | Some y -> y |> f
    | None -> None

The type inferred by F# for lift is ('a -> 'b option) -> ('a option -> 'b option). Where 'a and 'b are generic types. It's quite a mouthful and abstract, but let's put it side-by-side with the more concrete signature of liftGetCreditCard from above.

(User -> CreditCard option) -> (User option -> CreditCard option)

('a -> 'b option) -> ('a option -> 'b option`)

The concrete User type has been replaced with a generic type 'a and the concrete CreditCard type has been replaced with the generic type 'b. That's because lift doesn't care what's inside the option box, it's just saying "give me some function 'f' and I'll apply it to the value contained within 'x' if that value exists." The only constraint is that the function f accepts the type which is inside the option.

OK, now we can cleanup chargeUserCard even more.

let chargeUserCard (amount: double) (userId: UserId): TransactionId option = 
    userId 
    |> lookupUser 
    |> lift getCreditCard 
    |> lift (chargeCard amount)

Now it's really looking close to the version without the optional data. One last thing though, let's rename lift as andThen because intuitively we can think of that function as continuing the computation when the data is present. So we can say, "do something and then if it succeeds does this other thing".

let chargeUserCard (amount: double) (userId: UserId): TransactionId option = 
    userId 
    |> lookupUser 
    |> andThen getCreditCard 
    |> andThen (chargeCard amount)

That reads quite nicely and translates well to how we wanted to think about this function. We look up the user, then if they exist we get their credit card information and finally if that exists then we charge their card.

You just discovered monads 👏

That lift / andThen function we wrote is what makes option values monads. Typically when talking about monads it's called bind, but that's not important to grok them. What's important is that you can see why we defined it and how it works. Monads are just a class of things with this "then-able" type of functionality defined¹.

Hey, I recognise you! 🕵️‍♀️

There's another reason that I renamed lift to andThen. If you're a JavaScript developer then this should look familiar to a Promise with a then method. In which case you've probably already grokked monads. A Promise is also a monad. Exactly like with option, it has a then which takes another function as input and calls it on the result of the Promise if it's successful.

Monads are just "then-able" containers 📦

Another good way to intuit monads is to think of them as value containers. An option is a container that either holds a value or is empty. A Promise is a container that "promises" to hold the value of some asynchronous computation if it returns successfully.

There are of course others too, like List (which holds the values from many computations) and Result which contains a value if a computation succeeds or an error if it fails. For each of these containers we can define a andThen function which defines how to apply a function which requires the thing inside the container to a thing wrapped in a container.

Spotting Monads in the wild

If you ever find yourself working with functions that take some plain input, like an int, string or User and which perform some side-effect thereby returning something like option, Promise or Result then there's probably a monad lurking around. Especially if you have several of these functions that you want to call sequentially in a chain.

What did we learn? 👨‍🎓

We learnt that monads are just types of containers that have a "then-able" function defined for them, which goes by the name bind. We can use this function to chain operations together that natively go from an unwrapped value to a wrapped value of a different type.

This is useful because it's a common pattern that springs up for lots of different types and by extracting this bind function we can eradicate a lot of boiler plate when dealing with those types. Monads are just a name given to things that follow this pattern and like Richard Feynman said, names don't constitute knowledge.

Next time

If you remember the original goal we set ourselves when starting this refactoring journey, you'll know that we wanted to write something like this

let chargeUserCard (amount: double) (userId: UserId): TransactionId option =
    let user = lookupUser userId
    let creditCard = u.CreditCard
    chargeCard amount creditCard

But still have it work when dealing with optional values. We didn't quite fully achieve that goal here. In the next post we'll see how we can use F#'s computation expressions to recover this more "imperative" style of programming even when working with monads.