F Sharp Programming/Computation Expressions
F# : Computation Expressions 
Computation expressions are easily the most difficult, yet most powerful language constructs to understand in F#.
Monad Primer
[edit  edit source]Computation expressions are inspired by Haskell monads, which in turn are inspired by the mathematical concept of monads in category theory. To avoid all of the abstract technical and mathematical theory underlying monads, a "monad" is, in very simple terms, a scary sounding word which means execute this function and pass its return value to this other function.
 Note: The designers of F# use the term "computation expression" and "workflow" because it's less obscure and daunting than the word "monad", and because monad and computation expression, while similar, are not precisely the same thing. The author of this book prefers "monad" to emphasize the parallel between the F# and Haskell (and, strictly as an aside, it's just a neat sounding fivedollar word).
Monads in Haskell
Haskell is interesting because it's a functional programming language where all statements are executed lazily, meaning Haskell doesn’t compute values until they are actually needed. While this gives Haskell some unique features such as the capacity to define "infinite" data structures, it also makes it hard to reason about the execution of programs since you can't guarantee that lines of code will be executed in any particular order (if at all).
Consequently, it's quite a challenge to do things which need to be executed in a sequence, which includes any form of I/O, acquiring locks objects in multithreaded code, reading/writing to sockets, and any conceivable action which has a sideeffect on any memory elsewhere in our application. Haskell manages sequential operations using something called a monad, which can be used to simulate state in an immutable environment.
Visualizing Monads with F#
To visualize monads, let's take some everyday F# code written in imperative style:
let read_line() = System.Console.ReadLine()
let print_string(s) = printf "%s" s
print_string "What's your name? "
let name = read_line()
print_string ("Hello, " + name)
We can rewrite the read_line
and print_string
functions to take an extra parameter, namely a function to execute once our computation completes. We’d end up with something that looks more like this:
let read_line(f) = f(System.Console.ReadLine())
let print_string(s, f) = f(printf "%s" s)
print_string("What's your name? ", fun () >
read_line(fun name >
print_string("Hello, " + name, fun () > () ) ) )
If you can understand this much, then you can understand any monad.
Of course, it is perfectly reasonable to say what masochistic reason would anyone have for writing code like that? All it does it print out "Hello, Steve" to the console! After all, C#, Java, C++, or other languages we know and love execute code in exactly the order specified—in other words, monads solve a problem in Haskell which simply doesn't exist in imperative languages. Consequently, the monad design pattern is virtually unknown in imperative languages.
However, monads are occasionally useful for modeling computations which are difficult to capture in an imperative style.
The Maybe Monad
A wellknown monad, the Maybe monad, represents a shortcircuited computation which should "bail out" if any part of the computation fails. Using a simple example, let’s say we wanted to write a function which asks the user for 3 integer inputs between 0 and 100 (inclusive)  if at any point, the user enters an input which is nonnumeric or falls out of our range, the entire computation should be aborted. Traditionally, we might represent this kind of program using the following:
let addThreeNumbers() =
let getNum msg =
printf "%s" msg
// NOTE: return values from .Net methods that accept 'out' parameters are exposed to F# as tuples.
match System.Int32.TryParse(System.Console.ReadLine()) with
 (true, n) when n >= 0 && n <= 100 > Some(n)
 _ > None
match getNum "#1: " with
 Some(x) >
match getNum "#2: " with
 Some(y) >
match getNum "#3: " with
 Some(z) > Some(x + y + z)
 None > None
 None > None
 None > None
 Note: Admittedly, the simplicity of this program  grabbing a few integers  is ridiculous, and there are many more concise ways to write this code by grabbing all of the values up front. However, it might help to imagine that
getNum
was a relatively expensive operation (maybe it executes a query against a database, sends and receives data over a network, initializes a complex data structure), and the most efficient way to write this program requires us to bail out as soon as we encounter the first invalid value.
This code is very ugly and redundant. However, we can simplify this code by converting it to monadic style:
let addThreeNumbers() =
let bind(input, rest) =
match System.Int32.TryParse(input()) with
 (true, n) when n >= 0 && n <= 100 > rest(n)
 _ > None
let createMsg msg = fun () > printf "%s" msg; System.Console.ReadLine()
bind(createMsg "#1: ", fun x >
bind(createMsg "#2: ", fun y >
bind(createMsg "#3: ", fun z > Some(x + y + z) ) ) )
The magic is in the bind
method. We extract the return value from our function input
and pass it (or bind it) as the first parameter to rest
.
Why use monads?
The code above is still quite extravagant and verbose for practical use, however monads are especially useful for modeling calculations which are difficult to capture sequentially. Multithreaded code, for example, is notoriously resistant to efforts to write in an imperative style; however it becomes remarkably concise and easy to write in monadic style. Let's modify our bind method above as follows:
open System.Threading
let bind(input, rest) =
ThreadPool.QueueUserWorkItem(new WaitCallback( fun _ > rest(input()) )) > ignore
Now our bind method will execute a function in its own thread. Using monads, we can write multithreaded code in a safe, imperative style. Here's an example in fsi demonstrating this technique:
> open System.Threading
open System.Text.RegularExpressions
let bind(input, rest) =
ThreadPool.QueueUserWorkItem(new WaitCallback( fun _ > rest(input()) )) > ignore
let downloadAsync (url : string) =
let printMsg msg = printfn "ThreadID = %i, Url = %s, %s" (Thread.CurrentThread.ManagedThreadId) url msg
bind( (fun () > printMsg "Creating webclient..."; new System.Net.WebClient()), fun webclient >
bind( (fun () > printMsg "Downloading url..."; webclient.DownloadString(url)), fun html >
bind( (fun () > printMsg "Extracting urls..."; Regex.Matches(html, @"http://\S+") ), fun matches >
printMsg ("Found " + matches.Count.ToString() + " links")
)
)
)
["http://www.google.com/"; "http://microsoft.com/"; "http://www.wordpress.com/"; "http://www.peta.org"] > Seq.iter downloadAsync;;
val bind : (unit > 'a) * ('a > unit) > unit
val downloadAsync : string > unit
>
ThreadID = 5, Url = http://www.google.com/, Creating webclient...
ThreadID = 11, Url = http://microsoft.com/, Creating webclient...
ThreadID = 5, Url = http://www.peta.org, Creating webclient...
ThreadID = 11, Url = http://www.wordpress.com/, Creating webclient...
ThreadID = 5, Url = http://microsoft.com/, Downloading url...
ThreadID = 11, Url = http://www.google.com/, Downloading url...
ThreadID = 11, Url = http://www.peta.org, Downloading url...
ThreadID = 13, Url = http://www.wordpress.com/, Downloading url...
ThreadID = 11, Url = http://www.google.com/, Extracting urls...
ThreadID = 11, Url = http://www.google.com/, Found 21 links
ThreadID = 11, Url = http://www.peta.org, Extracting urls...
ThreadID = 11, Url = http://www.peta.org, Found 111 links
ThreadID = 5, Url = http://microsoft.com/, Extracting urls...
ThreadID = 5, Url = http://microsoft.com/, Found 1 links
ThreadID = 13, Url = http://www.wordpress.com/, Extracting urls...
ThreadID = 13, Url = http://www.wordpress.com/, Found 132 links
Its interesting to notice that Google starts downloading on thread 5 and finishes on thread 11. Additionally, thread 11 is shared between Microsoft, Peta, and Google at some point. Each time we call bind
, we pull a thread out of .NET's threadpool, when the function returns the thread is released back to the threadpool where another thread might pick it up again—its wholly possible for async functions to hop between any number of threads throughout their lifetime.
This technique is so powerful that it's baked into F# library in the form of the async workflow.
Defining Computation Expressions
[edit  edit source]Computation expressions are fundamentally the same concept as seen above, although they hide the complexity of monadic syntax behind a thick layer of syntactic sugar. A monad is a special kind of class which must have the following methods: Bind
, Delay
, and Return
.
We can rewrite our Maybe monad described earlier as follows:
type MaybeBuilder() =
member this.Bind(x, f) =
match x with
 Some(x) when x >= 0 && x <= 100 > f(x)
 _ > None
member this.Delay(f) = f()
member this.Return(x) = Some x
We can test this class in fsi:
> type MaybeBuilder() =
member this.Bind(x, f) =
printfn "this.Bind: %A" x
match x with
 Some(x) when x >= 0 && x <= 100 > f(x)
 _ > None
member this.Delay(f) = f()
member this.Return(x) = Some x
let maybe = MaybeBuilder();;
type MaybeBuilder =
class
new : unit > MaybeBuilder
member Bind : x:int option * f:(int > 'a0 option) > 'a0 option
member Delay : f:(unit > 'a0) > 'a0
member Return : x:'a0 > 'a0 option
end
val maybe : MaybeBuilder
> maybe.Delay(fun () >
let x = 12
maybe.Bind(Some 11, fun y >
maybe.Bind(Some 30, fun z >
maybe.Return(x + y + z)
)
)
);;
this.Bind: Some 11
this.Bind: Some 30
val it : int option = Some 53
> maybe.Delay(fun () >
let x = 12
maybe.Bind(Some 50, fun y >
maybe.Bind(Some 30, fun z >
maybe.Return(x + y + z)
)
)
);;
this.Bind: Some 50
val it : int option = None
Syntax Sugar
[edit  edit source]Monads are powerful, but beyond two or three variables, the number of nested functions becomes cumbersome to work with. F# provides syntactic sugar which allows us to write the same code in a more readable fashion. Workflows are evaluated using the form builder { compexpr }
. For example, the following pieces of code are equivalent:
Sugared syntax  Desugared syntax 

let maybe = new MaybeBuilder()
let sugared =
maybe {
let x = 12
let! y = Some 11
let! z = Some 30
return x + y + z
}

let maybe = new MaybeBuilder()
let desugared =
maybe.Delay(fun () >
let x = 12
maybe.Bind(Some 11, fun y >
maybe.Bind(Some 30, fun z >
maybe.Return(x + y + z)
)
)
)

 Note: You probably noticed that the sugared syntax is strikingly similar to the syntax used to declare sequence expressions,
seq { expr }
. This is not a coincidence. In the F# library, sequences are defined as computation expressions and used as such. The async workflow is another computation expression you'll encounter while learning F#.
The sugared form reads like normal F#. The code let x = 12
behaves as expected, but what is let!
doing? Notice that we say let! y = Some 11
, but the value y
has the type int option
rather than int
. The construct let! y = ...
invokes a function called maybe.Bind(x, f)
, where the value y
is bound to parameter passed into the f
function.
Similarly, return ...
invokes a function called maybe.Return(x)
. Several new keywords desugar to some other construct, including ones you've already seen in sequence expressions like yield
and yield!
, as well as new ones like use
and use!
.
This fsi sample shows how easy it is to use our maybe monad with computation expression syntax:
> type MaybeBuilder() =
member this.Bind(x, f) =
printfn "this.Bind: %A" x
match x with
 Some(x) when x >= 0 && x <= 100 > f(x)
 _ > None
member this.Delay(f) = f()
member this.Return(x) = Some x
let maybe = MaybeBuilder();;
type MaybeBuilder =
class
new : unit > MaybeBuilder
member Bind : x:int option * f:(int > 'a0 option) > 'a0 option
member Delay : f:(unit > 'a0) > 'a0
member Return : x:'a0 > 'a0 option
end
val maybe : MaybeBuilder
> maybe {
let x = 12
let! y = Some 11
let! z = Some 30
return x + y + z
};;
this.Bind: Some 11
this.Bind: Some 30
val it : int option = Some 53
> maybe {
let x = 12
let! y = Some 50
let! z = Some 30
return x + y + z
};;
this.Bind: Some 50
val it : int option = None
This code does the same thing as the desugared code, only its much much easier to read.
Dissecting Syntax Sugar
[edit  edit source]According the F# spec, workflows may be defined with the following members:
Member  Description 

member Bind : M<'a> * ('a > M<'b>) > M<'b>

Required member. Used to desugar let! and do! within computation expressions.

member Return : 'a > M<'a>

Required member. Used to desugar return within computation expressions.

member Delay : (unit > M<'a>) > M<'a>

Required member. Used to ensure side effects within a computation expression are performed when expected. 
member Yield : 'a > M<'a>

Optional member. Used to desugar yield within computation expressions.

member For : seq<'a> * ('a > M<'b>) > M<'b>

Optional member. Used to desugar for ... do ... within computation expressions. M<'b> can optionally be M<unit>

member While : (unit > bool) * M<'a> > M<'a>

Optional member. Used to desugar while ... do ... within computation expressions. M<'b> can optionally be M<unit>

member Using : 'a * ('a > M<'b>) > M<'b> when 'a :> IDisposable

Optional member. Used to desugar use bindings within computation expressions.

member Combine : M<'a> > M<'a> > M<'a>

Optional member. Used to desugar sequencing within computation expressions. The first M<'a> can optionally be M<unit>

member Zero : unit > M<'a>

Optional member. Used to desugar empty else branches of if/then within computation expressions.

member TryWith : M<'a> > M<'a> > M<'a>

Optional member. Used to desugar empty try/with bindings within computation expressions.

member TryFinally : M<'a> > M<'a> > M<'a>

Optional member. Used to desugar try/finally bindings within computation expressions.

These sugared constructs are desugared as follows:
Construct  Desugared Form 

let pat = expr in cexpr

let pat = expr in cexpr

let! pat = expr in cexpr

b.Bind(expr, (fun pat > cexpr))

return expr

b.Return(expr)

return! expr

b.ReturnFrom(expr)

yield expr

b.Yield(expr)

yield! expr

b.YieldFrom(expr)

use pat = expr in cexpr

b.Using(expr, (fun pat > cexpr))

use! pat = expr in cexpr

b.Bind(expr, (fun x > b.Using(x, fun pat > cexpr))

do! expr in cexpr

b.Bind(expr, (fun () > cexpr))

for pat in expr do cexpr

b.For(expr, (fun pat > cexpr))

while expr do cexpr

b.While((fun () > expr), b.Delay( fun () > cexpr))

if expr then cexpr1 else cexpr2

if expr then cexpr1 else cexpr2

if expr then cexpr

if expr then cexpr else b.Zero()

cexpr1

b.Combine(cexpr1, b.Delay(fun () > cexpr2))

try cexpr with patn > cexprn

b.TryWith(expr, fun v > match v with (patn:ext) > cexprn  _ raise exn)

try cexpr finally expr

b.TryFinally(cexpr, (fun () > expr))

What are Computation Expressions Used For?
[edit  edit source]F# encourages a programming style called language oriented programming to solve problems. In contrast to general purpose programming style, language oriented programming centers around the programmers identifying problems they want to solve, then writing domain specific minilanguages to tackle the problem, and finally solve problem in the new minilanguage.
Computation expressions are one of several tools F# programmers have at their disposal for designing minilanguages.
Its surprising how often computation expressions and monadlike constructs occur in practice. For example, the Haskell User Group has a collection of common and uncommon monads, including those which compute distributions of integers and parse text. Another significant example, an F# implementation of software transactional memory, is introduced on hubFS.
Additional Resources
[edit  edit source] Haskell.org: All About Monads  Another collection of monads in Haskell.