2009/4/1 Patai Gergely <patai_gergely@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