[Haskell-beginners] Lazy variant of sequence (or other way to approach problem)

[Ertugrul Söylemez]

Nathan Hüsken <nathan.huesken at posteo.de> wrote:

> On 09/27/2012 01:45 AM, Ertugrul Söylemez wrote:
> > Nathan Hüsken <nathan.huesken at posteo.de> wrote:
> > 
> >> In my (SDL based) haskell program, I do:
> >>
> >> events <- liftM ( takeWhile (/= NoEvent)) $ sequence $ repeat
> >> pollEvent
> >>
> >> The execution of this never returns, I am guessing that is because
> >> sequence evaluation never stops.
> >>
> >> But if sequence would be lazy (and assuming pollEvent returns
> >> NoEvent at some point) this should stop, should it not?
> >> Is there a lazy variant of sequence? Or am I missing something here
> >> completely?
> > 
> > The sequence function itself cannot be lazy, and there can't be a
> > lazy variant of it.
> 
> I understand, that it is a bad Idea. But why is it impossible to have
> an lazy sequence? Why can it not wait with the execution of the action
> for the list elements to be evaluated?

Because the Monad class does not have a combinator for that.  Unsafe
interleaving is a feature of the IO monad, not of monads in general.
However I was lying a bit.  Whether sequence is lazy does not depend on
its implementation, but on the monad.  If asking for the head of the
result list only ever depends on part of the computation, then only that
part has to be performed.  This is especially true for the 'Reader e'
and '(->) e' monads (which are the isomorphic, btw.):

    sequence (sin : undefined)
        = liftM2 (:) sin (sequence undefined)
        = \e -> sin e : sequence undefined e

A trivial example is Identity:

    sequence (return 3 : undefined)
        = liftM2 (:) (return 3) (sequence undefined)
        = Identity (3 : runIdentity (sequence undefined))

IIRC monads with that property are called affine monads.  The Maybe
monad does not have this property:

    sequence (Just 3, undefined)
        = liftM2 (:) (Just 3) (sequence undefined)
        = case Just 3 of
            Just x ->
                case sequence undefined of
                  Just xs -> Just (x:xs)
                  Nothing -> Nothing
            Nothing -> Nothing

This will reach the undefined in the inner case, before it gets the
opportunity to deliver a result, because the ability to deliver a
results depends on whether 'sequence undefined' is a Just.  The Maybe
monad's counterpart to unsafeInterleaveIO is:

    unsafeInterleaveMaybe :: Maybe a -> Maybe a
    unsafeInterleaveMaybe ~(Just x) = Just x

With the help of this combinator you can actually write
unsafeLazySequenceMaybe.


> > By the way, if your application is non-continuously rendered, which
> > is suggested by your ignoring of NoEvent, you shouldn't use
> > pollEvent at all.
>
> The Idea of the line what to return all events that happened in the
> current frame (which are to my understanding all events until
> pollEvent returns NoEvent).

Lazy sequence is not what you want for that.  It would be semantically
wrong or at least weird if a second invocation of that action could ever
produce a result, because the first one is supposed to have produced all
events that ever happened.


Greets,
Ertugrul

-- 
Not to be or to be and (not to be or to be and (not to be or to be and
(not to be or to be and ... that is the list monad.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 836 bytes
Desc: not available
URL: <http://www.haskell.org/pipermail/beginners/attachments/20120927/65d8d493/attachment.pgp>