[Haskell-cafe] ZipList monad, anyone?

[Luke Palmer]

2009/4/1 Patai Gergely <patai_gergely at fastmail.fm>

> Does ZipList have any useful monad instance? The thought came up while
> thinking about higher order dataflows and an ArrowApply interface for
> Yampa. As a ZipList can be thought of as a function with a discrete
> domain, I figured its monadic form could be analogous to the reader
> monad, hence:
>
> instance Monad ZipList where
>    return = ZipList . repeat
>    ZipList xs >>= f = ZipList $ zipWith ((!!) . getZipList . f) xs
>    [0..]
>
> Correct me if I'm wrong, but it seems to me that f always returning an
> infinite list is a sufficient condition for the monad laws to hold.
> However, this is painfully inefficient. I assume that bringing FRP-like
> switching and some clever data structure (which optimises stateless
> streams for starters) into the picture can potentially lead to
> constant-time access at least in the case of sequential sampling. Is
> there any recent work going in this direction?


Having spent several months on this exact problem, I'll say that I consider
it pretty unlikely.  To give you an idea of the frustration involved, the
end of that time was no longer spent trying to implement it, but rather
trying to characterize a mathematical reason that it was impossible (to no
avail).

A clever data structure might give you logarithmic or even amortized
constant time access in sequential cases, but you probably will not have
good garbage collection properties (all data will remain for all time).

I don't mean to be a buzzkill without giving any concrete evidence. I've
(intentionally) distanced myself from these problems for a few months, so
explaining is difficult.

Stick with Applicative for this type of thing.  Monad will drive you insane
:-)

Luke
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090401/0212ac1e/attachment.htm