Strict Identity Monad

Posted on January 7, 2017 by Kwang Yul Seo

In my previous post, I explained the difference between the lazy and strict state monads. What I didn’t mention in the post is that the state monad is not special in this regard. Other monads also can have both lazy and strict variants. For example, transformers package provides both flavors of monads for RWS and Writer monads too.

It is also possible to have identity monads with either lazy or strict semantics. transformers package provides only the lazy variant, but it is not hard to image a strict variant of the identity monad. Here’s the definition of Control.Monad.StrictIdentity defined in strict-identity package.

newtype StrictIdentity a =  StrictIdentity {runStrictIdentity_ :: a }

instance Monad StrictIdentity where
    return !a = StrictIdentity $! a
    (!m) >>= (!k)  = k $! runStrictIdentity  m

The strict identity monad when bound to a function always evaluate its argument. We can see that both BangPatterns and the strict application operator ($!) are used to enforce strict evaluation of arguments.

In this sense, Eval monad from Control.Parallel.Strategies is also an identity monad. It enforces the strict evaluation of the argument with pattern matching.

data Eval a = Done a

instance Monad Eval where
  return x = Done x
  Done x >>= k = k x   -- Note: pattern 'Done x' makes '>>=' strict

In Implementing a call-by-value interpreter in Haskell, I mistakenly used the lazy identity monad to force the evaluation order. We need to keep in mind that transforming a program into a monadic form does not automatically guarantees the evaluation order unless the monad is strict.

UPDATE: Calling arbitrary monads lazy or strict is not appropriate as each monad has varying degree of strictness. For example, the StrictIdentity is more strict than the Eval monad. See the Reddit discussion thread for details.

λ> Control.Monad.StrictIdentity.runStrictIdentity $ do x <- return undefined; return 1
*** Exception: Prelude.undefined
λ> Control.Parallel.Strategies.runEval $ do x <- return undefined; return 1