Grokking Monad Transformers

Earlier in this series, in Grokking Monads, 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 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.

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

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.

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). We're basically back to the same situation that we found ourselves in when we first introduced this in Grokking Monads. 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.

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.
2. 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.
3. 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.

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.

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

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.

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.

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.

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.

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.

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.

Solution

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

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 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.
2. 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.
3. 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.

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.

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

Comments

[Bytesource]

You have a talent of breaking a complex topic into easy to follow logical steps. Never thought a post on monad transformers could be so interesting. Thanks a lot!

[Matt Thornton]

Thanks. That’s made my day!