Sun 4 May 2008

Kefer asked a question in the comments of my post about (co)monadic (co)strength about Uustalu and Vene's ComonadZip class from p157 of The Essence of Dataflow Programming. The class in question is:

class Comonad w => ComonadZip w where czip :: f a -> f b -> f (a, b)

In response I added Control.Functor.Zip [Source] to my nascent rebundled version of category-extras, which was posted up to hackage earlier today.

Putting aside the dual operation for the moment, we can dispense with the inverse of zip quite simply, for much the same reason that every functor in Haskell is strong, every functor in haskell is unzippable:

unfzip :: Functor f => f (a, b) -> (f a, f b) unfzip = fmap fst &&& fmap snd

On the other hand the question of what Functors are zippable is a little trickier. Allowing for a circular definition between fzip and fzipWith we can start with the following class for which you have to implement at least one of fzip or fzipWith.

class Functor f => Zip f where fzip :: f a -> f b -> f (a, b) fzip = fzipWith (,) fzipWith :: (a -> b -> c) -> f a -> f b -> f c fzipWith f as bs = fmap (uncurry f) (fzip as bs)

Here we set aside the restriction that we only be able to Zip a comonad, and simply require that if the functor in question is a comonad, then it is a "symmetric semi-monoidal comonad", which is to say that zipping and then extracting yields the same result as extracting from each separately. You may note a lot of similarity in the above to the definition for Control.Functor.Zap the Dual functor from the other day.

Now, we can throw ourselves with reckless abandon at the easy cases:

instance Zip Identity where fzipWith f (Identity a) (Identity b) = Identity (f a b) instance Zip [] where fzip = zip fzipWith = zipWith instance Zip Maybe where fzipWith f (Just a) (Just b) = Just (f a b) fzipWith f _ _ = Nothing

But we note that Either causes us to break down, we can't handle the 'mixed' cases of Left and Right cleanly. We can however use the same 'cheat' that makes the Writer Monad work, however, and rely on an instance of Monoid, and leaving the left hand side of the bifunctor unchanged to enable us to define:

instance Monoid a => Zip (Either a) where fzipWith f (Left a) (Left b) = Left (mappend a b) fzipWith f (Right a) (Left b) = Left b fzipWith f (Left a) (Right b) = Left a fzipWith f (Right a) (Right b) = Right (f a b)

and similarly:

instance Monoid a => Zip ((,)a) where fzipWith f (a, c) (b, d) = (mappend a b, f c d)

Unfortunately the instance for ((,)a) is a little less than satisfying, what we really want to say there is that we have a Bifunctor and that it has two parameters that can be zipped together:

class Bifunctor p => Bizip p where bizip :: p a c -> p b d -> p (a,b) (c,d) bizip = bizipWith (,) (,) bizipWith :: (a -> b -> e) -> (c -> d -> f) -> p a c -> p b d -> p e f bizipWith f g as bs = bimap (uncurry f) (uncurry g) (bizip as bs)

Now, we can define a more satisfying instance for (,):

instance Bizip (,) where bizipWith f g (a,b) (c,d) = (f a c, g b d)

However, by its very nature, an instance for Either eludes us.

Now, we can define a "Bifunctor-Functor-Functor Bifunctor" transformer that takes a bifunctor and a pair of functors to wrap it around, and derives a new bifunctor and lift the zippability of each of the parts to the zippability of the whole:

newtype BiffB p f g a b = BiffB { runBiffB :: p (f a) (g b) } instance (Functor f, Bifunctor p, Functor g) => Bifunctor (BiffB p f g) where bimap f g = BiffB . bimap (fmap f) (fmap g) . runBiffB instance (Zip f, Bizip p, Zip g) => Bizip (BiffB p f g) where bizipWith f g as bs = BiffB $ bizipWith (fzipWith f) (fzipWith g) (runBiffB as) (runBiffB bs)

What is interesting about this is that the cofree comonad and free monad can be defined in terms of BiffB given a definition for the fixed point of a bifunctor:

newtype FixB s a = InB { outB :: s a (FixB s a) } instance Bifunctor s => Functor (FixB s) where fmap f = InB . bimap f (fmap f) . outB type Cofree f a = FixB (BiffB (,) Identity f) a type Free f a = FixB (BiffB Either Identity f) a

Then we can define that the fixed point of a zippable bifunctor is a zippable functor:

instance Bizip p => Zip (FixB p) where fzipWith f as bs = InB $ bizipWith f (fzipWith f) (outB as) (outB bs)

Then it immediately follows by the construction for BiffB that every Cofree Comonad of a zippable base functor is Zippable because they are the fixed point of BiffB (,) Identity f. and since (,) is zippable and Identity is zippable, then given f zippable the base bifunctor is zippable, so Cofree f is zippable.

On the other hand, we do not get the same result for the Free Monad, because it is built over BiffB Either Identity f, and Either is not a zippable bifunctor.

We can define some other functors and bifunctors which are zippable, i.e. we can define a "functor-wrapped bifunctor bifunctor":

newtype FunctorB f p a b = FunctorB { runFunctorB :: f (p a b) } liftFunctorB :: Functor f => (p a b -> p c d) -> FunctorB f p a b -> FunctorB f p c d liftFunctorB f = FunctorB . fmap f . runFunctorB instance (Functor f, Bifunctor p) => Bifunctor (FunctorB f p) where bimap f g = liftFunctorB (bimap f g) instance (Zip f, Bizip p) => Bizip (FunctorB f p) where bizipWith f g as bs = FunctorB $ fzipWith (bizipWith f g) (runFunctorB as) (runFunctorB bs)

But the general pattern was set by Either and Maybe. Whenever your functor has a branch you need a way to uniquely determine the way the constant terms combine.

While I think the above yields a pleasingly generic version of zip. I do not believe that I have exhausted the set of possible instances, but yielding them automatically for cofree comonads of zippable functors, and hence for rose trees, streams, was rather nice.

If you have any other instances of note, I would welcome the insight.

May 5th, 2008 at 3:53 pm

your Zip class is almost the same as Applicative:

fzipWith f a b = fmap f a b

Your fzip function is suggested in the Applicative paper as making more sense from a category theory perspective.

This also raises the question of what exactly fzip should do. How do you say that it should ‘zip’? For instance [] is also an applicative functor with the usual Monad-style cartestian product behaviour.

Specifying that unfzip is the inverse of fzip is a good idea. For [] fzip is only a right inverse of unfzip, since you could zip lists of different lengths. The same holds for Maybe: funzip (fzip (Just x) Nothing) /= (Just x, Nothing).

May 5th, 2008 at 4:48 pm

[...] Twan van Laarhoven pointed out that fzip from the other day is a close cousin of applicative chosen to be an inverse of universal construction: unfzip [...]

June 5th, 2008 at 2:34 pm

[...] In an earlier post about the cofree comonad and the expression problem, I used a typeclass defining a form of duality that enables you to let two functors annihilate each other, letting one select the path whenever the other offered up multiple options. To have a shared set of conventions with the material in Zipping and Unzipping Functors, I have since remodeled that class slightly: [...]

June 20th, 2009 at 3:13 pm

fzipWith = liftA2, at least ignoring the inverse law for fzip and funzip as you seem to have for [] (where you chose the ZipList semantics) and Maybe. Perhaps the [] and Maybe instances for Zip should be removed, and instances for known Applicatives which follow the inverse law should be added?

June 22nd, 2009 at 4:59 pm

@Jake

I almost agree. I’ve had people point out the connection to Applicative on several occasions before, but it falters slightly.

There is no requirement for the existence of unit, so your functor need not be pointed. This permits the class of zippable functors to be slightly wider than the class of applicative functors.

Secondly the particular near-applicative operation is selected explicitly so it will be a left inverse to unzip.

fzip . unfzip = id

Since that should hold for any functor to claim to be a member of Zip the definition is narrower than that of Applicative. Using list monad semantics for fzip on [] would fail this law.

So Zip is neither a superclass nor a subclass of Applicative.

That, at least, was my justification for a zippable functor as an independent concept; I may not have fully articulated the justification back when i wrote this article.

February 22nd, 2012 at 3:29 pm

I also want liftPair in Applicative