`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

`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`

`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.
## 4 comments:

Nice observation on the additional law for zipWith.

One note is that as commonly used, a zippable container need not provide an empty value. so they are often only the 'semigroup' portion of the Applicative functor, rather than the full strong lax monoidal functor.

@Ed - yes, actually, in our code, we split just the align function out into its own typeclass (called 'Align') and there are a couple places that are bounded by Align rather than Alignable.

What is a "strong lax monoidal functor"? :)

Even if your container doesn't provide an empty value, you can always get a free alignable functor by composing Maybe.

A "strong lax monoidal functor" is the more formal notion expressed by Applicative.

class Functor f => Monoidal f where

unit :: a -> f a

(^*^): f a -> f b -> f (a, b)

When your category (like Haskell) has arbitrary exponential objects, the two formalisms are equivalent. In other categories you can have Monoidal when Applicative isn't definable.

Post a Comment