[Haskell-cafe] ZipList monad, anyone?

[David Menendez]

2009/4/1 Luke Palmer <lrpalmer at gmail.com>:
> 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.

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