Why the Haskell sequence function can't be lazy or why recursive monadic functions can't be lazy
haskell, lazy-evaluation, loops, monads, recursion
Solution
The problem isn't the definition of `sequence`, it's the operation of the underlying monad. In particular, it's the strictness of the monad's `>>=` operation that determines the strictness of `sequence`.
For a sufficiently lazy monad, it's entirely possible to run `sequence` on an infinite list and consume the result incrementally. Consider:
Prelude> :m + Control.Monad.Identity
Prelude Control.Monad.Identity> runIdentity (sequence $ map return [1..] :: Identity [Int])
and the list will be printed (consumed) incrementally as desired.
It may be enlightening to try this with `Control.Monad.State.Strict` and `Control.Monad.State.Lazy`:
-- will print the list
Prelude Control.Monad.State.Lazy> evalState (sequence $ map return [1..] :: State () [Int]) ()
-- loops
Prelude Control.Monad.State.Strict> evalState (sequence $ map return [1..] :: State () [Int]) ()
In the `IO` monad, `>>=` is by definition strict, since this strictness is exactly the property necessary to enable reasoning about effect sequencing. I think @jberryman's answer is a good demonstration of what is meant by a "strict `>>=`". For `IO` and other monads with a strict `>>=`, each expression in the list must be evaluated before `sequence` can return. With an infinite list of expressions, this isn't possible.
Problem
With the question Listing all the contents of a directory by breadth-first order results in low efficiencyI learned that the low efficiency is due to a strange behavior of the recursive monad functions. Try ``` sequence $ map return [1..]::[[Int]] sequence $ map return [1..]::Maybe [Int] ``` and ghci will fall into an endless calculation. If we rewrite the sequence function in a more readable form like follows: ``` sequence' [] = return [] sequence' (m:ms) = do {x<-m; xs<-sequence' ms; return (x:xs)} ``` and try: ``` sequence' $ map return [1..]::[[Int]] sequence' $ map return [1..]::Maybe [Int] ``` we get the same situation, an endless loop. Try a finite list ``` sequence' $ map return [1..]::Maybe [Int] ``` it will spring out the expected result `Just [1,2,3,4..]` after a long time waiting. From what we tried,we can come to the conclusion that although the definition of sequence' seems to be lazy, it is strict and has to make out all the numbers before the result of sequence' can be printed. Not only just sequence', if we define a function ``` iterateM:: Monad m => (a -> m a) -> a -> m [a] iterateM f x = (f x) >>= iterateM0 f >>= return.(x:) ``` and try ``` iterateM (>>=(+1)) 0 ``` then endless calculation occurs. As we all know,the non-monadic iterate is defined just like the above iterateM, but why the iterate is lazy and iterateM is strict. As we can see from above, both iterateM and sequence' are recursive monadic functions.Is there some thing strange with recursive monadic functions