<div class="gmail_quote">2009/4/1 Patai Gergely <span dir="ltr"><<a href="mailto:patai_gergely@fastmail.fm">patai_gergely@fastmail.fm</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
Does ZipList have any useful monad instance? The thought came up while<br>
thinking about higher order dataflows and an ArrowApply interface for<br>
Yampa. As a ZipList can be thought of as a function with a discrete<br>
domain, I figured its monadic form could be analogous to the reader<br>
monad, hence:<br>
<br>
instance Monad ZipList where<br>
return = ZipList . repeat<br>
ZipList xs >>= f = ZipList $ zipWith ((!!) . getZipList . f) xs<br>
[0..]<br>
<br>
Correct me if I'm wrong, but it seems to me that f always returning an<br>
infinite list is a sufficient condition for the monad laws to hold.<br>
However, this is painfully inefficient. I assume that bringing FRP-like<br>
switching and some clever data structure (which optimises stateless<br>
streams for starters) into the picture can potentially lead to<br>
constant-time access at least in the case of sequential sampling. Is<br>
there any recent work going in this direction?</blockquote><div><br></div><div>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).</div>
<div><br></div><div>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).</div>
<div><br></div><div>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.</div><div><br></div><div>
Stick with Applicative for this type of thing. Monad will drive you insane :-)</div><div><br></div><div>Luke</div></div>