Much Ado About Monads – Creating Extended Builders

In the past two posts in this series, we’ve covered both the State Monad and Reader Monad, not only the motivations, but how you would implement them in F#.  With defining the Return and Bind methods on our computation expression builders, we’re able to do composable linear programming.  But, what we lack is an imperative programming model on top to allow for such things as if statements, for and while loops, and try/catch or try/finally blocks.  Luckily, there is a programmatic model to follow to make these things possible inside of our expressions.  Let’s cover each of these functions in turn and see what each one does and in the process implement them for the Reader Monad.

Explaining the Methods

In order to enable the syntactic sugar we’ve enjoyed in this post series, we have been defining custom builders.  For the most part, we’ve spent the majority of our time defining both Bind and Return.  This time, I’ll walk you through each of these methods that are supported and I’ll show how they should work through the beauty of tests (examples).

Return

First, let’s look back at our Return method.  This method is one of the core monadic methods that takes a value and then encapsulates it within the monadic type.  For example, in the List Monad, the Return method would take a value and then encapsulate it in a list, and in the case of the Reader Monad from the last post, it would simply ignore the environment variable and simply return the value.  Implementing the Return method enables the use of the return keyword which then wraps the value in the monadic type.

To enable the return keyword, we must implement the Return method which looks like the following, keeping in mind that the Monad type is replaced with the actual monadic type.  This method takes a value and returns it encapsulates it within the monadic type.

type Builder() =
  member Return : value : 'a -> ' Monad<'a>

Now that we have a general idea of the format of this method, we can write a test to verify the behavior.  What we’ll do is have the Reader implementation return our expected value and then compare it with the value we get when we run our Reader.

[<Fact>]
let ``Return should enable return``() =
  let expected = 1
  let r = reader {
    return expected }

  let actual = runReader r 0
  areEqual expected actual

Now that we have our test in place, we can now turn our attention to implementing the Return method.  The implementation of the Reader Monad take a value return should return a Reader with the constructed function which ignores the environment parameter and returns our value.

type ReaderBuilder() =
  member this.Return(a) = Reader (fun _ -> a)

Now, let’s move onto ReturnFrom.

ReturnFrom

The next method we’ll implement is ReturnFrom.  This method enables the return! keyword inside of our computation expressions.  Through the use of this keyword, we’re able to simply take a monadic value and return it from our computation expression, as opposed to the return keyword which encapsulates a value in it’s corresponding monadic type.  In order to enable this return! keyword, we’ll implement the ReturnFrom method which has the following signature which takes a monadic value and returns a monadic value.

type Builder =
  member ReturnFrom : computaton : Monad<'a> -> Monad<'a>

We should be able to easily write a test for the Reader Monad method implementation which will invoke the ask method which does nothing more than return a Reader with a function that takes the environment and returns that same environment.  I’ll then call runReader with my Reader and the environment of my expected value and my actual should be the same value.

let ask = Reader (id)

[<Fact>]
let ``ReturnFrom should enable return!``() =
  let expected = 1
  let r = reader {
    return! ask }

  let actual = runReader r expected
  areEqual expected actual

Implementing this method is by far the easiest as we simply return the value we are given.

type ReaderBuilder() =
  member this.ReturnFrom(a:Reader<'r,'a>) = a

Now, let’s move onto the Bind method

Bind

The next method we'll look at the Bind method.  This method, like the Return method are the core monadic methods and provide some of the basic functionality within our computation expressions.  By implementing this method, we enable the ability to use the let! keyword.  When thinking about LINQ, you can think of this method as SelectMany, which by no means is a coincidence as Erik Meijer, the creator of LINQ was also instrumental in the Haskell 98 report.  Let’s look at the method signature required.

 

type Builder =
  member Bind : computation : Monad<'a> *  
                binder : ('a -> Monad<'b>) -> Monad<'b>

Our first argument, the computation is a valid in the monadic type, our second argument is a function that mapes the underlying type of the first argument to another monadic type and the result of this function is that other monadic type.  To explain further, we can explain it in four stages:

  1. The monadic type of the first argument is unwrapped to expose any number of values of type ‘a.
  2. The binder function is applied to all values to create monadic types of Monad<’b>.
  3. The monadic result from the function is also unwrapped to expose it’s values of 'type ‘b.
  4. The monadic structure of Monad<’b> is then reassembled over all results, which then is represented by a single value of Monad<’b>.

Let’s now write a test that defines the expected behavior of the Bind function and its syntactic sugar equivalent of let!.  We’ll first create a reader which asks for the environment and then we’ll return that value much as we’ve done before.  Then, we’ll ensure that our expected value of 1 is returned when we call runReader.  

[<Fact>]
let ``Bind should enable let!``() =
  let expected = 1
  let r = reader {
    let! env = ask
    return env }

  let actual = runReader r expected
  areEqual expected actual

Implementing this method is quite straight forward such as the following:

type ReaderBuilder() =
  member this.Bind(comp, binder) = 
    Reader (fun env -> runReader (binder (runReader comp env)) env)

The Bind method takes two parameters, the computation which is our Reader, and then our second parameter of our binder.  We break down the Bind into the following steps:

  1. Run the reader of our computation (comp) and our environment (env)
  2. Apply the binder function to the result of step 1
  3. Run the reader against the result of step 2 and our environment

Next, let’s turn our attention to the Zero method.

Zero

The Zero method, when provided, gives us the ability to execute expressions that have no value.  Examples of this could include a return with an if without a matching else and the condition was false, or in the case of the List Monad, an empty list.  In order to enable this functionality, our Zero method must look like the following:

type Builder =
  member Zero : unit -> Monad<unit>

We can write a test to define the expected behavior of this method by simulating a false condition of an if statement without a corresponding else statement, such as the following:

[<Fact>]
let ``Zero should allow no else branch``() =
  let called = ref false
  let r = reader {
    if false then
      called := true }

  runReader r 1
  isFalse !called

In this case, we have an if statement that should never execute and to ensure that we change a called to true.  In the end, our called should always be false and our computation expression should execute normally and return a unit value.  Implementing the Zero method is quite simple for the Reader Monad in that we simply return a unit value.  

type ReaderBuilder() =
  member this.Zero() = this.Return ()

In the above method, we have the Zero method calling the Return method with unit, which then wraps it in our Reader type.  Next, let’s move onto Combine.

Combine

The last method we’re going to cover in this post is the Combine method.  This method, when given two computations, runs the first which returns unit (or void), and then returns the value of the second.  This way, we can link together such things as if statements, for and while loops, etc which all return unit, with another computation.  In order to make this functionality available, we should implement the Combine method which has the following signature.

type Builder =
  member Combine : comp1 : Monad<unit> * comp2 : Monad<'a> -> Monad<'a>

As you can see, we have two computations, comp1 and comp2.  The first computation returns unit (or void to others), the second returns a generic type, and our return is our second parameter.  This is useful in such scenarios as the State Monad where the state could change within this unit computation and we need to feed it to the next binding call.  Now, we need a test to show how this should work for the Reader Monad.  In this case, let’s have an if statement (which should have no return value), and then we return our original value we fed to the Reader Monad.  As with our tests, we want to do nothing more than what is required to show off this functionality, and in this instance we’re doing very little but combining the result of an if statement with a return.

[<Fact>]
let ``Combine should combine if statement``() =
  let expected = 0
  let r = reader {
    let! x = ask
    
    if true then ()

    return x }
    
  let actual = runReader r expected
  areEqual expected actual

In order to implement this method, we could use our existing Bind method to express a Combine.  In order to do so, we can supply the first Reader as the first argument to our Bind, and our second argument to the Bind would be a function which takes no arguments and returns the second Reader instance.

type ReaderBuilder() =
  member this.Combine(r1, r2) =
    this.Bind(r1, fun () -> r2)

What’s Next?

We’ve still got a bit left to cover to enable some imperative programming structures inside our custom computation expressions.  These include:

  • For
  • While
  • Try/Catch
  • TryFinally
  • Yield/YieldFrom
  • Using

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.  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. 

We have a bit more in this series as well when talking about Monads/Computation Expressions as we work our way towards the Continuation Monad and the basis for the Async Workflow and the Reactive Extensions.

No Comments