Grokking Monads, Imperatively
Tags: fsharp, functional, programming, grokking
Published: 2021-03-26 10:06:28

Previously, in [Grokking Monads](https://dev.to/choc13/grokking-monads-in-f-3j7f), we discovered monads by going through a worked example. By the end we'd created the basic machinery in the form of a `andThen` function for the `option` type, but we hadn't quite reached our ultimate goal. We were hoping to write the code in the same way that we would if we didn't have to deal with `option` values. We wanted to write it in a more "imperative" style. In this post we're going to see how to achieve that with F#'s computation expressions whilst also deepening our intuition about monads.

# Recap

Let's quickly recap the domain model 

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

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

We wanted to write `chargeUserCard` with the signature 

```fsharp
UserId -> TransactionId option
```

If we didn't have to deal with the `option` values then we could write it in the "imperative" style.

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

Our goal was to write something that looked like this even when we had to deal with optional values in the middle of the computation. 

We got as far as factoring out the following `andThen` function

```fsharp
let andThen f x =
    match x with
    | Some y -> y |> f
    | None -> None
```

Using that the best we could manage was the following version of `chargeUserCard`

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

# What's the problem 🤷‍♂️
You might rightly be wondering what the issue is here. Our final implementation of `chargeUserCard` is readable. It quite clearly describes our intent and we've eliminated the repetitive code. So is this just a case of aesthetics?

To see why the ability to use the "imperative" style extends beyond simple aesthetics, let's introduce another requirement. This will stress our current implementation and show its weakness.

Users must now set spend limits on their profile. For backwards compatibility the limit is modelled as an `option`. If a limit exists we must check that the spend is under the limit, if the user has not yet set a limit we terminate the computation and return `None`. 

This limit is stored in the `User` model like this.

```fsharp
type User =
    { Id: UserId
      CreditCard: CreditCard option
      Limit: double option }
```

Let's start by implementing a `getLimit` function (like we did for `getCreditCard`) along these lines.

```fsharp
let getLimit (user: User): double option =
    user.Limit
```

So how do we go about updating `chargeUserCard` to take into account spend limits? We need to perform the following steps:
1. Lookup the user based on their id
1. If the user exists lookup the credit card
1. If the user exists lookup the limit
1. If the limit and credit card exist then charge the card providing the amount is less than the limit

Let's first write this as if there were no `option` values to give us something to aim for in the "imperative" style.

```fsharp
let chargeUserCardSafe (amount: double) (userId: UserId) =
    let user = lookupUser userId
    let card = getCreditCard user
    let limit = getLimit user
    if amount <= limit then
        chargeCard amount card
    else 
        None
```

Let's reintroduce the `option` values and naively convert it to the pipeline form using `andThen`.

```fsharp
let chargeUserCard (amount: double) (userId: UserId): TransactionId option = 
    userId 
    |> lookupUser 
    |> andThen getCreditCard 
    |> andThen getLimit
    |> andThen 
        (fun limit -> 
            if amount <= limit then 
                chargeCard amount ??
            else
                None)
```

This won't compile for two reasons:
1. We can't write `andThen getLimit` after `getCreditCard`, because at that point we've got access to the `CreditCard`, but we need to pass a `User` into `getLimit`.
1. We don't have access to a `CreditCard` value at the point where we want to call `chargeCard`.

# Breaking the chain 🔗
There no longer seems to be one sequential flow of data. This is because we need to use the `user` to lookup both the `CreditCard` and the `limit` and we need both of those things to exist before we can charge the card. 

After some head scratching we can find a way to write this function in the pipeline style using `andThen`, but beware, it gets hairy! 

```fsharp
let chargeUserCard (amount: double) (userId: UserId) : TransactionId option =
    let applyDiscount discount = amount * (1. - discount)

    userId
    |> lookupUser
    |> andThen
        (fun user ->
            user
            |> getCreditCard
            |> andThen
                (fun cc ->
                    user
                    |> getLimit
                    |> Option.map (fun limit -> {| Card = cc; Limit = limit |})))
    |> andThen
        (fun details ->
            if amount <= details.Limit then
                chargeCard amount details.Card
            else
                None)
```

Wow! That escalated quickly!

Don't worry if you've not fully comprehended this implementation. That's kind of the point, it's become difficult to understand and we need to find a way to tame it.

When this type of scenario occurs it makes chaining cumbersome. In order to keep using the `|>` operator we need to accumulate more and more state so that we can finally use all of it at the end of the chain. This is what we used the anonymous record for above in the deeply nested part of the expression. 

We might start to wonder whether functional programming is really so great. In the good old imperative days we'd just assign those values to a variable and then reference them all at the end of the method when we needed them.

# Having our cake and eating it 🍰
Fortunately there is a way out of this mess.

This time we're going to invent some new syntax to make it work with `option` values. We're going to define `let!`. It's like `let` but rather than just binding the name to the expression, it's going to bind the name to the value inside the `option` if it exists. If the value doesn't exist then it's going to terminate the function immediately with a value of `None`. This is exactly the same behaviour as the `andThen` function we invented before, except now it allows us to name the result.

With this new syntax `chargeUserCard` is simply

```fsharp
let chargeUserCard (amount: double) (userId: UserId) =
    let! user = lookupUser userId
    let! card = getCreditCard user
    let! limit = getLimit user
    if amount <= limit then
        chargeCard amount card
    else 
        None
```

Barely any difference to the version without the `option`. "That's great", I hear you say, "but you can't just invent new syntax!". Well lucky for us we don't have to. F# provides `let!` out of the box as part of a feature called Computation Expressions.

# Computation Expressions != Magic 🪄
F# isn't entirely magic though, we have to teach it how `let!` should behave for a given monad. We have to define a new computation expression.

I'm not going to go into great details about how to do this here, the [F# docs](https://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/computation-expressions#creating-a-new-type-of-computation-expression) are a good place to start for that. All that's relevant for us is that F# requires us to create a type with a `Bind` method. We already know how to write `Bind` because we discovered it and called it `andThen`. The computation expression builder for an `option` ends up looking like this.

```fsharp
let andThen f x =
    match x with
    | Some y -> y |> f
    | None -> None

type OptionBuilder() =
    member _.Bind(x, f) = andThen f x
    member _.Return(x) = Some x
    member _.ReturnFrom(x) = x
```

We also needed to define `Return`, which lets us return a regular value from the computation expression by wrapping it in a `Some` case and `ReturnFrom`, which lets us return the result of an expression which produces an `option`. 

*`ReturnFrom` might seem superfluous because it's so simple. However, in other computation expressions we might require more complex behaviours. By making it extensible F# has granted us that power at the expense of some trivial boilerplate in this case.*

With the computation expression in place our final implementation of `chargeUserCard` becomes

```fsharp
let chargeUserCard (amount: double) (userId: UserId) =
    option {
        let! user = lookupUser userId
        let! card = getCreditCard user
        let! limit = getLimit user

        return!
            if amount <= limit then
                chargeCard amount card
            else
                None
    }
```

Pretty neat! We just need to wrap the body in `option {}` to indicate we wanted to use the `option` computation expression we just defined. We also had to use `return!` on the final line to tell it to return the `option` value produced by that expression.

# Test driving the computation expression 🚘
To give some insights into the computation expression we just defined and to prove it really does behave as we want, let's run a few tests in the F# repl.

```fsharp
> option {
-     let! x = None
-     let! y = None
-     return x + y 
- };;
val it : int option = None
```

So when both `x` and `y` are `None` then result is `None`. What about when just `x` or `y` are `None`?

```fsharp
> option {
-     let! x = Some 1
-     let! y = None
-     return x + y 
- };;
val it : int option = None

> option {
-     let! x = None
-     let! y = Some 2
-     return x + y 
- };;
val it : int option = None
```

3 for 3! We just need to make sure it actually returns a `Some` containing the addition when both `x` and `y` have some value.

```fsharp
> option {
-     let! x = Some 1
-     let! y = Some 2
-     return x + y 
- };;
val it : int option = Some 3
```

Full marks! 🎉

# More monad intuition
This "imperative" style might look familiar to you. If this were an `async` computation then `let!` is just like `await`. The reason people love `async/await`, especially those who remember the days of nested promise callback hell, is because it allows us to write programs as if they weren't async. It removes all of the noise associated with having to deal with the fact that results wont be immediately available and might also fail.

F#'s computation expressions allow us to make this work with all the monads flavours, not just `async`. This is really powerful as we can now write the code in an easy to comprehend "imperative" style, but without the mutable state and other side effects of fully imperative programming.

# Do I have to roll my own 🗞
The [F# core library](https://docs.microsoft.com/en-us/dotnet/fsharp/language-reference/computation-expressions#built-in-computation-expressions) includes some built in computation expressions for sequences, async workflows and LINQ query expressions. There are many more useful ones implemented in open source libraries too. [FSharpPlus](https://fsprojects.github.io/FSharpPlus//computation-expressions.html) has even taken it a step up by creating a single `monad` computation expression which works for many monadic types.

# What did we learn 🧑‍🎓
We've seen that whilst the `andThen` function is the underlying machinery for chaining monadic computations, it can quickly become cumbersome to work with it directly when we don't have such an obvious linear sequence for the operations we want to perform. By utilising F#'s computation expressions we can hide this "plumbing" away and instead write the code as if we weren't dealing with a monad. This is exactly what `async/await` does, but just in the narrower sense of `Tasks` or `Promises`. So if you've grokked `async/await` then you're well on your way to having grokked monads and computation expressions.