Is Haskell's mapM not lazy?

Question

UPDATE: Okay this question becomes potentially very straightforward.

q <- mapM return [1..]

Why does this never return?

---

Does mapM not lazily deal with infinite lists?

The code below hangs. However, if I replace line A by line B, it doesn't hang anymore. Alternatively, if I preceed line A by a "splitRandom $", it also doesn't hang.

Q1 is: Is mapM not lazy? Otherwise, why does replacing line A with line B "fix this" code?

Q2 is: Why does preceeding line A with splitRandom "solve" the problem?

import Control.Monad.Random
import Control.Applicative

f :: (RandomGen g) => Rand g (Double, [Double])
f = do
    b <- splitRandom $ sequence $ repeat $ getRandom
    c <- mapM return b -- A
    -- let c = map id b -- B
    a <- getRandom
    return (a, c)

splitRandom :: (RandomGen g) => Rand g a -> Rand g a
splitRandom code = evalRand code <$> getSplit

t0 = do
    (a, b) <- evalRand f <$> newStdGen
    print  a
    print (take 3 b)

The code generates an infinite list of random numbers lazily. Then it generates a single random number. By using splitRandom, I can evaluate this latter random number first before the infinite list. This can be demonstrated if I return b instead of c in the function.

However, if I apply the mapM to the list, the program now hangs. To prevent this hanging, I have to apply splitRandom again before the mapM. I was under the impression that mapM can lazily

Answer 1

Well, there's lazy, and then there's lazy. mapM is indeed lazy in that it doesn't do more work than it has to. However, look at the type signature:

mapM :: (Monad m) => (a -> m b) -> [a] -> m [b]

Think about what this means: You give it a function a -> m b and a bunch of as. A regular map can turn those into a bunch of m bs, but not an m [b]. The only way to combine the bs into a single [b] without the monad getting in the way is to use >>= to sequence the m bs together to construct the list.

In fact, mapM is precisely equivalent to sequence . map.

In general, for any monadic expression, if the value is used at all, the entire chain of >>=s leading to the expression must be forced, so applying sequence to an infinite list can't ever finish.

If you want to work with an unbounded monadic sequence, you'll either need explicit flow control--e.g., a loop termination condition baked into the chain of binds somehow, which simple recursive functions like mapM and sequence don't provide--or a step-by-step sequence, something like this:

data Stream m a = Nil | Stream a (m (Stream m a))

...so that you only force as many monad layers as necessary.

Edit:: Regarding splitRandom, what's going on there is that you're passing it a Rand computation, evaluating that with the seed splitRandom gets, then returning the result. Without the splitRandom, the seed used by the single getRandom has to come from the final result of sequencing the infinite list, hence it hangs. With the extra splitRandom, the seed used only needs to thread though the two splitRandom calls, so it works. The final list of random numbers works because you've left the Rand monad at that point and nothing depends on its final state.

Answer 2

Okay this question becomes potentially very straightforward.

q <- mapM return [1..]

Why does this never return?

It's not necessarily true. It depends on the monad you're in.

For example, with the identity monad, you can use the result lazily and it terminates fine:

newtype Identity a = Identity a

instance Monad Identity where
  Identity x >>= k = k x
  return = Identity

-- "foo" is the infinite list of all the positive integers
foo :: [Integer]
Identity foo = do
  q <- mapM return [1..]
  return q

main :: IO ()
main = print $ take 20 foo -- [1 .. 20]