What is a purpose of Zap Functor and zap function in Haskell?

Question

I came across this construction in Haskell. I couldn't find any examples or explanations of how can I use zap/zapWith and bizap/bizapWith in real code. Do they in some way related to standard zip/zipWith functions? How can I use Zap/Bizap functors in Haskell code? What are the benefits of them?

Answer 1

This is covered by this wonderful Kmett blog post, Cofree Comonad and the Expression Problem. Unfortunately there's quite a lot of terminology in that blog post and I don't quite understand everything myself but we can try and sketch out the details.

Peano numbers

Let's define the natural numbers in a very strange way. We will first define the Peano zero and successor functions:

zero :: ()
zero = ()

incr :: a -> Identity a
incr = Identity

Then we can define some numbers:

one :: Identity ()
one = incr zero

two :: Identity (Identity ())
two = incr . incr $ zero

three :: Identity (Identity (Identity ()))
three = incr . incr . incr $ zero

Bizarre but it seems to work. You can convert 3 :: Int to three and back. (Try it.) Can we write a function f to convert any arbitrary number to our strange representation and back? Unfortunately no. The Haskell type system will not let us construct an infinite type, which is the exact kind of type we want for f.

A yet bigger problem is that, as a lazy functional programmer, I wish to stop typing Identity so many times. At this rate I willl be forced to type it O(n^2) times to define n numbers. This is 2016 and I find this unacceptable.

We can turn to the Free datatype for help for both of our problems. (Some people call this the Free monad, but there is no reason for us to say "monad" when we can just say "type".)

newtype Free f a = Free (Either a (f (Free f a)))

zero :: a -> Free Identity a
zero x = Free (Left x)

incr :: Free Identity a -> Free Identity a
incr = Free . Right . Identity

one :: a -> Free Identity a
one x = incr (zero x)

two :: a -> Free Identity a
two x = incr (incr (zero x))

three :: a -> Free Identity a
three = incr . incr . incr . zero

Pretty. This (surprisingly perhaps) is identical to our unusual Identity-wrapping representation above.

Streams

Now let us try to build a stream. Say, the stream of centurial leap years starting from 2000 (2000, 2400, 2800). But in a strange way.

unfold :: (a -> a) -> a -> (a, (a, (a, ...)))
unfold a2a a = (a, unfold a2a (a2a a))

centurials :: (Int, (Int, (Int, ...)))
centurials = unfold (+ 400) 2000

Assuming the compiler allowed us to write down our infinite type, this would be a suitable representation for a stream of numbers. To the rescue comes Cofree, the "dual" type to Free. Dual in the category theoretical sense, where if you took the time and pulled out a category theory textbook and boiled a lot of coffee and drew out the categorical diagram and then flipped around all the arrows you would go from one to the other (or the other to the one). This poor explanation will have to suffice as the hand-wavey paragraph on duality.

newtype Cofree f a = Cofree (a, f (Cofree f a))

unfold :: Functor f => (a -> f a) -> a -> Cofree f a
unfold a2fa a = Cofree (a, fmap (unfold a2fa) (a2fa a))

centurials :: Cofree Identity Int
centurials = unfold (Identity . (+ 400)) 2000

This (again surprisingly perhaps) is equivalent to our infinite Russian nesting doll representation above.

Indexing streams with Peano numbers

But how to seek to specific elements in the stream? By taking advantage of the duality between Free and Cofree, we can actually use our representation of Peano numbers to index into our representation of streams.

It turns out that, in Haskell, if f and g are dual in a mathematical sense then the following property holds true:

class Zap f g | f -> g, g -> f where
  zap :: (a -> b -> r) -> f a -> g b -> r

We will have to elide a discussion about duality and why this property holds true for dual functors.

We can implement the simplest instance: the mathematical duality between an identity functor (represented in Haskell as newtype Identity a = Identity a) and itself.

instance Zap Identity Identity where
  zap ab2r (Identity a) (Identity b) = ab2r a b

This property can be extended to bifunctors also:

class Bizap f g | f -> g, g -> f where
  bizap :: (a -> c -> r) -> (b -> d -> r) -> f a b -> g c d -> r

We can instantiate this class for Haskell's encoding of sum and product, which are (non-trivially!) dual in category theory:

instance Bizap Either (,) where
  bizap ac2r bd2r (Left a) (c, d) = ac2r a c
  bizap ac2r bd2r (Right b) (c, d) = bd2r b d

instance Bizap (,) Either where
  bizap ac2r bd2r (a, b) (Left c) = ac2r a c
  bizap ac2r bd2r (a, b) (Right d) = bd2r b d

We now have enough machinery to show the same duality in Haskell between Free and Cofree.

instance Zap f g => Zap (Cofree f) (Free g) where
  zap ab2r (Cofree as) (Free bs) = bizap ab2r (zap (zap ab2r)) as bs

instance Zap f g => Zap (Free f) (Cofree g) where
  zap ab2r (Free as) (Cofree bs) = bizap ab2r (zap (zap ab2r)) as bs

These instances exploit the dual bifunctor nature of Either and (,) as well as the inherited zap from the duality of f and g, which in our examples will always be Identity and Identity in order to "unpeel" a layer off of Free and Cofree and to recursively call zap on that lower layer.

Finally, let's see it in action:

year2800 :: Int
year2800 = zap id (two id) centurials

It is by exploiting this zap or "annhilation" property that we are able to retrieve values from a stream built by Cofree using natural number indices built by Free. Though far from a real-world example, the code exists as an exercise in how we can encode high-falutin' ideas from category theory in Haskell types and typeclasses. That we are able to do this serves as a brain teaser and also a sanity check for our choice of types for Free and Cofree.

You may find the instances useful for one-liners or when you data structures happen to line up just right, as detailed in Gurkenglas' answer. Should you find duality to be a useful property to exploit, definitely reach for this part of the category-extras package. But even if we cannot find a usage for it we can certainly appreciate the beauty of everything neatly fitting together.

As for zipping

You are correct in thinking that there is a connection between Zap and Zip. They are named in the Kmett style of wordplay-driven development. Encoding zippable functors leads to a very similar typeclass Zip:

class Functor f => Zip f where
  fzipWith :: (a -> b -> c) -> f a -> f b -> f c

You can derive a generic zipping function for trees and streams (again using Cofree) by following this construction. See the blog post for more details.

Answer 2

Zap relates dual Functors. In Haskell, that means that one carries extra information and the other one uses it up, and that's all both of them do. (r, a) is an a value carrying an extra r value, r -> b is a b value that first requires an r value. zapWith (+) read ("123", 321) will plug the "123" into read, and plug the 123 and the 321 into the (+). All Zap does is help with the plugging, if you find a piece of code where it fits. zap = uncurry for this instance, by the way. Reader and Coreader are isomorphic to ((->) r) and ((,) r) respectively. Other instances would be one providing two values and the other using both up, or f providing an r, then using up an s, while g provides an s, then uses up an r.