Grokking Monads
Tags: fsharp, functional, programming, grokking
Published: 2021-03-16 11:33:43

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:

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

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

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

```fsharp
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 `option`s to deal with. Let's call this `chargeUserCardSafe` and it would look like this.

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

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

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

1. 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.

1. 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.

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

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

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

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

```fsharp
(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.

```fsharp
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".

```fsharp
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<sup>1</sup>.

# 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](https://www.youtube.com/watch?v=lFIYKmos3-s).

# 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

```fsharp
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](https://dev.to/choc13/grokking-monads-imperatively-394a) we'll see how we can use F#'s computation expressions to recover this more "imperative" style of programming even when working with monads.


***
#### Footnotes
1. Category theorists, please forgive me.