How to lazily build a Haskell list inside a monad?

Question

Consider the following two almost identical functions:

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

The Haskell petting aspect allows the buildList generate the list without significant overhead in memory, because it generates the head of the list and then creates the tail.

But the monadic version of buildListM seems to use more memory as n gets bigger, because it must first build a tail and then add a head.

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

Answer 1

Many Monads (for example, IO , strict ST s , strict State s ) are "strict" because >>= is strict in its left operand. Others, especially Identity , but also (->) a , lazy State s , lazy Writer q , lazy ST s , are "lazy" in the sense that >>= not strict in its left operand. Consider using toListM in the Identity monad:

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

Here return = Identity and Identity m >>= f = fm , therefore

 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 run time, buildListM actually matches the buildList when run in the Identity monad. This is a special monad, not a monadic nature, which makes things strict.

Sometimes you can do lazy things in "strict" monads in one of two ways:

• Exchange using unsafeInterleaveIO or unsafeInterleaveST .

• Use the more powerful MonadFix abstraction, which allows you to get the result of the calculation before it is executed, but it will not work if you get access to such a result before it is available.