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
1

mtl (or its underlying transformers) package provides two types of State monad; Control.Monad.State.Strict and Control.Monad.State.Lazy. Control.Monad.State re-exports Control.Monad.State.Lazy.

The difference between these two state monads does not matter in most cases, but it may cause unexpected surprises when infinite lists are involved. In this post, I am going to explain the subtle difference between lazy and strict state monads.

Let’s start the discussion with a simple example. The program shown below returns an infinite list of integers [1..] in a lazy state monad. Running the program prints [1,2,3,4,5] as expected.

import Control.Monad.State.Lazy

foo :: State () [Int]
foo = traverse pure [1..]

main = print $ take 5 (evalState foo ())

However, when we replace the import with Control.Monad.State.Strict, the program hangs up.

import Control.Monad.State.Strict

foo :: State () [Int]
foo = traverse pure [1..]

main = print $ take 5 (evalState foo ())

What happened here? The definition of traverse might give us a hint.

instance Traversable [] where
  traverse f = List.foldr cons_f (pure [])
    where cons_f x ys = (:) <$> f x <*> ys

From the definition of traverse, we can see that traverse return [1..] expands to

(:) <$> (return 1) <*> ((:) <$> (return 2) <*> ((:) <$> (return 3) <*> (...)))

(<$>) and (<*>) operators are used to combine values. (<$>) are (<*>) are defined in Functor and Applicative instances of State monad respectively.

Let’s compare the definitions of these operators.

• Control.Monad.Trans.State.Lazy

instance (Functor m) => Functor (StateT s m) where
    fmap f m = StateT $ \ s ->
        fmap (\ ~(a, s') -> (f a, s')) $ runStateT m s

instance (Functor m, Monad m) => Applicative (StateT s m) where
    pure a = StateT $ \ s -> return (a, s)
    StateT mf <*> StateT mx = StateT $ \ s -> do
        ~(f, s') <- mf s
        ~(x, s'') <- mx s'
        return (f x, s'')

• Control.Monad.Trans.State.Strict

instance (Functor m) => Functor (StateT s m) where
    fmap f m = StateT $ \ s ->
        fmap (\ (a, s') -> (f a, s')) $ runStateT m s

instance (Functor m, Monad m) => Applicative (StateT s m) where
    pure a = StateT $ \ s -> return (a, s)
    StateT mf <*> StateT mx = StateT $ \ s -> do
        (f, s') <- mf s
        (x, s'') <- mx s'
        return (f x, s'')

The two definitions are almost the same except for a small difference in pattern matching. Did you find it? Yes, the lazy version uses a tilde ~ in pattern matching on a pair. It is a lazy pattern matching.

Here’s the secret. In the strict version, the pattern matches on the pair forces its evaluation. So traverse pure [1..] never returns until its evaluation is finished. The lazy version avoids this evaluation of the pair using an irrefutable pattern ~(a,w). Evaluation is forced later when the pair is actually needed. This is why we can manipulate infinite lists in a lazy state monad.

But this observation does not imply that we should always prefer the lazy version of state monad because the lazy state monad often builds up large thunks and causes space leaks due to its laziness.