Much Ado About Monads – Reader Edition

In the previous post, we talked a bit about the State Monad, what it is and how you could use it today in your F# application.  But, with any new piece of information such as this, it should be taken in context, and there are other patterns as well when dealing with a multi-paradigm language such as F#.  We also talked about how the State Monad might not have been the best choice for modeling our web scripting DSL as our browser state is encapsulated in the Browser class, and once it is set, it doesn’t change.  With that, we could turn our eyes to using the Reader Monad as we read from our environment.

Reading From Our Environment

If you recall from the previous post, we had a simple example of keeping track of browser state our ultimate goal was to have the state managed for us underneath the covers.  When dealing with the State Monad, each bind call would not only return us our calculated value, but also our new state as well.  In this case, this was wasteful due to the fact that once the state was set, it never changed, as the state was fully encapsulated inside the Browser object.  So, our ultimate goal would be instead to have our environment set once and then read from it implicitly.  We still want to keep what we have here in terms of our script, but change the underlying mechanism for how it happens:

[<Fact>]
let ``Can find CodeBetter on Bing``() =
  reader {
    do! openPage "http://bing.com"
    do! enterText "q" "CodeBetter"
    do! clickButton "go"
    let! result = containsText "CodeBetter"
    isTrue result
    do! closePage } |> runScript

As the State Monad allows us to plumb a piece of mutable state through our code, the Reader Monad helps us pass immutable state around underneath the covers.  This immutable state could be anything, such as configuration data, environment variables and so on.  Instead of relying on a static dependency like the Environment or ConfigurationManager class within .NET, you might imagine having some abstraction passed around implicitly inside the Reader Monad.  This way, our testing scenarios become easier as we don’t have to try and mock static calls.  Just as well, you can abstract other items behind the scenes as well such as locks, transactions and so forth.

Now that we defined the problem and generally speaking what the Reader Monad is, let’s go ahead and define it.  To do this, we’ll need an overarching container to describe this environment that we’re maintaining.  In this case, we have the Reader<’r,’a> type which the ‘a is our result type and the ‘r is our type of our environment.  This Reader type has a constructor that takes a function which takes our environment parameter and returns our result. 

type Reader<'r,'a> = Reader of ('r -> 'a)

In addition, we’ll need a way to run our Reader so that we can provide it with our environment and return our calculated value.  Let’s create a function called runReader which takes our Reader and our environment, and returns our calculated value.

// val runReader : Reader<'a,'b> -> 'a -> 'b
let runReader (Reader r) env = r env

Before we get to some of our helper functions, let’s get to the monad part.  As you may remember from the previous post, the monad must support three basic rules.  First, a type construction, for each underlying type, we must be able to get the corresponding monadic type.  Second, we must have a function that maps an underlying value to a value in the corresponding monadic type, which is called the return function.  Third, we must have a binding operation where the first argument is a value in a monadic type, its second argument is a function that maps from the underlying type of the first argument to another monadic type, and its result is in that other monadic type.

Let’s first tackle the return function.  You should recall that our return function must have the following signature, keeping in mind that M defined below is our monadic type.

val returnF : 'a -> M<'a>

In the case of the Reader Monad, it should look like this where we take in a value and return a Reader of our environment and return value.

val returnF : 'a -> Reader<'r,'a>

Now, let’s look at the implementation.  In the case of return, we simply return a Reader with the constructed function taking in any value and returning our calculated value.  Our return value should be the same no matter what the environment value that is passed in, so we can safely ignore it.

let returnF a = Reader (fun _ -> a)

Next, we need to define the bind operation.  As you may recall, our bind operation must look like the following code, keeping in mind that M defined below is our monadic type.

val bind : M<'a> -> ('a -> M<'b>) -> M<'b>

In the case of our Reader Monad, it should look like this:

val bind : Reader<'r,'a> -> ('a -> Reader<'r, 'b>) -> Reader<'r, 'b>

Let’s break this down a little more to show what is really going on underneath the covers.

val bind : ('r -> 'a)       -> 
           ('a -> 'r -> 'b) -> 
           ('r -> 'b)

What we see is that the first argument is a function which takes our environment and produces a our calculated value.  Our second argument is a function that takes a value and our environment and then generates our new calculated value.  What our goal is to combine these two functions into a larger function from our environment to our new calculated value. 

let bind m k = 
  Reader (fun r -> runReader (k (runReader m r)) r)

What we did above is make our environment available to both the inside execution and outside execution of our runReader.  Taking these two functions together, the bind and return, we can now create a builder which can provide us some syntactic sugar when writing functions using the Reader Monad.

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

  member this.Bind(m, k) = 
    Reader (fun r -> runReader (k (runReader m r)) r)

By no means are these two the only methods that we could implement, and in fact, there are quite a few more we could do, but that’s for the next post.  Now, we need to revisit some helper functions that are necessary when dealing with the Reader Monad.  For example, how can we get our current environment?  All we have to do is ask:

// val ask : Reader<'r,'r>
let ask = Reader (id)

What this function simply does is return our environment to us by using the id function, which is to say that you return what you are given.  As you recall, our Reader has a constructing function with ‘r –> ‘a and in this case, the ‘a will also be the ‘r.  Also, instead of just returning our environment, what about also providing a function that applies a function over our environment as well?  Let’s implement that as asks:

// val asks : ('r -> 'a) -> Reader<'r,'a>
let asks f = reader {
  let! r = ask
  return (f r) }

One more function to consider is the local function.  This function allows us to execute a given function on a modified environment.  The local function takes a function which modifies the environment as well as a reader to run, and the returns a reader with the changed environment.  This doesn’t change the environment globally, but gives you a way to locally change the environment and execute a function against it.

// val local : ('r1 -> 'r2) -> Reader<'r1,'a> -> Reader<'r2,'a>
let local f m = Reader (f >> runReader m)

The function implementation is fairly straight forward as it returns a Reader with the constructing function that first executes the f function on the environment, and then we run our Reader parameter against this new environment value.  Now that we’ve got some basic ideas, let’s venture into a scenario or two.

A Scenario

Let’s look at a scenario for how we might use the Reader Monad.  One interesting example came from Greg Neverov to handle locks as the environment using this monad.  Let’s look at that a little deeper.  In order to support such a scenario, we’d need a few pieces.  First, we would need the ability to run a particular reader while handling the locking behind the scenes.  Let’s take a look at what that would entail:

open System.Threading

let tryRunLock lock m =
  let lock = box lock
  let lockTaken = ref false
  Monitor.Enter(lock, lockTaken)

  match !lockTaken with
  | true -> try Some(runReader m lock)
            finally Monitor.Exit lock
  | _ -> None

Our tryRunLock function takes a lock and our reader that we wish to execute.  We call Monitor.Enter with our lock that has been boxed and a flag to determine whether the lock has been taken.  We then check whether the lock has been taken and if so, we return Some of our Reader result, else we return None to indicate a failure.

Next, we need the ability to notify all waiting threads that there has been a change in our state.  To do that, we must call the Monitor.PulseAll method. 

let pulseAll = Reader Monitor.PulseAll

Here we partially applied the environment to the Monitor.PulseAll method call so there was no need to specify the argument explicitly.  After this, we need one more function which is to release the lock and block the current thread until we can reacquire it.  To do this, we simply call the Monitor.Wait method.

let wait = Reader (Monitor.Wait >> ignore)

Now we can apply these in a scenario such as moving items between two Stacks in which we pop from one and push to another.  Let’s turn our attention first to the pop function which takes our Stack, and then while the Stack count is zero, then it blocks and waits.  When there is something in the Stack, we simply call Pop and return the value.

open System.Collections.Generic

let pop (stack:Stack<_>) = reader {
  while stack.Count = 0 do return! wait
  return stack.Pop() }

Note that there is a while loop here which we will work on implementing in the next post.  We can now turn our attention to the push function which takes our Stack and a value to push.   If our Stack count is zero, then we call pulseAll which indicates there is a state change.  After this we simply push the value onto the Stack.

let push (stack:Stack<_>) x = reader {
  if stack.Count = 0 then return! pulseAll
  do stack.Push(x) }

Moving on, we can now define a function called move which takes a value from one Stack and moves it to another using locks behind the scenes.

// Our lock object
let lockObj = new obj()

let move s1 s2 = 
  reader { 
    let! x = pop s1 
    do! push s2 x
    return x } 
  |> tryRunLock lockObj

We can run this through to verify our behavior such as the following:

> let s1 = new Stack<int>([1..3])
> let s2 = new Stack<int>()
> let moved = move s1 s2;;

val s1 : Stack<int>
val s2 : Stack<int>
val moved : int option = Some 3

> s2;;
val it : Stack<int> = seq [3]

As you can see, it took the last value from our s1 and moved it to the s2 and did so using locks in a composable fashion.  Let’s look at our original example again.

Back to the Web Example

Revisiting our web example again, we can rewrite much of what we had before using the State Monad as the Reader Monad.  To do this takes very little effort.  First, we must instead of calling getState in the State Monad, we simply ask for the environment and then call the appropriate method on our Browser object.  For example, we can implement the openPage function as follows:

let openPage (url:string) = reader {
  let! (browser : Browser) = ask
  return browser.GoTo url }

We could have also implemented the openPage using the standard Reader constructor as well:

let openPage (url:string) = 
  Reader (fun (browser : Browser) -> browser.GoTo url)

Just as well, we could utilize the asks function as well to execute a function against our environment.  We could rewrite our openPage such as this to take advantage:

let openPage (url:string) = reader {
  return! asks (fun (browser : Browser) -> browser.GoTo url) }

But, in order to make this happen, we need to implement another method on our ReaderBuilder that we implemented above.  The method required is called ReturnFrom which basically does nothing to our Reader but return it.

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

I’ll cover the rest of the other methods you can introduce to your builders in order to take advantage of such things as try/catch, try/finally, using, for, while, etc in the next post.  Following the same pattern on all the other methods from the previous post, we can now execute our script and it will work much as it did for the State Monad.

[<Fact>]
let ``Can find CodeBetter on Bing``() =
  reader {
    do! openPage "http://bing.com"
    do! enterText "q" "CodeBetter"
    do! clickButton "go"
    let! result = containsText "CodeBetter"
    isTrue result
    do! closePage } |> runScript

By using this design pattern, we have a nice way of abstracting this environment that we can create a very flexible syntax.  But with any pattern, it’s about finding the right applications for it.

Conclusion

Once again, by looking at Monads, we can discover what abstractions can be accomplished with them, but just as well, what they are not about.  Certainly, functional languages don’t need them, but they certainly can be quite useful.  When we find repeated behavior, such as maintaining state, this abstraction can be quite powerful.  Practically though in languages such as F#, they can be useful, but other patterns and abstractions can as well.  Find the right abstraction and use it.

In the next post, we’ll cover the additional methods you can add to your builder to enable such things as while loops, for loops, try/catch blocks, and so on before wrapping up this series again.

This entry was posted in F#, Functional Programming, Haskell. Bookmark the permalink. Follow any comments here with the RSS feed for this post.
  • David Taylor-Fuller

    I believe the computed type for local is incorrect it is currently.

    // val local : (‘r1 -> ‘r2) -> Reader -> Reader

    when it really should be

    // val local : (‘r1 -> ‘r2) -> Reader -> Reader

    the function signature for the function composition (>>) is ‘a -> ‘b -> ‘b -> ‘c

    which should force the type of the new reader created in local to be ‘r1 -> ‘a since function composition would expand out to ‘r1 -> ‘r2 -> ‘r2 -> ‘a

  • http://www.research-service.com/employee/joe Joe Holt

    I cant wait for your next post as Im very much interested on adding such things as while loops, for loops and try/catch blocks.