Type Slowly

What’s the difference between the strict and lazy identity monads?

I came across this question while reading  Simon Marlow et al’s paper “Seq no more: better strategies for parallel Haskell”, which describes the Eval monad (representing the result of a parallel computation) as being equivalent to the Strict identity monad. 

Now, it may seem obvious that it’s possible to have identity monads with either lazy or strict semantics, but I’d never come across them in the wild before, and it took a little bit of thinking to fully understand the difference between them.

First, it’s important to note that when we describe a monad as being lazy or strict, we’re describing the semantics of the bind operation with respect to the monadic value it’s operating on. So, a strict monad when bound to a function will always evaluate its argument, whereas a lazy monad will only evaluate its argument if the bound function references it.

The key to implementing this lies in the fact that pattern-matching arguments to a function forces strict evaluation - in order to carry out a pattern-match, the argument must be evaluated. Therefore, if we define our bind function to pattern-match against its first argument, we are implicitly affording strict semantics to our monad. If, on the other hand, we do not pattern match against the first argument, our monad will have lazy semantics. In code:

import Control.Monad

data LazyID a = LazyID { runLazyID :: a }

instance Monad LazyID where
  return = LazyID
  m >>= f = f (runLazyID m)

data StrictID a = StrictID { runStrictID :: a }
instance Monad StrictID where
  return = StrictID
  (StrictID v) >>= f = f v