In this article, we discuss how to use F# computation expressions to provide syntax for monadic computations. We start by defining a simple computation using bind and return and then add the support for sequencing and additional control flow constructs. We show code for two examples - one demonstrating monadic container and the other demonstrating monadic computations. The difference is that monadic computation can capture (untracked) F# effects in the type `M<'T>` while monadic containers can not (because they represent fully evaluated values).

We use the Maybe monad (represented as `option<'T>`) as an example of monadic container and the Reader monad (represented as `'TState -> 'T`) as an example of monadic computation. The following snippet shows standard definitions of bind and return for these types (we use the name `unit` for return, because `return` is a reserved keyword):

```module Maybe =
/// The unit function of the Maybe monad
let unit value = Some(value)
/// The bind operation of the Maybe monad
let bind f = function
| None -> None
| Some(value) -> f value

/// Represents a computation that depends on 'TState
type Reader<'TState, 'T> = R of ('TState -> 'T)

let unit value = R (fun _ -> value)
let bind f (R comp1) = R (fun state ->
let (R comp2) = f (comp1 state)
comp2 state)```

### Computation builder definitions

Now that we have the bind and return operations, we can define two F# computation builders for writing monadic computations. The following snippet starts by defining just binding and return (which allows the `let!` and the `return` constructs). We also define `ReturnFrom` member to allow the `return!` keyword:

```/// Computation builder for the Maybe monad
type MaybeBuilder() =
member x.Bind(v, f) = Maybe.bind f v
member x.Return(v) = Maybe.unit v
member x.ReturnFrom(m) = m

member x.Bind(v, f) = Reader.bind f v
member x.ReturnFrom(m) = m

/// Objects representing computaiton builder instances
let maybe = MaybeBuilder()

The definitions above allows us to write a number of basic monadic computations. The following snippet demonstrates the syntax using the Maybe monad:

```/// Random number generator
let random = System.Random()

/// Either fails or returns some unit
let maybeFail() =
maybe { if random.Next(2) = 0 then
return ()
else
return! None }

/// Computation that either fails or returns a random number
let maybeDice() =
maybe { do! maybeFail()
return random.Next(6) }

/// Computation that adds two dices (fails in 3/4 of cases)
let maybeTwice =
maybe { let! n1 = maybeDice()
let! n2 = maybeDice()
return n1 + n2 }```

The `maybeFail` computation uses `return ()` to successfully return the unit value and `return! None` to fail. In the first case, the argument is a value that will be wrapped in the monadic type `option<unit>`, while in the second case, the argument is the computation to return - `None` is of type `Maybe<unit>`. The code samples are translated to the following code:

```let maybeFail() =
if random.Next(2) = 0 then maybe.Return( () )
else maybe.ReturnFrom(None)

let maybeDice() =
maybe.Bind(maybeFail(), fun () ->
maybe.Return(6))

let maybeTwice =
maybe.Bind(maybeDice(), fun n1 ->
maybe.Bind(maybeDice(), fun n2 ->
maybe.Return(n1 + n2)))```

As discussed in the paper, the well-known monad laws can be expressed in the computation expression syntax. The examples are very similar to the code that can be written using the `do` notation in Haskell. Assuming `m` is some computation builder that supports `Bind` and `Return`, we can write:

```/// The left identity monad law
let leftIdentity x f =
let m1 = m { let! v = m { return x }
return! f v }
let m2 = m { return! f x }
m1 |> shouldEqual m2

/// The right identity monad law
let rightIdentity n =
let m1 = m { let! x = n
return x }
let m2 = m { return! n }
m1 |> shouldEqual m2

let associativity n f g =
let m1 = m { let! y = m { let! x = n
return! f x }
return! g y }
let m2 = m { let! x = n
return! m { let! y = f x
return! g x } }
let m3 = m { let! x = n
let! y = f x
return! g x }
m1 |> shouldEqual m2
m1 |> shouldEqual m3```

As discussed in the paper, sequencing of effectfull monadic computation is done by adding members `Delay`, `Zero`, `Run` and, most importantly, `Combine`. There are two possible definitions, depending on whether the computation type `M<'T>` can accomodate untracked F# effects (in other words, whether the occurrence of `'T` is in a result of some function type. We refer to types that can accomodate effects monadic computations and types that cannot monadic containers.

The Reader monad is an example of monadic computation, because it is represented as a function `'TState -> 'T`. For such monads, the computation builders that allow sequencing can be defined as follows (place the mouse pointer over a member name to see the type):

```// Extend the ReaderBuilder with additional members
/// Creates a monadic unit computation
member m.Zero() =
m.Return( () )
/// Wraps the effects in the computation type
member m.Delay(f) =
m.Bind(m.Zero(), fun _ -> f())
/// Compose effectful and another computation
member m.Combine(m1, m2) =
m.Bind(m1, fun () -> m2)
/// Return a computation without affecting it
/// (Run is not used in this case and can be omitted)
member m.Run(m1) = m1```

All members are defined in terms of the existing. The `Combine` member is implemented by `Bind` with the restriction that the first computation must return `unit` (This is similar to the difference between function composition and sequencing using the semicolon operator.) The `Delay` member is implemented by taking an empty computation (`Zero`) and binding.

The above definitions enable a number of constructs (refer to the F# specification for full details). The most notable ones are `if` without the `else` branch (where `Zero` is used instead of the `else` branch). The `if` can also be followed by other computations (in which case, `Combine` is used to combine them). The following example defines two of helpers and then demonstrates a computation that requires the above members:

```/// Reads the state from the Reader monad
let runReader state m = (...)

/// Prints given message and optionally also the state
let printLog detailed message =
printfn "State: %s" state
printfn "Message: %s" message }

// Select & run to execute the sample
printLog true "Testing #1" |> runReader "State #1"
printLog false "Testing #2" |> runReader "State #2"```

The `printLog` function first prints the state (if `detailed = true`) and then prints the given message. It is translated to the following expression:

```let printLog detailed message =
( ( if detailed then
printfn "State: %s" state
printfn "Message: %s" message

The Maybe monad is an example of the second case - monadic container. For such monads, the `Bind` operation performs all effects immediately and so it is not possible to implement `Delay` that would return `M<'T>` computation without evaluating the function given as an argument. For this reason, we use a different type (called `D<'T>` in the paper) to represent a delayed monadic computation. For monadic containers, `D<'T> = unit -> M<'T>`. The computation builder can be defined as follows:

```// Extend the MaybeBuilder with additional members
type MaybeBuilder with
/// Creates a monadic unit computation
member m.Zero() =
m.Return( () )
/// Return the function as a delayed computation type
member m.Delay(f) = f
/// Compose computation and a delayed computation
member m.Combine(m1, d2) =
m.Bind(m1, fun () -> d2 ())
/// Run the effects of a delayed computation
member m.Run(d1) = d1()```

Note that the Maybe monad is perhaps not the best example of monadic computation, because it also provides monoidal structure (with `None` as the zero and left-biased choice as the binary operator). This means that there are two ways to implement the computation builder - one that uses the monadic structure (above) and another that would use the monoidal structure (using `None` for `Zero` and a different `Combine`). The second approach is very similar to imperative computation builder described elsewhere.

Using the monadic implementation of Maybe, we can write the following code.

```// Generates a number, but may fail if 'canFail' is true
let maybeNumber canFail =
maybe { if canFail then
do! maybeFail ()
return random.Next(6) }```

If the parameter `canFail` is true, then the computation uses `maybeFail` to fail with a 50% chance. Otherwise, it always succeeds, returning a random number from 0 to 5. The structure of the computation is very similar to the previous Reader monad example and so is the translation:

```let maybeNumber canFail =
maybe.Run(maybe.Delay(fun () ->
maybe.Combine
( ( if canFail then
maybe.Bind(maybeFail(), fun () ->
maybe.Zero())
else maybe.Zero() ),
( maybe.Delay(fun () ->
maybe.Return(random.Next(6)) )) )))```

The final addition that can be made to a monadic computation expression builder is the support for F# control flow constructs that are available in the computation block. These include two looping constructs (`for` and `while`) and also exception handling constructs (`try .. with` and `try .. finally`). The definition differs slightly for monadic computations and monadic containers. In particular, the `While` member and the exception handling constructs take one of the arguments as a delayed computation, which is either `M<'T>` or `unit -> M<'T>`.

The `ReaderBuilder` (a monadic computation) can be extended as follows:

```type ReaderBuilder with
/// The exception handling needs to be lifted into the monadic
/// computation type, so we need to use the computation structure
try body state
with e ->
let (Reader.R handlerBody) = handler e
handlerBody state)

/// The finalizer is defined similarly (but the body of the
/// finalizer cannot be monadic - just a `unit -> unit` function
try body state
finally finalizer() )

/// Similar to 'Bind', but it disposes of the resource (a way to do
/// deterministic finalization in .NET) after it gets out of scope
member m.Using(res, f) =
m.Bind(res, fun disposableRes ->
m.TryFinally(m.Delay(fun () -> f disposableRes), fun () ->
(disposableRes :> System.IDisposable).Dispose() ))

/// The 'while' loop evaluates the condition and then either ends
/// (returning 'Zero'), or evaluates body once and then runs recursively
member m.While(cond, body) =
if not (cond()) then m.Zero()
else m.Combine(m.Run(body), m.Delay(fun () -> m.While(cond, body)))

/// The 'for' loop can be defined using 'While' and 'Using'
member m.For(xs:seq<'T>, f) =
m.Using(m.Return(xs.GetEnumerator()), fun en ->
m.While( (fun () -> en.MoveNext()), m.Delay(fun () ->
f en.Current) ) )```

For monadic computations that encapsulate untracked F# effects, the members `TryWith` and `TryFinally` cannot be implemented in terms of other operations. They need to understand the structure of the computation, in order to wrap the appropriate call that actually runs the effects with `try .. with` or `try .. finally`. For the Reader monad, this is quite easy. We just need to wrap the call that runs the underlying function when the initial state is provided. However, it requires more structure than just monadic bind and return.

The `Using` member is not discussed in the paper (see F# specification for details), but we include it for completeness. It has the same type signature as `Bind`, except that the value produced by the first computation implements the `IDisposable` interface. The member guarantees that it will deterministically free the resource after it gets out of scope, whic can be implemented using `TryFinally`. The member enables the `use! x = foo` syntax in the computation builder.

Finally, the `For` and `While` members can be implemented in terms of the other operations. In general, the `for` loop iterates over an F# sequence, which is an imperative object that needs to be disposed of at the end. This can be done using the `Using` member.

The definitions for the Maybe monad are similar, but the exception handling members are implemented differently. In case of monadic containers that use `unit -> M<'T>` to represent delayed computation, we do not need to know anything about the `M<'T>` type:

```type MaybeBuilder with
/// The exception handling uses the delayed type directly
member m.TryWith(f, handler) =
try f()
with e -> handler e

/// The finalizer is defined similarly (but the body of the
/// finalizer cannot be monadic - just a `unit -> unit` function)
member m.TryFinally(f, finalizer) =
try f()
finally finalizer()

(Other members are the same as for computations)```

As an example, consider the following two examples. The first one implements safe modulo (division remainder) using the Maybe monad. The second tests whether a given number is divisible by all specified numbers and fails if that is not the case (otherwise it succeeds, returning `Some()`).

```/// Safe modulo using the Maybe monad
let safeMod a b =
maybe { try
return a % b
with _ ->
return! None }

/// Fail if the number is divisible by any divisor
let failDivisible num divisors =
maybe { for divisor in divisors do
let! res = safeMod num divisor
if res = 0 then return! None }

// Test whether 43 is a prime number
failDivisible 43 [ 2 .. 7 ]
// ... but fail when the input contains 0
failDivisible 43 [ 0 .. 7 ]```

The two functions defined above are transalted using the new computation builder members as follows (we omit the wrapping of the entire computation in `Run` and `Delay`, because it has no effect in this example and it makes the translation harder to follow):

```let safeMod a b =
maybe.TryWith
( maybe.Delay(fun () -> maybe.Return(a % b)),
fun _ -> maybe.ReturnFrom(None) )

let failDivisible num divisors =
maybe.For(divisors, fun divisor ->
maybe.Bind(safeMod num divisor, fun res ->
if res = 0 then maybe.ReturnFrom(None)
else maybe.Zero() ))```
Multiple items
val unit : 'a -> 'a option

The unit function of the Maybe monad

--------------------
type unit = Unit

Full name: Microsoft.FSharp.Core.unit
type: unit
val value : 'a
union case Option.Some: 'T -> Option<'T>
val bind : ('a -> 'b option) -> 'a option -> 'b option

The bind operation of the Maybe monad
val f : ('a -> 'b option)
union case Option.None: Option<'T>
type Reader<'TState,'T> = | R of ('TState -> 'T)

Represents a computation that depends on 'TState
Multiple items
val unit : 'a -> Reader<'b,'a>

--------------------
type unit = Unit

Full name: Microsoft.FSharp.Core.unit
type: unit

val f : ('a -> Reader<'b,'c>)
val comp1 : ('b -> 'a)
val state : 'b
val comp2 : ('b -> 'c)
type MaybeBuilder =
class
new : unit -> MaybeBuilder
member Bind : v:'c option * f:('c -> 'd option) -> 'd option
member Combine : m1:unit option * d2:(unit -> 'b option) -> 'b option
member Delay : f:'c -> 'c
member For : xs:seq<'T> * f:('T -> unit option) -> unit option
member Return : v:'b -> 'b option
member ReturnFrom : m:'a -> 'a
member Run : d1:(unit -> 'a) -> 'a
member TryFinally : f:(unit -> 'a) * finalizer:(unit -> unit) -> 'a
member TryWith : f:(unit -> 'a) * handler:(exn -> 'a) -> 'a
member Using : res:'a option * f:('a -> 'b option) -> 'b option (requires 'a :> System.IDisposable)
member While : cond:(unit -> bool) * body:(unit -> unit option) -> unit option
member Zero : unit -> unit option
end

Computation builder for the Maybe monad
val x : MaybeBuilder
member MaybeBuilder.Bind : v:'c option * f:('c -> 'd option) -> 'd option

val v : 'c option
type: 'c option
val f : ('c -> 'd option)
module Maybe

member MaybeBuilder.Return : v:'b -> 'b option

val v : 'b
val unit : 'a -> 'a option

The unit function of the Maybe monad
member MaybeBuilder.ReturnFrom : m:'a -> 'a

val m : 'a
class
member ReturnFrom : m:'a -> 'a
member Run : m1:'a -> 'a
end

member ReaderBuilder.ReturnFrom : m:'a -> 'a

val maybe : MaybeBuilder

Objects representing computaiton builder instances

val random : System.Random

Random number generator
namespace System
type Random =
class
new : unit -> System.Random
new : int -> System.Random
member Next : unit -> int
member Next : int -> int
member Next : int * int -> int
member NextBytes : System.Byte [] -> unit
member NextDouble : unit -> float
end

Full name: System.Random
val maybeFail : unit -> unit option

Either fails or returns some unit
System.Random.Next() : int
System.Random.Next(maxValue: int) : int
System.Random.Next(minValue: int, maxValue: int) : int
val maybeDice : unit -> int option

Computation that either fails or returns a random number
val maybeTwice : int option

type: int option

Computation that adds two dices (fails in 3/4 of cases)
val n1 : int
type: int
inherits: System.ValueType
val n2 : int
type: int
inherits: System.ValueType
val maybeFail : unit -> unit option

member MaybeBuilder.Return : v:'b -> 'b option
member MaybeBuilder.ReturnFrom : m:'a -> 'a
val maybeDice : unit -> int option

member MaybeBuilder.Bind : v:'c option * f:('c -> 'd option) -> 'd option
val maybeTwice : int option

type: int option
type M<'T> = | M of 'T

type: M<'a>
union case M.M: 'T -> M<'T>
type MBuilder =
class
new : unit -> MBuilder
member Bind : m:M<'T> * f:('T -> M<'R>) -> M<'R>
member Return : v:'T -> M<'T>
member ReturnFrom : m:M<'T> -> M<'T>
end

val x : MBuilder
member MBuilder.Bind : m:M<'T> * f:('T -> M<'R>) -> M<'R>

val m : M<'T>
type: M<'T>
val f : ('T -> M<'R>)
val failwith : string -> 'T

Full name: Microsoft.FSharp.Core.Operators.failwith
member MBuilder.Return : v:'T -> M<'T>

val v : 'T
member MBuilder.ReturnFrom : m:M<'T> -> M<'T>

val m : MBuilder

val shouldEqual : 'a -> 'a -> unit (requires equality)

val a : 'a (requires equality)
val b : 'a (requires equality)
val not : bool -> bool

Full name: Microsoft.FSharp.Core.Operators.not
val leftIdentity : 'a -> ('a -> M<'b>) -> unit (requires equality)

val x : 'a
val f : ('a -> M<'b>) (requires equality)
val m1 : M<'b> (requires equality)
type: M<'b>
val v : 'a
val m2 : M<'b> (requires equality)
type: M<'b>
val rightIdentity : M<'a> -> unit (requires equality)

val n : M<'a> (requires equality)
type: M<'a>
val m1 : M<'a> (requires equality)
type: M<'a>
val x : 'a (requires equality)
val m2 : M<'a> (requires equality)
type: M<'a>
val associativity : M<'a> -> ('a -> M<'a>) -> ('a -> M<'b>) -> unit (requires equality)

val n : M<'a>
type: M<'a>
val f : ('a -> M<'a>)
val g : ('a -> M<'b>) (requires equality)
val y : 'a
val m3 : M<'b> (requires equality)
type: M<'b>

Wraps the effects in the computation type

Compose effectful and another computation
member ReaderBuilder.Run : m1:'a -> 'a

Return a computation without affecting it
(Run is not used in this case and can be omitted)
val m1 : 'a

val state : 'a
let (Reader.R f) = m in f state

Prints given message and optionally also the state
val detailed : bool
type: bool
inherits: System.ValueType
val message : string
type: string
val state : string
type: string
val printfn : Printf.TextWriterFormat<'T> -> 'T

Full name: Microsoft.FSharp.Core.ExtraTopLevelOperators.printfn

member ReaderBuilder.Run : m1:'a -> 'a

Return a computation without affecting it
(Run is not used in this case and can be omitted)

Wraps the effects in the computation type

Compose effectful and another computation
val m : MaybeBuilder
member MaybeBuilder.Zero : unit -> unit option

member MaybeBuilder.Delay : f:'c -> 'c

Return the function as a delayed computation type
val f : 'c
member MaybeBuilder.Combine : m1:unit option * d2:(unit -> 'b option) -> 'b option

Compose computation and a delayed computation
val m1 : unit option
type: unit option
val d2 : (unit -> 'b option)
member MaybeBuilder.Run : d1:(unit -> 'a) -> 'a

Run the effects of a delayed computation
val d1 : (unit -> 'a)
val maybeNumber : bool -> int option

val canFail : bool
type: bool
inherits: System.ValueType
val maybeNumber : bool -> int option

member MaybeBuilder.Run : d1:(unit -> 'a) -> 'a

Run the effects of a delayed computation
member MaybeBuilder.Delay : f:'c -> 'c

Return the function as a delayed computation type
member MaybeBuilder.Combine : m1:unit option * d2:(unit -> 'b option) -> 'b option

Compose computation and a delayed computation
member MaybeBuilder.Zero : unit -> unit option

The exception handling needs to be lifted into the monadic
computation type, so we need to use the computation structure
val body : ('a -> 'b)
Multiple items
val e : exn
type: exn

--------------------
val e : exn
type: exn
val handlerBody : ('a -> 'b)
val e : exn
type: exn

The finalizer is defined similarly (but the body of the
finalizer cannot be monadic - just a `unit -> unit` function
val finalizer : (unit -> unit)

Similar to 'Bind', but it disposes of the resource (a way to do
deterministic finalization in .NET) after it gets out of scope
val disposableRes : #System.IDisposable
type: #System.IDisposable

The finalizer is defined similarly (but the body of the
finalizer cannot be monadic - just a `unit -> unit` function
Multiple items
type IDisposable =
interface
member Dispose : unit -> unit
end

Full name: System.IDisposable

--------------------
System.IDisposable

The 'while' loop evaluates the condition and then either ends
(returning 'Zero'), or evaluates body once and then runs recursively
val cond : (unit -> bool)

The 'while' loop evaluates the condition and then either ends
(returning 'Zero'), or evaluates body once and then runs recursively

The 'for' loop can be defined using 'While' and 'Using'
val xs : seq<'T>
type: seq<'T>
inherits: System.Collections.IEnumerable
Multiple items
val seq : seq<'T> -> seq<'T>

Full name: Microsoft.FSharp.Core.Operators.seq

--------------------
type seq<'T> = System.Collections.Generic.IEnumerable<'T>

Full name: Microsoft.FSharp.Collections.seq<_>
type: seq<'T>
inherits: System.Collections.IEnumerable

Similar to 'Bind', but it disposes of the resource (a way to do
deterministic finalization in .NET) after it gets out of scope
System.Collections.Generic.IEnumerable.GetEnumerator() : System.Collections.Generic.IEnumerator<'T>
val en : System.Collections.Generic.IEnumerator<'T>
type: System.Collections.Generic.IEnumerator<'T>
inherits: System.IDisposable
inherits: System.Collections.IEnumerator
System.Collections.IEnumerator.MoveNext() : bool
property System.Collections.Generic.IEnumerator.Current: 'T
member MaybeBuilder.TryWith : f:(unit -> 'a) * handler:(exn -> 'a) -> 'a

The exception handling uses the delayed type directly
val f : (unit -> 'a)
val handler : (exn -> 'a)
member MaybeBuilder.TryFinally : f:(unit -> 'a) * finalizer:(unit -> unit) -> 'a

The finalizer is defined similarly (but the body of the
finalizer cannot be monadic - just a `unit -> unit` function)
/// Similar to 'Bind', but it disposes of the resource (a way to do
/// deterministic finalization in .NET) after it gets out of scope
member m.Using(res, f) =
m.Bind(res, fun disposableRes ->
m.TryFinally(m.Delay(fun () -> f disposableRes), fun () ->
(disposableRes :> System.IDisposable).Dispose() ))

/// The 'while' loop evaluates the condition and then either ends
/// (returning 'Zero'), or evaluates body once and then runs recursively
member m.While(cond, body) =
if not (cond()) then m.Zero()
else m.Combine(m.Run(body), m.Delay(fun () -> m.While(cond, body)))

/// The 'for' loop can be defined using 'While' and 'Using'
member m.For(xs:seq<'T>, f) =
m.Using(m.Return(xs.GetEnumerator()), fun en ->
m.While( (fun () -> en.MoveNext()), m.Delay(fun () ->
f en.Current) ) )
val safeMod : int -> int -> int option

Safe modulo using the Maybe monad
val a : int
type: int
inherits: System.ValueType
val b : int
type: int
inherits: System.ValueType
val failDivisible : int -> seq<int> -> unit option

Fail if the number is divisible by any divisor
val num : int
type: int
inherits: System.ValueType
val divisors : seq<int>
type: seq<int>
inherits: System.Collections.IEnumerable
val divisor : int
type: int
inherits: System.ValueType
val res : int
type: int
inherits: System.ValueType
val safeMod : int -> int -> int option