Saturday, December 24, 2016

Understanding Monads in F#

Note feedback is welcome. Thank you for reading!

 

1 What is a Monad?

 

In F#, monads are called computation expressions because the authors of F# believed the term "monad" might intimidate people.[1] This article uses "monad" to refer to the class that defines the behavior of a monad, and "computation expression" to refer to code that is run using a monad. For more about why monads are called computation expressions in F#, see Why Do This?

 

1.1 Enriched Types

 

To understand monads, we must first understand enriched types. An enriched type is a simple type plus metadata. An example of a simple type is float. Some examples of enriched types are:

 

Enriched Type

Description

Option<float>

Might or might not contain a value. Similar in concept to System.Nullable<T>, though it does not actually use that type.

Array<float>

A mutable collection of values.

Seq<float>

An immutable collection of lazily evaluated values.

List<float>

An immutable collection of values.

List<List<float>>

A list of lists.

Async<float>

An asynchronous computation that, when run, eventually returns a value.

 

1.2 Option<'a>

 

The Option<'a>[2] type is typically used for the result of a computation that might succeed or fail. For example, consider the function:

 

Listing 1.2.1

let divide_10_by (x : float) : float = 10.0 / x

 

When x is 0, divide_10_by raises a System.DivideByZeroException. The code that applies[3] divide_10_by must handle this exception. It would be better to encode this information in the function's return type.

 

Listing 1.2.2

let divide_10_by (x : float) : Option<float> =

    if x = 0.0 then None

    else Some (10.0 / x)

 

The type system now requires the code that applies divide_10_by to unpack the result to see whether it is Some or None:

 

Listing 1.2.3

match divide_10_by 2.0 with

| Some x -> do printfn "%.2f" x

| None -> do printfn "None"

// Output: 5.00

 

1.3 Composition

 

We can compose multiple applications of the version of divide_10_by that returns a float:

 

Listing 1.3.1

let result = 2.0 |> divide_10_by |> divide_10_by |> divide_10_by

// result = 5.0

 

But we cannot do this with the version of divide_10_by that returns an Option<float>. Instead, we must unpack the result of each application of divide_10_by before we apply divide_10_by to the result.

 

Listing 1.3.2

let input = 2.0

let result =

    match divide_10_by input with

    | None -> None

    | Some x ->

        match divide_10_by x with

        | None -> None

        | Some y ->

            match divide_10_by y with

            | None -> None

            | Some z -> Some z

// result = Some 5.0

 

Note the way this code marches to the right of the screen. This is typical of code that you can improve with a monad.

 

With a Maybe monad, we can rewrite the code in Listing 1.3.2 as follows:

 

Listing 1.3.3

let input = 2.0

let (result : Option<float>) = MaybeMonad () {

    let! x = divide_10_by input

    let! y = divide_10_by x

    let! z = divide_10_by y

    return z

}

// result = Some 5.0

 

This isn't as clean as using the forward composition (|>) operator, but it abstracts away the unpacking of the result of each application of divide_10_by. Don't worry if this code doesn't make sense yet - we'll see how it works shortly.

 

1.4 M, Return, and Bind

 

We'll start with three basic monadic functions.[4]

 

1.      The type constructor, M, promotes a type to a more enriched type. For example, the Option<'a> type constructor promotes the type int to Option<int>. It promotes the type Option<int> to Option<Option<int>>.

2.      Return promotes a type value to a more enriched type value. For the Option<'a> type, the Return operation is Some. It promotes the int value 3 to Some 3. It promotes the Option<int> value Some 3 to Some (Some 3).

3.      Bind unpacks a type value from an enriched type value, and binds a name to it. We will look more closely at Bind soon.

 

Note Return is referred to as "Unit" outside F#. However, F# already has a type named Unit. Also, as we will see, in F# Return is not the same as in a C-derived or other imperative language.

 

Note the terms "simple" and "enriched", as applied to types and type values, are not fully accurate, because you can nest enriched types. For example, for the Maybe monad, the result of Return (Return (3)) is Some (Some 3). So we could use the terms "inner" and "outer" instead. However, I find "simple" and "enriched" conceptually easier to deal with, especially since we will not be dealing with many examples of nested enriched types in this article.

 

2 Monad Implementation, Part 1

 

2.1 Return

 

In F#, you define a monad as a class with the appropriate methods, depending on what functionality you want. A basic definition of the Maybe monad is as follows.

 

Listing 2.1.1

type MaybeMonad () =

    member this.Return (x : 'a) : Option<'a> = Some x

 

For the Maybe monad, the signature of Return is 'a -> Option<'a>. For any monad, not just the Maybe monad, the signature of Return is 'a -> M<'a>.

 

When trying to understand a given monad, the first question to ask is: what enriched type is the monad based on? The Maybe monad is based on the enriched type Option<'a>.

 

With a monad that defines the Return method, you can then write a computation expression as follows.

 

Listing 2.1.2

let (result : Option<int>) = MaybeMonad () {

    return 3

}

// result = Some 3

 

The computation expression is enclosed by curly braces.

 

The return keyword is syntactic sugar for the Return method of the monad class. The return keyword in F# is not the same as in a C-derived or other imperative language.

 

You use the return keyword and the corresponding Return method to return the result of the computation expression. In Listing 2.1.2, the result of the computation expression is Some 3.

 

In Listing 2.1.2, we annotate the type of result as a reminder that a Maybe monad computation expression evaluates to an Option<'a>. Using type annotations in F# code is usually not required, but it cuts down on both compiler and runtime errors.

 

2.2 The return Keyword in F#

 

In F#, you cannot return a result in the middle of a function body.

 

Listing 2.2.1

let get_result () : int =

    let x = 1

    x

    2

    3

let result = get_result ()

// result = 3   

 

If you run the code in Listing 2.2.1, the return value of the get_result function is 3. The attempts to return x and 2 are ignored.

 

Listing 2.2.2

let get_result () : unit =

    let x = 1

    x

    2

    3

    do printfn "Done."

// result = unit

 

If you run the code in Listing 2.2.2, the return value of the get_result function is unit, because that is the value of the statement do printfn "Done."

 

You also cannot return a result in the middle of a computation expression, except in certain circumstances.

 

Listing 2.2.3

let (result : Option<int>) = MaybeMonad () {

    return 3

    do printfn "This is wrong."

}

 

If you run the code in Listing 2.2.3, the F# compiler raises the following error.[5]

 

error FS0708: This control construct may only be used if the computation expression builder defines a 'Combine' method

 

This further distinguishes the return keyword in F# from the versions in other languages.

 

2.3 ReturnFrom

 

As we saw in Listing 2.1.1, Return expects a simple type value. What if you want to apply Return to an enriched type value? Consider the following code.

 

Listing 2.3.1

type MaybeMonad () =

    member this.Return (x : 'a) : Option<'a> = Some x

 

let (result : Option<Option<int>>) = MaybeMonad () {

    return (Some 3)

}

// result = Some (Some 3)

 

The result of applying Return to Some 3 is Some (Some 3), but the result we want is Some 3. To resolve this, we must define the ReturnFrom method.

 

Listing 2.3.2

type MaybeMonad () =

    member this.Return (x : 'a) : Option<'a> = Some x

    member this.ReturnFrom (x : Option<'a>) : Option<'a> = x

 

For the Maybe monad, the signature of ReturnFrom is Option<'a> -> Option<'a>. For any monad, not just the Maybe monad, the signature of ReturnFrom is M<'a> -> M<'a>.

 

Whereas the return keyword is syntactic sugar for the Return method of the monad class, the return! keyword is syntactic sugar for the ReturnFrom method. We can now write the following code.

 

Listing 2.3.3

let (result : Option<int>) = MaybeMonad () {

    return! (Some 3)

}

// result = Some 3

 

2.4 Bind

 

Bind needs more explanation. Recall an enriched type is a simple type plus metadata. We can't really do anything with an enriched type value directly - we have to extract the simple type value inside. Consider the following code.

 

Listing 2.4.1

let x = Some 3

do printfn "%d" x

 

The code in Listing 2.4.1 won't work because the second line can't determine whether x is Some or None. Instead, we must do the following.

 

Listing 2.4.2

let x = Some 3

do printfn

    match x with

    | Some y -> "%d" y

    | None -> "None"

 

Extracting the simple type from the enriched type requires us to process the enhanced type metadata. For type Option<'a>, the metadata is whether the value is Some or None. To process this metadata, we use the match control construct.

 

Here is the Maybe monad with Bind defined. We'll look more closely at this in a moment.

 

Listing 2.4.3

type MaybeMonad () =

    member this.Return (x : 'a) : Option<'a> = Some x

    member this.Bind (result : Option<'a>, rest : 'a -> Option<'b>) : Option<'b> =

        match result with

        | Some x -> rest x

        | None -> None

 

You can now write a computation expression that uses let!. let! is syntactic sugar for the Bind method of the monad class.

 

Listing 2.4.4

let (result : Option<int>) = MaybeMonad () {

    let! x = Some 3

    return x

}

// result = Some 3

 

Think of this line:

 

let! x = Some 3

 

as saying: Bind the name x, in the scope of the computation expression, to the simple type value contained in the enriched type value Some 3.

 

Alternately, think of let! as seeing the computation expression as follows.

 

{

    let! (value name) = (result argument to Bind)

    (rest argument to Bind)

}

 

Strictly speaking, result and rest are not parameters to Bind. As you can see from Listing 2.4.3, Bind has one parameter, a tuple, which has two parts. The parts are typically named result and rest, respectively. If you define Bind with two parameters instead of one, the F# compiler raises errors; for more information see Bind Signature. However, for simplicity, this article refers to result and rest as parameters (when talking about the definition of Bind) or arguments (when talking about applying Bind).

 

Note Bind does not see the value name specified by let!. Bind only determines the value to which that name is bound.

 

The job of Bind is to:

1. Extract the simple type value from the result argument, which is an enriched type value.

2. Apply the rest argument, which is a function that represents the rest of the computation expression, to the simple type value.

 

That is, think of the rest argument to Bind as follows.

 

fun x -> m {

    // The rest of the computation expression, now with x defined

}

 

Consider the following computation expression.

 

Listing 2.4.5

MaybeMonad () {

    let! x = Some 3

    let! y = Some (x + 1)

    let! z = Some (y + 2)

    return z

}

 

Here is what the computation expression in Listing 2.4.5 looks like with let! de-sugared to Bind and return de-sugared to Return.

 

Listing 2.4.6

Bind (Some 3, fun x ->

    Bind (Some (x + 1), fun y ->

        Bind (Some (y + 2), fun z ->

            Return z)))

 

Here is a table that shows result and rest as each let! expression is evaluated. The final column shows what rest looks like with let! de-sugared to Bind and return de-sugared to Return.

 

Table 2.4.1

Expression

result

rest

rest (de-sugared)

let! x = Some 3

Some 3

let! y = Some (x + 1)

let! z = Some (y + 2)

return z

fun x ->

    Bind (Some (x + 1), fun y ->

        Bind (Some (y + 2), fun z ->

            Return z))

let! y = Some (x + 1)

Some (x + 1)

let! z = Some (y + 2)

return z

fun y ->

    Bind (Some (y + 2), fun z ->

        Return z)

let! z = Some (y + 2)

Some (y + 2)

return z

fun z ->

    Return z

 

Now let's look at the definition of Bind again.

 

Listing 2.4.7

member this.Bind (result : Option<'a>, rest : 'a -> Option<'b>) : Option<'b> =

    match result with

    | Some x -> rest x

    | None -> None

 

The code in Listing 2.4.7 does the following.

1.      Use the match control construct to extract the simple type value from the enriched type value (result).

a.      If result is Some x, x is the simple type value.

                                                    i.     Apply the rest argument to x (that is, bind, in the scope of the computation expression, the simple type value contained in x).

                                                   ii.     Return the result of applying rest.

b.      If result is None, there is no simple type value.

                                                    i.     Do not evaluate the rest of the computation expression.

                                                   ii.     Return None as the result of evaluating the computation expression.

 

To see why we do not evaluate the rest of the computation expression in case 1b, consider the following code.

 

Listing 2.4.8

let (result : Option<unit>) = MaybeMonad () {

    let! x = None     // No value to bind the name x to

    do printfn "%d" x // Not evaluated

    return x          // Not evaluated

}

// result = None

 

Recall that Bind extracts a simple type value from an enriched type value. If the enriched type value is None, there is no simple type value. In the first line of the computation expression in Listing 2.4.8, there is nothing to bind the name x to. Therefore the remaining lines are not evaluated. If they were evaluated, they would raise errors because x would be undefined.

 

We annotate the type of result as Option<unit>, though we could use any inner type such as int, float, string, and so on. We do this because the return type of Bind, as specified in its signature, is Option<'b>. However, in the computation expression in Listing 2.4.8, Bind returns None, and Return is applied to a value that is undefined. As a result, the F# compiler cannot infer the type of 'b in Option<'b>, so it raises an error. Annotating the type of result helps the F# compiler infer the type of 'b.

 

2.5 Why Do This?

 

Recall the code in Listing 2.4.4.

 

Listing 2.5.1

let (result : Option<int>) = MaybeMonad () {

    let! x = Some 3

    return x

}

// result = Some 3

 

This does the following.

1.      Unpack the simple type value 3 from the enriched type value Some 3.

2.      Bind the name x to the simple type value 3.

3.      Promote the value of x, which is the simple type value 3, to the enriched type value Some 3.

 

At first, this does not seem useful. But let's go back to the divide_10_by function:

 

Listing 2.5.2

let divide_10_by (x : float) : Option<float> =

    if x = 0.0 then None

    else Some (10.0 / x)

 

To compose multiple applications of divide_10_by, we must do the following after each application.

1.      Determine whether the result of divide_10_by is None or Some.

a.      If the result is None, do not evaluate any more applications of divide_10_by. Return None.

b.      If the result is Some x, evaluate the next application of divide_10_by to x.

 

Recall the code in Listing 1.3.2. This is how we compose multiple applications of divide_10_by without the Maybe monad.

 

Listing 2.5.3

let input = 2.0

let result =

    match divide_10_by input with

    | None -> None

    | Some x ->

        match divide_10_by x with

        | None -> None

        | Some y ->

            match divide_10_by y with

            | None -> None

            | Some z -> Some z

// result = Some 5.0

 

Now recall the code in Listing 1.3.3. This is how we compose multiple applications of divide_10_by with the Maybe monad.

 

Listing 2.5.4

let input = 2.0

let (result : Option<float>) = MaybeMonad () {

    let! x = divide_10_by input

    let! y = divide_10_by x

    let! z = divide_10_by y

    return z

}

// result = Some 5.0

 

This does the same thing as the code in Listing 2.5.3, except the boilerplate code to compose multiple applications of divide_10_by is abstracted away by the Maybe monad definition.

 

A monad lets us compose the application of functions that have the signature 'a -> M<'a>, where M<'a> is the enriched type on which the monad is based.[6]

The second question to ask when trying to understand a given monad is: what kind of function does the monad let us compose multiple applications of?
The Maybe monad lets us compose applications of functions with the signature 'a -> Option<'a>.

 

Recall in F# you cannot return a result in the middle of a function body or a computation expression.[7] However, with Bind, we can stop the evaluation of a computation expression before the end. In that case, Bind returns a value that is determined by Bind, rather than by the computation expression.

 

A monad lets us abstract away code that performs or emulate some kind of imperative computation. That is why, in F#, they are called computation expressions.
The third question to ask when trying to understand a given monad is: what kind of imperative computation does the monad abstract away?
The Maybe monad abstracts away the if/else branching needed for a series of expressions that we might want to stop evaluating before the end.

 

2.6 Bind Signature

 

For the Maybe monad, the signature of Bind is as follows.

 

Option<'a> * ('a -> Option<'b>) -> Option<'b>

 

For any monad, not just the Maybe monad, the signature of Bind is as follows.

 

M<'a> * ('a -> M<'b>) -> M<'b>

 

1.      M<'a> is the type of the result parameter.

2.      ('a -> M<'b>) is the type of the rest parameter.

3.      M<'b> is the return type of Bind.

 

Let's look at these in more detail.

 

1. For the result parameter, M<'a> simply means an enriched type, such as Option<'a>, List<'a>, and so on.

 

2. For the rest parameter, 'a is the simple type value we want to bind in the scope of the computation expression. M<'b> means that evaluating the computation expression returns an enriched type. Recall the rest argument represents the rest of the computation expression.

 

Why do rest and Bind return type M<'b> rather than M<'a>? Whereas the rest of the computation expression must return the same enriched type as result, that enriched type can contain a different simple type. For example, the following code is legal.

 

Listing 2.6.1

let (result : Option<string>) = MaybeMonad () {

    let! x = Some 3

    return "Success."

}

// result = Some "Success."

 

In this case, when Bind is applied, the result argument is of type Option<int>, and the rest argument is of type (int -> Option<string>).

 

3. For the return type of Bind, M<'b> means that Bind also returns an enriched type, because it typically returns the result of applying rest.

 

With the Maybe monad, Bind returns either:

1.      None, which is a value of an enriched type (Option<'b>).

2.      The result of evaluating rest, which also returns an enriched type (Option<'b>).

 

Why must a monad evaluate to type M<'b> rather than 'b? Consider the following code.

 

Listing 2.6.2

let input = 2.0

let (result : Option<float>) = MaybeMonad () {

    let! x = divide_10_by input

    let! y = divide_10_by x

    let! z = divide_10_by y

    return z

}

// result = Some 5.0

match result with

| Some x -> do printfn "%.2f" x

| None -> do printfn "None"

// Output: 5.00

 

Why must we extract the simple type value (5.0) from the result of evaluating the monad? Why can the monad not simply evaluate to 5.0?

 

Recall two things:

1.      The signature of divide_10_by is float -> Option<float>, which is a specific instance of 'a -> M<'b>.

2.      Our Maybe monad composes applications of divide_10_by. The end result of such a series therefore must be Option<float>, which is a specific instance of M<'b>.

 

Also recall the definition of Bind.

 

Listing 2.6.3

member this.Bind (result : Option<'a>, rest : 'a -> Option<'b>) : Option<'b> =

    match result with

    | Some x -> rest x

    | None -> None

 

If result is None, then Bind must return None, which has type Option<'b>.

 

Also recall the non-monadic way to compose multiple applications of divide_10_by.

 

Listing 2.6.4

let input = 2.0

let result =

    match divide_10_by input with

    | None -> None

    | Some x ->

        match divide_10_by x with

        | None -> None

        | Some y ->

            match divide_10_by y with

            | None -> None

            | Some z -> Some z    // Must return Some z to match the return type of the other cases

// result = Some 5.0

 

If at some point in the series, we try to apply divide_10_by to the argument 0, the result is None. At that point we must stop evaluating the series and return None. None is itself a simple value (that is, it contains no other information), but it still belongs to the enriched type Option<float>; it does not belong to the simple type float. Therefore, if we evaluate the whole series successfully, we must also return an Option<float>, so the success and failure cases both have the same return type.

 

I think of a computation expression like an operating room. In the OR, you can open a patient up and take the organs out and inspect them, but you must put them back inside the patient before you leave. Likewise, in a computation expression, you can open up an enriched type value and take out the simple type value (by applying Bind), but you must put the simple type value back into an enriched type value (by applying Return) before you exit.

 

Finally, in the documentation about monads in functional languages other than F#, you might see the signature of Bind given as follows.

 

Listing 2.6.5

M<'a> -> ('a -> M<'b>) -> M<'b>

 

In the signature in Listing 2.6.5, the result (M<'a>) and rest ('a -> M<'b>) parameters are separate.

 

In F#, however, Bind has a single parameter, which is a tuple with two parts. If you try to compile the following code:

 

Listing 2.6.6

type MaybeMonad () =

    member this.Return (x : 'a) : Option<'a> = Some x

    member this.Bind (result : Option<'a>) (rest : 'a -> Option<'b>) : Option<'b> =

        match result with

        | Some x -> rest x

        | None -> None

 

let (result : Option<int>) = MaybeMonad () {

    let! x = Some 3    // Error

    return x

}

 

the F# compiler raises the following error.

 

error FS0001: This expression was expected to have type

    Option<'a>   

but here has type

    'b * 'c

 

This is because F# cannot find a definition of Bind with the correct signature in the MaybeMonad class.

 

2.7 do!

 

Suppose you want to compose a series of functions that return success or failure. However, you are not interested in the details of the successes or failures; you only want to stop evaluating the series if one of the functions returns failure. This is sometimes the case with functions that have side effects such as reading input from the user or writing a file to disk.

 

Start with the usual Maybe monad definition.

 

Listing 2.7.1

type MaybeMonad () =

    member this.Return (x : 'a) : Option<'a> = Some x

    member this.Bind (result : Option<'a>, rest : 'a -> Option<'b>) : Option<'b> =

        match result with

        | Some x -> rest x

        | None -> None

 

For this example, we have functions that perform imaginary side-effects that either succeed or fail. We represent success or failure as an Option<unit> because we are not interested in the details of the success or failure. Unit is represented in F# as (). It is analogous to the void type in a C-derived language.

 

Listing 2.7.2

let succeed () = Some ()

let fail () = None

 

We can now write the following code.

 

Listing 2.7.3

let (result : Option<unit>) = MaybeMonad () {

    do! succeed ()

    do! fail ()

    do! succeed ()

    return ()

}

// result = None

 

The do! keyword, like let!, is syntactic sugar for the Bind method of the monad class. If the result argument to Bind is Some, Bind evaluates the rest of the computation expression. If the result argument is None, Bind stops evaluating the computation expression and returns None. But unlike let!, do! does not bind a value name.

 

If you encounter errors using do!, see Appendix A.

 

2.8 What Does ! Mean?

 

Some F# monad keywords end in !; others do not. What's the difference?[8]

 

A monad keyword that does not end in ! is applied to a simple type value.

 

For example, the return keyword is used as follows.

 

Listing 2.8.1

let (result : Option<int>) = MaybeMonad () {

    return 3 // 3 is a simple type value

}

// result = Some 3

 

A monad keyword that ends in ! is either:

1.      Applied to an enriched type value.

2.      Used in an assignment where there is an enriched type value on the right side of the equation.

 

For example, the let!, do!, and return! keywords are used as follows.

 

Listing 2.8.2

let (result : Option<int>) = MaybeMonad () {

    let! x = Some 1 // Some 1 is an enriched type value

    do! Some 2      // Some 2 is an enriched type value

    return! Some 3  // Some 3 is an enriched type value

}

// result = Some 3

 

Note you can use let (without the !) inside or outside a computation expression, but it is not a monadic keyword. Inside a computation expression, you can use let to bind a value name to either a simple or enriched type value, but in neither case will Bind be applied.

 

Listing 2.8.3

let (result : Option<int>) = MaybeMonad () {

    let x = 1      // Does not apply Bind

    let y = Some 2 // Does not apply Bind

    return x

}

// result = Some 1

 

Now that we've covered the key methods (Return and Bind), let's look at some related methods.

 

2.9 Monadic Recursion

 

As we saw in previous sections:

1.      Monadic keywords that end in ! are applied to enriched type values. (See What Does ! Mean?.)

2.      The result of evaluating a computation expression is an enriched type value. (See Bind Signature.)

From these two things, it follows that monadic keywords that end in ! can also be applied to the result of evaluating a computation expression.

 

Here is an example. Start with a definition of the Maybe monad that includes the ReturnFrom method.

 

Listing 2.9.1

type MaybeMonad () =

    member this.Return (x : 'a) : Option<'a> = Some x

    member this.ReturnFrom (x : Option<'a>) : Option<'a> = x

    member this.Bind (result : Option<'a>, rest : 'a -> Option<'b>) : Option<'b> =

        match result with

        | Some x -> rest x

        | None -> None

 

We can now have one computation expression return the result of another.

 

Listing 2.9.2

let m = MaybeMonad ()

 

let (result_1 : Option<int>) = m {

    return 1

}

// result_1 = Some 1

 

let (result_2 : Option<int>) = m {

    return! result_1

}

// result_2 = Some 1

 

In the definition of result_2, we use return! instead of return because we are returning an enriched type value instead of a simple type value.

 

We can also nest computation expressions.

 

Listing 2.9.3

let m = MaybeMonad ()

 

let (result : Option<int>) = m {

    return! m {

        return 1

    }

}

// result = Some 1

 

We can also have a function that returns the result of evaluating a computation expression, and have the computation expression return! the result of the function. In effect, we can have a recursive computation expression.

 

Listing 2.9.4

let m = MaybeMonad ()

 

let rec count (n : int) : Option<int> =

    m {

        if n <= 0 then return 0

        else

            do printf "%d " n

            return! count (n - 1)

    }

let result = count 10

// result = Some 0

 

Running the code in Listing 2.9.4 produces the following output.

 

10 9 8 7 6 5 4 3 2 1

 

This is of course not the simplest or most efficient way to count down from 10. It is meant to show how return! can be applied to a recursive function application.

 

We can also use let! to bind the result of evaluating a computation expression.

 

Listing 2.9.5

let m = MaybeMonad ()

 

let rec sum (n : int) : Option<int> =

    m {

        if n <= 0 then return 0

        else

            let! x = sum (n - 1)

            return n + x

    }

let result = sum 10

// result = Some 55

 

Again, this is not the simplest or most efficient sum function. It is meant to show how let! can be applied to a recursive function application.

 

2.10 Yield and YieldFrom

 

Before continuing, we need to mention two other methods, Yield and YieldFrom.

 

Yield is applied when you use the yield keyword in a computation expression. Its signature is 'a -> M<'a>.

 

YieldFrom is applied when you use the yield! keyword in a computation expression. Its signature is M<'a> -> M<'a>.

 

As you can see, Yield and YieldFrom are similar to Return and ReturnFrom. As far as I can tell, the difference between the two sets of methods is only a matter of convention.

 

·        Return and ReturnFrom are used when a computation expression returns only one result.

·        Yield and YieldFrom are used when a computation expression returns multiple results.

 

F# has a built-in monad called the Sequence monad. Computation expressions written using the Sequence monad typically return multiple results. Accordingly, the Sequence monad allows the yield and yield! keywords, but not the return and return! keywords. If we use return or return! in a Sequence monad, the F# compiler raises one of the following errors.

 

error FS0635: In sequence expressions, results are generated using 'yield'

 

error FS0797: In sequence expressions, multiple results are generated using 'yield!'

 

We can also use the yield and yield! keywords in a list comprehension. For example, consider the following code.

 

Listing 2.10.1

let words = [

    for x in ['a'; 'b'; 'c'] do

        yield x

        yield! ['d']

    ]

do printfn "%A" words

 

Running the code in Listing 2.10.1 produces the following output.

 

['a'; 'd'; 'b'; 'd'; 'c'; 'd']

 

Again, however, if we use the return or return! keyword in a list comprehension, the F# compiler raises one of the following errors.

 

error FS0635: In sequence expressions, results are generated using 'yield'

 

error FS0797: In sequence expressions, multiple results are generated using 'yield!'

 

3 List Monad

 

Whereas the Maybe monad is based on the enriched type Option<'a>, the List monad is based on the enriched type List<'a>.

 

To see how the List monad is useful, consider the following code that uses list comprehension syntax.

 

Listing 3.0.1

let words = [

    for x in ['a'; 'b'; 'c'] do

        for y in ['d'; 'e'; 'f'] do

            for z in ['g'; 'h'; 'i'] do

                yield sprintf "%c%c%c" x y z

    ]

do printfn "%A" words

 

Running the code in Listing 3.0.1 produces the following output.

 

["adg"; "adh"; "adi"; "aeg"; "aeh"; "aei"; "afg"; "afh"; "afi"; "bdg"; "bdh"; "bdi"; "beg"; "beh"; "bei"; "bfg"; "bfh"; "bfi"; "cdg"; "cdh"; "cdi"; "ceg"; "ceh"; "cei"; "cfg"; "cfh"; "cfi"]

 

Of course, this is a trivial example, but the shape of this code should look familiar to anyone who has had to traverse a nested data structure. As with Listing 1.3.2, note the way the code marches to the right of the screen.

 

With the List monad, we can rewrite Listing 3.0.1 as follows.

 

Listing 3.0.2

let (words : List<char>) =

    ListMonad () {

        let! x = ['a'; 'b'; 'c']

        let! y = ['d'; 'e'; 'f']

        let! z = ['g'; 'h'; 'i']

        return sprintf "%c%c%c" x y z

    }

do printfn "%A" words

 

In Listing 3.0.2, the reduction in boilerplate code is not as obvious as it was in Listing 1.3.3. However, in a later section we will see how a variant of the List monad helps us write intuitive solutions to certain problems.

 

Here is a basic definition of the List monad.

 

Listing 3.0.3

type ListMonad () =

    member this.Return (x : 'a) : List<'a> = [x]

    member this.Bind (result : List<'a>, rest : 'a -> List<'b>) : List<'b> =

        List.map rest result |> List.concat

 

Recall that Return promotes a simple type value to an enriched type value. In the case of the List monad, the enriched type is List<'a>.

 

Bind requires more explanation.

 

3.1 Bind

 

Recall the job of Bind is to extract a simple type value from an enriched type value. For the List monad, the enriched type is List<'a>. But how do we extract a simple type value from a list, which might contain more than one simple type value? The answer is as follows.

 

1.      Extract the first simple type value from the list.

2.      Bind a name to the simple type value in the scope of the computation expression.

3.      Evaluate the rest of the computation expression using the simple type value defined in step 2.

4.      Add the result of the computation expression to a result list.

5.      Repeat steps 1 through 4 until there are no more values in the original list.

 

The List monad lets us compose applications of functions with the signature 'a -> List<'a>.

The List monad abstracts away the use of for loops.

 

Consider the following computation expression.

 

Listing 3.1.1

ListMonad () {

    let! x = [1; 2; 3]

    return x * 2

}

 

The computation expression in Listing 3.1.1 evaluates to the following.

 

[2; 4; 6]

 

Based on the steps described previously, we can think of the computation expression in Listing 3.1.1 as equivalent to the following.

 

Listing 3.1.2

List.concat [

    [

        let x = 1

        yield x * 2

    ];

    [

        let x = 2

        yield x * 2

    ];

    [

        let x = 3

        yield x * 2

    ]

]

 

A simpler way to express the code in Listing 3.1.2 is the following.

 

Listing 3.1.3

List.map (fun x -> x * 2) [1; 2; 3]

 

List.map applies a function to each item in a list and returns a list that contains the results. Now consider the definition of Bind in Listing 3.0.3 again.

 

member this.Bind (result : List<'a>, rest : 'a -> List<'b>) : List<'b> =

    List.map rest result |> List.concat

 

Recall we can think of let! as seeing the computation expression as follows.

 

{

    let! (value name) = (result)

    (rest)

}

 

Also recall we can think of the rest argument to Bind as a function.

 

fun x -> m {

    // The rest of the computation expression, now with x defined

}

 

This means we can use List.map to apply the function represented by the rest argument to the list in the result argument.

 

In the case of Listing 3.1.1, when we apply Bind with the let! keyword, the rest argument looks like the following.

 

Listing 3.1.4

fun x -> ListMonad () {

    return x * 2

}

 

The expression in Listing 3.1.4 is equivalent to the following.

 

Listing 3.1.5

fun x -> ListMonad.Return (x * 2)

 

Based on the definition of Bind in Listing 3.0.3, we use List.map to apply the function in Listing 3.1.5 to the result argument, which, based on Listing 3.1.1, is [1; 2; 3].

 

Listing 3.1.6

List.map (fun x -> ListMonad.Return (x * 2)) [1; 2; 3]

 

The expression in Listing 3.1.6 evaluates to the following.

 

[[2]; [4]; [6]]

 

Recall from Listing 3.0.3 that ListMonad.Return promotes values of type 'a to type List<'a>. Also recall from Listing 3.0.3 that Bind then uses List.concat to flatten the list of lists into a single list.

 

[2; 4; 6]

 

Finally, note we can clean up the definition of Bind by using List.collect.

 

member this.Bind (result : List<'a>, rest : 'a -> List<'b>) : List<'b> =

    List.collect rest result

 

List.collect rest result is equivalent to List.map rest result |> List.concat.

 

3.2 Multiple Lists

 

We can also use the List monad with multiple lists. Consider the following computation expression.

 

Listing 3.2.1

ListMonad () {

    let! x = [1; 2]

    let! y = [3; 4]

    let! z = [5; 6]

    return x * y * z

}

 

Bind and Return translate the computation expression in Listing 3.2.1 to the following expression.

 

Listing 3.2.2

[1; 2] |> List.collect (fun x ->

    [3; 4] |> List.collect (fun y ->

        [5; 6] |> List.collect (fun z ->

            [x * y * z])))

 

If we disregard the nesting of lists, the expression in Listing 3.2.2 evaluates to the following.

 

[1 * 3 * 5;

1 * 3 * 6;

1 * 4 * 5;

1 * 4 * 6;

2 * 3 * 5;

2 * 3 * 6;

2 * 4 * 5;

2 * 4 * 6]

 

This reduces to the following.

 

[15; 18; 20; 24; 30; 36; 40; 48]

 

4 Distribution Monad

 

A more interesting variant of the List monad is the Distribution monad.[9]

 

Whereas the List monad is based on the enriched type List<'a>, the Distribution monad is based on the enriched type List<'a * float>, which represents a probability distribution.

 

Type 'a is typically a discriminated union that describes a set of outcomes. The float type represents the probability of each outcome. For example, the probability distributions for a fair coin and a loaded coin are as follows.

 

Listing 4.0.1

type CoinFlipOutcome = Heads | Tails

 

let fair_coin_flip_dist = [Heads, 0.5; Tails, 0.5]

let loaded_coin_flip_dist = [Heads, 0.6; Tails, 0.4]

 

As for the Distribution monad itself, we'll start with the definition of Return and ReturnFrom.

 

Listing 4.0.2

type Distribution<'a> = List<'a * float>

 

type DistributionMonad () =

    member this.Return (x : 'a) : Distribution<'a> = [x, 1.0]

    member this.ReturnFrom (x : Distribution<'a>) : Distribution<'a> = x

 

The Distribution<'a> type is simply an alias to make our type annotations simpler.

 

Return promotes a simple type value to a distribution. Since the distribution only contains one outcome, its probability is 1.0.

 

ReturnFrom simply returns its argument as is typical.

 

4.1 Bind

 

Next we look at Bind.

 

Listing 4.1.1

    member this.Bind (result : Distribution<'a>, rest : 'a -> Distribution<'b>) : Distribution<'b> =

        [

            for (outcome_1 : 'a, probability_1 : float) in result do

                for (outcome_2 : string, probability_2 : float) in rest outcome_1 do

                    yield (sprintf "%A %s" outcome_1 outcome_2), probability_1 * probability_2

        ]

 

Bind might make more sense if we also look at a computation expression that makes use of it.

 

Listing 4.1.2

let (result : Distribution<string>) =

    DistributionMonad () {

        let! toss_1 = fair_coin_flip_dist

        let! toss_2 = fair_coin_flip_dist

        let! toss_3 = fair_coin_flip_dist

        return ""

    }

do printfn "%A" result

 

The code in Listing 4.1.2 computes all possible outcomes, and the probability of each outcome, from tossing a fair coin three times. Running this code produces the following output.

 

[("Heads Heads Heads ", 0.125); ("Heads Heads Tails ", 0.125); ("Heads Tails Heads ", 0.125); ("Heads Tails Tails ", 0.125);

 ("Tails Heads Heads ", 0.125); ("Tails Heads Tails ", 0.125); ("Tails Tails Heads ", 0.125); ("Tails Tails Tails ", 0.125)]

 

The Distribution monad lets us compose applications of functions with the signature 'a -> List<'a * float>.

Like the List monad, the Distribution monad abstracts away the use of for loops.

 

Now we'll go through the definition of Bind line by line.

 

    member this.Bind (result : Distribution<'a>, rest : 'a -> Distribution<'b>) : Distribution<'b> =

 

We can better explain result and rest farther into the body of Bind.

 

        [

 

Bind returns a value of type Distribution<'b>, which is a list. We use list comprehension syntax because it is the most intuitive approach in this case.

 

            for (outcome_1 : 'a, probability_1 : float) in result do

 

Recall the job of Bind is to extract a simple type value from an enriched type value. Also recall in the case of the List monad that means to apply rest to each item contained in result. The Distribution<'a> type is just an alias for List<'a * float>, so we can use the same approach here. Each item in result consists of an outcome of type 'a and a corresponding probability of type float.

 

                for (outcome_2 : string, probability_2 : float) in rest outcome_1 do

 

We apply rest to the outcome extracted from result, but not to the probability of the outcome. Why? We want to evaluate rest in terms of a particular outcome, so we treat that outcome as having already occurred.

 

rest has return type Distribution<'b>. As with result, we extract each outcome and its corresponding probability from the distribution. But what does this distribution represent? Each outcome returned by rest represents a combination of outcomes that take place in rest.

 

                    yield (sprintf "%A %s" outcome_1 outcome_2), probability_1 * probability_2

        ]

 

We combine the outcome and probability from result with the outcome and probability from rest, and yield the result.

 

probability_1 and probability_2 have the same type (float), so we can simply multiply them. We'll look at the concatenation of outcome_1 and outcome_2 later.

 

4.2 How Does This Work?

 

Now let's look at Bind in terms of the computation expression in Listing 4.1.2.

 

1. The first line is:

 

let! toss_1 = fair_coin_flip_dist

 

which means result is [Heads, 0.5; Tails, 0.5], and rest is equivalent to the following.

 

Listing 4.2.1

fun toss_1 ->

    DistributionMonad () {

        let! toss_2 = fair_coin_flip_dist

        let! toss_3 = fair_coin_flip_dist

        return ""

    }

 

We apply rest to each outcome in result, which means we evaluate the function in Listing 4.1.1 for arguments Heads and Tails.

 

2. The second line of the computation expression is as follows.

 

let! toss_2 = fair_coin_flip_dist

 

which means result is [Heads, 0.5; Tails, 0.5], and rest is equivalent to the following.

 

Listing 4.2.2

fun toss_2 ->

    DistributionMonad () {

        let! toss_3 = fair_coin_flip_dist

        return ""

    }

 

Again we apply rest to each outcome in result.

 

3. The third line of the computation expression is as follows.

 

let! toss_3 = fair_coin_flip_dist

 

which means result is [Heads, 0.5; Tails, 0.5], and rest is equivalent to the following.

 

Listing 4.2.3

fun toss_3 ->

    DistributionMonad () {

        return ""

    }

 

4. The fourth line of the computation expression is as follows.

 

return ""

 

This is equivalent to the following.

 

DistributionMonad.Return ""

 

rest returns the following.

 

["", 1.0]

 

This is the root distribution, in which no outcomes have yet taken place.

 

5. Now backtrack to step 3. result is [Heads, 0.5; Tails, 0.5] and the return value of rest is ["", 1.0]. Recall Bind returns the product of result and the return value of rest, which is as follows.

 

[("Heads ", 0.5); ("Tails ", 0.5)]

 

6. Now backtrack to step 2. result is [Heads, 0.5; Tails, 0.5] and the return value of rest is [("Heads ", 0.5); ("Tails ", 0.5)]. Again, Bind returns their product, which is as follows.

 

[("Heads Heads ", 0.25); ("Heads Tails ", 0.25); ("Tails Heads ", 0.25); ("Tails Tails ", 0.25)]

 

7. Now backtrack to step 1. result is [Heads, 0.5; Tails, 0.5]and the return value of rest is [("Heads Heads ", 0.25); ("Heads Tails ", 0.25); ("Tails Heads ", 0.25); ("Tails Tails ", 0.25)]. Again, Bind returns their product, which is as follows.

 

[("Heads Heads Heads ", 0.125); ("Heads Heads Tails ", 0.125); ("Heads Tails Heads ", 0.125); ("Heads Tails Tails ", 0.125);

 ("Tails Heads Heads ", 0.125); ("Tails Heads Tails ", 0.125); ("Tails Tails Heads ", 0.125); ("Tails Tails Tails ", 0.125)]

 

4.3 More on Bind, Part 1

 

Consider again the following lines in Bind.

 

for (outcome_1 : 'a, probability_1 : float) in result do

    for (outcome_2 : string, probability_2 : float) in rest outcome_1 do

 

Previously we mentioned that we treat outcome_1 as an outcome that has already occurred. What this means might be clearer if we rewrite the computation expression as follows.

 

Listing 4.3.1

let (result : Distribution<string>) =

    DistributionMonad () {

        let! toss_1 = fair_coin_flip_dist

        do printfn "First coin toss: %A" toss_1

        let! toss_2 = fair_coin_flip_dist

        do printfn "Second coin toss: %A" toss_2

        let! toss_3 = fair_coin_flip_dist

        do printfn "Third coin toss: %A" toss_3

        return ""

    }

 

Running the code in Listing 4.3.1 produces the following output.

 

First coin toss: Heads

Second coin toss: Heads

Third coin toss: Heads

Third coin toss: Tails

Second coin toss: Tails

Third coin toss: Heads

Third coin toss: Tails

First coin toss: Tails

Second coin toss: Heads

Third coin toss: Heads

Third coin toss: Tails

Second coin toss: Tails

Third coin toss: Heads

Third coin toss: Tails

 

Here is the output in table form.

 

Table 4.3.1

Coin Toss

Outcome

First

Heads

Tails

Second

Heads

Tails

Heads

Tails

Third

Heads

Tails

Heads

Tails

Heads

Tails

Heads

Tails

 

In other words, for each distribution, we loop through all possible outcomes for that distribution, and for a given outcome, we evaluate all remaining distributions in light of that outcome.

 

4.4 More on Bind, Part 2

 

Consider again the following line from Bind.

 

yield (sprintf "%A %s" outcome_1 outcome_2), probability_1 * probability_2

 

outcome_2 has type string because that is a simple way to combine multiple outcomes that might come from different distribution types.

 

We use %A to format outcome_1 because it has type 'a. We use %s to format outcome_2 because it has type string.

 

How do we know outcome_2 has type string, aside from the type annotation?

 

First, recall outcome_2 is part of the return value of rest.

 

Second, recall the computation expression ends with this expression.

 

return ""

 

Recall Return promotes the "" to ["", 1.0]. This is the return value of the innermost application of rest (and the application of rest that is first to complete). "", which has type string, is bound to outcome_2.

 

Each successive application of Bind then returns a Distribution<'a> that is populated by this expression.

 

yield (sprintf "%A %s" outcome_1 outcome_2), probability_1 * probability_2

 

sprintf returns a string. This means Bind returns a value of type Distribution<string>, which is a List<string * float>. The previous application of Bind then unpacks this return value as follows.

 

for (outcome_2 : string, probability_2 : float) in rest outcome_1 do

 

So the first part of each tuple in the distribution has type string.

 

5 State Monad

 

The enriched type on which the State monad is based is itself a function type. The function type has the following signature.

 

'state -> 'state * 'a

 

A function with this signature is applied to a state and returns a tuple. The first part of the tuple is a new state. The second part is an ordinary return value. For example, consider a function that returns a pseudorandom non-negative integer and does not have side effects. It would have the following signature.

 

int -> int * int

 

The parameter is the random seed state. The return value is a tuple. The first part of the tuple is the new random seed state. The second part is the pseudorandom number.

 

.NET lets us generate pseudorandom numbers using the methods of the Random class, such as Random.Next, which returns a pseudorandom non-negative integer. However, Random.Next has side effects, namely mutation of an internal variable that contains the random seed state.

 

Currently, F# has no built-in function to generate pseudorandom numbers that does not have side effects. To define such a function is outside the scope of this article. For simplicity, we define a procedure that uses Random.Next but has the signature we described previously (int -> int * int). Also for simplicity, we refer to this procedure as a function.

 

Listing 5.0.1

let generator = new System.Random ()

 

let get_rand (seed : int) : int * int =

    let seed, rand = seed, generator.Next ()

    seed, rand

 

get_rand is applied to a random seed state and returns a tuple. The first part of the tuple is the same random seed state. The second part is the pseudorandom number. A version of get_rand without side effects would return a new random seed state along with the pseudorandom number.

 

As with the divide_10_by function from Listing 1.2.2, we cannot compose multiple applications of get_rand. As with Listing 1.3.2, we must unpack the result of each application of get_rand before we apply get_rand to the new random seed state.

 

Listing 5.0.2

let initial_seed = 0

let seed_1, rand_1 = get_rand initial_seed

let seed_2, rand_2 = get_rand seed_1

let seed_3, rand_3 = get_rand seed_2

 

With the State monad, we can rewrite the code in Listing 5.0.2 as follows.

 

Listing 5.0.3

let initial_seed = 0

let (f : StatefulFunc<'state, int>) = StateMonad () {

    let! rand_1 = get_rand

    let! rand_2 = get_rand

    let! rand_3 = get_rand

    return rand_3

}

// result = <pseudorandom number>

let result = initial_seed |> f |> snd

 

The State monad lets us compose applications of functions with the signature 'a -> ('state -> 'state * 'a).

 

5.1 Definition

 

We start with a type alias for the enriched type.

 

Listing 5.1.4

type StatefulFunc<'state, 'a> = 'state -> 'state * 'a

 

For the State monad, as usual we start with Return and ReturnFrom.

 

Listing 5.1.5

type StateMonad () =

    member this.Return (x : 'a) : StatefulFunc<'state, 'a> =

        fun state -> state, x

    member this.ReturnFrom (x : StatefulFunc<'state, 'a>) : StatefulFunc<'state, 'a> =

        x

 

As usual, ReturnFrom is straightforward; it is applied to an enriched type value, in this case a StatefulFunc<'state, 'a>, and simply returns its argument.

 

Return promotes a simple type value into an enriched type value, in this case a function of type StatefulFunc<'state, 'a>. This function is applied to a state value and returns a tuple. The first part of the tuple is the same state value. The second part is the simple type value.

 

It might seem odd to have a function that is applied to a state value and then simply returns it. But recall we want to compose the applications of several such functions. This means the state is passed from each of these functions to the next, and its value is potentially read and changed by each of them. The function returned by Return is meant to be the last in such a series of functions. It is applied to the final state value and returns a tuple. The first part of the tuple is the same final state value. The second part is the result of the computation expression.

 

5.2 Bind

 

The key to the State monad is Bind.

 

Listing 5.2.1

    member this.Bind (result : StatefulFunc<'state, 'a>, rest : 'a -> StatefulFunc<'state, 'b>) : StatefulFunc<'state, 'b> =

        fun state ->

            let state_, x = result state

            state_ |> rest x

 

We'll go through Bind line by line shortly. First, it might be helpful to look at a simple function defined with and without the State monad. Recall Listing 5.0.3.

 

Listing 5.2.2

let initial_seed = 0

let (f : StatefulFunc<'state, int>) = StateMonad () {

    let! rand_1 = get_rand

    let! rand_2 = get_rand

    let! rand_3 = get_rand

    return rand_3

}

// result = <pseudorandom number>

let result = initial_seed |> f |> snd

 

The following code is the same as Listing 5.2.2 but without the State monad.

 

Listing 5.2.3

let initial_seed = 0

let (f : StatefulFunc<'state, int>) =

    fun state_0 ->

        let state_1, rand_1 = get_rand state_0 // Bind

        state_1 |>

            (fun state_1 ->

                let state_2, rand_2 = get_rand state_1 // Bind

                state_2 |>

                    (fun state_2 ->

                        let state_3, rand_3 = get_rand state_2 // Bind

                        state_3 |>

                            (fun state_3 -> state_3, rand_3) // Return

                    )

            )

// result = <pseudorandom number>

let result = initial_seed |> f |> snd

 

As with Listings 1.3.2 and 3.0.1, note the way the code marches to the right of the screen.

 

Note when we say, for example, state_1 |> (fun state_1 -> ...), the two state_1 values are not identical, because they exist in different scopes, though they do have the same value. We have given them the same name to show how the state is passed from one function to the next.

 

Note the computation expression in Listing 5.2.3 evaluates to a StatefulFunc<'state, 'a> that composes a series of nested StatefulFunc<'state, 'a> applications.

 

The innermost StatefulFunc<'state, 'a> is:

 

fun state_3 -> state_3, rand_3

 

The second innermost StatefulFunc<'state, 'a> is:

 

fun state_2 ->

    let state_3, rand_3 = get_rand state_2

    state_3 |>

        (fun state_3 -> state_3, rand_3)

 

The outer StatefulFunc<'state, 'a> applies its state value to the inner StatefulFunc<'state, 'a> and returns the result.

 

Extrapolating this, we can think of the entire computation expression as the following StatefulFunc<'state, 'a>.

 

fun state_0 ->

    // ...

    state_3, rand_3

 

We'll now go through Bind line by line.

 

    member this.Bind (result : StatefulFunc<'state, 'a>, rest : 'a -> StatefulFunc<'state, 'b>) : StatefulFunc<'state, 'b> =

 

The result argument is a StatefulFunc<'state * 'a>; that is, a function of type 'state -> 'state * 'a. It is applied to the existing state value in the computation expression, performs some calculation with the state value, and returns a tuple. The first part of the tuple is the new state value. The second part is a simple value type. In the case of get_rand, the existing state value is the random seed state. The new state value is the new random seed state after generating a pseudorandom number. The simple type value is the pseudorandom number.

 

As you can see from Listing 5.2.2, the State monad lets us abstract out the management of the random seed state. That way, we can essentially treat get_rand as if it had the signature unit -> int. However, note we do not actually apply get_rand to any argument when we use it in the computation expression.

 

The rest argument is a function that represents the rest of the computation expression. We apply rest to the simple type value returned by result.

 

Bind returns the result of rest, which is a StatefulFunc<'state, 'b>.

 

        fun state ->

 

Again, Bind returns a StatefulFunc<'state, 'b>, so we start with the anonymous function declaration.

 

            let state_, x = result state

 

We apply result to the existing state value. It returns a tuple. The first part of the tuple is the new state value. The second part is a simple type value.

 

            state_ |> rest x

 

The rest argument is a function that represents the rest of the computation expression. We apply rest to the simple type value returned by result. rest then returns a StatefulFunc<'state', b>, and we apply that to the new state value returned by result.

 

5.3 Explicit State Manipulation

 

We might want to have a computation expression manipulate the state explicitly. Here are two functions to let us do so.

 

Listing 5.3.1

let get_state : StatefulFunc<'state, 'state> = fun s -> s, s

let set_state (s : 'state) : StatefulFunc<'state, unit> = fun _ -> s, ()

 

get_state is applied to the state value by Bind. It returns a tuple. The first and second parts of the tuple each contain the same state value. This both propagates the state to the rest of the computation expression, and lets you bind the state value to a name.

 

set_state is applied to a new state value explicitly. It discards the existing state value. It returns a tuple. The first part of the tuple is the specified state value, which is propagated to the rest of the computation expression as the new state value. The second part of the tuple is unit.

 

These functions are used as follows.

 

Listing 5.3.2

let initial_state = 0

let (f : StatefulFunc<'state, int>) = StateMonad () {

    let! x = get_state

    do! set_state (x + 1)

    return x // The state value is now 1, but x is still 0

}

// result = (1, 0)

let result = initial_state |> f

 

Again, because get_state is a StatefulFunc<'state, 'a>, we do not apply it to anything in the computation expression. Bind applies it to the existing state value.

 

set_state does not bind a value, so we apply do! to it instead of let!.

 

5.4 State Monad Recursion

 

It can be useful to have recursive functions of type StatefulFunc<'state, 'a>. Here is a simple example.

 

Listing 5.4.1

let decrement (s : int) : int * int = s - 1, s

 

let rec countdown : StatefulFunc<int, unit> =

    StateMonad () {

        let! (s : int) = decrement

        do printf "%d " s

        if s <= 0 then

            return ()

        else

            return! countdown

    }

 

do 10 |> countdown |> ignore

 

Running the code in Listing 5.4.1 produces the following output.

 

10 9 8 7 6 5 4 3 2 1 0

 

decrement is a StatefulFunc<int, int> that is applied to a state value, which is an integer, and returns a tuple. The first part of the tuple is the new state value, which is the argument decremented by one. The second part is simply the argument. The second part is not decremented because it is printed with printf and then discarded.

 

countdown is applied to an integer and counts down to 0, printing each number as it goes. We'll go through countdown line by line.

 

let rec countdown : StatefulFunc<int, unit> =

    StateMonad () {

 

It might look intimidating to have a recursive function application within a State monad computation expression, but recall that computation expression just evaluates to another StatefulFunc<'state, 'a>.

 

countdown returns a StatefulFunc<int, unit>. That means the state is of type int and the return value is of type unit. The latter is because countdown is only for demonstration and relies on side effects.

 

        let! (s : int) = decrement

 

This line is one of the keys to countdown. It applies Bind to the decrement function. Note the computation expression does not apply decrement itself. It is Bind that applies decrement to its argument, which is the state value at that point in the evaluation of computation expression.

 

We could, in fact, write this line as follows, by substituting the function body of decrement.

 

        let! (s : int) = fun s -> (s - 1), s

 

decrement returns a tuple. Bind binds the name s to the second part of the tuple, which is the old state value. Bind then applies the rest of the computation expression to the first part of the tuple, which is the new state value.

 

The type annotation of s is just to show we are binding s to the old state value, which is type int.

 

        do printf "%d " s

 

This line simply prints the old state value.

 

        if s <= 0 then

            return ()

 

If the old state value was 0, we stop the recursion.

 

        else

            return! countdown

    }

 

If the old state value was not 0, we return countdown. Bind then recursively applies countdown to the new state value. That bears repeating: as with decrement, the computation expression does not apply countdown; Bind does. We can see this better by looking at countdown defined without the State monad.

 

Listing 5.4.2

let rec countdown : StatefulFunc<int, unit> =

    fun state ->

        let state_, (s : int) = decrement state

        state_ |> (

            do printf "%d " s

            if s <= 0 then

                fun state -> state, ()

            else

                countdown

        )

 

Note the code in parentheses.

 

(

    do printf "%d " s

    if s <= 0 then

        fun state -> state, ()

    else

        countdown

)

 

It might look strange to apply this code to state_, given it is not a function. However, in F#, everything is an expression that evaluates to something. This code is an expression, made up of smaller expressions, and it evaluates to either the anonymous function (fun state -> state, ()), or countdown. That function is then applied to state_.

 

5.5 Usage

 

The example in this section is inspired by Structure and Interpretation of Computer Programs (SICP) by Harold Abelson and Gerald Sussman.[10] [11] In SICP, the authors claim mutation is useful for modular design. As an example, they implement Cesaro's method for estimating pi, using mutation.

 

Cesaro's method for estimating pi is:

 

P (gcd (n1, n2) = 1) = 6 / (π2) where P is probability and n1 and n2 are random non-negative integers.

 

It can be implemented as follows.

1.      Generate two random numbers, r1 and r2.

2.      Check whether both r1 and r2 are primes. If so, increment p.

3.      Repeat steps 1 and 2 n times. The larger n is, the better the estimate of pi.

4.      Let r = p / n.

5.      The estimate of pi = square root (6 / r).

 

Here is the SICP definition translated into F#.[12] This assumes the definition of the State monad from Listings 5.1.4, 5.1.5, and 5.2.1.

 

Listing 5.5.1

let rec gcd (x : int) (y : int) : int =

    if y = 0 then x

    else gcd y (x % y)

 

let get_rand : unit -> int =

    let r = new System.Random ()

    fun () -> rand.Next ()

 

let cesaro () : bool =

    gcd (get_rand ()) (get_rand ()) = 1

 

let monte_carlo (trials : int) (experiment : unit -> bool) : float =

    let rec helper (trials : int) (passed : int) : float =

        if trials <= 0 then

            (float) passed / (float) trials

        else

            if experiment () then

                helper (trials - 1) (passed + 1)

            else

                helper (trials - 1) passed

    helper trials 0

 

let estimate_pi (trials : int) : float =

    System.Math.Sqrt (6. / (monte_carlo trials cesaro))

 

The anonymous procedure bound to the name get_rand uses side effects because it uses Random.Next. By extension, so do the cesaro and monte_carlo procedures.

 

Abelson and Sussman then implement a version without mutation. Here it is, translated into F#. We use the get_rand function we defined in Listing 5.0.1.

 

Listing 5.5.2

let rec gcd (x : int) (y : int) : int =

    if y = 0 then x

    else gcd y (x % y)

 

let generator = new System.Random ()

 

let get_rand (seed : int) : int * int =

    let seed, rand = seed, generator.Next ()

    seed, rand

 

let cesaro (seed_0 : int) : int * bool =

    let seed_1, rand_1 = get_rand seed_0

    let seed_2, rand_2 = get_rand seed_1

    seed_2, (gcd rand_1 rand_2 = 1)

 

let monte_carlo (trials : int) (initial_seed : int) : float =

    let rec helper (trials : int) (passed : int) (old_seed : int) : float =

        if remaining <= 0 then

            (float) passed / (float) trials

        else

            let new_seed, cesaro_passed = cesaro old_seed

            if cesaro_passed then

                helper (trials - 1) (passed + 1) new_seed

            else

                helper (trials - 1) passed new_seed

    helper trials 0 initial_seed

 

let estimate_pi (trials : int) : float =

    let initial_seed = 0

    System.Math.Sqrt (6. / (monte_carlo trials initial_seed))

 

In Listing 5.5.1, the get_rand, cesaro, and monte_carlo procedures were independent of one another. In Listing 5.5.2, the get_rand, cesaro, and monte_carlo functions are entangled, because monte_carlo and cesaro each need an additional parameter for the random seed state to which get_rand is applied. Also, the monte_carlo function in Listing 5.5.2 is less generic than its counterpart in Listing 5.5.1, because it is no longer applied to an experiment of type unit -> bool; instead it must reflect the particulars of the experiment, cesaro.

 

Fortunately, thanks to the State monad, there is a third way.[13]

 

Listing 5.5.3

let rec gcd (x : int) (y : int) : int =

    if y = 0 then x

    else gcd y (x % y)

 

let generator = new System.Random ()

 

let get_rand (seed : int) : int * int =

    let seed, rand = seed, generator.Next ()

    seed, rand

 

let cesaro : StatefulFunc<int, bool> =

    StateMonad () {

        let! r1 = get_rand

        let! r2 = get_rand

        return (gcd r1 r2 = 1)

    }

 

The gcd function and get_rand functions in Listing 5.5.3 are the same as in Listing 5.5.2. cesaro now uses the State monad to manage the random seed state to which get_rand is applied. cesaro is applied to an initial random seed state. It returns a tuple. The first part of the tuple is the new random seed state returned by the final application of get_rand. The second part is a bool that indicates whether the two random numbers were both primes.

 

This, however, is not the important change.

 

Listing 5.5.4

let rec repeat (experiment : StatefulFunc<'state, bool>) (trials : int) (results : List<bool>) : StatefulFunc<'state, List<bool>> =

    StateMonad () {

        if trials <= 0 then

            return results

        else

            let! result = experiment

            return! repeat experiment (trials - 1) (result :: results)

    }

 

We'll go through repeat line by line.

 

let rec repeat (experiment : StatefulFunc<'state, bool>) (trials : int) (results : List<bool>) : StatefulFunc<'state, List<bool>> =

    StateMonad () {

 

repeat applies experiment, which is a function of type StatefulFunc<'state, bool>, a number of times determined by trials, and collects the results in the results.

 

repeat returns the result of a State monad computation expression. This result has type StatefulFunc<'state, List<bool>>.  So repeat is applied to an initial state value and returns a tuple. The first part of the tuple is the final state value. The second part is the collected results of applying experiment.

 

        if trials <= 0 then

            return results

 

If trials is 0, we apply Return to results. Recall from Listing 5.1.5 this promotes results to:

 

fun state -> state, results

 

state is the current state value. Recall the state value is being passed from one monadic function to the next, including recursive applications of repeat, though we do not see this because the State monad abstracts it out of the computation expression. To sum up, we return a tuple. The first part is the final state value. The second part is the collected results of applying experiment.

 

        else

            let! result = experiment

 

If trials is not 0, we apply experiment. We use Bind because experiment is of type StatefulFunc<'state, bool>. Bind applies experiment to the current state value and it returns a tuple. The first part of the tuple is the new state value. The second part is the result of the experiment, which we bind to the name result.

 

            return! repeat experiment (trials - 1) (result :: results)

    }

 

Finally, we do the following.

·        Add the result of the experiment to the collected results.

·        Decrement trials.

·        Recursively apply repeat and return the result.

 

repeat has return type StatefulFunc<'state, List<bool>>. That is, repeat returns a function with the signature 'state -> 'state * List<bool>. Bind applies this function to the current state value, ensuring the state is passed on to the next recursive application of repeat. We can see this better by looking at repeat defined without the State monad.

 

Listing 5.5.5

let rec repeat (experiment : StatefulFunc<'state, bool>) (trials : int) (results : List<bool>) : StatefulFunc<'state, List<bool>> =

    fun state ->

        if trials <= 0 then

            state, results

        else

            let state_, result = experiment state

            state_ |> (repeat experiment (trials - 1) (result :: results))

 

Next we define the monte_carlo function.

 

Listing 5.5.6

let monte_carlo (experiment : StatefulFunc<'state, bool>) (trials : int) : float =

    let initial_seed = 0

    let passed = initial_seed |> repeat experiment trials [] |> snd |> List.filter id |> List.length

    (float) passed / (float) trials

 

In the monte_carlo function, we apply repeat to experiment, the specified number of trials, and an empty results list.

 

repeat returns a value of type StatefulFunc<'state, 'a>, which we apply to the initial random seed state. The StatefulFunc<'state, 'a> returns a tuple. The first part of the tuple is the final random seed state. The second part is the collected results of the experiment. We discard the final random seed state.

 

We then filter the collected results of the experiment to remove all false values, as these represent failures, and count the remaining results. Finally, we return the ratio of the number of times the experiment succeeded to the number of trials.

 

Listing 5.5.7

let estimate_pi (trials : int) : float =

    System.Math.Sqrt (6. / (monte_carlo cesaro trials))

 

estimate_pi simply finishes the math. If I run estimate_pi with 1000 trials, the result is 3.151789148, but your results might vary.

 

The State monad abstracts away the management of state without requiring the use of mutation.

 

6 Monad Implementation, Part 2

 

6.1 Delay

 

In this section we will look at how F# evaluates computation expressions. For simplicity, we'll return to the Maybe monad. For now, we define only the Return method, as the following examples do not require the ReturnFrom or Bind method. We also add a trace statement to the definition of Return.

 

Listing 6.1.1

type MaybeMonad () =

    member this.Return (x : 'a) : Option<'a> =

        do printfn "Return applied to value: %A" x

        Some x

 

Now we write a trivial computation expression, but we also add trace statements here.

 

Listing 6.1.2

let (result : Option<int>) = MaybeMonad () {

    do printfn "Start of computation expression."

    return 1

}

// result = Some 1

do

    printfn "Computation expression result = %A" result

    printfn "End of program."

 

Running the code in Listings 6.1.1 and 6.1.2 produces the following output.

 

Start of computation expression.

Return applied to value: 1

Computation expression result = Some 1

End of program.

 

Note F# evaluates the computation expression when result is defined. But we might want F# to wait to evaluate the computation expression, for example because the computation expression performs some side effect whose timing we want to control.

 

Looking at Listing 6.1.2, one solution is to change result to a function with signature unit -> 'a, then apply the function to unit when we want to evaluate the computation expression. However, as with Bind, monads give us a way to do this more abstractly, namely the Delay method.

 

Listing 6.1.3

type MaybeMonad () =

    member this.Return (x : 'a) : Option<'a> =

        do printfn "Return applied to value: %A" x

        Some x

    member this.Delay (f : unit -> Option<'a>) : Option<'a> =

        do printfn "Delay applied."

        f ()

 

With the definition of the Delay method in Listing 6.1.3, running the code in Listing 6.1.2 produces the following output.

 

Delay applied.

Start of computation expression.

Return applied to value: 1

Computation expression result = Some 1

End of program.

 

We see that Delay is applied before the computation expression is evaluated. Otherwise, it appears nothing has changed. That is because we defined Delay with the signature:

 

(unit -> M<'a>) -> M<'a>

 

Delay has one parameter of type (unit -> M<'a>). The argument to Delay is a function that represents the delayed evaluation of the computation expression. By applying this argument to unit, we cause the computation expression to be evaluated. It is conceptually similar to the rest parameter to Bind, which is a function that represents the rest of a computation expression following a let! expression.

 

We can also define Delay with the signature:

 

(unit -> M<'a>) -> (unit -> M<'a>)

 

In other words, we do not apply Delay's argument to unit, but simply return it. The changes are in bold.

 

Listing 6.1.4

type MaybeMonad () =

    member this.Return (x : 'a) : Option<'a> =

        do printfn "Return applied to value: %A" x

        Some x

    member this.Delay (f : unit -> Option<'a>) : (unit -> Option<'a>) =

        do printfn "Delay applied."

        f

 

We now add more trace statements to the computation expression to show the effect this has. The changes are in bold.

 

Listing 6.1.5

let (result : Option<int>) = MaybeMonad () {

    do printfn "Start of computation expression."

    return 1

}

// result = fun () -> Some 1

do

    printfn "Computation expression result = %A" result

    printfn "Computation expression defined but not evaluated."

    printfn "Evaluating computation expression."

    printfn "Computation expression result = %A" <| result ()

    printfn "End of program."

 

Running the code in Listing 6.1.5 produces the following output.

 

Delay applied.

Computation expression result = <fun:result@19>

Computation expression defined but not evaluated.

Evaluating computation expression.

Start of computation expression.

Return applied to value: 1

Computation expression result = Some 1

End of program.

 

result is initially an unevaluated function, which F# represents as <fun:result@19>. It might appear differently when you run this code.

 

By having Delay simply return its argument, we can evaluate the computation expression when we want to, rather than having it evaluated as soon as we define it.

 

So far, we can determine the following about how F# evaluates computation expressions.[14]

 

Table 6.1.1

Is Delay Defined?

Behavior

No

Evaluate computation expression

Yes

Delay (fun () -> Evaluate computation expression)

 

6.2 Run

 

The Delay method has a counterpart named Run. It is possible to define Delay and not Run, or to define Run and not Delay, though the latter case is not typical.

·        If Delay is not defined, Run is simply applied to the return value of the computation expression.

·        If Delay is defined, Run is applied to the return value of Delay.

 

We can therefore update Table 6.1.1 as follows.

 

Table 6.2.1

Is Delay Defined?

Is Run Defined?

Behavior

No

No

Evaluate computation expression

Yes

No

Delay (fun () -> Evaluate computation expression)

No

Yes

Run (Evaluate computation expression)

Yes

Yes

Run (Delay (fun () -> Evaluate computation expression))

 

The signature of Run depends on whether Delay is defined, and if so, what signature Delay has.[15]

 

Table 6.2.2

Is Delay Defined?

Delay Signature

Run Signature

No

-

M<'a> -> M<'a>*

Yes

(unit -> M<'a>) -> M<'a>

M<'a> -> M<'a>*

Yes

(unit -> M<'a>) -> (unit -> M<'a>)

(unit -> M<'a>) -> M<'a>

 

*If Delay is not defined, or if Delay evaluates its argument (that is, Delay has the signature (unit -> M<'a>) -> M<'a>), it is typically not necessary to define Run.

 

The following is a valid combination of definitions of Delay and Run, because the return type of Delay matches the parameter type of Run.

 

Listing 6.2.1

type MaybeMonad () =

    member this.Return (x : 'a) : Option<'a> =

        Some x

    member this.Delay (f : unit -> Option<'a>) : (unit -> Option<'a>) =

        f

    member this.Run (f : unit -> Option<'a>) : Option<'a> =

        f ()

 

The following is an invalid combination of definitions of Delay and Run, because the return type of Delay does not match the parameter type of Run.

 

Listing 6.2.2

type MaybeMonad () =

    member this.Return (x : 'a) : Option<'a> =

        Some x

    member this.Delay (f : unit -> Option<'a>) : (unit -> Option<'a>) =

        f

    member this.Run (f : Option<'a>) : Option<'a> =

        f

 

let (result : Option<int>) = MaybeMonad () {

    return 1

}

// Error

 

If we run the code in Listing 6.2.2, the F# compiler raises the following error:

 

error FS0001: This expression was expected to have type

    Option<'a>   

but here has type

    unit -> Option<'b>

 

Again, it is possible to define Delay and not Run, as we saw in Listing 6.1.4. It is also possible to define Run and not Delay, but not typical, so we do not show that here.

 

We will see more about why Delay and Run are useful in the section on Combine.

 

6.3 Zero

 

Zero is applied when a computation expression either:

1.      Does not return a value at all.

2.      Returns a value, but not on the last line.

 

The signature of Zero is unit -> M<'a>.

 

The following listing shows how Zero is applied when the computation expression does not return a value at all.

 

Listing 6.3.1

type MaybeMonad () =

    member this.Zero () : Option<'a> = None

 

let (result : Option<unit>) = MaybeMonad () {

    do printfn "Evaluating computation expression."

}

// result = None

 

We annotate the type of result as Option<unit> because otherwise the F# compiler cannot infer the type of 'a in the Option<'a> returned by Zero, which causes it to raise an error.

 

We will see in a later section how Zero is applied when the computation expression returns a value, but not on the last line.

 

6.4 Combine

 

Combine is applied when a computation expression returns more than one value. The following is a basic definition of Combine.

 

Listing 6.4.1

type MaybeMonad () =

    member this.Return (x : 'a) : Option<'a> =

        do printfn "Return applied to value: %A" x

        Some x

    member this.Delay (f : unit -> Option<'a>) : Option<'a> =

        f ()

    member this.Combine (result_1 : Option<'a>, result_2 : Option<'a>) : Option<'a> =

        do printfn "Combine applied to values %A and %A." result_1 result_2

        match result_1, result_2 with

        | Some x, None -> Some x

        | None, Some y -> Some y

        | Some x, Some y -> Some (x + y)

        | _ -> None

 

Note we will see why Delay is also defined in the section Combine and Delay.

 

Combine is applied to a tuple that contains two enriched type values. It combines them into a single enriched type value, which it returns. In the case of the Maybe monad, it does so as follows.

 

1.      If one value is Some and the other is None, Combine returns the Some value.

2.      If both values are None, Combine returns None.

3.      If both values are Some, Combine extracts the simple type values contained in them, combines them, and returns a Some value that contains the combined value.[16]

 

As with Bind, Combine has one parameter, a tuple, which has two parts. If you define Combine with two parameters instead of one, the F# compiler raises errors. However, for simplicity, this article refers to the two parts of the tuple as parameters (when talking about the definition of Combine) or arguments (when talking about applying Combine).

 

Evaluating the following computation expression causes Combine to be applied.

 

Listing 6.4.2

let (result : Option<int>) = MaybeMonad () {

    return 1

    return 2

    return 4

    return 8

}

// result = Some 15

do

    printfn "Computation expression result: %A" result

    printfn "End of program."

 

Running the code in Listings 6.4.1 and 6.4.2 produces the following output.

 

Return applied to value: 1

Return applied to value: 2

Return applied to value: 4

Return applied to value: 8

Combine applied to values Some 4 and Some 8.

Combine applied to values Some 2 and Some 12.

Combine applied to values Some 1 and Some 14.

Computation expression result: Some 15

End of program.

 

If a computation expression returns only one value, Combine is not applied. If a computation expression returns more than one value, Combine is applied to the values with a right fold. For example, when we run the code in Listing 6.4.2, Combine is applied as follows.

 

Listing 6.4.3

Combine (Some 1,

    Combine (Some 2,

        Combine (Some 4, Some 8)))

 

The innermost expression, Combine (Some 4, Some 8), is evaluated first. That returns Some (12). The remaining applications of Combine are as follows.

 

Combine (Some 1,

    Combine (Some 2, Some 12))

 

Combine (Some 1, Some 14)

 

In other words, Combine is first applied to the last two return values of the computation expression. Afterward, Combine is applied to:

1.      The remaining last return value of the computation expression.

2.      The return value of the previous application of Combine.

This continues until all return values of the computation expression are combined.

 

However, Delay complicates this picture.

 

6.5 Combine and Delay

 

If a monad defines Combine, it must also define Delay.

 

Recall Delay is applied to the delayed evaluation of a computation expression. However, when a computation expression returns more than one value (which means Combine is applied), Delay is applied to both:

1.      The delayed evaluation of the last return value of the computation expression.

2.      The delayed evaluation of each application of Combine.

 

Note if a computation expression returns more than one value, the result of the computation expression is the result of the outermost application of Combine. Delay is then applied to the delayed evaluation of the outermost application of Combine. So we can still say that Delay is applied to the delayed evaluation of the computation expression.

 

Given the second argument to Combine is either (1) the last return value of the computation expression or (2) the return value of the previous application of Combine, we can see that with the introduction of Delay, we must revise our description of how Combine is applied.

 

Combine is first applied to:

1.      The second to last return value of the computation expression.

2.      The result of applying Delay to the delayed evaluation of the last return value of the computation expression.

Afterward, Combine is applied to:

1.      The remaining last return value of the computation expression.

2.      The result of applying Delay to the delayed evaluation of the previous application of Combine.

This continues until all return values of the computation expression are combined.

 

This might be clearer if we update Listing 6.4.3 to show the relationship between Combine and Delay.

 

Listing 6.5.1

Delay (fun () -> Combine (Some 1,

    Delay (fun () -> Combine (Some 2,

        Delay (fun () -> Combine (Some 4,

            Delay (fun () -> Some 8)))))))

 

Also recall Delay can simply return its argument rather than evaluate it. Let's see what happens in that case, by updating Listing 6.4.1 as follows. The changes are in bold.

 

Listing 6.5.2

member this.Delay (f : unit -> Option<'a>) : (unit -> Option<'a>) =

    f

 

Now, if we try to run the code in Listing 6.4.2, the line return 1 causes the F# compiler to raise the following error.

 

error FS0001: This expression was expected to have type

    Option<int>   

but here has type

    unit -> Option<'a>

 

This error is caused by a conflict between the signatures of Delay and Combine.

 

The signature of Combine depends on the signature of Delay.[17]

 

Table 6.5.1

Delay Signature

Combine Signature

(unit -> M<'a>) -> M<'a>

(M<'a> * M<'a>) -> M<'a>

(unit -> M<'a>) -> (unit -> M<'a>)

(M<'a> * (unit -> M<'a>)) -> M<'a>

 

Because we have changed the signature of Delay from Listing 6.4.1, we must update Combine accordingly. The changes are in bold.

 

Listing 6.5.3

type MaybeMonad () =

    member this.Return (x : 'a) : Option<'a> =

        do printfn "Return applied to value: %A" x

        Some x

    member this.Delay (f : unit -> Option<'a>) : (unit -> Option<'a>) =

        f

    member this.Combine (result_1 : Option<'a>, result_2 : (unit -> Option<'a>)) : Option<'a> =

        let result_2_ = result_2 ()

        do printfn "Combine applied to values %A and %A." result_1 result_2_

        match result_1, result_2_ with

        | Some x, None -> Some x

        | None, Some y -> Some y

        | Some x, Some y -> Some (x + y)

        | _ -> None

 

The changes are as follows.

1.      The second part of the parameter to Combine has changed from type Option<'a> to (unit -> Option<'a>) to reflect the change in the return type of Delay.

2.      The second part of the argument to Combine is evaluated by applying it to unit.

 

We also must update the code in Listing 6.4.2. The changes are in bold.

 

Listing 6.5.4

let (result : unit -> Option<int>) = MaybeMonad () {

    return 1

    return 2

    return 4

    return 8

}

// result = fun () -> Some 15

do

    printfn "Computation expression result: %A" <| result ()

    printfn "End of program."

 

The changes are as follows.

1.      The result type of the computation expression has changed from type Option<'a> to (unit -> Option<'a>) to reflect the change in the return type of Delay.

2.      The result of the computation expression is evaluated by applying it to unit.

 

Running the code in Listings 6.5.3 and 6.5.4 produces the following output.

 

Return applied to value: 1

Return applied to value: 2

Return applied to value: 4

Return applied to value: 8

Combine applied to values Some 4 and Some 8.

Combine applied to values Some 2 and Some 12.

Combine applied to values Some 1 and Some 14.

Computation expression result: Some 15

End of program.

 

Why involve Delay with Combine like this? If a computation expression returns multiple values, we might not want to evaluate all of the return values at once. For example, the Sequence monad allows a computation expression to return infinite values. So the job of Combine, with the help of Delay, is not only to combine the return values of a computation expression, but to determine when (or whether) to evaluate the remaining return values. We will see more about this when we talk about the Sequence monad.

 

The delayed second parameter to Combine is conceptually similar to the rest parameter to Bind, which is a function that represents the rest of a computation expression following a let! expression.

 

6.6 Combine, Delay, and Run

 

In Listing 6.5.4, the return value of the computation expression was delayed, so we had to apply it to unit to evaluate it. But recall there is a built-in way to do this, namely the Run method. Here is Listing 6.5.3 with the Run method added. Also, we include trace statements in both Delay and Run. The changes are in bold.

 

Listing 6.6.1

type MaybeMonad () =

    member this.Return (x : 'a) : Option<'a> =

        do printfn "Return applied to value: %A" x

        Some x

    member this.Delay (f : unit -> Option<'a>) : (unit -> Option<'a>) =

        do printfn "Delay applied."

        f

    member this.Run (f : unit -> Option<'a>) : Option<'a> =

        do printfn "Run applied."

        f ()

    member this.Combine (result_1 : Option<'a>, result_2 : (unit -> Option<'a>)) : Option<'a> =

        let result_2_ = result_2 ()

        do printfn "Combine applied to values %A and %A." result_1 result_2_

        match result_1, result_2_ with

        | Some x, None -> Some x

        | None, Some y -> Some y

        | Some x, Some y -> Some (x + y)

        | _ -> None

 

We can now revert the changes we made from Listing 6.4.2 to Listing 6.5.4. The changes are in bold.

 

Listing 6.6.2

let (result : Option<int>) = MaybeMonad () {

    return 1

    return 2

    return 4

    return 8

}

// result = Some 15

do

    printfn "Computation expression result: %A" result

    printfn "End of program."

 

Running the code in Listings 6.6.1 and 6.6.2 produces the following output.

 

Listing 6.6.3

Delay applied.

Run applied.

Return applied to value: 1

Delay applied.

Return applied to value: 2

Delay applied.

Return applied to value: 4

Delay applied.

Return applied to value: 8

Combine applied to values Some 4 and Some 8.

Combine applied to values Some 2 and Some 12.

Combine applied to values Some 1 and Some 14.

Computation expression result: Some 15

End of program.

 

Recall when the computation expression returns more than one value, Delay is applied to both:

1.      The delayed evaluation of the last return value of the computation expression.

2.      The delayed evaluation of each application of Combine.

 

Run, however, is applied only to the return value of the outermost application of Delay. This means we need to update Listing 6.5.1 to show the relation between Combine, Delay, and Run.

 

Listing 6.6.4

Run (Delay (fun () -> Combine (Some 1,

    Delay (fun () -> Combine (Some 2,

        Delay (fun () -> Combine (Some 4,

            Delay (fun () -> Some 8))))))))

 

Why, in Listing 6.6.3, is Delay applied before Run? Recall that the delayed argument to the outermost Delay has not been evaluated yet. In effect, what F# sees is the following.

 

Run (Delay (fun () -> ?

 

The innermost expression, Delay (fun () -> ?, is evaluated first. But Delay simply returns its argument, so the next expression to be evaluated is Run (fun () -> ?.

 

It might help to match up the output in Listing 6.6.3 to the expression in Listing 6.6.4. At each step, we highlight the part of the expression to which the output corresponds.

 

Table 6.6.1

Output

Expression

Delay applied.

Run (Delay (fun () -> Combine (Some 1,

    Delay (fun () -> Combine (Some 2,

        Delay (fun () -> Combine (Some 4,

            Delay (fun () -> Some 8))))))))

Run applied.

Run (fun () -> Combine (Some 1,

    Delay (fun () -> Combine (Some 2,

        Delay (fun () -> Combine (Some 4,

            Delay (fun () -> Some 8)))))))

Return applied to value: 1

Combine (Some 1,

    Delay (fun () -> Combine (Some 2,

        Delay (fun () -> Combine (Some 4,

            Delay (fun () -> Some 8))))))

Delay applied.

Combine (Some 1,

    Delay (fun () -> Combine (Some 2,

        Delay (fun () -> Combine (Some 4,

            Delay (fun () -> Some 8))))))

Return applied to value: 2

Combine (Some 1,

    fun () -> Combine (Some 2,

        Delay (fun () -> Combine (Some 4,

            Delay (fun () -> Some 8)))))

Delay applied.

Combine (Some 1,

    fun () -> Combine (Some 2,

        Delay (fun () -> Combine (Some 4,

            Delay (fun () -> Some 8)))))

Return applied to value: 4

Combine (Some 1,

    fun () -> Combine (Some 2,

        fun () -> Combine (Some 4,

            Delay (fun () -> Some 8))))

Delay applied.

Combine (Some 1,

    fun () -> Combine (Some 2,

        fun () -> Combine (Some 4,

            Delay (fun () -> Some 8))))

Return applied to value: 8

Combine (Some 1,

    fun () -> Combine (Some 2,

        fun () -> Combine (Some 4,

            fun () -> Some 8)))

Combine applied to values Some 4 and Some 8.

Combine (Some 1,

    fun () -> Combine (Some 2,

        fun () -> Combine (Some 4,

            fun () -> Some 8)))

Combine applied to values Some 2 and Some 12.

Combine (Some 1,

    fun () -> Combine (Some 2,

        fun () -> Some 12))

Combine applied to values Some 1 and Some 14.

Combine (Some 1,

    fun () -> Some 14)

Computation expression result: Some 15

Some 15

End of program.

 

 

The following diagram illustrates the relationship between Return/ReturnFrom, Combine, Delay, and Run.[18]

 

 

 

 

We will see why Run is applied only to the return value of the outermost application of Delay when we look at the Sequence monad.

 

6.7 Combine, Delay, and Zero

 

We mentioned earlier that Zero is applied when a computation expression returns a value, but not on the last line. This means the computation expression has two return values (one returned by Return/ReturnFrom and one returned by Zero), which means Combine is applied.

 

Listing 6.7.1

type MaybeMonad () =

    member this.Return (x : 'a) : Option<'a> =

        Some x

    member this.Delay (f : unit -> Option<'a>) : Option<'a> =

        f ()

    member this.Combine (result_1 : Option<'a>, result_2 : Option<'a>) : Option<'a> =

        do printfn "Combine applied to values %A and %A." result_1 result_2

        match result_1, result_2 with

        | Some x, None -> Some x

        | None, Some y -> Some y

        | Some x, Some y -> Some (x + y)

        | _ -> None

    member this.Zero () : Option<'a> =

        do printfn "Zero returning Some 2."

        Some 2

 

let (result : Option<int>) = MaybeMonad () {

    return 1

    do printfn "The last line of the computation expression does not return a value."

}

// result = Some 3

do printfn "Computation expression result: %A" result

 

Running the code in Listing 6.7.1 produces the following output.

 

The last line of the computation expression does not return a value.

Zero returning Some 2.

Combine applied to values Some 1 and Some 2.

Computation expression result: Some 3

 

Because the last line of the computation expression in Listing 6.7.1 does not return a value, Zero is applied, and Combine is applied to the result of Return and of Zero. Note the return value of Zero is treated as the last return value of the computation expression, which makes it the second argument to Combine, and its evaluation is delayed.

 

Note for the Maybe monad, Zero typically returns None. We have it return a different value here only for the purpose of this example.

 

Note defining a monad class with both Combine and Zero methods lets you return a result in the middle of a computation expression, but return does not act as a control flow construct the way it does in an imperative language. That is, the rest of the computation expression following the return or return! expression is still evaluated unless:

1.      Delay is also defined with signature (unit -> Option<'a>) -> (unit -> Option<'a>); that is, it does not evaluate its argument.

2.      Combine does not evaluate the second part of its argument, which has type unit -> Option<'a>, and which represents the rest of the computation expression.

 

Here is a trivial definition of the Maybe monad in which both these conditions are met.

 

Listing 6.7.2

type MaybeMonad () =

    member this.Return (x : 'a) : Option<'a> = Some x

    member this.Zero () : Option<'a> = None

    member this.Delay (f : unit -> Option<'a>) : (unit -> Option<'a>) =

        f

    member this.Combine (a : Option<'a>, b : (unit -> Option<'a>)) =

        a

 

let (result : unit -> Option<'a>) = MaybeMonad () {

    return 1

    do printfn "This will never be shown."

}

// result = fun () -> Some 1

do printfn "%A" <| result ()

 

Running the code in Listing 6.7.2 produces the following output.

 

Some 1

 

Note the printfn statement following the return is never evaluated.

 

7 Sequence Monad

 

In lecture 5A of Structure and Interpretation of Computer Programs, Gerald Sussman implements a sequence as an example of why mutation is useful even in a functional language (in this case, Scheme).[19] Here is his implementation translated into F#.

 

Listing 7.0.1

let make_counter (n : int) =

    let mutable _n = n

    fun () ->

        do _n <- _n + 1

        _n

 

let s = make_counter 0

do

    s () |> printf "%d "

    s () |> printf "%d "

    s () |> printf "%d "

 

Running the code in Listing 7.0.1 produces the following output.

 

1 2 3

 

Note the use of the delay (fun () ->) to make the sequence lazily evaluated. That is necessary because the sequence is infinite.

 

F# has built-in sequences, represented by the seq<'a> data type. We can generate a sequence with the built-in Sequence monad.

 

The Sequence monad is based on the enriched type seq<'a>, which represents a lazily evaluated and possibly infinite stream of items.

The Sequence monad is not mainly about composing applications of functions. Rather, it is about generating sequences.

The Sequence monad abstracts away the need to use delays and mutation to generate a sequence.

 

The following is a definition of the Fibonacci sequence using the built-in Sequence monad.

 

Listing 7.0.2

let rec fibonacci (n1 : int) (n2 : int) : seq<int> = seq {

    yield n1

    yield! fibonacci n2 (n1 + n2)

}

do fibonacci 1 1 |> Seq.take 10 |> Seq.iter (printf "%d ")

 

The code in Listing 7.0.2 outputs the following.

 

1 1 2 3 5 8 13 21 34 55

 

The application of yield is what generates the numbers we see when we evaluate the sequence. The application of yield! is what makes the sequence infinite. Recall that a monadic keyword that ends in ! is applied to an enriched type value, and that value can be the result of a recursive application.

 

Note the recursive application of fibonacci does not result in an infinite loop. This is because fibonacci returns a sequence, the evaluation of which is delayed.

 

To better understand how the Sequence monad works, we will define our own version.

 

First, we need some helper types from which to build a sequence.

 

Listing 7.0.3

type Seq<'a> = unit -> SeqNode<'a>

and SeqNode<'a> =

| None

| Some of SeqItem<'a>

and SeqItem<'a> = {

    item : 'a;

    next : unit -> SeqNode<'a>;

}

 

Note F# already has a built-in type seq<'a>, but F# is case-sensitive, so we can define a new type Seq<'a>. In production code we would use a less similar name.

 

The first type is Seq<'a>, which wraps the second type, SeqNode<'a>, in a delay. This is because we do not want a sequence to be evaluated until we evaluate it explicitly.

 

The second type, SeqNode<'a>, is a discriminated union with two cases:

1.      None, which terminates the sequence.

2.      Some, which contains a sequence item.

 

The third type, SeqItem<'a>, is a record type with two fields:

1.      item, which contains the data of type 'a.

2.      next, which links to the next SeqNode<'a>, with a delay. Note this is identical to the Seq<'a> type, and indeed we can think of next as containing another sequence.

 

This is similar to a basic definition of a linked list, with a couple of differences.

 

First, we use the type system to distinguish a sequence item (Some) from the sequence terminator (None). This is safer than simply terminating the sequence with null, as linked lists implemented in C-derived languages often do.

 

Second and more importantly, the next field of SeqItem<'a> includes a delay:

 

unit -> SeqNode<'a>

 

The delay ensures the next item in the sequence is not evaluated until we evaluate it explicitly by applying the value of next to unit.

 

For the monad itself, we start by defining Yield and YieldFrom, which, following convention, we define instead of Return and ReturnFrom.

 

Listing 7.0.4

type SeqMonad () =

    member this.Yield (x : 'a) : Seq<'a> =

        fun () ->

            SeqNode<'a>.Some {

                item = x;

                next = fun () -> SeqNode.None;

            }

    member this.YieldFrom (x : Seq<'a>) : Seq<'a> =

        x

 

As usual, YieldFrom is straightforward; it is applied to an enriched type value, in this case a sequence, and simply returns its argument.

 

Let's go through Yield line by line.

 

    member this.Yield (x : 'a) : Seq<'a> =

 

Recall that Yield is essentially the same as Return, which means it promotes a simple type value to an enriched type value. In this case, the enriched type value is a sequence that contains only the one simple type value.

 

        fun () ->

 

Yield returns a Seq<'a>, so we start with a delay.

 

            SeqNode<'a>.Some {

 

The delay wraps a SeqNode<'a> of case SeqNode.Some. The inner type (SeqItem<'a>) value is as follows.

 

                item = x;

 

item contains the argument (x) to which the yield keyword was applied in the computation expression.

 

                next = fun () -> SeqNode.None;

            }

 

next links to the sequence terminator, SeqNode.None.

 

We will also define Combine, so we can use Yield and YieldFrom to create multiple sequences that are then combined.

 

7.1 Combine

 

Next we define Combine, which is the key to the Sequence monad.[20]

 

Listing 7.1.1

    member this.Combine (a : Seq<'a>, b : unit -> Seq<'a>) : Seq<'a> =

        fun () ->

            match a () with

            | SeqNode.None -> (b ()) ()

            | SeqNode.Some x ->

                SeqNode.Some {

                    item = x.item;

                    next = this.Combine (x.next, b)

                }

 

Let's go through this line by line.

 

member this.Combine (a : Seq<'a>, b : unit -> Seq<'a>) : Seq<'a> =

 

Recall that Combine is applied when a computation expression returns more than one value, as in Listing 7.0.2. Combine is applied to two sequences and returns a new sequence that combines its arguments.

 

Note parameter b is delayed. As we will see in the next section, the signature of parameter b is due to our definition of Delay. Given that the type Seq<'a> already contains a delay, this additional delay of parameter b might not seem necessary, but it is, as we will see later.

 

    fun () ->

 

Combine returns a Seq<'a>, so we start with a delay.

 

        match a () with

 

We evaluate the first item of sequence a so we can determine whether it is the sequence terminator or not. In effect, we move the delay from sequence a to the return value of Combine. We do this so we can describe how to process the first item of sequence a without actually evaluating it yet.

 

        | SeqNode.None -> (b ()) ()

 

In this case, sequence a is empty, so we discard it.

 

We remove the delay from argument b by applying it to unit, which gives us a Seq<'a>. We then evaluate the first step of that sequence and return the result.

 

If the return type of Combine is Seq<'a>, why do we evaluate the first item of the sequence in argument b rather than simply return b? Recall the return value of Combine already begins with a delay, so we do not need an additional delay before we begin to evaluate the sequence in argument b.

 

        | SeqNode.Some x ->

 

In this case, sequence a contains at least one item. We use the full name SeqNode.Some to distinguish it from Option.Some.

 

            SeqNode.Some {

 

We want to return a new sequence that combines the sequences in arguments a and b. Sequence a contains at least one item, so we return a new sequence that also contains at least one item, which we wrap with SeqNode.Some.

 

The item itself is represented by type SeqItem<'a>, which is a record type, so we open the new SeqItem<'a> value with {. F# infers the record type from the fields we define.

 

                item = x.item;

 

We simply copy the item field from the first item of sequence a to the new item.

 

                next = this.Combine (x.next, b)

            }

 

Several things are going on here. First, recall the next field of the SeqItem<'a> type has signature unit -> SeqNode<'a>. That is because we want each sequence item to be delayed so it is not evaluated until we evaluate it explicitly by applying the value of next to unit.

 

Second, recall we want to return a new sequence that combines the sequences in arguments a and b. To do that, we must create a new sequence that contains all the items in sequence a, followed by all the items from the sequence in argument b. The naive approach is as follows.

 

1.      Evaluate sequence a until we reach the sequence terminator, SeqNode.None.

2.      Back up to the last SeqItem<'a> value in argument a, and set its next field to the sequence in argument b.

 

However, we do not want to evaluate the remainder of sequence a yet.

 

Instead we recursively apply Combine to the remainder of sequence a (x.next), and to an unchanged argument b. We want to set the next field of the last item in sequence a to the sequence in argument b, but we do not have that last item in sequence a yet; we must continue to evaluate sequence a until we reach the sequence terminator.

 

In effect, we create a promise to continue to combine the sequences in arguments a and b without having to evaluate any more items in either sequence for now.

 

7.2 Delay and Run

 

Recall that because we define Combine, we must also define Delay. We also define Run.

 

Listing 7.1.2

    member this.Delay (f : unit -> SeqNode<'a>) : (unit -> SeqNode<'a>) =

        f

    member this.Run (f : unit -> Seq<'a>) : Seq<'a> =

        f ()

 

Our definition of Delay simply returns its argument; our definition of Run evaluates its argument and returns the result. Several things follow from these definitions.

 

The first thing has to do with the return value of the computation expression.

1.      Recall because Delay is defined, the evaluation of the computation expression is delayed. That is, the return value of the computation expression has type unit -> Seq<'a>.

2.      Delay is applied to the return value of the computation expression. Our definition of Delay simply returns its argument, so its return value also has type unit -> Seq<'a>.

3.      Recall Run is applied to the return value of Delay. Our definition of Run evaluates its argument and returns the result, so its return value has type Seq<'a>.

 

In other words, with regard to the return value of the computation expression, it is as if we defined neither Delay nor Run. However, we will see later there are other reasons for defining these methods this way.

 

Second, recall the signature of Delay affects the signature of Combine. Because our definition of Delay simply returns its argument, the second parameter to Combine is delayed.

 

member this.Combine (a : Seq<'a>, b : unit -> Seq<'a>) : Seq<'a> =

 

Again, this might seem like a needless complication; again, we will see there is a reason for our defining Delay the way we have.

 

Third, recall Delay is applied to the result of the delayed evaluation of each application of Combine, and recall our definition of Combine recursively applies itself. Note the part in bold.

 

Listing 7.1.3

    member this.Combine (a : Seq<'a>, b : unit -> Seq<'a>) : Seq<'a> =

        fun () ->

            match a () with

            | SeqNode.None -> (b ()) ()

            | SeqNode.Some x ->

                SeqNode.Some {

                    item = x.item;

                    next = this.Combine (x.next, b)

                }

 

However, when Combine is applied explicitly, as we do in Listing 7.1.3, its evaluation is not delayed, and Delay is not applied to its return value. In other words, the result of our recursive application of Combine does not have type unit -> Seq<'a>, but simply type Seq<'a>. Therefore, we can bind this result to the next field of the SeqItem<'a>.

 

We will see why we define Delay and Run this way in the next section.

 

7.3 Usage

 

Now we'll recreate the code in Listing 7.0.2 using our own definition of the Sequence monad. First we also need our own versions of the Seq.take and Seq.iter functions.

 

Listing 7.3.1

let rec seq_take (count : int) (s : Seq<'a>) : Seq<'a> =

    fun () ->

        if count <= 0 then SeqNode.None

        else

            match s () with

            | SeqNode.None -> SeqNode.None

            | SeqNode.Some x ->

                SeqNode.Some {

                    item = x.item;

                    next = seq_take (count - 1) x.next;

                }

 

seq_take is applied to a sequence and returns a new sequence that contains the specified number of items copied from the source sequence. We'll go through seq_take in more detail.

 

let rec seq_take (count : int) (s : Seq<'a>) : Seq<'a> =

    fun () ->

 

Because we are returning a new sequence, we start with a delay.

 

        if count <= 0 then SeqNode.None

 

If we have already copied the specified number of sequence items to the new sequence, we return the sequence terminator.

 

        else

            match s () with

 

We evaluate the first item of the source sequence to see whether or not it is the sequence terminator.

 

            | SeqNode.None -> SeqNode.None

 

If the item is the sequence terminator, we simply return it.

 

            | SeqNode.Some x ->

                SeqNode.Some {

                    item = x.item;

                    next = seq_take (count - 1) x.next;

                }

 

If the item is not the sequence terminator, we copy it from the source sequence to the new one.

 

We recursively apply seq_take to a decremented count and to the remainder of the source sequence. We change the next field of the SeqItem<'a> to point to the return value of seq_take.

 

seq_iter simply applies the specified function to each sequence item in the specified sequence. The function returns unit, so it is assumed to have side effects.

 

Listing 7.3.2

let rec seq_iter (f : 'a -> unit) (s : Seq<'a>) : unit =

    match s () with

    | SeqNode.None -> ()

    | SeqNode.Some x ->

        do f x.item

        seq_iter f x.next

 

We can now recreate the Fibonacci function from Listing 7.0.2.

 

Listing 7.3.3

let rec fibonacci (n1 : int) (n2 : int) : Seq<int> =

    SeqMonad () {

        yield n1

        yield! fibonacci n2 (n1 + n2)

    }

do fibonacci 1 1 |> seq_take 10 |> seq_iter (printf "%d ")

 

Running the code in Listing 7.3.3 produces the following output.

 

1 1 2 3 5 8 13 21 34 55

 

7.4 How Does This Work?

 

Recall we defined Delay and Run as follows.

 

Listing 7.4.1

member this.Delay (f : unit -> SeqNode<'a>) : (unit -> SeqNode<'a>) =

    f

member this.Run (f : unit -> Seq<'a>) : Seq<'a> =

    f ()

 

In other words, Delay simply returns its argument, and Run evaluates its argument. To see how these definitions affect the fibonacci function, we've added comments to it in bold to show when Combine, Delay, and Run are applied.

 

Listing 7.4.2

let rec fibonacci (n1 : int) (n2 : int) : Seq<int> =

    (* Run <| Delay <| fun () -> *) SeqMonad () {

        yield (* Combine argument a *) n1

        yield! (* Combine argument b <| Delay <| fun () -> *) fibonacci n2 (n1 + n2)

    }

 

We'll take a closer look at what these comments mean.

 

(* Run <| Delay <| fun () -> *) SeqMonad () {

 

1.      The evaluation of the Sequence monad computation expression is delayed.

2.      Delay is applied to the delayed evaluation of the computation expression, and simply returns its argument.

3.      Run is applied to the return value of Delay, and evaluates its argument. So Run evaluates the computation expression.

 

This means the return type of fibonacci is Seq<int>, which is not delayed. (The evaluation of the sequence itself is delayed, but that is part of the Seq<'a> type.) This is just what we want.

 

yield (* Combine argument a *) n1

 

n1 becomes the first argument to Combine because it is the second to last return value of the computation expression.

 

yield! (* Combine argument b <| Delay <| fun () -> *) fibonacci n2 (n1 + n2)

 

1.      The evaluation of the recursive application of fibonacci is delayed.

2.      Delay is applied to the delayed evaluation of the computation expression, and simply returns its argument.

3.      Run is not applied to the return value of Delay because it is not the outermost application of Delay.

4.      The return value of Delay becomes the second argument to Combine, because it contains the last return value of the computation expression.

 

This means the evaluation of the recursive application of fibonacci is delayed. Again, this is just what we want.

 

In other words, we want the evaluation of the initial application of fibonacci to not be delayed, but we want the evaluations of subsequent applications of fibonacci to be delayed. Why? If the evaluation of the recursive application of fibonacci were not delayed, it would result in an infinite loop.

 

Combine then removes the delay. Here is the definition of Combine with the key parts bolded.

 

Listing 7.4.3

member this.Combine (a : Seq<'a>, b : unit -> Seq<'a>) : Seq<'a> =

    fun () ->

        match a () with

        | SeqNode.None -> (b ()) ()

        | SeqNode.Some x ->

            SeqNode.Some {

                item = x.item;

                next = this.Combine (x.next, b)

            }

 

It might also help to add trace statements to the definitions of the Sequence monad and the seq_iter function. Here is the definition of the Sequence monad with changes in bold.

 

Listing 7.4.4

type SeqMonad () =

(* Yield and YieldFrom omitted. *)

    member this.Combine (a : Seq<'a>, b : unit -> Seq<'a>) : Seq<'a> =

        fun () ->

            do printfn "Combine evaluated."

            match a () with

            | SeqNode.None -> (b ()) ()

            | SeqNode.Some x ->

                SeqNode.Some {

                    item = x.item;

                    next = this.Combine (x.next, b)

                }

    member this.Delay (f : unit -> Seq<'a>) : (unit -> Seq<'a>) =

        do printfn "Delay applied."

        f

    member this.Run (f : unit -> Seq<'a>) : Seq<'a> = // Add Run

        do printfn "Run applied."

        f ()

 

Here is the definition of seq_iter with changes in bold.

 

Listing 7.4.5

let rec seq_iter (f : 'a -> unit) (s : Seq<'a>) : unit =

    match s () with

    | SeqNode.None -> ()

    | SeqNode.Some x ->

        do printf "seq_iter applying f: "

        do f x.item

        seq_iter f x.next

 

Here is our application of fibonacci with changes in bold.

 

Listing 7.4.6

do fibonacci 1 1 |> seq_take 10 |> seq_iter (printfn "%d")

 

With the revisions in Listings 7.4.4 and 7.4.5, running the code in Listing 7.4.6 produces the following output. At each step, we highlight the code to which the output corresponds. For the fibonacci function, we use the version in Listing 7.4.2 with comments to show when Combine, Delay, and Run are applied.

 

Output

Code

Delay applied.

let rec fibonacci (n1 : int) (n2 : int) : Seq<int> =

    (* Run <| Delay <| fun () -> *) SeqMonad () {

        yield (* Combine argument a *) n1

        yield! (* Combine argument b <| Delay <| fun () -> *) fibonacci n2 (n1 + n2)

    }

Run applied.

let rec fibonacci (n1 : int) (n2 : int) : Seq<int> =

    (* Run <| Delay <| fun () -> *) SeqMonad () {

        yield (* Combine argument a *) n1

        yield! (* Combine argument b <| Delay <| fun () -> *) fibonacci n2 (n1 + n2)

    }

Delay applied.

let rec fibonacci (n1 : int) (n2 : int) : Seq<int> =

    (* Run <| Delay <| fun () -> *) SeqMonad () {

        yield (* Combine argument a *) n1

        yield! (* Combine argument b <| Delay <| fun () -> *) fibonacci n2 (n1 + n2)

    }

Combine evaluated.

let rec fibonacci (n1 : int) (n2 : int) : Seq<int> =

    (* Run <| Delay <| fun () -> *) SeqMonad () {

        yield (* Combine argument a *) n1

        yield! (* Combine argument b <| Delay <| fun () -> *) fibonacci n2 (n1 + n2)

    }

seq_iter applying f: 1

let rec seq_iter (f : 'a -> unit) (s : Seq<'a>) : unit =

    match s () with

    | SeqNode.None -> ()

    | SeqNode.Some x ->

        do printf "seq_iter applying f: "

        do f x.item

        seq_iter f x.next

Combine evaluated.

member this.Combine (a : Seq<'a>, b : unit -> Seq<'a>) : Seq<'a> =

    fun () ->

        do printfn "Combine evaluated."

        match a () with

        | SeqNode.None -> (b ()) ()

        | SeqNode.Some x ->

            SeqNode.Some {

                item = x.item;

                next = this.Combine (x.next, b)

            }

Delay applied.

let rec fibonacci (n1 : int) (n2 : int) : Seq<int> =

    (* Run <| Delay <| fun () -> *) SeqMonad () {

        yield (* Combine argument a *) n1

        yield! (* Combine argument b <| Delay <| fun () -> *) fibonacci n2 (n1 + n2)

    }

...

 

 

The output repeats until the final line, seq_iter applying f: 55.

 

8 Pause Monad

 

A variant of the Sequence monad is the Pause monad.[21] We use the Pause monad to build coroutines. A coroutine is a computation expression that can yield control to another coroutine without returning. With coroutines we can carry out tasks using shared multitasking. For simplicity, our Pause monad creates coroutines that use side effects.

 

Coroutines can be used to model AI players in a game. Such a coroutine might have the following instructions.

1.      Wait until we have control.

2.      Read the shared state.

3.      If the game is over, terminate.

4.      If the game is not over, determine how to react to the shared state.

5.      Modify the shared state.

6.      Yield control to another coroutine.

7.      Return to step 1.

 

As with the Sequence monad, we start with a helper type from which to build a coroutine.

 

Listing 8.0.1

type Coroutine<'a> = unit -> CoroutineStep<'a>

and CoroutineStep<'a> =

| Done of 'a

| Paused of Coroutine<'a>

 

Coroutine<'a> represents a coroutine. It is delayed so it is not evaluated until we evaluate it explicitly by applying it to unit. This helps a schedule switch control from one coroutine to another. CoroutineStep<'a> represents a coroutine step.

 

CoroutineStep<'a> is a discriminated union with two cases:

1.      Done, which terminates the coroutine and returns a value.

2.      Paused, which links to the next coroutine step, with a delay.

 

The Pause monad is based on the enriched type Coroutine<'a>, which represents a coroutine.

Like the Sequence monad, the Pause monad is not mainly about composing applications of functions. Rather, it is about generating coroutines.

 

Compare Coroutine<'a> and CoroutineStep<'a> to the sequence helper types originally defined in Listing 7.0.3.

 

Listing 8.0.2

type Seq<'a> = unit -> SeqNode<'a>

and SeqNode<'a> =

| None

| Some of SeqItem<'a>

and SeqItem<'a> = {

    item : 'a;

    next : unit -> SeqNode<'a>;

}

 

Similarities:

·        Both Coroutine<'a>, which represents a coroutine, and Seq<'a>, which represents a sequence, include a delay.

·        Both CoroutineStep<'a>, which represents a coroutine step, and SeqNode<'a>, which represents a sequence item, are discriminated unions. Each has one case that represents the termination of the coroutine or sequence, and one case that represents its continuation.

 

Differences:

·        SeqItem<'a> contains both a link to the next sequence item, and data of type 'a. SeqNode.None, the sequence terminator, contains no data.

·        CoroutineStep<'a> contains only a link to the next coroutine step. Only PauseStep.Done, the sequence terminator, contains data.

 

Now we'll define the Pause monad itself, starting as usual with Return and ReturnFrom. We define these instead of Yield and YieldFrom because, unlike the Sequence monad, a Pause monad computation expression typically has only return value.

 

Listing 8.0.3

type PauseMonad () =

    member this.Return (x : 'a) : Coroutine<'a> = fun () -> Done x

    member this.ReturnFrom (x : Coroutine<'a>) : Coroutine<'a> = x

 

As usual, ReturnFrom is straightforward; it is applied to an enriched type value, in this case a coroutine, and simply returns its argument.

 

Return returns a coroutine with only one step, which is the terminator.

 

8.1 Bind

 

The key to the Pause monad is Bind. Bind introduces a delay into a computation expression. This allows the consumer of the computation expression to only evaluate part of it at a time.

 

Listing 8.1.1

    member this.Bind (result : Coroutine<'a>, rest : 'a -> Coroutine<'b>) : Coroutine<'b> =

        fun () ->

            match result () with

            | Done x -> (rest x) ()

            | Paused (p : Coroutine<'a>) -> Paused (this.Bind (p, rest))

 

We'll go through Bind line by line.

 

    member this.Bind (result : Coroutine<'a>, rest : 'a -> Coroutine<'b>) : Coroutine<'b> =

 

The result argument is a coroutine. The rest argument is a function that is applied to the return value from result. rest returns another coroutine, which is evaluated using the return value from result.

 

Because rest is applied to the return value from the result coroutine, we must evaluate the result coroutine to the end before we can do anything with rest.

 

        fun () ->

 

Bind returns a coroutine, so we start with a delay.

 

            match result () with

 

We evaluate the first step of the result coroutine so we can determine whether it is the coroutine terminator or not. In effect, we move the delay from the result coroutine to the return value of Bind. We do this so we can describe how to process the result coroutine step without actually evaluating it yet.

 

            | Done x -> (rest x) ()

 

In this case, the result coroutine step is the coroutine terminator. We do the following.

1.      Get the return value from the result coroutine.

2.      Apply the rest argument to the return value from the result coroutine.

3.      The rest argument returns another coroutine. Evaluate the first step of that coroutine and return the result.

 

            | Paused (p : Coroutine<'a>) -> Paused (this.Bind (p, rest))

 

In this case, the result coroutine step is not the coroutine terminator. We recursively apply Bind to the remainder of the result coroutine, and to an unchanged rest argument. We want to apply the rest argument to the return value of the result coroutine, but we do not have that return value yet; we must continue to evaluate the result coroutine until we reach the coroutine terminator.

 

This is similar to the Combine method of the Sequence monad, in which we had to fully evaluate the first argument using recursive applications of Combine before we evaluated the second argument.

 

We apply the PauseStep.Paused constructor to the result of the recursive application of Bind to identify the result as type CoroutineStep<'b> rather than Coroutine<'b>. Recall Bind has the return type Coroutine<'b>, which is an alias for unit -> CoroutineStep<'b>. We have already written fun () ->, so we need a value of type CoroutineStep<'b> to complete the expression. If we did not apply the PauseStep.Paused constructor to the result of the recursive application of Bind, we would return an expression of type unit -> Coroutine<'b>, which does not match the return type of Bind.

 

The Pause monad abstracts away the insertion of delays to create a coroutine.

 

8.2 Usage

 

Now we look at how to use a coroutine. First we need some helper functions.

 

Listing 8.2.1

let rec race (a : Coroutine<'a>) (b : Coroutine<'a>) : 'a =

    match a (), b () with

    | Done x, _ ->

        do printfn "Coroutine a finished first."

        x

    | _, Done x ->

        do printfn "Coroutine b finished first."

        x

    | Paused a_, Paused b_ -> race a_ b_

 

race is applied to two coroutines. It evaluates one step from each coroutine. If either coroutine is finished, race returns the return value from that coroutine. If neither coroutine is finished, race recursively applies itself to the remainders of the two coroutines.

 

Listing 8.2.2

let pause () =

    fun () -> Paused (fun () -> Done ())

 

pause simply returns a coroutine that contains one step and the terminator. A coroutine computation expression uses pause to yield control. We will see more about this shortly.

 

Listing 8.2.3

let rec get_coroutine (name : string) (count : int) : Coroutine<'a> =

    PauseMonad () {

        do! pause ()

        do printfn "Coroutine %s, step %d." name count

        if count <= 1 then

            return ()

        else

            return! get_coroutine name (count - 1)

    }

 

We'll go through get_coroutine line by line.

 

let rec get_coroutine (name : string) (count : int) : Coroutine<'a> =

    PauseMonad () {

 

get_coroutine returns a new coroutine. The name parameter specifies the name of the coroutine, so it can use side effects to show when it is running. The count parameter indicates how many steps the coroutine has, not including the terminator.

 

        do! pause ()

 

The first thing the coroutine does is yield control. This gives the consumer of the coroutine a chance to check whether the coroutine is finished.

 

        do printfn "Coroutine %s, step %d." name count

 

If the coroutine is not finished, we show the name of the coroutine and the number of steps remaining.

 

        if count <= 1 then

            return ()

 

If this is the last step, we apply Return to indicate this step is the terminator. The coroutine returns unit.

 

        else

            return! get_coroutine name (count - 1)

    }

 

If this is not the last step, we recursively apply get_coroutine. get_coroutine returns another coroutine, which we indicate as the return value of this coroutine by applying ReturnFrom to it.

 

Finally, we create two coroutines and run them as follows.

 

Listing 8.2.4

let coroutine_a = get_coroutine "a" 5

let coroutine_b = get_coroutine "b" 7

do race coroutine_a coroutine_b |> ignore

 

Running the code in Listing 8.2.4 produces the following output.

 

Coroutine a, step 5.

Coroutine b, step 7.

Coroutine a, step 4.

Coroutine b, step 6.

Coroutine a, step 3.

Coroutine b, step 5.

Coroutine a, step 2.

Coroutine b, step 4.

Coroutine a, step 1.

Coroutine b, step 3.

Coroutine a finished first.

 

8.3 How Does This Work?

 

The key to Listing 8.2.3 is the pause function. A coroutine uses pause to yield control. It does so by applying the do! keyword to the result of pause. The do! keyword de-sugars to Bind. As always, Bind is applied to two arguments, result and rest.

·        result contains the coroutine returned by pause. pause simply returns a coroutine that contains one step (case PauseStep.Paused) and the terminator (case PauseStep.Done).

·        rest is a function that represents the rest of the computation expression.

 

Note another difference between the Pause and Sequence monads is that the former uses Bind to introduce a delay to the evaluation of the computation expression, whereas the latter uses Combine and Delay. Why? When we write a function to generate a sequence, such as fibonacci, it's typical for each application of the function to return one sequence item, the evaluation of which we want to delay. When writing a coroutine, we might want to introduce more than one delay into a series of expressions, and these delays might not correspond neatly with function boundaries.

 

Let's look at Bind again.

 

Listing 8.3.1

    member this.Bind (result : Coroutine<'a>, rest : 'a -> Coroutine<'b>) : Coroutine<'b> =

        fun () ->

            match result () with

            | Done x -> (rest x) ()

            | Paused (p : Coroutine<'a>) -> Paused (this.Bind (p, rest))

 

The result argument is the result of pause:

 

fun () -> Paused (fun () -> Done ())

 

As we can see from Listing 8.3.1, Bind applies the result argument to unit. The result is:

 

Paused (fun () -> Done ())

 

Bind then matches this with PauseStep.Paused. So, substituting the value of result, Bind now looks like the following.

 

Listing 8.3.2

    member this.Bind (result : Coroutine<'a>, rest : 'a -> Coroutine<'b>) : Coroutine<'b> =

        fun () ->

            Paused (this.Bind (fun () -> Done (), rest))

 

The recursive application of Bind has a result argument of fun () -> Done (). As we can see from Listing 8.3.1, Bind applies the result argument to unit. The result is Done (). Bind then matches that with PauseStep.Done and returns (rest ()) ().

 

So, substituting the result of the recursive application of Bind, Bind now looks like the following.

 

Listing 8.3.3

    member this.Bind (result : Coroutine<'a>, rest : 'a -> Coroutine<'b>) : Coroutine<'b> =

        fun () ->

            Paused ((rest ()) ())

 

The return value of Bind begins with a delay. This delay is how the coroutine yields control.

 

1.      A coroutine has type Coroutine<'a>, which is an alias for unit -> CoroutineStep<'a>. The delay means the first coroutine step has not been evaluated yet.

2.      The consumer of the coroutine evaluates one step of the coroutine by applying it to unit.

3.      If the coroutine step evaluates to PauseStep.Done, the coroutine is finished.

4.      If the coroutine step evaluates to PauseStep.Paused, it contains a value of type Coroutine<'a>, which is an alias for unit -> CoroutineStep<'a>. The delay means the next coroutine step has not been evaluated yet.

5.      The consumer can now evaluate a step from a different coroutine.

6.      Return to step 1.

 

In Listing 8.3.3, rest is applied to unit. Recall that rest is a function that represents the rest of the computation expression, and to apply it to unit means we do not want to bind any value. rest returns a value of type Coroutine<'a>. In other words, the rest of the computation expression is itself a coroutine.

 

We apply the Coroutine<'a> value to unit to evaluate the first step of the rest of the computation expression. Recall the return value of Bind already begins with a delay, so we do not need an additional delay before we begin to evaluate the rest of the computation expression.

 

Appendix A: Troubleshooting do!

 

Using do! can introduce a couple of gotchas involving F#'s type inference.

 

Recall the signature of Bind is:

 

M<'a> * ('a -> M<'b>) -> M<'b>

 

When you use the do! keyword, F# expects the Bind method to apply the rest argument to unit. That is, it expects the rest argument to have the signature (unit -> M<'b>).

 

Suppose the succeed function from Listing 2.7.2 also returns status information.

 

Listing A.1

let succeed () = Some "Success"

let fail () = None

 

Now, when you compile the code in Listing 2.7.3, the line:

 

do! succeed ()

 

causes the F# compiler to raise the following error.

 

error FS0001: This expression was expected to have type

    string   

but here has type

    unit

 

This is caused by conflicting information about the type of 'a in the signature of Bind. The result argument is Some "Success" (as returned by the succeed function), which is type Option<string>, which means the type of 'a is string. However, the rest argument, which is type ('a -> M<'b>), expects type 'a to be unit.

 

To fix this, we need to overload the Bind method of the Maybe monad class:

 

Listing A.2

type MaybeMonad () =

    member this.Return x = Some x

    // let! Also do! when result : Option<unit>

    member this.Bind (result : Option<'a>, rest : 'a -> Option<'b>) : Option<'b> =

        match result with

        | Some x -> rest x

        | None -> None

    // do! when result : Option<string>

    member this.Bind (result : Option<string>, rest : unit -> Option<'b>) : Option<'b> =

        match result with

        | Some x -> rest ()

        | None -> None

 

The first overload of Bind is used when you either:

1.      Use let!.

2.      Use do! and the result argument to Bind is of type Option<unit>, as in Listings 2.7.2 and 2.7.3. In other words, when the type of 'a is the same, namely unit, for both the result argument (Option<'a>) and the rest argument ('a -> Option<'b>).

 

The second overload of Bind is used when you use do! and the result argument to Bind is of type Option<string>, as in listings A.1 and 2.7.3. In other words, when the result argument is of type Option<string> and the rest argument is of type (unit -> Option<'b>).

 

Note if you were to change the succeed function in Listing A.1 to return a different type, for example Option<int>, you would need to change the second overload of Bind accordingly; that is, so the result parameter is of type Option<int>.

 

Overloading Bind introduces another problem: sometimes F# cannot tell which overload of Bind it should apply for a let! expression. Suppose we add a let! expression to the code in Listing 2.7.3:

 

Listing A.3

let (result : Option<unit>) = MaybeMonad () {

    let! x = Some "Success"

    do! succeed ()

    do! fail ()

    do! succeed ()

    return ()

}

// result = None

 

When you compile this code, the line:

 

let! x = Some "Success"

 

causes the F# compiler to raise the following error:

 

error FS0041: A unique overload for method 'Bind' could not be determined based on type information prior to this program point. A type annotation may be needed. Candidates: member MaybeMonad.Bind : result:Option<'a> * rest:('a -> Option<'b>) -> Option<'b>, member MaybeMonad.Bind : result:Option<string> * rest:(unit -> Option<'b>) -> Option<'b>

 

This happens because the let! expression in Listing A.3 is compatible with both overloads of Bind.

 

The result argument (Some "Success") is of type Option<string>. This matches the type of the result parameter for both the first overload of Bind (Option<'a>) and the second overload (Option<string>).

 

F# then looks at the rest parameter of each overload of Bind.

 

1.      For the first overload of Bind, the rest parameter is of type ('a -> Option<'b>). Recall the type of 'a must be the same for both the result parameter (Option<'a>) and the rest parameter ('a -> Option<'b>). Since the result argument is of type Option<string>, the rest argument must be of type (string -> Option<'b>). Recall applying the rest argument to a value is how you bind a name to that value in the scope of the computation expression. So if you intend to bind the name x to the value "Success", which is of type string, this is the correct overload of Bind to use.

2.      For the second overload of Bind, the rest parameter is of type (unit -> Option<'b>). So if you intend to bind the name x to the unit value, this is the correct overload of Bind to use.

 

The solution is to add a type annotation to the let! expression. Since we want to bind the name x to the value "Success", we annotate x as type string.

 

Listing A.4

let (result : Option<unit>) = MaybeMonad () {

    let! (x : string) = Some "Success"

    do! succeed ()

    do! fail ()

    do! succeed ()

    return ()

}

// result = None

 

The type annotation tells F# that the let! expression should use the first overload of Bind. The code now compiles as expected.

 

Note it is possible to tell F# to use the second overload of Bind by annotating x as type unit:

 

let! (x : unit) = Some "Success"

 

You can verify for yourself that F# applies the second overload of Bind by adding a printfn statement to it.

 

This is almost equivalent to:

 

do! Some "Success"

 

but not quite, since the former gives you a unit value named x and the latter does not.

 

Bibliography

 

Abelson, Harold, and Sussman, Gerald. "The Benefits of Introducing Assignment." Structure and Interpretation of Computer Programs, 17 Apr. 2000, https://mitpress.mit.edu/sicp/full-text/sicp/book/node53.html. Accessed 6 Dec. 2016.

 

Maggiore, Giuseppe, and Costantini, Giulia. Friendly F#. Smashwords ed., 2011.

 

Milewski, Bartosz. "Monads for the Curious Programmer, Part 1." Bartosz Milewski's Programming Cafe, 9 Jan. 2011, https://bartoszmilewski.com/2011/01/09/monads-for-the-curious-programmer-part-1/. Accessed 22 Dec. 2016.

 

MIT OpenCourseWare. "Lecture 5A." MIT 6.001 Structure and Interpretation of Computer Programs, 1986, 08 Apr. 2009, https://www.youtube.com/watch?v=jl8EHP1WrWY. Accessed 06 Dec. 2016.

 

Petricek, Tomas. "Layered Monads." Try Joinads, n.d., http://tryjoinads.org/docs/computations/layered.html. Accessed 9 Dec. 2016.

 

Syme, Don, et al. Expert F# 3.0. 3rd ed., Apress, 2012.

 

Wlaschin, Scott. "Implementing a builder: Delay and Run." F# for Fun and Profit, n.d., http://fsharpforfunandprofit.com/posts/computation-expressions-builder-part3/. Accessed 22 Dec. 2016.

 

Wlaschin, Scott. "Implementing a builder: Zero and Yield." F# for Fun and Profit, n.d., https://fsharpforfunandprofit.com/posts/computation-expressions-builder-part1/. Accessed 22 Dec. 2016.

 

 



[1] Syme, 2015, pp. 479-480.

[2] C-derived languages typically use T to name a template or generic type parameter. F# requires type parameter names to begin with a single quote mark ('). In F# it is more common to use 'a to name a generic type parameter. This article follows the F# convention.

[3] In functional languages, we speak of applying functions to arguments rather than calling them. This is to further distinguish functions from procedures, which have side effects. A side effect is a change of state. Examples include mutating a variable, reading from a file, or writing to the console.

[4] There is a fourth operation, Join, that converts an enriched type value to a less enriched type value. For example, the result of Join (Some (Some 3)) is Some 3. Join is not precisely the opposite of Return, because it cannot convert an enriched type value to a simple type value. That is, trying to evaluate Join (Some 3) would result in an error, because the signature of Join is M<M<'a>> -> M<'a>.

[5] The F# compiler raises this particular error because to evaluate the computation expression in Listing 2.2.3 requires the monad class to define both the Combine and Zero methods. See Combine, Delay, and Zero.

[6] Milewski, 2011.

[7] Unless the monad class defines both the Combine and Zero methods. See Combine, Delay, and Zero.

[8] Wlaschin, n.d. "Implementing a builder: Zero and Yield." See "Operations with and without '!'"

[9] Syme, 2015, pp. 487-491.

[10] Abelson and Sussman, 2000.

[11] MIT OpenCourseWare, 2009. See 1:03:47.

[12] I'm testing my F# code with repl.it. For some reason, the gcd function causes the F# runtime to raise the following error.

Stack overflow: IP: 0x4139a194, fault addr: 0x7ffd04ee0fd8

Stacktrace:

exited with non-zero status

To fix this, I rewrote the gcd function as follows.

let rec gcd (x : int) (y : int) : int =

    if y = 0 then x

    else

        do System.Threading.Thread.Sleep (1)

        gcd y (x % y)

[13] Presumably, Abelson and Sussman were reckoning without monads. The first edition of SICP was published in 1985 and the recordings of the SICP lectures at MIT were made in 1986. Philip Wadler's papers that introduced monads into Haskell were not published until 1992.

[14] Delay is applied to the delayed evaluation of a computation expression. This means that typically its parameter is of type (unit -> M<'a>). However, it is possible to define Return or ReturnFrom to return a value of a type other than M<'a>, in which case the parameter to Delay would also have a different type. It is also possible to define Delay to return a value of a type other than (unit -> M<'a>) or M<'a>. These scenarios are not typical and we will not consider them here.

[15] Again, it is possible to define Run to return a value of a type other than M<'a>. Again, this scenario is not typical and we will not consider it here.

[16] Running the code in Listing 6.4.1 will raise an exception if values of type 'a cannot be combined using the + operator.

[17] Again, it is possible to define Return, ReturnFrom, Zero, or Combine to return a value of a type other than M<'a>. That would change the signature of Delay, which in turn would change the signature of Combine. Again, this scenario is not typical and we do not consider it here.

[18] Wlaschin, n.d. "Implementing a builder: Zero and Yield." See "When is [D]elay called?"

[19] MIT OpenCourseWare, 2009. See 47:22.

[20] Petricek, n.d.

[21] Maggiore and Costantini, 2011. See Chapter 5.

7 comments:

  1. This is amazing work. Please write about other portions of F#, might I suggest Type Providers?

    ReplyDelete
    Replies
    1. Thank you very much Nicholas! To be honest I haven't spent much time on type providers yet; I'm currently trying to wrap my brain around some more monad-related subjects that I hope to add to this tutorial at some point.

      Delete
  2. Superb article! I've spent almost 2 weeks for just reading, can't even imagine how long did it take you to write it.

    ReplyDelete
    Replies
    1. Hi Vladimir, thank you very much for the kind words! It took about six weeks to write, but it's been coming together in my head for at least a year now.

      Delete
  3. In listing 3.0.2, the type of words should be List<string> rather than List<char>.

    Thanks for writing this, and for including references!

    ReplyDelete