Non-monolithic version of 'sequence' for IO monad?
Is there any way, short of using unsafePerformIO, to implement a combinator f :: [IO a] -> IO [a] in a way that the the result is produced lazily? The problem with sequence :: (Monad m) => [m a] -> m [a] sequence = foldr (liftM2 (:)) (return []) where liftM2 f a b = do { a' <- a; b' <- b; return (f a' b') } is that it consumes the entire input before producing a result. Thanks for any advice, --Joe English jenglish@flightlab.com
Is there any way, short of using unsafePerformIO, to implement a combinator f :: [IO a] -> IO [a] in a way that the the result is produced lazily?
The problem with sequence :: (Monad m) => [m a] -> m [a] sequence = foldr (liftM2 (:)) (return []) where liftM2 f a b = do { a' <- a; b' <- b; return (f a' b') } is that it consumes the entire input before producing a result.
Are you *really* sure that the latter consumes its entire input before producing any result? It looks pretty lazy to me, and I seem to be able to give it an infinite list of computations and yet start receiving results immediately.... Regards, Malcolm
Malcolm Wallace wrote: | > sequence :: (Monad m) => [m a] -> m [a] | > sequence = foldr (liftM2 (:)) (return []) | Are you *really* sure that the latter consumes its | entire input before producing any result? It looks | pretty lazy to me, and I seem to be able to give it an | infinite list of computations and yet start receiving | results immediately.... This is not true, as the following example demonstrates: main :: IO () main = sequence [ return i | i <- [1..] ] >>= print The IO monad is strict. This means that one cannot look at the result `a' of a computation of type `IO a' before all the IO in that computation is done. (Note that in other monads that are not strict, the above computation works without problems.) The function `unsafeInterleaveIO' in Hugs, GHC and HBC (and NHC?) can turn a computation of type `IO a' into an "empty" computation of type `IO a', which means we can start looking at the result before any IO is done. This operator is often used inside implementations to implement functions like `hGetContents' and `readFile'. /Koen.
On Tue, 6 Nov 2001, Koen Claessen wrote:
Malcolm Wallace wrote:
| > sequence :: (Monad m) => [m a] -> m [a] | > sequence = foldr (liftM2 (:)) (return [])
| Are you *really* sure that the latter consumes its | entire input before producing any result? It looks | pretty lazy to me, and I seem to be able to give it an | infinite list of computations and yet start receiving | results immediately....
This is not true, as the following example demonstrates:
main :: IO () main = sequence [ return i | i <- [1..] ] >>= print
The IO monad is strict. This means that one cannot look at the result `a' of a computation of type `IO a' before all the IO in that computation is done.
The statement "The IO monad is strict" is a bit too strong. Indeed, the IO monad is strict in all implementations (and rightly so). But I cannot find anything in the report saying that the IO monad is strict.
(Note that in other monads that are not strict, the above computation works without problems.)
Let me elaborate on the strictness of a monad. The strictness of a monad depends on how one implements the `bind' function. If the monad has a strict bind then in examples like Koen's the print function will never be called. If bind is lazy then the list will be produced incrementally. For many monads it makes sense to have both a strict and a lazy instance. One example is the ST monad which comes in both flavours. So why is it useful to have both? The above situation shows that one may expect a monad to have a lazy behavour. In these cases the lazy instance is good. But lazy monads can have really bad memory behaviour and that is why the ST monad is strict by default. For instance, monadic tail calls can be implemented efficiently with with strict instances but not with lazy ditto. Why am I writing all this? I think the previous discussion shows that the Haskell community is not very aware of the subtleties in strict versus lazy monads. I hope I've shed some light, or at least made people start to think about it. All the best, /Josef
On Tuesday 06 November 2001 01:20 pm, Josef Svenningsson wrote:
Let me elaborate on the strictness of a monad. The strictness of a monad depends on how one implements the `bind' function. If the monad has a strict bind then in examples like Koen's the print function will never be called. If bind is lazy then the list will be produced incrementally.
Can you elaborate? The bind for the Maybe monad is strict in its first argument. Is the Maybe monad strict in your sense? If that's the case, we should understand what is a bottom for the type IO a (for some type a), before deciding whether the IO monad is strict or not. Do you have a definition for that? Coming back to IO monad, I'd rather say it's eager (trying to avoid the word strict, but that's what I mean) in its actions, but certainly not in the values it produces. All the actions will be performed before you can view any results, but the results themselves are lazily produced. My favorite example is: fixIO (\cs -> getChar >>= \c -> return (c:cs)) you wait until getChar is done, but the final list is produced lazily. I'd really love to see a more formal definition of the strictness of a monad, especically for internal monads like IO and ST. -Levent.
On Tue, 6 Nov 2001, Levent Erkok wrote:
On Tuesday 06 November 2001 01:20 pm, Josef Svenningsson wrote:
Let me elaborate on the strictness of a monad. The strictness of a monad depends on how one implements the `bind' function. If the monad has a strict bind then in examples like Koen's the print function will never be called. If bind is lazy then the list will be produced incrementally.
Can you elaborate? The bind for the Maybe monad is strict in its first argument. Is the Maybe monad strict in your sense? If that's the case, we should understand what is a bottom for the type IO a (for some type a), before deciding whether the IO monad is strict or not. Do you have a definition for that?
Yes, the Maybe monad is strict in my sense. So what I really mean by a strictness of a monad is the strictness of the first argument of bind. I usually think of it in terms of the state monad. Suppose we have: type StateM s a = s -> (s,a) The we can give two reasonable definitions of bind: bind1 m f = \s -> let (s',a) = m s in f a s' bind2 m f = \s -> case m s of (s',a) -> f a s' bind1 corresponds to my intuitive notion of a lazy bind. bind2 is the strict version. In bind1, the expression m s will not be computed until a of s' is needed in f. This is ofcourse nice since we all like to program in a lazy language. But it can really bit when it comes to memory behavour. bind2 on the other hand allows for efficient tail calls while it computes m s right away, not leaving much room for lazyness. But when it comes to the IO monad I'm not shure would be bottom for a type IO a.
Coming back to IO monad, I'd rather say it's eager (trying to avoid the word strict, but that's what I mean) in its actions, but certainly not in the values it produces. All the actions will be performed before you can view any results, but the results themselves are lazily produced. My favorite example is:
fixIO (\cs -> getChar >>= \c -> return (c:cs))
you wait until getChar is done, but the final list is produced lazily.
Yes, you're absolutely correct. I must admit that my understanding of the lazyness and eagerness of the different operations in the IO monad is lacking. My statement of the IO monad being strict is an over simplification.
I'd really love to see a more formal definition of the strictness of a monad, especically for internal monads like IO and ST.
So would I. Cheers, /Josef
Josef Svenningsson wrote: | bind1 m f = \s -> let (s',a) = m s | in f a s' : | bind2 m f = \s -> case m s of | (s',a) -> f a s' There are two more binds I would like to add to this list: bind3 m f = \s -> s `seq` bind1 m f s bind4 m f = \s -> s `seq` bind2 m f s In other words, here we make sure that we have evaluated the initial state completely before we continue. Could you eleborate on these a little bit more? /Koen.
| I seem to be able to give it an | infinite list of computations and yet start receiving | results immediately....
This is not true, as the following example demonstrates:
main :: IO () main = sequence [ return i | i <- [1..] ] >>= print
You are right. I was confused between the visible results of the action and the functional result. For example, sequence [ print i | i <- [1..] ] outputs the numbers to screen immediately, but never produces a value. Regards, Malcolm
participants (5)
-
Joe English -
Josef Svenningsson -
Koen Claessen -
Levent Erkok -
Malcolm Wallace