A Kick in the Monads – Creating Extended Builders Part III

So far in this series, we’ve covered some of the methods you can implement for custom computation expressions (aka Monads) in F# such as bind and return, as well as exception and resource management.  For the last part in the series, we’ll take a look at looping constructs.  As we know, F# is a pragmatic multi-paradigm language which supports not only functional features, but imperative ones as well, which include mutability, looping constructs and so on.  Just as regular F# supports for and while loops, we have the ability to take advantage of them as well inside of our computation expressions by implementing two methods.  Let’s start with the while loop.

Implementing the While Method

In order to enable the while loop construct within F#, we need to implement the While method.  This method should have the following signature which takes a guard function which takes no parameters and returns a bool, and a monadic type of unit, and the return is a monadic type of unit.  The reason for the unit return is that in imperative programming we typically perform some side effect inside a looping construct such as a while and for loop.  That’s not to say we can’t return a value, and we’ll talk about that later.

type Builder = 
  member While : guard : unit -> bool *
                 computation : Monad<unit> ->
                 Monad<unit>

We can write a test to express how this should behave once it has been implemented.  In this instance, we want to loop at least once to ensure the loop works and then check our value that has been incremented.  Just as well, we should also write a test to express behavior where it should not increment if the guard is never satisfied.  But in the mean time, let’s focus on the first scenario.

[<Fact>]
let ``while should increment count``() =
  let count = ref 0
  let r = reader {
    while !count < 1 do
      incr count }
  
  runReader r ()

  areEqual 1 !count

Now the question is, how do we implement this?  In the case where our guard function fails, we want to return a monadic type of unit which indicates nothing was done, whereas when it succeeds, we want to bind together our computation and a function which takes no parameters and returns a recursive call to our While loop.

type ReaderBuilder() = 

  member this.While(guard, computation) =
    if guard() then 
      this.Bind(computation, (fun () -> this.While(guard,computation))) 
    else 
      this.Return ()

Now we have the ability to execute any while loop inside our computation expression.  For the most part, this implementation is rather boilerplate and can apply to any number of monad implementations.  Now, let’s move onto implementing for loops.

Implementing the For Method

Just as we needed to implement the While method to enable while loops in our custom computation expressions, we will need to implement the For method to enable for loops.  In order to implement this method, it should conform to the following signature which takes a sequence of any type, and a body which takes an item from the sequence and returns a monadic type of unit.  

type Builder =
  member For : sequence : seq<'T> *
               body : ('T -> Monad<unit>) ->
               Monad<unit>

Let’s take a look at how we might use it through the example of a test.  In this instance, we will simply iterate over a for loop and increment a count and then check its result.  In another test, we should also have an empty collection we try to iterate and check that it does not increment.

[<Fact>]
let ``for should increment count``() =
  let count = ref 0
  let r = reader {
    for i = 0 to 1 do
      incr count }
  
  runReader r ()

  areEqual 1 !count

Now, how might we pull this one off?  In order to do this, we must introduce another method, called Delay.  This method helps us delay any side effects from happening until they are absolutely needed.  Unlike Haskell, F# is an eager functional programming language, so such constructs are necessary.  Let’s look at the signature required for the Delay method below, which takes no parameters and returns a monadic type of T.

type Builder =
  member Delay : unit -> Monad<'T>

Knowing this, we can go ahead an implement both our Delay and For methods.  In the Delay method, we simply bind a monadic wrapped unit with our function, when then in turn will return our Reader<’R,’T>.  Next, we have a For method which takes a sequence and a body to run against each item.  We can reuse the Using method to ensure proper disposal for our IEnumerator<T> and then call While with a function of whether we can move next, and then a delayed function which runs the body function against the current item.  Below is how the implementation should look.

type ReaderBuilder() =

  member this.Delay(f) =
    this.Bind(this.Return (), f)

  member this.For(sequence : seq<_>, body) =
    this.Using(sequence.GetEnumerator(), 
      (fun enum -> 
         this.While(
           (fun () -> enum.MoveNext()), 
           this.Delay(fun () -> body enum.Current))))

Now that we have the looping constructs defined, let’s look at another way of thinking about looping.

Looping and Yield Methods Together

In addition to the style we’ve shown in this series with our Bind/Return for our non-collection types, we also have the ability to define a a yield statement which looks and acts much like the C# equivalent.  Commonly, this yield is used in conjunction with some sort of looping construct.  For example, this construct is already available on sequence expressions inside F#.  

seq { for i = 1 to 10 do
        yield i * 25 }

Such constructs make a lot of sense when we’re thinking about interactive and reactive collections, the latter of which we’ll get to later when we’re talking about the Reactive Extensions Observable monad.  In order to enable the Yield behavior, we simply need to implement the Yield method which should look like the following:

type Builder =
  member Yield : value : 'T -> Monad<'T>

The actual implementation of this for our Reader (should we decide to implement it) should look no different than our Return method.  To either call return or yield is simply a matter of style when dealing with collection versus non-collection based computation expressions.  Just as we defined the ReturnFrom method in a previous post to enable the return! keyword, we can also follow the same logic to implement the YieldFrom method which should have the following signature.

type Builder =
  member YieldFrom : comp : Monad<'T> -> Monad<'T>

Together, this enables such behavior as getting all the files from a directory like the following:

open System.IO

let rec getFiles dir = seq {
  for file in Directory.GetFiles dir do yield file
  for subDir in Directory.GetDirectories dir do yield! getFiles subDir }

Just as well, we could use the yield to show Observable collections such as events:

let getMouseMove() = obs {
  for md in form.MouseDown do
    for mm in form.MouseMove |> Observable.until form.MouseUp do
      yield mm }

It’s a matter of style which one we use, whether we are specifying collection like intent or not.  With that, this should wrap up how to implement a custom computation expression.  Much of this code, outside of Bind/Return TryCatch/TryFinally is boilerplate and can apply to any number of computation expression instances such as the State, Reader, Error, Maybe, and some yet to come such as the mother of all monads, the Continuation Monad, and of course the Observable Monad.

Conclusion

Besides the usual Bind and Return functions that we’ve talked about extensively here, there are quite a few other constructs which allow for rich programming models inside our computation expressions that we just explored.  Whereas LINQ has a rather linear programming model based upon monads, the computation expression includes richer features which include exception handling, control statements, loops, and side effects. 

Still left in this series, we’ll dive into the root of both the F# Async Workflows and Reactive Extensions for .NET, the Continuation Monad as well as the Observable one as well.

No Comments