« F# computation expressions for beginners, part 1: what’s the problem? | Main | Decommoditise me, baby »

December 13, 2010

F# computation expressions for beginners, part 2: keeping it simple

When I started trying to get my head around F# computation expressions, I went looking for nice simple, basic examples.  Unfortunately, even the simplest examples I could find were rather intimidating.  Here’s my attempt to strip it back to the very basics.

Use case

The example I’m going to use is based on the null-safe member example from the previous instalment.  However, F# tends to eschew both nulls and members in favour of options and functions, so instead of dealing with members that might be null, I’m going to deal with functions that return options.

So my computation expression will work just like normal F# control flow, except that if a function call returns None instead of Some, I’ll treat that as a failure and bail out on the rest of the expression.

Here’s an example of the kind of function I want to be able to use:

let tryDecr x n = 
  if x > n then Some (x - n) else None

And here’s an example of how I want to be able to use it:

let maybeDecr x = maybe {
   
let!
y = tryDecr x 10
   
let!
z = tryDecr y 30
   
let!
t = tryDecr z 50
   
return t
  }

The idea is that if the first tryDecr call fails, the maybe block will stop it going on to the second tryDecr, and so on.  I don’t need to clutter the code up with explicit if expressions or pattern matching: the computation expression will magically abort out of the block (and return None) the first time any function returns None.

let! – all the letting, but with more excitement

Notice that inside the maybe block I’m using let! for assignment instead of the normal let.  This is how my computation expression gets to interfere in the control flow.  The normal let doesn’t give the custom flow logic a chance to get involved.  Inside a computation expression, I have to use let! instead when I want my custom logic to run.  That is, code inside a computation expression block still has to opt into whatever weird behaviour the computation expression defines.

Once we’ve seen how to build a computation expression, it will be clear that there are other reasons we need to keep the standard assignment behaviour around.  I’ll try to come back to this.

A workflow builder for maybe

What is the custom flow logic for maybe expressions?  Informally it looks like this:

If the expression at hand returns None, then the value of the whole computation expression will be None; don’t bother evaluating the rest of the expressions.

If the expression at hand returns Some a, then carry out the rest of the computation expression on the value a.


(That “on the value a” bit in the second paragraph is deliberately nebulous for now.)

We need to tighten up this informal specification into code, but before we can do that we need to know where that code is going to sit.  The answer is in a builder class. The methods you implement on the class depend on what constructs you need in your computation expressions.  For overriding control flow in a let!, we need to implement a method on the builder class called Bind.

The signature of Bind is defined by F# in terms of the kind of data we want to be able to use in let! expressions.  Basically it takes a value representing the result of the expression at hand – the right hand side of the let! – and a function representing the rest of the computation expression, and it has to return a value representing the result of the computation expression as a whole.

Implementing the custom flow logic for maybe

In the maybe example, the right hand side of the let! has to evaluate to an option value.  And the rest of the computation expression is going to operate on the content of that option value, if it has any.  And the result of the maybe block as a whole must be an option, because we have to be able to return None if any of the contained expressions evaluate to None.

So our Bind method has to take an option value and a function from non-option to option, and return an option:

Bind : 'a option -> ('a -> 'b option) -> 'b option

With F# forcing this signature on us, and our informal specification at hand, writing the implementation becomes almost trivial:

type MaybeBuilder() =
  member this.Bind(p, rest) = match p with
                              | None ->
None
                              | Some a
-> rest a

What is this saying?

If p is None, then Bind doesn’t evaluate the rest function, and returns None.

If p is Some a, then Bind returns the rest function applied to a.


But when F# calls Bind, p is the result of the expression at hand – the right hand side of the let! – and rest is a function comprising the rest of the computation expression, and whatever Bind returns becomes the result of the computation expression as a whole.  Calling rest on a is exactly “carrying out the rest of the computation expression on a.”  So this seems like a pretty exact translation of our informal specification.

Getting a value out of a maybe block

So now we can write a sequence of let! operations, and our Bind implementation will take care of conditionally running the rest of the computation.  But eventually that ‘rest’ is going to have to come up with a value.

Here’s the ‘how to use it’ sample again:

let maybeDecr x = maybe {
   
let!
y = tryDecr x 10
   
let!
z = tryDecr y 30
   
let!
t = tryDecr z 50
   
return t
  }

Obviously, we need to implement the return keyword.  To do this, we need to add another method to our builder class, the Return method.

What does Return look like?  Well, at some point we know that Return is going to be the ‘rest of the computation.’  That means it’s got to be compatible with the rest argument to Bind.  Which means Return has to be a function from non-option to option.  If the computation got as far as Return, then it means Bind didn’t abort the computation early, which means the computation was successful and we want to get the value out.  How do we get a value in an option?  Using Some, of course!

So Return pretty much writes itself:

type MaybeBuilder() =
 
member
this.Return(x) = Some x

A builder object

It turns out that Bind and Return are all we need for a simple conditional chaining strategy.  So all we need to do now is define that ‘maybe’ we’ve been blithely flinging around and hook it up to our builder class.

This turns out to be deceptively easy: just declare maybe to be an instance of the builder class!

let maybe = new MaybeBuilder()

‘maybe’ isn’t a keyword: it’s just a variable.

Putting it all together

Here’s our conditional flow engine in full:

type MaybeBuilder() =
 
member
this.Return(x) = Some x
 
member this.Bind(p, rest) = match p with
                              | None ->
None
                              | Some a
->
rest a

let maybe = new MaybeBuilder()

I’ll add a bit of logging to the tryDecr method so we can see how often it gets called, then use it in a maybe block:

let tryDecr x n = 
  printfn
"Conditionally decrementing %A by %A"
x n
 
if x > n then Some (x - n) else
None

let
maybeDecr x = maybe {
   
let!
y = tryDecr x 10
   
let!
z = tryDecr y 30
   
let!
t = tryDecr z 50
   
return t
  }

And let’s see what happens:

> maybeDecr 100;;
Conditionally decrementing 100 by 10
Conditionally decrementing 90 by 30
Conditionally decrementing 60 by 50
val it : int option = Some 10
> maybeDecr 30;;
Conditionally decrementing 30 by 10
Conditionally decrementing 20 by 30
val it : int option = None
> maybeDecr 5;;
Conditionally decrementing 5 by 10
val it : int option = None

In the first test, tryDecr has been successful each time, so normal control flow has been sustained, and maybeDecr has produced the correct result.

In the second and third tests, tryDecr has failed on the second and first attempt respectively (calculating z and y respectively).  But instead of going on to attempt the remaining calculations, the maybe block has returned None immediately – without us having to write explicit code to check for failure.  The block allows us to write top-to-bottom code and let the ‘maybe’ object take care of the more complex flow that is actually required.

Conclusion

The maybe block is about as simple as a computation expression can get.  I’ve tried to strip it back to the absolute basics, so that it’s simple enough for me to get my head around.  Nevertheless, it’s not a toy (although I have illustrated it with a toy example): it does real work which could be used to simplify real code.

With this basic example at hand, we have a foundation for building more sophisticated and useful workflows, and for exploring what’s actually going on when F# encounters a computation expression.

December 13, 2010 in Software | Permalink

TrackBack

TrackBack URL for this entry:
https://www.typepad.com/services/trackback/6a00d8341c5c9b53ef0148c6a6c6b7970c

Listed below are links to weblogs that reference F# computation expressions for beginners, part 2: keeping it simple:

Comments

Thanks for the detailed post. F# always amazes me. Can this only be used with let!?

Posted by: jason at Dec 13, 2010 1:38:31 PM

Computation expressions allow you to override a variety of things, depending on what methods you implement in your builder class. What I've shown so far with Bind is limited to let! (and do!). But by implementing other builder methods you can also override the flow of for and while loops, try and use blocks and the yield! and return! keywords. There is also an intriguing description of a builder method which is "called for sequencing." Unfortunately, I haven't yet figured out how or when to implement all (or even most!) of these methods -- part of the point of writing this is to build up my own understanding, so hopefully I will get to them soon! Inthe meantime, http://msdn.microsoft.com/en-us/library/dd233182.aspx has a list of keywords that have special meaning in computation expressions and what you have to implement to override them.

Posted by: Ivan at Dec 13, 2010 1:57:02 PM

Thanks,
I've been trying to understand this for some time. Your explanation is first class !

Posted by: Anon at Jan 7, 2011 9:59:53 AM