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

Here's an attempt at a proof that mapM return [1..] doesn't terminate. Let's assume for the moment that we're in the Identity monad (the argument will apply to any other monad just as well):

mapM return [1..] -- initial expression
sequence (map return [1 ..]) -- unfold mapM
let k m m' = m >>= \x ->
             m' >>= \xs ->
             return (x : xs)
in foldr k (return []) (map return [1..]) -- unfold sequence

So far so good. But note that sequence invokes a foldr, which will work from the back of the list. This is already your sign that something is going to go wrong...

-- unfold foldr
let k m m' = m >>= \x ->
             m' >>= \xs ->
             return (x : xs)
    go [] = return []
    go (y:ys) = k y (go ys)
in go (map return [1..])

-- unfold map so we have enough of a list to pattern-match go:
go (return 1 : map return [2..])
-- unfold go:
k (return 1) (go (map return [2..])
-- unfold k:
(return 1) >>= \x -> go (map return [2..]) >>= \xs -> return (x:xs)

Recall that return a = Identity a in the Identity monad, and (Identity a) >>= f = f a in the Identity monad. Continuing:

-- unfold >>= :
(\x -> go (map return [2..]) >>= \xs -> return (x:xs)) 1
-- apply 1 to \x -> ... :
go (map return [2..]) >>= \xs -> return (1:xs)
-- unfold >>= :
(\xs -> return (1:xs)) (go (map return [2..]))

Note that at this point we'd love to apply to \xs, but we can't yet! We have to instead continue unfolding until we have a value to apply:

-- unfold map for go:
(\xs -> return (1:xs)) (go (return 2 : map return [3..]))
-- unfold go:
(\xs -> return (1:xs)) (k (return 2) (go (map return [3..])))
-- unfold k:
(\xs -> return (1:xs)) ((return 2) >>= \x2 ->
                         (go (map return [3..])) >>= \xs2 ->
                         return (x2:xs2))
-- unfold >>= :
(\xs -> return (1:xs)) ((\x2 -> (go (map return [3...])) >>= \xs2 ->
                        return (x2:xs2)) 2)

At this point, we still can't apply to \xs, but we can apply to \x2. Continuing:

-- apply 2 to \x2 :
(\xs -> return (1:xs)) ((go (map return [3...])) >>= \xs2 ->
                         return (2:xs2))
-- unfold >>= :
(\xs -> return (1:xs)) (\xs2 -> return (2:xs2)) (go (map return [3..]))

Now we've gotten to a point where neither \xs nor \xs2 can be reduced yet! Our only choice is:

-- unfold map for go, and so on...
(\xs -> return (1:xs))
  (\xs2 -> return (2:xs2))
    (go ((return 3) : (map return [4..])))

So you can see that, because of foldr, we're building up a series of functions to apply, starting from the end of the list and working our way back up. Because at each step the input list is infinite, this computation will never terminate.

This makes sense if you look at this example (borrowed from another StackOverflow thread, I can't find which one at the moment). In the following list of monads:

mebs = [Just 3, Just 4, Nothing]

we would expect sequence to catch the Nothing and return a failure for the whole thing:

sequence mebs = Nothing

However, for this list:

mebs2 = [Just 3, Just 4]

we would expect sequence to give us:

sequence mebs = Just [3, 4]

In other words, sequence has to see the whole list of monadic computations, string them together, and run them all in order to come up with the right answer. There's no way sequence can give an answer without seeing the whole list.