Alignable functors: a typeclass for 'zippy' containers

Applicative functors don't quite work for some applications. At work we had some code that needed to abstract over several containers each equipped with some sort of "zipWith" operation (for instance: lists, maps, trees). Unfortunately the Applicative-derived version of zipWith was unsuitable. Here's that implementation:

zipWith :: (a -> b -> c) -> f a -> f b -> f c
zipWith f x y = f <$> x <*> y

For "zippy" applicatives, in addition to the usual Applicative laws, zipWith should satisfy:

zipWith f xs xs == fmap (\x -> f x x) xs

Aside: it is well known that we could define <*> in terms of zipWith: (<*>) = zipWith ($)

The Applicative-derived zipWith has no good way of handling containers with different shapes. Since the lifted function always receives both an a and a b, the shape of the resulting f c must be the intersection of the two shapes being zipped -- zipWith has no way to notify the zipping function, f, that it has encountered a position where only the first container or only the second container has a value.

Here are some examples of how this plays out:

• zipWith for two lists results in a list whose length is the smaller of the two


• zipWith for two maps results in a map whose key set is the intersection of the two input key sets


• zipWith for two binary trees will contain only the nodes with a path from the root that exists in both input trees

This behavior might be acceptable for some applications but for ours it wasn't. Incidentally, the behavior also propagates to Traversable, so for instance using traverse to transpose a [[a]] will truncate the output lists:

Prelude> getZipList $ sequenceA [ZipList [1], ZipList [1,2]]
[[1,1]]

The second column, the one that should be [2], is removed because not all lists being transposed have a second element. We get similar behavior with other zippy applicatives.

If we choose to take the union of the two shapes being zipped rather than their intersection, we obtain the Alignable typeclass:

class Functor f => Alignable f where 
   empty :: f a
   align :: (OneOrBoth a b -> c) -> f a -> f b -> f c

data OneOrBoth a b = Both a b | OneL a | OneR b

This should satisfy:

• align f a empty == fmap (f . OneL) a
• align f empty a == fmap (f . OneR) a
• align f a a == fmap (\x -> f $ Both x x) a

So where Applicative has pure, Alignable has empty, and where Applicative has <*>, Alignable has align. Like Applicative, we could use these to implement fmap.

If you have an Alignable for some f, you can lift Iteratee, Reducer and various other Reducer-like objects to f. Monoids and groups can also be lifted to Alignable. And the version of traverse based on Alignable is more appropriate for some applications.

One of the problems with Alignable is it doesn't provide a way to lift algebraic structures with more than one distinguished element. If the structure has just one distinguished element (like a monoid or group), then empty can represent the lifted version of that element - we just need to have the function we pass to align fill in this element when it receives a OneL or a OneR. If there's multiple distinguished elements (like in a ring) then this doesn't work and we need something like pure :: a -> f a. But this can't be the infinite constant container of f like in a typical zippy applicative. We want it to interact properly with align - pure should satisfy align f a (pure b) == fmap (\a -> f (Both a b)) a. Most containers aren't going to have a way of representing pure which satisfies this property, so it seems we have to rely on a datatype like this:

data PureT f a = Pure a | Finite (f a)

This just adds a data constructor for symbolically representing the result of a call to pure. And we can define our Alignable instance such that Pure a has the desired meaning.