A Kick in the Monads – Writer Edition

Tuesday, February 2, 2010

In the past couple of Monads posts, we’ve talked briefly about the State and Reader Monads and their potential uses and misuses. Before this series completes, I have a few more to cover including the Writer, Continuation and eventually Observable monad. Today, we’ll get started looking at the Writer Monad and what it can do for us.

What’s the Motivation?

Before we dive deep into what the Writer Monad is, let’s go deeper into the motivation of why we might consider this approach. Like proper developers should when approaching a new concept, we should ask, “What problem are we trying to solve? What’s the motivation here?” else we end up with an over-applied solution to our problem. In this case, let’s take the simple example of logging or tracing in our application. Typically in logging scenarios, we could have the dreaded singleton logger.

let doSomething() =
  Logger.Instance.Log("Beginning doing something")
  
  // Doing something
  
  Logger.Instance.Log("End doing something")

Or perhaps, we could have an injected ILogger instance handed to us via a constructor for the purposes of logging.

type ILogger =
  abstract member Log : message : string -> unit

type DreadedManager(logger : ILogger) =

  member __.DoSomething() =
    logger.Log ("Start doing something")
    
    // Do something

    logger.Log("End doing something")

Or even in other scenarios, we might imagine putting in some AOP behavior for the purposes of logging, but that may of course not be fined grained enough what we need. Instead of doing this, how about generating some output “on the side” in a more functional manner. What if we could instead write something like the following where I add two numbers (simplistic example I know) and then run the computation?

let addNumbers x y = writer {
  do! logMsg (sprintf "Adding %d and %d" x y)
  return x + y };;
  
> val addNumbers : int -> int -> Writer<string list,int>

> addNumbers 3 4 |> runWriter;;
val it : int * string list = (7, ["Adding 3 and 4"])

What we’re seeing is that in my addNumbers function, I take two integer arguments and then log a message and finally return the computed value. What’s more interesting is the fact that we’re logging something physically alters the signature of our method to indicate such a thing is happening. When we compute our function, we not only get the result of 7 that we’re expecting, but also our transaction log as well. Then we can decide what we want to do with the log, for example persist it somewhere, clean it up, etc. So, how can we do this exactly?

Defining the Writer

So, now that we covered the motivations around what it is and why we might use it, let’s look at how we might implement it. In order to maintain both the transaction log and the return value of our method, we’ll need to create a container to hold these values. In this case, we have the Writer<’W,’T> where the ‘W is the writer, which in our case above was a simple string list, and the ‘T is the result of our method. We have a constructing function of our Writer which takes a function with no parameters and returns a tuple of our result and the log.

type Writer<'W,'T> = Writer of (unit -> 'T * 'W)

In addition, we’ll need a way to run our Writer so that we can return our tuple of our value and the log. Let’s create a function called runWriter which computes our Writer.

let runWriter<'W,'T> (Writer w) : ('T * 'W) = w()

Before we get started on the Monad part, there is another piece we need to understand, and that’s the Monoid.

Don’t Avoid the Monoid

Before everyone panics as I’ve brought up a work that sounds like Monad, just rest easy. In fact, it’s much easier to understand than the dreaded M word. A Monoid is an algebraic data structure with a simple associative binary operation and an identity element. Just to bring that into real-world speak, we could have a Monoid for natural numbers with an identity element of 0 and the associative binary operator of addition, or in the case of lists, we could have the identity element of an empty list and an associative binary operator of append. In Haskell, such a thing is implemented through a type class, but since in F#, we don’t have this, let’s instead create a simple interface to encompass the same behavior.

type IMonoid<'T> =
  abstract member mempty  : unit -> 'T
  abstract member mappend : 'T * 'T -> 'T

In this instance, we have two methods we care about, defining our identity (mempty) and our binary operator (mappend). For example, we could implement a Monoid for a simple F# list such as the following:

type ListMonoid<'T>() =
  interface IMonoid<'T list> with
    member this.mempty() = []
    member this.mappend(a, b) = a @ b

This instance in particular will come in handy when we’re talking about a simple logging solution. Our mempty simply returns an empty list of our ‘T objects and our mappend appends the first list to the next. Now, what we need is some sort of registration process for our IMonoid instances so that we could pick one up based upon the incoming type. We could use something like a Common Service Locator to do this and it could be idea for a testing situation, but for now, lets just hand roll a global associations which maps an instance of our IMonoid to our proper type.

type MonoidAssociations private() = 
  
  static let associations = new Dictionary<Type, obj>()
  
  static member Add<'T>(monoid : IMonoid<'T>) = 
    associations.Add(typeof<'T>, monoid)
  
  static member Get<'T>() = 
    match associations.TryGetValue(typeof<'T>) with 
    | true, assoc -> assoc :?> IMonoid<'T>
    | false, _    -> 
        failwithf "No IMonoid defined for %O" <| typeof<'T>

Once we have this defined, we could add instances to this associations class such as a string list implementation:

MonoidAssociations.Add(new ListMonoid<string>())

And now we can use the associations class to call instances of our IMonoid for our functions of mempty and mappend.

let mempty<'T> = MonoidAssociations.Get<'T>().mempty
let mappend<'T> a b = MonoidAssociations.Get<'T>().mappend(a, b)

After that little diversion, we’re now able to get back to the point of the post, the Writer itself. But outside of here, that’s probably the last time you’ll probably use the word Monoid. But, I’m sure now you could impress your friends with the use of said word.

Defining the Builder

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. From our previous creating a Builder posts, we should remember that the Return should have the following signature where we take a value of T and then return it’s Monadic type.

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

Our implementation should take a value of a and construct a Writer with a function with no arguments and return a tuple of our value and an empty Monoid instance.

type WriterBuilder() =

  member this.Return<'W,'T>(a : 'T) : Writer<'W,'T> = 
    Writer(fun () -> a, mempty())

Next, we need to define the bind operation. The point of this method is so that we can bind two monadic types together such as two let! or do! statements. As you might recall, this method takes a Monadic type of ‘T and a function that takes a ‘T and returns a Monadic type of ‘U, and the return type of our bind should be the Monadic type of ‘U.

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

Our implementation should look like the following which creates a Writer with a constructed function which takes no parameters and then calls runWriter on our first Writer m which returns a tuple of our result and a log. We then execute the binder function with our result a which then gives us our second result and a log. Finally, we return a tuple of our second result with our two logs appended to each other.

type WriterBuilder() =

  member this.Bind<'W,'T,'U>(
    computation: Writer<'W,'T>, 
    binder : 'T -> Writer<'W,'U>)  : Writer<'W,'U> =
    Writer(fun () ->
      let (res1, log1)  = runWriter computation
      let (res2, log2) = runWriter (binder res1)
      in  (res2, mappend<'W> log1 log2))

You can find the rest of the methods in order to create a fully functioned builder as a Gist on my GitHub. Now let’s talk about some helper methods. The first, and most useful method is the tell which adds an entry to our log. This function takes a log entry and creates a Writer with a function that takes no arguments and returns a tuple of unit (void for some folks) and our log entry.

let tell logEntry = Writer(fun () -> (), logEntry)

Next up is the listen function. This allows us to listen to our log output that is being generated by our writer. This function takes a Writer and executes it while returning a tuple of our result and a log, as well as a log.

let listen writer = 
  Writer(fun () -> let (result, log) = runWriter writer 
                   in ((result, log), log))

The last function we’ll cover is the censor function. This function returns a new Writer whose result is the same, but the alters the log based upon what is supplied as a parameter

let pass   m = 
  Writer(fun () -> let ((a, f), w) = runWriter m in (a, f w))
  
let censor censoredValue writer = 
  writer { let! result = writer
           return (result, censoredValue)
         } |> pass

Doing Something Useful With It

Ok, our helpers are now defined, so let’s go back and figure out how we’re going to log messages. If you remember from above, we have the tell function which does exactly that. Let’s implement that to take a message and call the tell function with our message wrapped in a list.

let logMsg (message : string) = tell [message]

Now we can try it out in such a function which does some file processing for us with some logging along the way.

let processFiles files = writer {
  try

    do! logMsg "Begin processing files"
    for file in files do
      do! logMsg (sprintf "Processing %s" file) 
      processFile file

    do! logMsg "End processing files" 

  with e -> 
    do! logMsg (sprintf "An exception occurred %s" (e.ToString())) }

At the end of this method, it should return to us a tuple of unit and our log entries that happened along the way such as this:

> processFiles files |> runWriter;;
val it : unit * string list =
  (null,
   ["Begin processing files"; "Processing C:\Test1.txt";
    "Processing C:\Test2.txt"; "End processing files"])

This of course is a pretty contrived and simple example, yet pretty interesting nonetheless. But, in an impure world that we live in with such languages as F#, C#, etc, how practical is it? That’s another matter altogether and good arguments on both sides. Using a writer implies some sort of change to your system to allow for logging, whereas in a more impure environment, logging could take place everywhere. So, when dealing with an impure world already, just go with what you know.

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