Non-monolithic version of 'sequence' for IO monad?
Joe English
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
_______________________________________________
Haskell mailing list
Has...@haskell.org
http://www.haskell.org/mailman/listinfo/haskell
Malcolm Wallace
> 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
Koen Claessen
| > 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.
Josef Svenningsson
> 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
Malcolm Wallace
>| 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
Levent Erkok
> 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.
Josef Svenningsson
> 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
Koen Claessen
| 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.