WTF is... a Computation Expression?

WTF is... a Computation Expression?

...and why should I care?

Every time computation expressions in F# are discussed it's only a matter of time before the dreaded M-word is mentioned. So let's get it out of the way early....

Monad

Right, that's that done and let's not mention it again. Suffice to say, a computation expression is an interesting concept with no direct equivalent in C# and no necromancy is required to use or make them.

If you've done any async work in F# or anything involving sequences then odds are you've already used a computation expression (CE).

let mySequence =
    seq {
        "First Item"
        "Second Item"
    }
    
let myAsyncThing =
    async {
        let! result = DoTheAsyncThing
        return result
    }

The F# compiler has no built-in tricks or optimisations for these, they're just plain computation expressions, just like you can write too!

Every computation expression needs a backing builder class, usually named after the computation, so async would have a builder of type AsyncBuilder. All it has to do to be used as a CE is implement certain methods, which map to particular keywords inside a CE.


Method Typical signature(s) Description
Bind M<'T> * ('T -> M<'U>) -> M<'U> Called for let! and do! in computation expressions.
Delay (unit -> M<'T>) -> M<'T> Wraps a computation expression as a function.
Return 'T -> M<'T> Called for return in computation expressions.
ReturnFrom M<'T> -> M<'T> Called for return! in computation expressions.
Run M<'T> -> M<'T> or M<'T> -> 'T Executes a computation expression.
Combine M<'T> * M<'T> -> M<'T> or M<unit> * M<'T> -> M<'T> Called for sequencing in computation expressions.
For seq<'T> * ('T -> M<'U>) -> M<'U> or seq<'T> * ('T -> M<'U>) -> seq<M<'U>> Called for for...do expressions in computation expressions.
TryFinally M<'T> * (unit -> unit) -> M<'T> Called for try...finally expressions in computation expressions.
TryWith M<'T> * (exn -> M<'T>) -> M<'T> Called for try...with expressions in computation expressions.
Using 'T * ('T -> M<'U>) -> M<'U> when 'T :> IDisposable Called for use bindings in computation expressions.
While (unit -> bool) * M<'T> -> M<'T> Called for while...do expressions in computation expressions.
Yield 'T -> M<'T> Called for yield expressions in computation expressions.
YieldFrom M<'T> -> M<'T> Called for yield! expressions in computation expressions.
Zero unit -> M<'T> Called for empty else branches of if...then expressions in computation expressions.
Quote Quotations.Expr<'T> -> Quotations.Expr<'T> Indicates that the computation expression is passed to the Run member as a quotation. It translates all instances of a computation into a quotation.

Now that all looks complicated so let's take a quick look at what advantages a CE gives us over writing plain code.

Let's consider an example where we need to pass an item through several validation checks

let itemToValidate = SomeThingThatNeedsValidating()

// Each validation methhod has signature Item -> Result<Item, Error>

let firstValidation = firstValidationCheck itemToValidate

let secondValidation =
    match firstValidation with
    | Error e -> e
    | Ok item -> secondValidationCheck item

let thirdValidation =
    match secondValidation with
    | Error e -> e
    | Ok item -> thirdValidationCheck item

You probably look at that and think there must be a better way to write that. And you'd be right, this is a great example where we can use a computation expression.

To build it, let's look at the Result type and see if it has anything that can help us.

There is already a Result.bind that does the same as the match statements above, so let's use that instead of reinventing the wheel.

type ResultBuilder() =

    // This can be used in a CE via the let! keyword
    // Result<'a,'b> * ('a -> Result<'c,'d>) -> Result<'c,'d>
    member __.Bind(r, f) = Result.bind f r
    
    // This can be used in a CE via the return keyword
    // 'a -> Result<'a, 'b>
    member __.Return(x) = Ok x
    
// This exposes the builder type as a computation expression
// It's what allows to use it like below...
let result = ResultBuilder()

Short, sharp and to the point, right? But now we can express the validation checks above like this...

let itemToValidate = SomeThingThatNeedsValidating()

let validatedItem =
    result { // result here is the created instance of ResultBuilder from above
        let! firstCheck = firstValidationCheck itemToValidate
        let! secondCheck = secondValidationCheck firstCheck
        let! thirdCheck = thirdValidationCheck secondCheck
        return thirdCheck
    }

The beauty of this approach is that the let! keyword will only bind the successful validation and allow the CE to continue evaluating. If an error is returned from any of the validation checks then the entire CE will short circuit and return that error immediately.

Congratulations, you now have a basic working CE of your very own! But a lot of that code looks like we shouldn't need it. Why assign each intermediate result to a variable along the way, surely we should just be able to pipe each step in to the next, right?

Let's  add two further items to where we create our ResultBuilder

// F# allows us to define our own operators
// By convention, >>= usually refers to a bind method
let (>>=) result binder = Result.bind binder result

type ResultBuilder() =

    // This can be used in a CE via the let! keyword
    // Result<'a,'b> * ('a -> Result<'c,'d>) -> Result<'c,'d>
    member __.Bind(r, f) = Result.bind f r
    
    // This can be used in a CE via the return keyword
    // 'a -> Result<'a, 'b>
    member __.Return(x) = Ok x
    
    // This can be used in a CE via the return! keyword
    // Result<'a, 'b> -> Result<'a, 'b>
    member __.ReturnFrom x = x
    
let result = ResultBuilder()

Now we can chain together our validation checks and it becomes a lot easier to be able to add new checks, compose smaller ones together, or reorder them without having to rename every variable along the way.

let itemToValidate = SomeThingThatNeedsValidating()

let validatedItem =
    result {
        return!
            firstValidationCheck itemToValidate
            >>= secondValidationCheck
            >>= thirdValidationCheck
    }

Now if we found we needed an extra check that should be between secondValidationCheck and thirdValidationCheck, it is as simple as adding it in.

Hopefully this has helped to show you the power of a computation expression and that they aren't as scary as they first seemed. Of course this was a relatively simple example but from here you can see how they can be extended with additional functionality and even custom keywords that can be used to create miniature programming languages to solve problems. More to come on that front....