2009/4/1 Luke Palmer
2009/4/1 Patai Gergely
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.
Yes, although you should use an actual infinite list type if you're depending on that. In fact, the Stream package provides an infinite list type with Applicative and Monad instances.
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).
The problem is that there is no sequential access to optimize. If you
break (>>=) into fmap and join, you can see that join has to get the
diagonal. Each inner list is accessed once.
Really, you're better off just using Nat -> a. The primary advantage
to using a list over a function is avoiding recomputation, but nothing
is getting recomputed here.
--
Dave Menendez