How to build a Haskell list inside a monad lazily?

Question

Consider the following two nearly identical functions:

buildList 0 = []
buildList n = n : buildList (n - 1)

buildListM 0 = return []
buildListM n = buildListM (n - 1) >>= return . (n :)

The laziness aspect of Haskell allows for buildList to generate the list without much overhead in memory because it generates the head of the list and then builds the tail.

But the monadic version buildListM seems to use more memory as n gets larger because it must build the tail first and then prepend the head.

Is this a good way to build lists inside monads, or is there a more efficient way?

Answer 1

Many Monads (e.g., IO, strict ST s, strict State s) are "strict", in that >>= is strict in its left operand. Others, most notably Identity but also (->) a, lazy State s, lazy Writer q, lazy ST s, are "lazy" in the sense that >>= is not strict in its left operand. Consider applying toListM in the Identity monad:

buildListM 0 = return []
buildListM n = buildListM (n - 1) >>= return . (n :)

Here, return = Identity and Identity m >>= f = f m, so

buildListM 0 = Identity []
buildListM n = Identity . (n :) $ runIdentity (buildListM (n - 1))
             = Identity (n : runIdentity (buildListM (n - 1)))

Since Identity and runIdentity are complete no-ops at runtime, buildListM is actually the same as buildList when run in the Identity monad. It's the particular monad, not the monadic nature, that makes things strict.

You can sometimes do lazy things in "strict" monads in one of two ways:

1. Cheat using unsafeInterleaveIO or unsafeInterleaveST.

2. Use the more powerful MonadFix abstraction which lets you get hold of the result of a computation before it's been executed, but that will fail on you if you access such a result before it's available.