You’re already familiar with the basic pattern for writing computation expressions, but until now, you haven’t seen how they work beyond a brief glimpse behind the scenes when we created some additional query operators in Extending Query Expressions. To reiterate for the more general case, computation expressions take the following form:

builder-name { computation-expression-body }

Computation expressions are designed around an underlying computation type (sometimes called a monadic type) that we compute by transparently invoking methods exposed by a builder class. In the preceding syntax, builder-name represents a concrete instance of a builder class, and computation-expression-body represents the series of nested expressions that map to the method calls necessary to produce an instance of the computation type. For example, asynchronous workflows are based on Async<'T> and built via AsyncBuilder. Similarly, query expressions are based on QuerySource<'T, 'Q> and built via QueryBuilder.

Builder classes define the operations supported by a computation expression. Defining a builder class is largely a matter of convention, as there are no specific interfaces to implement or base classes to inherit. There aren’t any steadfast rules for naming builder classes, but you typically do so by appending Builder to the underlying type name (for example, AsyncBuilder and QueryBuilder).

Although computation expressions are part of the language, they are really just syntactic sugar—a more convenient way to call into the builder class’s methods. When the compiler encounters what appears to be a computation expression, it attempts to convert the code to a series of method calls through a process called desugaring. This process involves replacing each operation in the computation expression with a call to a corresponding instance method on the builder type (similar to how LINQ query expressions are translated to extension method calls and delegates in C# and Visual Basic). I like to think of the builder class methods as belonging to either of two groups. The first group, listed in Table 12-1, controls various syntactic elements such as bindings, for and while loops, and return values.

The second group of methods, those that control how computation expressions are evaluated, is listed in Table 12-2.

Because computation expressions are intended to be designed in such a way that they apply to a variety of situations, it’s important to keep them as generic as possible. This is reflected in the highly generalized structure of the signatures. For instance, the notation M<_> is used to indicate that the underlying type wraps another value.

It is not necessary to implement each method listed in Table 12-1 in your builder classes. Should you omit any of those methods, though, the corresponding mapped syntax will not be available within the computation expression and the compiler will produce an error. For example, if you try to include a use binding within a custom computation expression but omit the Using method from the builder class, compilation will fail with the message:

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

Likewise, it is not always necessary to implement each method from Table 12-2, but failure to do so in some situations can lead to undesirable results. For instance, not implementing the Delay method will prevent you from composing expressions that yield multiple results. Furthermore, when your computation expression involves side effects, not implementing the Delay method can invoke the side effects prematurely—regardless of where they appear within the expression—because they are evaluated immediately when they’re encountered instead of wrapped up in a function for deferred execution.

Computation expressions can be difficult to understand when discussed in abstract terms focused on the builder classes and method calls. I think it’s far more helpful to walk through some simple implementations to see how the pieces work together. We’ll spend the remainder of the chapter discussing two examples. In particular, we’ll look at the builder implementations, their corresponding expression syntax, and the desugaring process.

In Chapter 7, we looked at a few ways to solve the FizzBuzz problem by iterating over a sequence using Seq.map and using pattern-matching functions with active patterns and partial active patterns to identify which value should be printed. At its core, however, the FizzBuzz problem is essentially just an exercise in sequence transformation. As such, the problem can easily be solved with a computation expression.

When implemented as a computation expression, our FizzBuzz sequence can be constructed in a manner such that it looks and behaves like a standard sequence expression. With the computation expression, though, mapping a number to the corresponding string will be completely abstracted away within the builder class.

Because FizzBuzz transforms integers to strings and carries no intrinsic state, we’ll forego creating an intermediary wrapper type and jump right into creating the builder class incrementally, beginning with the Yield method.

type FizzBuzzSequenceBuilder() =
  member x.Yield(v) =
    match (v % 3, v % 5) with
    | 0, 0 -> "FizzBuzz"
    | 0, _ -> "Fizz"
    | _, 0 -> "Buzz"
    | _ -> v.ToString()

Now that we have a rudimentary builder class, we can create the instance that we’ll use for every FizzBuzz computation expression, like this:

let fizzbuzz = FizzBuzzSequenceBuilder()

That’s it! There’s nothing fancy here; we just create an instance of the class via its primary constructor. To use the instance as a computation expression, we can write something such as the following:

> fizzbuzz { yield 1 };;
val it : string = "1"

As you can see, evaluating the preceding expression doesn’t give us quite the result we’re looking for. Instead of returning a sequence of strings, it gives us only a single string, because so far the builder class doesn’t know how to create a sequence; it simply yields a string based on an integer value. You can see this a bit more clearly in the desugared form, which resembles this:

fizzbuzz.Yield 1

To get a sequence of strings, we could make Yield return a singleton sequence (a sequence containing only a single item), but doing so would complicate implementing other methods, such as For and While. Instead, we’ll extend the builder class to include the Delay method as follows (be sure to re-create the builder instance after updating the builder class to ensure that the fizzbuzz expressions are evaluated using the latest definitions):

type FizzBuzzSequenceBuilder() =
-- snip --
member x.Delay(f) = f() |> Seq.singleton

Evaluating the previous fizzbuzz expression with the Delay method in place gives us a slightly more desirable result:

> fizzbuzz { yield 1 };;
val it : seq<string> = seq ["1"]

Again, the desugared expression can help clarify what’s happening. With the inclusion of the Delay method, the desugared form now looks like this:

fizzbuzz.Delay(fun () -> fizzbuzz.Yield 1)

As it stands now, though, all we’ll ever get from a fizzbuzz expression is a singleton sequence because we can’t yield multiple values. In fact, trying to do so as follows will result in a compiler error indicating that the builder class must define a Combine method:

fizzbuzz {
  yield 1
  yield 2
  yield 3 }

To make the preceding snippet work, we’ll provide two overloaded implementations of the Combine method. The reason for overloading the methods is that, depending on their position within the expression, we’ll either be combining individual strings into a sequence or appending a new string to an existing sequence. We want to be careful that we don’t create a sequence containing a sequence, so we’ll also need to overload the existing Delay method to simply return a supplied sequence. We can implement each of these methods as follows:

type FizzBuzzSequenceBuilder() =
  -- snip --
  member x.Delay(f : unit -> string seq) = f()
  member x.Combine(l, r) =
    Seq.append (Seq.singleton l) (Seq.singleton r)
  member x.Combine(l, r) =
    Seq.append (Seq.singleton l) r

Now evaluating the preceding fizzbuzz expression will result in a sequence containing three strings:

> fizzbuzz {
  yield 1
  yield 2
  yield 3 };;
val it : seq<string> = seq ["1"; "2"; "Fizz"]

When yielding multiple results like this, the desugaring process produces a much more complicated chain of method calls. For instance, desugaring the preceding expression that yields three items results in code that resembles this:

fizzbuzz.Delay (fun () ->
  fizzbuzz.Combine (
    fizzbuzz.Yield 1,
    fizzbuzz.Delay (fun () ->
      fizzbuzz.Combine(
        fizzbuzz.Yield 2,
        fizzbuzz.Delay (fun () -> fizzbuzz.Yield 3)))))

Yielding instances one at a time as we’ve been doing isn’t a very effective way to build a sequence of any length. It would be much nicer if we could compose a fizzbuzz expression using a for loop. For this we need to implement the For method. The approach we’ll take is to simply wrap a call to Seq.map, as shown here:

type FizzBuzzSequenceBuilder() =
  -- snip --
  member x.For(g, f) = Seq.map f g

Now it’s trivial to generate FizzBuzz sequences because instead of using multiple yield expressions, we can nest a single yield expression within a for loop, like this:

fizzbuzz { for x = 1 to 99 do yield x }

Part of the beauty of implementing the Yield, Delay, Combine, and For methods in the builder class is that we can combine the styles for more flexible expressions. For instance, we can yield values directly before yielding them from a loop:

fizzbuzz { yield 1
           yield 2
           for x = 3 to 50 do yield x }

As it’s currently written, the builder class doesn’t support every way you could combine the various expressions, but you shouldn’t have trouble adding the appropriate overloads to support many more scenarios.

For your convenience, here’s the builder class in its entirety:

type FizzBuzzSequenceBuilder() =
  member x.Yield(v) =
    match (v % 3, v % 5) with
    | 0, 0 -> "FizzBuzz"
    | 0, _ -> "Fizz"
    | _, 0 -> "Buzz"
    | _ -> v.ToString()
  member x.Delay(f) = f() |> Seq.singleton
  member x.Delay(f : unit -> string seq) = f()
  member x.Combine(l, r) =
    Seq.append (Seq.singleton l) (Seq.singleton r)
  member x.Combine(l, r) =
    Seq.append (Seq.singleton l) r
  member x.For(g, f) = Seq.map f g

FizzBuzz does a nice job showing how you can use computation expressions to create your own sequence-like constructs with the For and Yield methods, but it’s not particularly practical for everyday computing. For a more useful example, we turn to a common programming task: combining strings.

It has long been established that constructing strings using a StringBuilder is usually more efficient than concatenation. StringBuilder’s fluent interface keeps the code fairly clean, as shown in the following snippet:

open System.Text

StringBuilder("The quick ")
  .Append("brown fox ")
  .Append("jumps over ")
  .Append("the lazy dog")
  .ToString()

Creating a StringBuider instance and chaining calls to the various Append methods doesn’t really fit into the functional-first paradigm, however. The Printf module tries to address this disconnect through the bprintf function, which formats a string and appends it to a StringBuilder instance as shown here:

let sb = System.Text.StringBuilder()
Printf.bprintf sb "The quick "
Printf.bprintf sb "brown fox "
Printf.bprintf sb "jumps over "
Printf.bprintf sb "the lazy dog"
sb.ToString() |> printfn "%s"

All bprintf really accomplishes, though, is replacing an instance method call with a call to a function that accepts a StringBuilder as an argument. What’s more, you still have to manage the StringBuilder instance and pass it to each bprintf call. With a computation expression, not only can you make string construction look like a natural part of the F# language, you can also abstract away the StringBuilder! The computation expression we’ll define shortly will allow us to compose strings using the following syntax:

buildstring {
  yield "The quick "
  yield "brown fox "
  yield "jumps over "
  yield "the lazy dog" }

Here, we chain together a number of strings by yielding them within a buildstring expression. To make this magic happen, we first need to define the underlying type for the expression. For convenience we’ll use a discriminated union called StringFragment to track all of the strings as we yield them. The StringFragment type is defined as follows:

open System.Text

type StringFragment =
| ① Empty
| ② Fragment of string
| ③ Concat of StringFragment * StringFragment
  override x.ToString() =
    let rec flatten frag (sb : StringBuilder) =
      match frag with
      | Empty -> sb
      | Fragment(s) -> sb.Append(s)
      | Concat(s1, s2) -> sb |> flatten s1 |> flatten s2
    (StringBuilder() |> flatten x).ToString()

The StringFragment union has three cases, Empty①, Fragment ②, and Concat ③. The Empty case represents empty strings, while the String case contains a single string. The final case, Concat, forms a hierarchy of StringFragment instances that will eventually be joined together through the ToString method. The beauty of this type is that once the builder is in place, you never have to manually manage these instances or the StringBuilder.

The builder class, which we’ll call StringFragmentBuilder, is similar to the

FizzBuzzBuilder, but instead of creating sequences it creates StringFragments. We already know based on the earlier syntax that we’ll be using the yield keyword, so we’ll need to provide a Yield method. To yield multiple items, we’ll need to implement the Combine and Delay methods as well. It would be nice to allow nested expressions, too, so we’ll implement a YieldFrom method. Here is the StringFragmentBuilder class in its entirety along with the instance used with buildString expressions:

type StringFragmentBuilder() =
  member x.Zero() = Empty
  member x.Yield(v) = Fragment(v)
  member x.YieldFrom(v) = v
  member x.Combine(l, r) = Concat(l, r)
  member x.Delay(f) = f()
  member x.For(s, f) =
    Seq.map f s
    |> Seq.reduce (fun l r -> x.Combine(l, r))

let buildstring = StringFragmentBuilder()

The StringFragmentBuilder class is considerably simpler than FizzBuzzSequenceBuilder because it’s concerned only with mapping strings to StringFragments and controlling execution. Let’s look at each method individually to understand how it’s used within the context of the computation expression.

The first method, Zero, returns a default value for the expression. In this case, we return Empty to indicate an empty string. During the desugaring process, a call to Zero will be inserted automatically in scenarios such as the expression returning unit, or a nested if expression not including an else branch.

The Yield method enables the yield keyword within the buildstring expression. In this implementation, Yield accepts a string, which it wraps in a new Fragment instance.

The YieldFrom method allows you to evaluate a nested buildstring expression through the yield! keyword. This method is similar to Yield, but instead of returning a new StringFragment, it returns the one created by the nested expression.

Each yield or yield! in the computation expression represents the end of a portion of the expression, so we need a way to merge them all together. For that we turn to the Combine method, which essentially treats the remainder of the expression as a continuation. Combine takes two StringFragments and wraps them each within a Concat instance.

buildstring {
  yield "A"
  yield "B" }

buildstring.Combine(
  buildstring.Yield("A"),
  buildstring.Yield("B"))

Concat (Fragment "A", Fragment "B")

buildstring.Combine(
  buildstring.Yield("A"),
  buildstring.Combine(
    buildstring.Yield("B"),
    buildstring.Yield("C")))

Concat (Fragment "A", Concat (Fragment "B", Fragment "C"))

The next method in the StringFragmentBuilder class, Delay, controls when the computation expression is evaluated. When a computation expression has multiple parts, the compiler requires you to define Delay to avoid prematurely evaluating expressions that contain side effects and control execution as expressions are combined. Many of the method calls are wrapped in a function that’s passed to Delay, so that those portions of the expression won’t be evaluated until Delay is invoked. More specifically, the entire expression is wrapped in one Delay call, as are the calls that compute the second argument to each Combine call. The desugared form looks a bit like this (simplified for clarity):

buildstring.Delay(
  fun () ->
    buildstring.Combine(
      buildstring.Yield("A"),
      buildstring.Delay(
        fun () ->
          buildstring.Combine(
           buildstring.Yield("B"),
             buildstring.Delay(
               fun () ->
                 buildstring.Yield("C"))))))

Finally, the For method allows us to use for loops within a buildstring expression. Unlike the FizzBuzz implementation, however, this version employs the Map/Reduce pattern to map the supplied sequence values to individual StringFragment instances and then reduce them into a single StringFragment instance through the Combine method. This flattened instance can then be used in conjunction with other instances.

Now that you’ve seen the builder class and understand how the methods work together through the desugaring process, let’s look at an example that exercises the entire chain. For this, we can use buildstring expressions to build the lyrics to a popular children’s song about a farmer and his dog, Bingo. The song’s simple lyrics and its repetitive nature make it easy to represent programmatically, like this:

let bingo() =
  let buildNamePhrase fullName =
    buildstring {
      yield "And "
      yield fullName
      yield " was his name-o
"
   }
  let buildClapAndSpellPhrases maxChars chars =
    let clapCount = maxChars - (List.length chars)
    let spellPart =
      List.init clapCount (fun _ -> "*clap*") @ chars
      |> Seq.ofList
      |> String.concat "-"
    buildstring {
      for i in 1..3 do yield spellPart
                       yield "
" }
  let rec buildVerse fullName (chars : string list) =
    buildstring {
      yield "There was a farmer who had a dog,
"
      yield! buildNamePhrase fullName
      yield! buildClapAndSpellPhrases fullName.Length chars
      yield! buildNamePhrase fullName
      match chars with
      | [] -> ()
      | _::nextChars -> yield "
"
                        yield! buildVerse fullName nextChars
    }
  let name = "Bingo"
  let letters = [ for c in name.ToUpper() -> c.ToString() ]
  buildVerse name letters

Nested within the bingo function are three functions: buildNamePhrase,buildClapAndSpellPhrases, and buildVerse. Each of these functions constructs a StringFragment through a buildstring expression. At the end of each verse, the buildstring expression includes a match expression to determine whether it should end with the Zero value (implied by returning unit) or recursively include another fully constructed verse via the yield! keyword.

Evaluating the preceding snippet should print the following string (remember, the %O token formats the corresponding argument by calling its ToString method):

> bingo() |> printfn "%O";;
There was a farmer who had a dog,
And Bingo was his name-o!
B-I-N-G-O
B-I-N-G-O
B-I-N-G-O
And Bingo was his name-o!

There was a farmer who had a dog,
And Bingo was his name-o!
*clap*-I-N-G-O
*clap*-I-N-G-O
*clap*-I-N-G-O
And Bingo was his name-o!

There was a farmer who had a dog,
And Bingo was his name-o!
*clap*-*clap*-N-G-O
*clap*-*clap*-N-G-O
*clap*-*clap*-N-G-O
And Bingo was his name-o!
-- snip --

Computation expressions play an important role within F#. Out of the box, they make creating sequences, querying data from disparate data sources, and managing asynchronous operations appear to be a native part of the language by reusing familiar language elements. They’re also fully extensible, so you can define your own computation expressions by creating a builder class that constructs an instance of an underlying type. Creating custom computation expressions can be a tricky endeavor, but once you understand the purpose of each builder class method and the desugaring process, the result can be cleaner, more descriptive code.

It can be difficult to find good information about computation expressions, but there are a few resources you can use for further study. First, the computation expressions series at F# for Fun and Profit (http://fsharpforfunandprofit.com/series/computation-expressions.htm) has plenty of examples covering the range of builder methods. For some more real-world examples, check out the ExtCore project on GitHub (https://github.com/jack-pappas/ExtCore/), which contains several practical applications for computation expressions, such as a lazy list implementation.