[Haskell-cafe] ZipList monad, anyone?
Dan Doel
dan.doel at gmail.com
Wed Apr 1 11:42:56 EDT 2009
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
More information about the Haskell-Cafe
mailing list