Going Deeper

---

We’ll start this section with some easier concepts that have less equivalence in C# (at least without some considerable work) but deepen our understanding of F# and add to our “thinking like an F# programmer” toolbox. We’ll begin with closures and discriminated unions, and then move on to active patterns and continuation passing style (CPS). We’ll revisit recursion that uses CPS and then take on two of the most difficult topics for developers new to functional programming: monads and computation expressions.

Closures

Closure is a concept you should be familiar with already, as it plays an important role in lambda expressions in C#. “In programming languages, a closure…is a function …together with a referencing environment—a table storing a reference to each of the non-local variables (also called free variables or upvalues) of that function. A closure—unlike a plain function pointer—allows a function to access those non-local variables even when invoked outside its immediate lexical scope.”[46]

For example, in C# we can demonstrate “print the value of the lexical scope” closure:

Resulting in the output:

We can write something similar in F#:

The previous code results in the same output (each number on a separate line). Closures are relied upon frequently in functional programming because one is often creating partial function applications that pass in values (or functions) that are part of the current lexical scope. One should become very comfortable with closures in order to be proficient at functional programming.

Discriminated unions…

“Discriminated unions provide support for values that can be one of a number of named cases, possibly each with different values and types. Discriminated unions are useful for heterogeneous data; data that can have special cases, including valid and error cases; data that varies in type from one instance to another; and as an alternative for small object hierarchies. In addition, recursive discriminated unions are used to represent tree data structures.”[47]

You can think of discriminated unions as providing additional semantic meaning to a type, by reading a discriminated union as something like “A type that can be an x, a y, or a z (etc.) where x, y, and z are of type a, b, and c, respectively.” This does not hold true in all cases, as we will see later.

…Instead of object hierarchies

Discriminated unions have no direct equivalent in imperative, object-oriented languages. The closest one can get is to implement an object hierarchy. Take for example two shapes: a circle and a rectangle. In an object-oriented paradigm, we would typically write an object model:

In F#, we can implement a discriminated union:

Note that in Visual Studio 2013, we can assign labels to the types: [48]

For our purposes, we’ll stay with the implementation of discriminated unions supported in Visual Studio 2012.

Note that the closest construct in C# would be a class, as illustrated earlier.

We can then calculate the area of our shapes using a function and pattern matching on the type:

Since this function only does matching on a single parameter with lambda expressions for each case, we use this shorthand syntax:

We can then compute the areas of our two shapes (F# console):

Comparing this to the C# code earlier, you could say that we have “de-virtualized” the class hierarchy and explicitly implemented the equivalent of a virtual table.

…Can act like enumerations

A discriminated union does not need to specify the “type of” for the case-identifier. We can construct something similar to an “enum” in C# using (F# console):

The salient difference with C#’s enumerations is that the case-identifiers (here “Truck” and “Car”) are not assigned values—the identifier is just that, an identifier.

…Can be self-referencing

Here I am defining an assembly that can be either a sub-assembly that has a name and further sub-assemblies, or the assembly can be the actual part, having a name.

…Are very useful when working with trees

One finds discriminated unions frequently in describing a node in a tree. For example, the following code defines a binary tree type as being either Empty (with no type) or having a Node with a three-element tuple type, being:

• another tree on the left of the same type,
• a value for the node, and
• another tree of the same type on the right.

This is one way of defining a binary tree. Note that the case-identifier Empty does not specify any “of-type” information—it merely serves as a placeholder identifier, allowing us to construct trees like this (F# console):

With this example we have constructed a small tree that looks like this:

Expression trees are another excellent example of where discriminated unions can be very effective. This example, borrowed from MSDN’s description of discriminated unions,[49] illustrates the concept:

Lessons

• You can use discriminated unions in places where you would otherwise have used object hierarchies.
• Discriminated unions are a useful construct for indicating that the “type-name” consists of specific identifiers, each of which can be of a different type.
• Discriminated unions might seem like typeof(…) in C#, but they’re really not. They’re more like a lookup—given an identifier name, this is its (optional) type.
• Use discriminated unions to attach semantic meaning to a type. The additional semantic meaning is used by the compiler to validate your computations.

Active patterns

Pattern matching is a common technique in functional programming languages. A match expression looks a little like a case statement in an imperative language, but there are significant differences. First, it’s an expression, not a statement. Second, in its most distinctive form, each case represents an alternative way a value of the type of the value being matched on could have been constructed, which provides a powerful generic way to take things of a given type apart. In some languages, the compiler will tell you whether the cases are exhaustive for the type or not. There are various extensions to the basic concept. A noteworthy one specific to F# is active patterns.

“Active patterns enable you to define named partitions that subdivide input data, so that you can use these names in a pattern-matching expression just as you would for a discriminated union. You can use active patterns to decompose data in a customized manner for each partition.”[50]

Similar to a discriminated union in which we create identifiers that may or may not be associated with types, with active patterns we can name “partitions” of a pattern in an active recognizer. For example:

This active recognizer will allow us to match the identifier Prefix when the prefix p is found at the start of the string “s”. Incidentally this code is a “partial active pattern” because we don’t care what the rest (the “_”) of the string is.

We use the active recognizer in a match statement:

This allows us to test for a particular pattern as determined by the active recognizer function. So, for example, this is the output of three pattern-matching tests (F# console):

You can use active patterns to decompose a value into different representations. For example, let’s say you want to decompose the result of a division into either the result itself or a quotient and its remainder. We can write two active patterns (please note that for the following examples, I am not dealing with division by zero):

Now let’s say we have two functions, and among other things, they will print the result either as a floating point result or as a quotient and divisor:

We can then call these two functions and obtain different results based on how we intend to match the input with the active pattern (F# console):

These two examples are certainly trivial. The real power of active patterns comes about when combining several options in the match expression using partial active patterns. For example, let’s say that we do not want a match in the floating point division if the fractional part (everything to the right of the decimal point) is more than two digits, so we use the quotient-remainder format instead. First, let’s write a small helper function to determine the length of the fractional part:

Next, we write a partial active pattern ending in the wildcard (_). This tells us it’s a partial pattern and that we will be returning None or Some:

(The casting is used to force the function to accept only integers and to return an optional float.)

The quotient-remainder pattern stays the same (and it also is not a partial pattern):

Finally, we can write a function that prints the result based on the match with the active pattern:

Now let’s see the result (F# console):

Here we can see that for 10/3, we fail to match the active pattern DivisionResult, but we do match the active pattern QuotientRemainder.

Lessons

• As with other concepts that we’ve already looked at (and will see again soon) the idea is to “invert” the behavior of the function.
• Instead of a complicated if…then…else statement with all the logic built into it, we have created reusable active patterns that can be applied in specific contexts.
• Again, there’s nothing here that can’t be done in an imperative language like C#; it’s simply that functional programming promotes more of a re-use style to programming (if you use it correctly).

Continuation passing style (CPS)

“[A] continuation represents the remainder of a computation given a point in the computation.”[51] Continuations are usually not encountered in imperative programming, but they have definite uses in a functional programming environment, which we’ll discuss further later on. Basically, the idea is that a function is provided with another function that is invoked with the result of the first function’s computation. So for example, rather than writing the database reader with a pipeline to create the Person records:

I could change the implementation of createReader to accept a continuation function and make a call using CPS:

Notice the pipeline (|>) token has disappeared and we’re providing the function to which we want to pass the result. The createReaderCps function is then defined as:

Notice how the last action of the createReaderCps function is to invoke the provided function f with the result of the ExecuteReader() call.

Continuations as inversion of control

We’re used to writing imperative code such that when an invalid condition is discovered, the method handles it in a particular way: throwing an exception, issuing a message, returning null, etc. The “fail” handling is intrinsic to the method. For example, in F# I can create a map of PersonIDs and the records associated with them:

I could access the record using Map.tryFind (F# console):

However, let’s use continuations to specify what we want to do once we find the record. For this, we’ll create a function that takes two functions (the success and fail) as well as the key and map:

Now we can provide the behavior (inversion of control) for the success and failure states. A very trivial example is printing the record value or “not found”:

(In this code I’m de-optioning the result by using the Value property of the option, which is generally not recommended, but in this case, because I know the function is only being called with a matching record, I know that it is safe to implement in this way.)

A more sophisticated example: caching

Let’s say that our records are cached and that if the key isn’t found in the cache, we want to hit the database to return the record and add it to our cache. Since caches are inherently mutable, we’re going to use the System.Collections.Generic namespace to instantiate a simple cache that only handles a single table:

Note: Because we are using a mutable structure, it is not thread-safe! The cache dictionary should be locked before updating and retrieving items.

Next, we create a function that updates the cache given a Person record (which we defined in Chapter 2). Note that this function returns the person record as well, which makes it easier to use with pipelining and binding the record to a variable:

I’m going to create a helper function for constructing a Person record from the SqlDataReader; this is intended to be used when we know we have only one record to read:

Next, we write a function that will retrieve a single record from the database or throw an exception. We will use this function when the “get record from the cache” fails. As this is an example only, it uses a bit of brute force:

Now we can write our continuation function. Note how we require the function onFail as the first parameter, which, if the record isn’t in the cache, we call with the desired ID. This puts it on the caller to provide the implementation for what to do when the record isn’t in the cache, thus turning the implementation inside-out—inversion of control.

Also note the call to TryGetValue. In F#, “out” parameters are returned, along with the method call result, in the form of a tuple. This is a very nice convenience because we can get both the success state of the TryGetValue as well as the value if successful, without resorting to reference types[52]—or worse, a mutable type to receive the out value.

We can now take advantage of partial application by creating two partial functions: one that handles getting data from the database in a “connected” environment, and one that simply throws an exception in a “disconnected” environment:

Let’s give it a test drive (F# console):

Note that the first call to getRecordConnected queries the database for ID 21, and the second call gets the record from the cache. Note also how, in the disconnected state, we can only get records from the cache—otherwise an exception is thrown.

Lessons

• Continuation passing style is a powerful technique for allowing the caller to define how the function continues processing, rather than embedding the processing in the function itself.
• Rethink object hierarchies, where functions are overridden because different behavior is required, using CPS instead.
• Look at your functions and consider what parts could be extracted using CPS to make your program more adaptable to the developer’s needs.
• Combine CPS with partial function application to create re-usable behaviors.

CPS and recursion

Recall that for the compiler to translate recursion to iteration, the recursive call must be the last call made in the function. There are times when this is difficult to achieve, especially when working with two or more different “branches” in a recursive process, such as parsing a binary tree.[53] Using our Tree discriminated union described earlier, we can see CPS is a necessary device to employ when, for example, tail-recursively determining the size of a tree. Let’s look at a straightforward recursive implementation that counts non-empty nodes:

The second half treeSize right 0 is a bit non-intuitive—we increment the accumulator because we have a node. It doesn’t matter whether we do this when recursively calling to process a left branch or a right branch; we just don’t do it for both left and right recursive calls—otherwise we will get double the count.

When we call it using our small tree defined earlier, we see that we get four nodes (F# console):

The problem is, this call is not tail-recursive, so we run the risk of a stack overflow.

To make this tail-recursive, we have to use CPS to pass in the continuation operation:

Here we are using double-recursion with left and right accumulators in a CPS to create a tail-recursive function. This is not easy to wrap one’s head around, so let’s put in some trace statements and see how this is working:

Here is the output (F# console):

We now have a better understanding of how this function works. Refer to Appendix A for a complete “stack” trace based on the previous output. The “magic” of this code happens in-line with that call to f with the sum of the left accumulator + the right accumulator + 1.

A very simple example will hopefully suffice to illustrate this: when the function is called with a single node (Empty, 10, Empty):

• The left side is Empty, so the function passed in is evaluated with the parameter 0, resulting in the inner function being called:

• The right side is Empty, so the function passed in is evaluated with the parameter 0, resulting in the inner function being called:

• This “seed” function is the identity function x -> x; thus 0 + 0 + 1 evaluates to 1. A tree with a single node has, well, one node.

With a more complicated tree, f is the function passed into each recursive call, thus each recursion “nests” the computation for the argument of fun lacc or fun racc. Once the function can evaluate, the value becomes the input for the previously nested function. Again, the trace in Appendix A should make this clearer, and I have illustrated the trace using a pseudo-stack for the function—once the innermost function evaluates, the stack is popped and the value is supplied as the parameter to the previous function on the stack.

A generalized tree recursion fold function

One question to ask when writing in a functional programming style is: “Can this computation be passed-in rather than hardwired in the function itself?” Earlier, in discussing higher-order functions, we showed how to write a function that takes a function as a parameter. This is a very powerful technique, and something similar can be done with continuations. For example, the code that determines the size of the tree can be refactored such that the “continuation,” in this case lacc + racc + 1, is passed in by the caller (I’ve renamed the function to the more generalized foldTree):

This results in a generalized tree fold operation. The previous computation, counting leaves, can now be passed in as part of the call:

We can pass in other computations, for example, adding all the values of the tree, given that a is of type integer:

with the result (F# console):

The “magic” here (besides being an excellent example of higher-order functions) is in the meaning of “accumulator”—in the first case, it’s an incrementing count, and in the second case, it’s a sum.

Lastly, we can employ a partial function application to create re-usable functions:

And now we can call our partial applications (F# console):

Notice in this code example that we have to specify the type for the getTreeSize function, as the type cannot be inferred since it isn’t used in the computation!

The identity function

This is the identity function:

It is an extremely useful construct when “seeding” the call to a recursive function that requires an initial function. This construct is so useful that it is actually an operator:[54]

You can use id anywhere you would otherwise explicitly write (fun x -> x).

Lessons

• CPS is a necessary tool to ensure tail recursion when working with “multi-path” recursion, such as trees.
• Learn to “invert” your thinking about functions—look at what’s inside the function and see if you want to expose it on the outside.
• Write your functions with partial application in mind: what are the “re-use” parameters and the “highly varying” parameters? The “re-use” parameters should go first so that partial function applications can be easily defined, therefore promoting function re-use.
• For further fun (pun intended) take a look at “Catamorphisms, part two.”[55]
• Familiarize yourself with the basic F# operators.[56] This can save you a lot of time when trying to figure out someone else’s code.

Computation expressions

The time has come to deal with the “m” word—monads. “Computation expressions in F# provide a convenient syntax for writing computations that can be sequenced and combined using control flow constructs and bindings. They can be used to provide a convenient syntax for monads, a functional programming feature that can be used to manage data, control, and side effects in functional programs.”[57]

But what is a monad?

“In functional programming, a monad is a structure that represents computations defined as sequences of steps. A type with a monad structure defines what it means to chain operations, or nest functions of that type together. This allows the programmer to build pipelines that process data in steps, in which each action is decorated with additional processing rules provided by the monad. As such, monads have been described as "programmable semicolons"; a semicolon is the operator used to chain together individual statements in many imperative programming languages, thus the expression implies that extra code will be executed between the statements in the pipeline. Monads have also been explained with a physical metaphor as assembly lines, where a conveyor belt transports data between functional units that transform it one step at a time.”[58]

One of the uses for a monad is to retain state without resorting to mutable variables. In this section, we will attempt to wrap our heads around computation expressions and monads as this ends up being a real mind-bender, especially coming from an imperative programming lifestyle. Also, monads have important uses with regard to functional programming and really have no equivalent (except loosely in terms of aspect-oriented programming) in the imperative world.

Continuations, again

Continuations are a key aspect of computation expressions. First off, when we write the following:

We need to realize that this is already a shorthand for the verbose in syntax:[59]

If we now pipe the value into a function of the same name as the identifier, we can rewrite the previous code using CPS:

But now, let’s make this more interesting by actually writing a function for the pipeline operator. The pipeline operator is defined as |> x f = f x. In other words, f is called with the parameter x. We can write our own pipeline operator as a function easily enough:

Now, our three let statements can be written as:

But wait! We can now introduce additional computations in pipeFnc! For example, we can log the values of x:

When we now call our converted let statements, we get (F# console):

We have successfully added additional code that does something behind the scenes and represents a very simple example of a computation expression workflow.

A Logger monad

If instead we move these operations into a class and use the F# computation expression syntactical sugar names, we would start with a class type that defines methods that control how the expression executes. This class type is known as a builder type and is usually given a builder name:

Using a de-sugared syntax so that the use of our LoggerBuilder class looks similar to how we were using the pipeFnc before, we can write:

The usage is equivalent to our CPS version, except that we are using member functions of a class and results in the same output, and the result exactly matches our CPS version.

Now let’s look at the sugared syntax:

The result is the same (F# console):

The Maybe monad (aka “May Be”)

Let’s try our hand at something called the Maybe monad—a computation expression that stops its computation when an invalid “state” is encountered. A simple example of this is doing a series of division operations where the denominator “may be” 0.

The “builder” class is simple enough (in all examples you will find of this computation expression, you will see it called MaybeBuilder, but I prefer the more semantically correct MayBeBuilder, so I will use that in the following examples):

We will also need a divideBy function that returns “None” if dividing by zero, or “Some n” to represent the result:

Now we can execute a workflow. For example (F# console):

Or, if we try dividing by 0 (F# console):

Again, this is just syntactical sugar for a continuation passing style of writing a workflow. One interesting thing about the Maybe monad that is not to be overlooked is that once the computation is deemed to be invalid (it returns “None”), the workflow stops.

A State monad

A state monad does not solve the overall issue of maintaining state throughout the lifetime of the application. For this, the mutable dictionary from the System.Collections.Generic namespace is one solution. Rather, a state monad maintains state within a specific workflow. I will take a simple example of generating pseudo-random numbers[60] (manually!), using a “multiply with carry” method. A mutable implementation in F# would look like this:

Resulting in (F# console):

When we convert this to an immutable form, we need to always return the new state along with the new random number:

Resulting in a tuple of tuples—(random number, (state)):

It certainly is inconvenient to have to extract the value from the tuple and pass on the state every time we make this function call.

To create a state monad, we will first define an operator that allows us to chain functions together. Why? Because getRandomImmutable is a function taking a state and returning a value and a state, and what we’re doing in the previous code by always passing in the new state to get the next random number is a manual form of chaining the function calls. Here’s our new operator:

This operator is borrowed from the functional programming language Haskell, which defines this operator as “Monad sequencing operator with value passing.” Here, x is function that returns a value and a new state given the initial state, s0. The operator is a partial function application because it is provided with x and the next function in the chain, but it isn’t given s0, the initial state.

Let’s look just at what this expression does:

And let’s pretend that x is this function (see how it is returning a tuple, a value, and the next state):

So, for example:

Here we have a “state system” that returns 10 times the current state value and the state incremented by 1.

The next state in the >>= operator is to apply the function f, which is on the right-side of the operator. We can do some useful things here:

We can see the results here (F# console):

Now, the trick here is that we want the continuation function f to have the right signature so that we can continue to use the >>= operator in our monadic sequence. Well, what would this be? It’s a function that takes a value and returns the function that performs the computation, in other words, p. So we can write this:

Now we can write a monadic sequence (F# console):

In other words, p evaluates with the value of 1, calls q which returns the partial function application of p, whose call is “finished” by the caller f v s. We could explicitly specify the state parameter as well:

But with partial function application, we don’t need to!

Now we can take what we learned about the >>= operator and apply it with our random number generator, which already conforms to the form of taking a state and returning a tuple of value and state. All we need to do is write this in a continuation passing style, providing the next function in the chain (F# console):

Now let’s write this with a StateBuilder class:

The Bind function is itself bound to the function we created earlier: a function that takes a state and returns a function that takes a value and a state. Thus, Bind is a function that takes a function accepting a state and returning a state and a value, which is passed to a function taking a value and a state.

That last part is where the continuation passing style comes into effect, allowing us to chain the function calls to getRandomImmutable.

The de-sugared call using the StateBuilder looks like this (note how it’s in the same continuous passing style form as all our previous monads):

Here, we start with a “seed” state that is passed to our monad sequence function, which returns a value and a state. The value is “a” (or “b”, or “c”) and the state “value” completes the partial application of the next call, which is again a function that takes a state and returns a value and a state. Again, if we wanted to be explicit about how state is being handled, we could write:

But it’s the partial function application syntax that allows us to easily translate the first CPS example to the sugared computation expression:

The result (F# console):

Observe the final return from the call to computeRandomValues. It’s a tuple with our return value of 0 and the current state of the random number generator. Simply printing a result isn’t very useful (and it’s a side effect, actually), so let’s modify this function slightly to return a list of random values:

And now the result (having commented out the printfn statement in getRandomImmutable) is a list of our three random numbers from the initial seed (F# console):

Hopefully these exercises have demystified monads and computation expressions. There are several more behaviors that a computation expression “sugars” that you can explore further on the MSDN pages on this topic.

Lessons

• When composing a workflow, the first step is to rewrite the workflow in a continuation passing style. This may involve “helper” functions such as the function defined by the operator >>= to make your continuation calls more readable.
• Once the workflow is behaving correctly in a continuation passing style syntax, you can easily translate it to a sugared computation expression.
• Let’s review one key part of the definition of a monad: “A type with a monad structure defines what it means to chain operations, or nest functions of that type together.” 
• Computation expressions are a way of writing workflows in a sugared syntax.
• Computation expressions are not monads—they are a sugared syntax for implementing monads in a workflow. This is an important differentiation—often, you will see “monads aka computation expressions” in the online literature, which is not accurate.
• When first encountering the state monad, one might think, “Ah, this is how you preserve state in an F# program.” That is not correct; the state monad allows you to preserve state within a workflow.
• Monads are a great way to create workflows where you have to manage data, control logic, and state (side effects). Whenever you encounter the need to perform a workflow (such as reading data from a database, a file stream, and so forth) you will most likely want to take advantage of monads and the CPS that is fundamental to the monad pattern. The computation expression syntax provided in F# makes defining and working with monads much more syntactically comprehensible, thus allowing you to write workflows that would otherwise require mutable members to preserve state.