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:
- In the case where
x
is a successful async computation that's returnedSome
value then we can apply the functionf
to the value. - In the case that the async operation successfully returns
None
then we just propagate theNone
value by wrapping it in a newasync
by usingreturn
. - Finally, if the async computation fails then we just let the
async
computation expression deal with that and propagate that failure without callingf
.
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.
- 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.
- 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.
- 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.
If you're wondering about those type annotations likeAppendix
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
'``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.
Top comments (2)
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!
Thanks. Thatโs made my day!