Is Haskell’s mapM not lazy?

by

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.

More Related Contents:

  1. Good examples of Not a Functor/Functor/Applicative/Monad?
  2. Applicatives compose, monads don’t
  3. Operating on a return from a Maybe that contains “Just”
  4. Explain this chunk of haskell code that outputs a stream of primes
  5. A monad is just a monoid in the category of endofunctors, what’s the problem?
  6. A Haskell function of type: IO String-> String
  7. What’s so bad about Lazy I/O?
  8. foldl versus foldr behavior with infinite lists
  9. Is monad bind (>>=) operator closer to function composition (chaining) or function application?
  10. IO happens out of order when using getLine and putStr
  11. What is indexed monad?
  12. How to extract value from monadic action
  13. Large-scale design in Haskell? [closed]
  14. What does the exclamation mark mean in a Haskell declaration?
  15. What is the purpose of the reader monad?
  16. Should do-notation be avoided in Haskell?
  17. Haskell: I/O and Returning From a Function
  18. Expressing do block using only monadic bind syntax
  19. Why do we need monads?
  20. Defining a new monad in haskell raises no instance for Applicative
  21. Concrete example showing that monads are not closed under composition (with proof)?
  22. How to use (->) instances of Monad and confusion about (->)
  23. Non-Trivial Lazy Evaluation
  24. Converting IO Int to Int
  25. How to interpret bind/>>= of the function instance?
  26. Why should Applicative be a superclass of Monad?
  27. How to enumerate a recursive datatype in Haskell?
  28. Haskell – depth for each node in binary tree using Reader monad
  29. In what sense is the IO Monad pure?
  30. How Monads are considered pure?

Leave a Comment