Grokking Monad Transformers
Tags: fsharp, functional, programming, grokking
Published: 2021-05-07 21:29:35

Earlier in this series, in [Grokking Monads](https://dev.to/choc13/grokking-monads-in-f-3j7f), we discovered that monads allowed us to abstract away the machinery of chaining computations. For example when dealing with optional values, they took care of the failure path for us in the background and freed us up to just write the code as if the data was always present. What happens though when we have multiple monads we'd like to use, how can we mix them together? 

Just like in the rest of this series, we're going to invent monad transformers ourselves by solving a real software design problem. At the end we'll see that we've discovered the monad transformer and in doing so we'll understand it more intuitively.

# The scenario
Let's revisit the same scenario we encountered in [Grokking Monads](https://dev.to/choc13/grokking-monads-in-f-3j7f) where we want 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 and email them a receipt, otherwise we'll have to signal that nothing happened. This time however, we're going to make the `lookupUser`, `chargeCard` and `emailReceipt` functions async because they call external services.

We'll start with the following data model and operations.

```fsharp
type UserId = UserId of string

type TransactionId = TransactionId of string

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

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

let lookupUser userId: Async<option<User>>

let chargeCard amount card: Async<option<TransactionId>>

let emailReceipt transactionId: Async<TransactionId>
```

The only difference from before is that `lookupUser`, `chargeCard` and  `emailReceipt` return `Async` now, because in reality they'll be calling a database, external payment gateway and sending messages.

# Our first implementation
Using our learnings from [Grokking Monads, Imperatively](https://dev.to/choc13/grokking-monads-imperatively-394a) then we might immediately reach for the `async` computation expression because that's the primary monad that we're dealing with here. So let's start with that.

```fsharp
let chargeUser amount userId = 
    async {
        let! user = lookupUser userId
        let card = user.CreditCard
        let! transactionId = chargeCard amount card
        return! emailReceipt transactionId
    }
```

Looks simple and it captures the essence of what we need to do, but it's not right. The line `let card = user.CreditCard` isn't going to compile, because at this point `user` is of type `User option`. We've also got a similar problem when writing `chargeCard amount card` because we'll actually have a `CreditCard option` there.

One way around this is to just start writing the pattern matching logic ourselves to get access to the values inside those options so that we can use them. Let's see what that looks like.

```fsharp
let chargeUser amount userId =
    async {
        match! lookupUser userId with 
        | Some user -> 
            match user.CreditCard with
            | Some card -> 
                match! chargeCard amount card with
                | Some transactionId -> return! (emailReceipt transactionId) |> Async.map Some
                | None -> return None
            | None -> return None
        | None -> return None
    }
```

This is much more cumbersome than before and the fairly simple logic of this function is obscured by the nested pattern matching (a.k.a. the [pyramid of doom](https://en.wikipedia.org/wiki/Pyramid_of_doom_(programming))). We're basically back to the same situation that we found ourselves in when we first introduced this in [Grokking Monads](https://dev.to/choc13/grokking-monads-in-f-3j7f). It seems like once we've got more than one monad to deal with, everything inside the outer one has to fall back to manually dealing with the failure path again through continual pattern matching.

# Inventing a new monad
At this point we might think to ourselves, why don't we invent a new monad? One that encapsulates the fact that we want to perform async computations that return optional results. It should behave like both the `async` monad when an async operation fails and the `option` monad when the async operation produces missing data. Let's call it `AsyncOption`.

What we need to do then is figure out how to implement `bind` for this new monad. Let's start with the types and then use them to guide us in writing it. In this case it will have the signature `(a' -> Async<option<'b>>) -> Async<option<'a>> -> Async<option<'b>>`. 

So this is telling us that we're given a function that wants some value of type `'a` and will return us a new value wrapped up in our `Async<option<_>>` type. We're also given an instance of this monad pair that encapsulates a value of type `'a`. So intuitively, we need to unwrap both the `Async` and `option` layers to get at this value of type `'a` and then apply it to the function.

```fsharp
let bind f x =
    async {
        match! x with
        | Some y -> return! f y
        | None -> return None
    }
```

Here we've achieved this by using the `async` computation expression. This allows us to use a `match!` which simultaneously unwraps the async value and pattern matches on the inner `option` to allow us to extract the value from that too.

We’ve had to deal with three possible cases:
1. In the case where `x` is a successful async computation that's returned `Some` value then we can apply the function `f` to the value.
1. In the case that the async operation successfully returns `None` then we just propagate the `None` value by wrapping it in a new `async` by using `return`. 
1. Finally, if the async computation fails then we just let the `async` computation expression deal with that and propagate that failure without calling `f`.

So with `bind` in place it's easy to create an `asyncOption` computation expression and we can write our function using that.

```fsharp
let chargeUser amount userId =
    asyncOption {
        let! user = lookupUser userId
        let! card = user.CreditCard
        let! transactionId = chargeCard amount card
        return! emailReceipt transactionId
    }
```

Much better, but the eagle eyed might have already spotted a problem with our plan. When we try and call `user.CreditCard` it won't work. The problem is that `user.CreditCard` returns a vanilla `option` and our `bind` (and therefore `let!`) has been designed to work with `Async<option<_>>`. 

On top of this, on the final line we have a similar problem. The `emailReceipt` function returns a plain `Async<_>` and so we can't just write `return!` because it's not producing an `Async<option<_>>`. It seems like we're stuck with needing everything to use exactly the same monad or things won't line up.

# Lifting ourselves out of a hole 🏋️
A simple way to solve the first problem is to just wrap that  vanilla `option` in a default `Async` value. What would a default `Async` be though? Well we want to just treat it as if it's a successful async computation that’s immediately resolved so let's just write a function called `hoist` that wraps its argument in an immediate async computation.

```fsharp
let hoist a =
    async {
        return a
    }
```

If you're a C# developer this is just like `Task.FromResult` and if you're a JavaScript developer then it's akin to `Promise.resolve`.

To solve the second problem we need a way to wrap up the value inside the `Async` in a default `option` value. The default `option` value would be `Some` in this case, and we saw in [Grokking Functors](https://dev.to/choc13/grokking-functors-bla) that the way to modify the contents of a wrapped value is to use `map`. So let's create a function called `lift` that just calls `map` with `Some`.

```fsharp
let lift (a: Async<‘a>): Async<option<‘a>> = a |> Async.map Some
```

So with this in hand we can finally finish off our `chargeUser` function.

```fsharp
let chargeUser amount userId =
    asyncOption {
        let! user = lookupUser userId
        let! card = user.CreditCard |> hoist
        let! transactionId = chargeCard amount card
        return! (emailReceipt transactionId) |> lift
    }
```

This is now looking quite tidy and the logic is clear to see, no longer hidden amongst nested error handling code. So is that all there is to monad transformers? Well not quite...

# A combinatorial explosion 🤯
Let's say for arguments sake that we wanted to use a `Task` instead of an `Async` computation. Or perhaps we want to start returning a `Result` now instead of an `option`. What about if we want to use a `Reader` too? 

You can probably see how the combinations of all of these different monads is going to get out of hand if we need to create a new monad to represent each pair. Not to mention the fact that we might want to create combinations of more than two.

Wouldn't it be nice if we could find a way to write a universal monad transformer? One that could let us combine any two monads to create a new one. Let's see if we can invent that.

Where do we start? Well we know by now that to create a monad we need to implement `bind` for it. We've also seen how to do that for a new monad created from the `Async` and `option` pair of monads. All we basically need to do is peel back each of monad layers to access the value contained inside the inner one and then apply this value to the function to generate a new monad pair.

Let's imagine for a minute that we have a universal `monad` computation expression which invokes the correct bind, by figuring out which version to use, based on the particular monad instance that it's being called on. With that to hand then we should be able to peel off two monadic layers to access to the inner value quite easily.

```fsharp
let bindForAnyMonadPair (f: 'a -> 'Outer<'Inner<'b>>) (x: 'Outer<'Inner<'a>>) =
    monad {
        let! innerMonad = x
        monad {
            let! innerValue = innerMonad
            return! f innerValue
        }
    }
```

Unfortunately it turns out that this doesn't work. The problem is that when we write `return! f value` it's not quite right. At that point in the code we're in the context of the inner monad's computation expression and so `return!` is going to expect `f` to return a value that's the same as the inner monad, but we know that it returns `'Outer<'Inner<'b>>` because that’s what we need it to have for our new bind. 

It might seem like there would be a way out of this. After all, we have the value we need to supply to `f`, so surely we must be able to just call it and generate the value we need somehow. However, we have to remember that computation expressions and `let!` are just syntactic sugar for `bind`. So what we're really trying to write is this.

```fsharp
let bindForAnyMonadPair (f: 'a -> Outer<Inner<'b>>) (x: Outer<Inner<'a>>) =
    x 
    |> bind 
        (fun innerMonad ->
            innerMonad
            |> bind (fun value -> f value))
```

And then it's (maybe) more obvious to see that `f` can't be used with the inner monad's `bind` because it's not going to return the right type. So it seems we can dig inside both monads to get to the value in a generic way, but we don't have a generic way of putting them back together again.

# There's still hope 🤞
We might have failed at creating a truly universal monad transformer, but we don't have to completely give up. If we could make even one of the monads in the pair generic then it would massively reduce the number of monad combinations we need to write.

Intuitively you might think about making the inner one generic, I know I did. However, you'll see that we fall into exactly the same trap that we did before when we tried to make both generic, so that won't work.

In that case our only hope is to try making the outer monad generic. Let's assume we've still got our universal `monad` computation expression to hand and see if we can write a version that works whenever the inner monad is an `option`.

```fsharp
let bindWhenInnerIsOption (f: 'a -> 'Outer<option<'b>>) (x: 'Outer<option<'a>>) =
    monad {
        match! option with
        | Some value -> return! f value
        | None -> return None
    }
```

🙌 It works! The reason we were able to succeed this time is because we could use `return!` when calling `f` because we were still in the context of the outer monad's computation expression. So `return!` is able to return a value that is of the type `Outer<option<_>>` which is precisely what `f` gives us back.

We're also going to need generic versions of `hoist` and `lift` too, but they're not too difficult to write.

```fsharp
let lift x = x |> map Some

let hoist = result x
```

In order to write `lift` we're assuming that the `Outer` monad has `map` defined for it and that `map` can select the correct one, because we don't know at this point in time which monad to call `map` on.

Also `hoist` is making use of a generic `result` function which is an alias for `return` because `return` is a reserved keyword in F#. Technically every monad should have `return`, as well as `bind`, defined for it. We haven't mentioned `return` before because it's so trivial, but it just wraps any plain value up in a monad. For example `result` for `option` would just be `Some`. 

# You just discovered the Monad Transformer 👏
With our invention of `bind`, `lift` and `hoist`, for the case when inner monad is an `option`, we've invented the `option` monad transformer. Normally this is called `OptionT` and is actually wrapped in a single case union to make it a new type, which I'll show in the appendix, but that's not an important detail when it comes to grokking the concept.

The important thing to realise is that when you need to deal with multiple monads you don't have to resort back to the pyramid of doom. Instead, you can use a monad transformer to represent the combination and easily create a new monad out of a pair of existing ones. Just remember that it's the inner monad that we define the transformer for.

# Test yourself

See if you can implement `bind`, `lift` and `hoist` for the `Result` monad.

{% details Solution %}

```fsharp
module ResultT =
    let inline bind (f: 'a -> '``Monad<Result<'b>>``) (m: '``Monad<Result<'a>>``) =
        monad {
            match! m with
            | Ok value -> return! f value
            | Error e -> return Error e
        }

    let inline lift (x: '``Monad<'a>``) = x |> map Ok

    let inline hoist (x: Result<'a, 'e>) : '``Monad<Result<'a>>`` = x |> result
```

{% enddetails %}

# Does this actually work? 😐
When we invented `bind` for `OptionT` we imagined that we had this all powerful `monad` computation expression to hand that would work for any monad. You might be wondering if such a thing exists? Particularly whether such a thing exists in F#. 

It seems like we need to ability to work with generic generics. In other words, we need to be able to work with any monad which itself can contain any value. This is called higher kinded types and you might be aware of the fact that F# doesn't support them. 

Fortunately for us, the excellent [FSharpPlus](https://fsprojects.github.io/FSharpPlus/abstraction-monad.html) has figured out a way to emulate higher kinded types and does have such an abstract `monad` computation expression defined. It also has plenty of monad transformers, like `OptionT`, ready to use. 

# Should I use a monad transformer?
Monad transformers are certainly quite powerful and can help us recover from having to write what would otherwise be heavily nested code. On the other hand though they're not exactly a free lunch. There are a few things to consider before using them.
1. If the monad stack gets large it can in itself become quite cumbersome to keep track of it. For instance the types can become large and the lifting across many layers can become tiring.
1. This is an area that pushes F# to its limits. Whilst FSharpPlus has done a fantastic job in figuring out how to emulate higher kinded types, it can lead to very cryptic compile time errors if you've got a type mismatch somewhere when using the monad transformer. 
1. It can also slow down compile times due to the fact it's pushing type inference beyond what it was really designed for.

In some cases then you might be better off just defining a new monad and writing `bind` etc for it yourself. If your application typically deals with the same stack of monads then the improved compiler errors will probably outweigh the relatively small maintenance burden of writing the code yourself.

# What did we learn? 🧑‍🎓
We've now discovered that it's possible to combine monads into new monads and that this lets us write tidier code when we would otherwise have to write nested pattern matches. We've also seen that while it's not possible to create a universal monad transformer for any pair, it is possible to at least define a monad transformer for a fixed inner type. That means we only need to write one transformer per monad in order to start creating more complex monad combinations.

{% details Appendix %}
As mentioned above a monad transformer usually has a new type associated with it. Below I'll show what this looks like for the `OptionT` monad transformer and then use that along with the generic `monad` computation expression from FSharpPlus to implement the `chargeUser` function.

```fsharp
#r "nuget: FSharpPlus"

open FSharpPlus

type OptionT<'``Monad<option<'a>>``> = OptionT of '``Monad<option<'a>>``

module OptionT =
    let run (OptionT m) = m

    let inline bind (f: 'a -> '``Monad<option<'b>>``) (OptionT m: OptionT<'``Monad<option<'a>>``>) =
        monad {
            match! m with
            | Some value -> return! f value
            | None -> return None
        }
        |> OptionT

    let inline lift (x: '``Monad<'a>``) = x |> map Some |> OptionT

    let inline hoist (x: 'a option) : OptionT<'``Monad<option<'a>>``> = x |> result |> OptionT

let chargeUser amount userId : Async<option<TransactionId>> =
    monad {
        let! user = lookupUser userId |> OptionT
        let! card = user.CreditCard |> OptionT.hoist
        let! transactionId = (chargeCard amount card) |> OptionT
        return! (emailReceipt transactionId) |> lift
    }
    |> OptionT.run
```

If you're wondering about those type annotations like ``` '``Monad<'a>`` ``` then they're really they're just fancy labels. We've used the ``` `` ``` quotations to just give a more meaningful name to show that they represent some generic `Monad`. This acts as documentation, but unfortunately it's not really doing any meaningful type checking. As far as the compiler is concerned that just like any other generic type. We could have easily just written `type OptionT<'a> = OptionT of 'a`. So the onus is back on us when implementing these functions to make sure we do write it as if it's actually a generic monad and not just any generic value.

{% enddetails %}