[Haskell-cafe] ZipList monad, anyone?

[Dan Doel]

On Wednesday 01 April 2009 6:44:35 am Patai Gergely wrote:
> 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.

It is. However, the ZipList type does not restrict one from writing functions 
that don't return infinite lists. 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:

  diag ((x:_):xs) = x : diag (map (drop 1) xs)
  diag ([]:xs)    = diag xs
  diag []         = []

but this version breaks associativity:

   diag . diag $ [[[1],[3,4]],[[],[7,8]]]     = [1,8]
   diag . map diag $ [[[1],[3,4]],[[],[7,8]]] = [1]

So, you seem to have a choice between breaking monad laws or inserting bottom 
placeholders to avoid breaking them.

This monad works fine for size enforced vectors (including if the size is 
infinite, a.k.a. streams, which seems to be what you're actually talking about 
in the first place, so my reply above may be irrelevant), but I'm skeptical 
that one could make something that works appropriately for unrestricted lists.

-- Dan