Chris Martin

# Problems with products, part one

Where we see a type parameter to the right of a function arrow (or with no arrow at all, since `a` is isomorphic to `() -> a`), we have a covariant functor (or simply, "functor").

``newtype Decode k v a = Decode{ decode :: Map k v -> a }``

Covariant functors quite often admit an applicative aspect that allows us to build up larger stuff within the type parameter.

``(★) :: Decode k v a -> Decode k v b -> Decode k v (a, b)``
``````at :: Ord k => k -> Decode k Char Char
at k = Decode (Map.findWithDefault '\0' k)``````
``````abc :: Map Int Char
abc = [(1, 'a'), (2, 'b'), (3, 'c')]``````
``(abc & decode (at 1 ★ at 2))  ==  ('a', 'b')``

To define `(★)` is left as an exercise for the reader; it is a good exercise for anyone who does not already immediately know how. The particularly Haskell-savvy, however, will likely choose to use a derived `Applicative` instance.

``````deriving newtype instance Functor (Decode k v)
deriving newtype instance Applicative (Decode k v)``````
``(★) = liftA2 (,)``

The two-tuple only takes us so far, and sooner or later (but probably sooner, if we're not just playing around) we'll want to start working with larger products. More than two things. `(★)` can be nested. (I knew this ahead of time, which is why I named it as an infix operator.)

``````(abc & decode (at 1 ★ at 2))           ==  ('a', 'b')
(abc & decode ((at 1 ★ at 2) ★ at 3))  ==  (('a', 'b'), 'c')
(abc & decode (at 1 ★ (at 2 ★ at 3)))  ==  ('a', ('b', 'c'))``````

This, of course, sucks, because nobody wants nested tuples like that. You want a three-tuple, right? Thus enters the real clever trick of the `Applicative` class.

``````(abc & decode (pure (,,) <*> at 1 <*> at 2 <*> at 3))
== ('a', 'b', 'c')``````

Better than tuples, even, we can use types that are more meaningful to us.

``data XYZ a = XYZ{ x :: a, y :: a, z :: a } deriving Eq``
``````decodeXYZ :: Decode Int Char (XYZ Char)
decodeXYZ = pure XYZ <*> at 1 <*> at 2 <*> at 3``````

And we can use `do` and record sugar to forget about field order.

``decodeXYZ' = do x <- at 1; y <- at 2; z <- at 3; pure XYZ{ x, y, z }``
``decodeXYZ'' = do x <- at 1; z <- at 3; y <- at 2; pure XYZ{ x, y, z }``

And it is, I think, fair to call it a trick. Because, for one thing, history implies that this approach wasn't obvious; I've seen nothing predating Applicative Programming with Effects which seems to have started circulating in 2005, the class appears in GHC's `base` library starting in 2006, and `ApplicativeDo` doesn't hit the compiler until 2016.

And for another thing, it's sort of weird. Consider the types of the subterms:

``````pure (,,)                   :: Decode Int Char (Char -> Char -> Char -> (Char, Char, Char))
pure (,,) <*> at 0          :: Decode Int Char (        Char -> Char -> (Char, Char, Char))
pure (,,) <*> at 0 <*> at 1 :: Decode Int Char (                Char -> (Char, Char, Char))``````

The idea that we have a `Decode` that represents a parser which produces a result of type `Char -> (Char, Char, Char)` is, frankly, not even what I'm thinking about when I write an applicative expression. It is only something I think about when I'm explaining why it works. To me this is enough to place any technique squarely in the category of clever trick.

The final reason I call applicative programming a trick is that when we step outside of covariant functors, we find that `Applicative` is no longer applicable. (Indeed the superclass constraint said this already.)

Just like we encode a product of values such as `XYZ` from an input map, so too may we be interested in the reverse: turning a record into a `Map` by turning each field into a `Map` and merging all the results together.

(This is not so contrived a topic. The problem posed here is one encountered whenever we encode and write process environment variables, HTTP headers, JSON objects, and so on.)

``newtype Encode k v a = Encode{ encode :: a -> Map k v }``
``````to :: k -> Encode k v v
to k = Encode \v -> Map.singleton k v``````

The `to` function can construct an `Encode` definition suitable for each of the three fields `x`, `y`, `z` of the `XYZ` record.

``````('a' & encode (to 1))  ==  [(1, 'a')]
('b' & encode (to 2))  ==  [(2, 'b')]
('c' & encode (to 3))  ==  [(3, 'c')]``````

We can define a 2-tuple combination, much like we did for `Decode`.

``````(★★) :: Ord k => Encode k v a -> Encode k v b -> Encode k v (a, b)
encodeA ★★ encodeB = Encode \(a, b) ->
(a & encode encodeA) <>
(b & encode encodeB)``````
``(('a', 'b') & encode (to 1 ★★ to 2))  ==  [(1, 'a'), (2, 'b')]``

And we can define an `Encode` for `XYZ`.

``````encodeXYZ :: Encode Int a (XYZ a)
encodeXYZ = Encode \xyz ->
(x xyz & encode (to 1)) <>
(y xyz & encode (to 2)) <>
(z xyz & encode (to 3))``````
``````(XYZ{ x = 'a', y = 'b', z = 'c' } & encode encodeXYZ)
== [(1, 'a'), (2, 'b'), (3, 'c')]``````

What we don't have is a combinator that works directly on `Encode` like `<*>` does for `Decode`. This may seem like an unimportant quibble, since `encodeXYZ` was not particularly difficult to define, but it ends up compounding into a bigger practical problems.

There is also one other concern of more obvious practical relevance:

``````encodeXYZ' = Encode \xyz ->
(x xyz & encode (to 1)) <>
(z xyz & encode (to 3))``````

If we accidentally neglect to encode one of the fields in the applicative-do `Decode` expression, the compiler emits a warning. If we omit an `Encode` step, as in `encodeXYZ'` above, the mistake goes unremarked upon.

When a type variable appears in both a covariant and a contravariant way, we have an invariant functor. The contravariant aspect prohibits defining `fmap`, and the covariant aspect prohibits defining `contramap`.

This happens, for example, when we bundle `Decode` and `Encode` together into one type, which seems like a reasonable thing to want to do:

``data Codec k v a = Codec{ co :: Encode k v a, dec :: Decode k v a }``
``````key :: Ord k => k -> Codec k Char Char
key k = Codec{ co = to k, dec = at k }``````

We can concoct combinations for invariant functors of products.

``````(★★★) :: Ord k => Codec k v a -> Codec k v b -> Codec k v (a, b)
formatA ★★★ formatB = Codec
{ dec = dec formatA ★ dec formatB
, co = co formatA ★★ co formatB
}``````

Exercise: Define `Format Int Char XYZ` in terms of `key 1`, `key 2`, and `key 3`.

``codecXYZ = Codec{ co = undefined, dec = undefined }``

It isn't terribly difficult, but it isn't terribly easy either. What you have to do is write the `Decode` and the `Encode` separately. They don't compose in parallel. It's up to you to make sure they're defined harmoniously. It's all terribly inconvenient.

Part two, if I am able to finish it, will be about solutions.

I write about Haskell and related topics; you can find my works online on Type Classes and in print from The Joy of Haskell.