14

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

Community
  • 1
  • 1
TorosFanny
  • 1,702
  • 1
  • 16
  • 25

3 Answers3

15

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.

John L
  • 27,937
  • 4
  • 73
  • 88
  • I am hazy on whether >>= of IO is lazy,If it is lazy why "sequence $ repeat getLine" can read lines one by one; If it is strict how to explain the common mistake that "wrong = do {fileData <- withFile "<=<.hs" ReadMode hGetContents; putStr fileData}" will get nothing? – TorosFanny Jan 24 '13 at 14:07
  • 1
    @TorosFanny many Haskell IO functions, e.g. `hGetContents`, perform lazy I/O, which circumvents the normal operation of IO's bind by use of the function `unsafeInterleaveIO`. `hGetContents` returns a lazy string that's evaluated on demand, however due to `withFile` the underlying handle is already closed before any of the data is forced. You could have used `unsafeInterleaveIO` for your directory traversal, but it's tricky to reason about and generally not recommended. – John L Jan 24 '13 at 16:25
  • Why does the use of Control.Monad.Identity solves the problem with strict evaluation of `>>=`? – Damian Nadales Jul 07 '15 at 16:55
  • @DamianNadales it has to do with the semantics of how `>>=` is implemented. For Identity, `m >>= k = k (runIdentity m)`. `runIdentity` just unpacks the newtype wrapper. There's nothing in the definition that requires `m` be evaluated, which means this `>>=` is non-strict. – John L Jul 25 '15 at 07:42
13

You're not quite grokking the mechanics of bind:

(>>=) :: Monad m => m a -> (a -> m b) -> m b

Here's an implementation of sequence that only works on 3-length lists:

sequence3 (ma:mb:mc:[]) = ma >>= (\a-> mb >>= (\b-> mc >>= (\c-> return [a,b,c] )))

You see how we have to "run" each "monadic action" in the list before we can return the outer constructor (i.e. the outermost cons, or (:))? Try implementing it differently if you don't believe.

This is one reason monads are useful for IO: there is an implicit sequencing of effects when you bind two actions.

You also have to be careful about using the terms "lazy" and "strict". It's true with sequence that you must traverse the whole list before the final result can be wrapped, but the following works perfectly well:

Prelude Control.Monad> sequence3 [Just undefined, Just undefined, Nothing]
Nothing
jberryman
  • 16,334
  • 5
  • 42
  • 83
  • 1
    thanks for your concern,with your sequence3 (ma:mb:mc:[]), I suddenly realize it. – TorosFanny Jan 24 '13 at 08:56
  • 1
    You're partly right, but some monads (Identity, the lazy version of State, etc) have a lazy implementation of bind. These "lazy monads" will return if you call sequence on an infinite list. – Jeremy List May 21 '14 at 06:17
11

Monadic sequence cannot in general work lazily on infinite lists. Consider its signature:

sequence :: Monad m => [m a] -> m [a]

It combines all monadic effects in its argument into a single effect. If you apply it to an infinite list, you'd need to combine an infinite number of effect into one. For some monads, it is possible, for some monads, it is not.

As an example, consider sequence specialized to Maybe, as you did in your example:

sequence :: [Maybe a] -> Maybe [a]

The result is Just ... iff all elements in the array are Just .... If any of the elements is Nothing then the result is Nothing. This means that unless you examine all elements of the input, you cannot tell if the result is Nothing or Just ....

The same applies for sequence specialized to []: sequence :: [[a]] -> [[a]]. If any of the elements of the argument is an empty list, the whole result is an empty list, like in sequence [[1],[2,3],[],[4]]. So in order to evaluate sequence on a list of lists, you have to examine all the elements to see what the result will look like.

On the other hand, sequence specialized to the Reader monad can process its argument lazily, because there is no real "effect" on Reader's monadic computation. If you define

inf :: Reader Int [Int]
inf = sequence $ map return [1..]

or perhaps

inf = sequence $ map (\x -> reader (* x)) [1..]

it will work lazily, as you can see by calling take 10 (runReader inf 3).

Petr
  • 62,528
  • 13
  • 153
  • 317
  • Although I like the explanation in terms of `Maybe`, this answer isn't necessarily true. – John L Jan 24 '13 at 08:32
  • @JohnL Thanks, you're completely right. I corrected the answer. – Petr Jan 24 '13 at 09:04
  • 1
    Regarding infinite lists, consider the Maybe example. You can in fact determine that the final result is `Nothing` as soon as you run into `Nothing` in the list. `sequence (repeat Nothing) == Nothing`. You do not need to "examine all elements of the input" if you ever encounter a "termination effect" such as `Nothing`. – Dan Burton Jan 29 '13 at 14:04
  • @DanBurton That is true. But if you get an infinite list without such a "termination effect" (like the asker did), you have to loop infinitely. – Petr Jan 29 '13 at 14:12
  • @newacct What exactly isn't true? I say that it's not possible for monads in general, for some it is, for some it isn't. – Petr Jan 08 '14 at 05:37