Can someone clarify monads / computation expressions and their syntax, in F#

Question

First, I've read:

https://fsharpforfunandprofit.com/posts/elevated-world/

and

https://ericlippert.com/2013/02/21/monads-part-one/

I feel like I have all the pieces, but not the part that joins it all together, so I have several questions that can probably be answered all together.

Also, F# is the first time I'm confronted to monads / computation expressions. I come from a C background and have no experience with other functional languages and these concepts.

I would like to clarify the terminology: as far as I understand, monads are the model and computation expressions are the F# implementation of this model. Is that correct?

To that effect, I seem to understand that there are a few underlying functionalities (bind, map, etc) that are called that way when you declare an expression, but require a totally different syntax (let!, yield!, etc) when used. However, you can still use the original terms as wanted (Option.map, etc). This seems very confusing, so I'm curious if I got this right, and if so, why two syntax for the same thing?

As far as practical uses, it looks to me like the following:

• You describe a model in which you wrap your data in whatever container you design and provide functions (like bind and map) to be able to chain container to container operations (like Result<int, _> -> Result<int, _>), or non container to containers operations (like int -> Result<int, _>), etc. Is that correct?
• Then you build, within that context, an expression that uses that model in order to build an operation chain. Is this a correct assumption, or am I missing the big picture?

I am routinely using Result, Option, etc but I'm trying to get a good sense of the underlying mechanism.

As experiment, I took this from the web:

type ResultBuilder () =
    member this.Bind(x, f) =
        match x with
        | Ok x    -> f x
        | Error e -> Error e
    member this.Return     x = Ok x
    member this.ReturnFrom x = x

without truly understanding how Return / ReturnFrom are used, and successfully used it that way:

ResultBuilder() {
    let! r1 = checkForEmptyGrid gridManager
    let! r2 = checkValidation r1
    let! r3 = checkMargin instrument marginAllowed lastTrade r2
    return r3
}

and it definitely allowed to skip the hierarchical result match chain I would have needed otherwise.

But, yesterday I posted a kind of unrelated question: trying to extend the result type.. unsuccesfully, in F#

and user @Guran pointed out that Result.map could achieve the same thing.

so, I went to https://blog.jonathanchannon.com/2020-06-28-understanding-fsharp-map-and-bind/, took the code and made a Jupyter notebook out of it in order to play with it.

I came to understand that Map will take a non wrapped (inside Result) function and put the result in the wrapped/Result format and Bind will attach/bind functions which are already inside the Result model.

But somehow, despite the two links at the top going through the topic in depth, I don't seem to see the big picture, nor be able to visualize the different operations to wrap / unwrap operations, and their results in a custom model.

Answer 1

Ok, let's try this one more time. What could go wrong? :-)

---

Programming is more or less about capturing patterns. Well, at least the fun parts of it anyway. Look at the GoF "design patterns" for example. Yeah, I know, bad example :-/

Monad is a name given to this one particular pattern. This pattern became so incredibly useful that monads kind of gained a divine quality and everybody is in awe of them now. But really, it's just a pattern.

To see the pattern, let's take your example:

• checkForEmptyGrid
• checkValidation
• checkMargin

First, every one of those functions may fail. To express that we make them return a Result<r, err> that can be either success or failure. So far so good. Now let's try to write the program:

let checkStuff gridManager instrument marginAllowed lastTrade =
    let r1 = checkForEmptyGrid gridManager
    match r1 with
    | Error err -> Error err
    | Ok r -> 
        let r2 = checkValidation r
        match r2 with
        | Error err -> Error err
        | Ok r ->
            let r3 = checkMargin instrument marginAllowed lastTrade r
            match r3 with
            | Error err -> Error err
            | Ok r -> Ok r

See the pattern yet? See those three nearly identical nested blocks in there? At every step we do more or less the same thing: we're looking at the previous result, if it's an error, return that, and if not, we call the next function.

So let's try to extract that pattern for reuse. After all, that's what we do as programmers, isn't it?

let callNext result nextFunc =
    match result with
    | Error err -> Error err
    | Ok r -> nextFunc r

Simple, right? Now we can rewrite the original code using this new function:

let checkStuff gridManager instrument marginAllowed lastTrade =
    callNext (checkForEmptyGrid gridManager) (fun r1 ->
        callNext (checkValidation r1) (fun r2 ->
            callNext (checkMargin instrument marginAllowed lastTrade r2) (fun r3 ->
                Ok r3
            )
        )
    )

Oh, nice! How much shorter that is! The reason it's shorter is that our code now never deals with the Error case. That job was outsourced to callNext.

Now let's make it a bit prettier. First, if we flip callNext's parameters, we can use piping:

let callNext nextFunc result =
    ...

let checkStuff gridManager instrument marginAllowed lastTrade =
    checkForEmptyGrid gridManager |> callNext (fun r1 ->
        checkValidation r1 |> callNext (fun r2 ->
            checkMargin instrument marginAllowed lastTrade r2 |> callNext (fun r3 ->
                Ok r3
            )
        )
    )

A bit fewer parens, but still a bit ugly. What if we made callNext an operator? Let's see if we can gain something:

let (>>=) result nextFunc =
    ...

let checkStuff gridManager instrument marginAllowed lastTrade =
    checkForEmptyGrid gridManager >>= fun r1 ->
        checkValidation r1 >>= fun r2 ->
            checkMargin instrument marginAllowed lastTrade r2 >>= fun r3 ->
                Ok r3

Oh nice! Now all the functions don't have to be in their very own parentheses - that's because operator syntax allows it.

But wait, we can do even better! Shift all the indentation to the left:

let checkStuff gridManager instrument marginAllowed lastTrade =
    checkForEmptyGrid gridManager >>= fun r1 ->
    checkValidation r1 >>= fun r2 ->
    checkMargin instrument marginAllowed lastTrade r2 >>= fun r3 ->
    Ok r3

Look: now it almost looks like we're "assigning" result of every call to a "variable", isn't that nice?

And there you go. You can just stop now and enjoy the >>= operator (which is called "bind" by the way ;-)

That's monad for you.

---

But wait! We're programmers, aren't we? Generalize all the things!

The code above works with Result<_,_>, but actually, Result itself is (almost) nowhere to be seen in the code. It might just as well be working with Option. Look!

let (>>=) opt f =
    match opt with
    | Some x -> f x
    | None -> None

let checkStuff gridManager instrument marginAllowed lastTrade =
    checkForEmptyGrid gridManager >>= fun r1 ->
    checkValidation r1 >>= fun r2 ->
    checkMargin instrument marginAllowed lastTrade r2 >>= fun r3 ->
    Some r3

Can you spot the difference in checkStuff? The difference is just the little Some at the very end, which replaced the Ok that was there before. That's it!

But that's not all. This could also work with other things, besides Result and Option. You know JavaScript Promises? Those work too!

let checkStuff gridManager instrument marginAllowed lastTrade =
    checkForEmptyGrid gridManager >>= fun r1 ->
    checkValidation r1 >>= fun r2 ->
    checkMargin instrument marginAllowed lastTrade r2 >>= fun r3 ->
    new Promise(r3)

See the difference? It's at the very end again.

So it turns out, after you stare at this for a while, that this pattern of "gluing next function to the previous result" extends to a lot of things that are useful. Except this one little inconvenience: at the very end we have to use different methods of constructing the "ultimate return value" - Ok for Result, Some for Option, and whatever black magic Promises actually use, I don't remember.

But we can generalize that too! Why? Because it also has a pattern: it's a function that takes a value and returns the "wrapper" (Result, Option, Promise, or whatever) with that value inside:

let mkValue v = Ok v  // For Result
let mkValue v = Some v  // For Option
let mkValue v = new Promise(v)  // For Promise

So really, in order to make our function-chaining code to work in different contexts, all we need to do is provide suitable definitions of >>= (usually called "bind") and mkValue (usually called "return", or in more modern Haskell - "pure", for complicated maths reasons).

And that's what a monad is: it's an implementation of those two things for a specific context. Why? In order to write down chaining computations in this convenient form rather than as a Ladder of Doom at the very top of this answer.

---

But wait, we're not done yet!

So useful monads turned out to be that functional languages decided it would be super nice to actually provide special syntax for them. The syntax is not magic, it just desugars to some bind and return calls in the end, but it makes the program look just a bit nicer.

The cleanest (in my opinion) job of this is done in Haskell (and its friend PureScript). It's called the "do notation", and here's how the code above would look in it:

checkStuff gridManager instrument marginAllowed lastTrade = do
    r1 <- checkForEmptyGrid gridManager
    r2 <- checkValidation r1
    r3 <- checkMargin instrument marginAllowed lastTrade r2
    return r3

The difference is that calls to >>= are "flipped" from right to left and use the special keyword <- (yes, that's a keyword, not an operator). Looks clean, doesn't it?

But F# doesn't use that style, it has its own. Partly this is due to the lack of type classes (so you have to provide a specific computation builder every time), and partly, I think, it's just trying to maintain the general aesthetic of the language. I'm not an F# designer, so I can't speak to the reasons exactly, but whatever they are, the equivalent syntax would be this:

let checkStuff gridManager instrument marginAllowed lastTrade = result {
    let! r1 = checkForEmptyGrid gridManager
    let! r2 = checkValidation r1
    let! r3 = checkMargin instrument marginAllowed lastTrade r2
    return r3
}

And the desugaring process is also a bit more involved than just inserting calls to >>=. Instead, every let! is replaced by a call to result.Bind and every return - by result.Return. And if you look at the implementations of those methods (you quoted them in your question), you'll see that they match exactly my implementations in this answer.

The difference is that Bind and Return are not in the operator form and they're methods on ResultBuilder, not standalone functions. This is required in F# because it doesn't have a general global overloading mechanism (such as type classes in Haskell). But otherwise the idea is the same.

Also, F# computation expressions are actually trying to be more than just an implementation of monads. They also have all this other stuff - for, yield, join, where, and you can even add your own keywords (with some limitations), etc. I'm not completely convinced this was the best design choice, but hey! They work very well, so who am I to complain?

---

And finally, on the subject of map. Map can be seen as just a special case of bind. You can implement it like this:

let map fn result = result >>= \r -> mkValue (fn r)

But usually map is seen as its own thing, not as bind's little brother. Why? Because it's actually applicable to more things than bind. Things that cannot be monads can still have map. I'm not going to expand on this here, it's a discussion for a whole other post. Just wanted to quickly mention it.