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 http://www.eyrie.org/~zednenem/

Having spent several months on this exact problem, I'll say that I consider it pretty unlikely. I wouldn't be very surprised if that was the case.

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 guess cleverness should be concentrated on aging streams properly. But I do see how the ability to extract the diagonal conflicts with such efforts.

Stick with Applicative for this type of thing. Monad will drive you insane :-) In fact, even applicative is far from trivial. ;) For instance, I still can't see how I could implement the <*> operator with stateless streams that don't need to keep track of their local time (needed when combining them with stateful streams, that is).

Gergely -- http://www.fastmail.fm - Access all of your messages and folders wherever you are

For instance, if we consider just join, with the above definition:

join [[1,2],[3]] = [1, _|_]

Which, I think, is fairly undesirable. You can try to avoid bottoms like so: Well, there is a trick you can use here: wrap everything in a Maybe. Not that it helps with the efficiency issue, but at least you can mark the empty spots of the diagonal, since it's possible to check the length of the list before extracting its nth element. Which leads to some kind of MaybeZipList:

newtype MaybeZipList a = MZL { getMZL :: [Maybe a] } deriving Show instance Monad MaybeZipList where return = MZL . repeat . Just MZL mxs >>= f = MZL $ zipWith bind mxs [0..] where bind mx n = do x <- mx let ys = getMZL (f x) if length (take (n+1) ys) <= n then Nothing else ys !! n But it's still not perfect, since the laws only apply modulo extra Nothings at the end of the resulting lists...

This monad works fine for size enforced vectors Sure, I just can't see any good use for those. After all, if you use arrays, you have to keep the whole structure in the memory just to discard most of it.

Thanks for all the answers! Gergely -- http://www.fastmail.fm - Or how I learned to stop worrying and love email again