Product and coproduct

A product A×BA \times B is an object in a category that is equipped with two morphisms, it's projections, pp and qq. This corresponds to the Cartesian product of the two objects AA and BB in the category SetSet.

The coproduct A+BA + B is an object in a category that is equipped with two morphisms, it's injections, ii and jj. This corresponds to the disjoint union of the two objects AA and BB in the category SetSet. Technically the elements of AA and BB are tagged in order to signify their origin, and the union of the tagged versions of the sets is taken:

A+B=(A×{0})(B×{1})A + B = (A \times \{0\}) \cup (B \times \{1\})

For a pair of objects AA and BB of a category CC we define a wedge to the pair A,BA, B as an object XX equipped with two morphisms XA,BX \rightarrow A, B. We also define a wedge from the pair A,BA, B is an object XX equipped with two morphisms A,BXA, B \rightarrow X:

For a given pair there may be many such wedges, on one side or the other. Our goal is to look for a best possible wedge, or technically a universal wedge. This means that for a given pair of objects A,BA, B in a category CC the product and coproduct of the pair is a wedge with the following universal property that for each wedge there is a unique morphism XmSX \xrightarrow {m} S for the product and SmXS \xrightarrow {m} X for the coproduct. This mediator for each wedge (which is unique for each wedge on XX) means that the two respective wedges commute:

Lemma 1

Given the product and coproduct wedges in the category CC and an endomorphism SkSS \xrightarrow {k} S then it holds that k=idSk = id_S. This verifies the uniqueness of the universal solution.

Lemma 2

For objects AA and BB in a category CC, a pair of product and coproduct wedges then P,QP, Q and I,JI, J are uniquely isomorphic over the wedges. That is, the unique morphisms f,gf, g between P,QP, Q are an inverse pair of isomorphisms, and similarly for the isomorphisms i,ji, j between I,JI, J. This means that if a pair of objects has a product or coproduct then it is essentially unique, and which leads to us speaking of the product or coproduct of a pair of objects.

The existence of products and coproducts varies from category to category.

What does this mean in programming?

In very general terms it means we can take various types in the category HaskHask and pick the best possible type.

Product example

If we have the types IntInt, (Int,Bool)(Int, Bool), and (Int,Int,Bool)(Int, Int, Bool) and two functions (projections) from each type (IntpIntInt \xrightarrow {p} Int and IntqBoolInt \xrightarrow {q} Bool), then the product tells us that all three are isomorphic, and the best candidate is the pair (Int,Bool)(Int, Bool). That is, there is a unique morphism mm from any candidate cc to the Cartesian product (a,b)(a, b). It simply combines the two projections into a pair. In Haskell:

This morphism can also be produced by a factorizing function, again in Haskell:

Coproduct example

The coproduct is the reverse of the product, the projections become injections so given an object cc with the two injections aica \xrightarrow {i} c and bjcb \xrightarrow {j} c, we say that object cc is better than some other object cc' equipped with the morphisms aica \xrightarrow {i'} c' and bjcb \xrightarrow {j'} c', if there is a morphism cmcc \xrightarrow {m} c' that factorizes the injections.

In this example we use the sum type ContactContact with the two injections PhonePhone and EmailEmail. In Haskell:

In Haskell, the coproduct is implemented as a datatype called EitherEither that is parameterized by two types aa and bb, and has the two type constructors LeftLeft and RightRight.

So given that EitherEither and ContactContact are isomorphic with the morphism mm:

This means that given a candidate type cc and two injections ii and jj the factorizer for EitherEither is implemented as:

In Haskell: