# 5. Products and Coproducts

# 5. Products and Coproducts¶

## Notes¶

An **initial object** in a category is an object that has 1 and only 1 morphism
going to any object in the category. Object a is more initial than b if
\(a \rightarrow b\).

In the category of sets, this is the `Void`

Haskell type with `absurd :: Void -> a`

as the universally polymorphic morphism.

A **terminal object** a category is an object that has 1 and only 1 morphism
going to it from any object in the category. Object a is more terminal than b
if \(a \leftarrow b\).

In the category of sets, this is a singleton set: `()`

in Haskell, with
`unit :: a -> ()`

as the morphism.

For any category \(C\), we can define the opposite category \(C^{op}\) by reversing the morphisms. If \(f :: a \rightarrow b\), \(g :: b \rightarrow c\) with their composition \(g \circ f = h :: a \rightarrow c\), then we can define \(f^{op} :: a \leftarrow b\), \(g^{op} :: b \leftarrow c\) and \(h^{op} :: a \leftarrow c\). The terminal object in \(C\) is the initial \(C^{op}\), and vice versa.

An **isomorphism** is a pair of morphisms such that \(f \circ g = id\) and
\(g \circ f = id\).

Initial objects are unique up to unique isomorphisms. Take 2 initial objects,
\(i_1\) and \(i_2\), with morphisms \(f :: i_1 \rightarrow i_2\) and
\(g :: i_2 \rightarrow i_1\). \(g \circ f\) is a morphism from
\(i_1 \rightarrow i_1\).
Since \(i_1\) is initial, there can be only 1 morphism from it, so
\(g \circ f = id_{i_1}\). Similarly, \(f \circ g = id_{i_2}\). \(f\)
and \(g\) must be the inverse of each other. Therefore, **any 2 initial
objects are isomorphic**.

### Products¶

A product of two objects \(a\) and \(b\) is the object \(c\) equipped
with two **projections** (\(p :: c \rightarrow a\) and \(q :: c \rightarrow b\))
such that for any other object \(c'\) equipped with two projections there is
a *unique morphism* \(m :: c' \rightarrow c\) that factorizes those projections.

For example, consider the product between the types `Int`

and `Bool`

. There
could be two candidates for the product of those two types, `Int`

and `(Int, Bool)`

:

In this case, \(p'\) and \(q'\) could be constructed in terms of \(m\):

```
m :: Int -> (Int, Bool)
m x = (x, True)
p :: (Int, Bool) -> Int
p (x, _) = x
q :: (Int, Bool) -> Bool
q (_, x) = x
p' :: Int -> Int
p' x = p (m x) -- this would equal x
q' :: Int -> Bool
q' x = q (m x) -- this would equal True
```

### Coproducts¶

A **coproduct** of two object \(a\) and \(b\) is the object \(c\)
equipped with two **injections** (\(i :: a \rightarrow c\) and
\(j :: b \rightarrow c\)) such that for any other object \(c'\) equipped
with two injections there is a *unique morphism* \(m :: c \rightarrow c'\)
that factorizes those injections:

In the category of sets, the coproduct is the *disjoint union* of two sets.
In programming, a coproduct can be a tagged union of 2 types - cannonically
`Either`

in Haskell:

```
data Either a b = Left a | Right b
```

### Asymmetries¶

The terminal object can be obtained from reversing the morphism directions of an initial object. A coproduct can be obtained from reversing the morphisms of a product. However, asymmetries exist in the category of sets. Take a function from a singleton set:

```
f100 :: () -> Integer
f100 () = 100
```

Functions are *total*, in that they are defined for every element of the
domain set. However, functions don’t have to cover the whole codomain. `f100`

is a total function in that is covers every value of `()`

, but only covers one
value of the codomain: `100`

in the set of integers. Functions that have a
smaller domain than the codomain *embed* the domain in the codomain. Functions
that tightly fill their codomains, on the other hand, are **surjective** or **onto**.

Functions can also map many elements of the domain onto one element of the codomain:

```
intToTrue:: Integer -> Bool
intToTrue _ = True
```

In this sense, they *collapse* the domain into the codomain. Functions that
do not do this are **injective** or **one-to-one**.

Some functions are *both surjective and injective*. They are **bijections**,
and are properly invertable. An ismorphism in the category of sets is a bijection.

## Challenges¶

### 5.1¶

**Show that the terminal object is unique up to unique isomorphism.**

We can basically just reverse the proof for the initial object.

Take 2 terminal objects, \(t_1\) and \(t_2\), with morphisms \(f :: t_2 \rightarrow t_1\) and \(g :: t_1 \rightarrow t_2\). \(g \circ f\) is a morphism from \(t_2 \rightarrow t_2\). Since \(t_2\) is terminal, there can be only 1 morphism to it from any object, and objects in a category have the identity morphism already, so \(g \circ f = id_{t_2}\). Similarly, \(f \circ g = id_{t_1}\). \(f\) and \(g\) must be the inverse of each other. Therefore, any 2 terminal objects are isomorphic. The terminal object is unique up to unique isomorphism.

### 5.2¶

**What is a product of two objects in a poset?**

To recap: a poset, or partially ordered set, is a category where a morphism is a relation between objects: for example, the relation of being less than or equal. It has:

*Identity morphisms*: an object is less than or equal to itself.*Composition*: \(a \leq b \land b \leq c \rightarrow a \leq c\).*Partial order*: additional condition that \(a \leq b \land b \leq a \rightarrow a = b\).

However, a partial order is not a total/linear order, in which every object has a morphism to every other.

If we have 2 objects, \(a\) and \(b\), we seek a \(c\) that is the product of those objects, with morphisms \(p :: c \rightarrow a\) and \(q :: c \rightarrow b\).

Given that the morphisms in this posset are the relation of being less than or equal, the morphisms from \(c\) are \(p :: c <= a\) and \(q :: c <= b\).

The product \(c\) must be a number that is less than or equal to a or b. It must also
be the *biggest* number less than or equal to a and b, as if were not, then the morphism
\(m :: c' <= c\) would factorize \(p'\) and \(q'\):

```
m :: c' <= c
p :: c <= a
q :: c <= b
p' :: c' <= a
q' :: c' <= b
p' :: m.p -> c' <= c && c <= a == c' <= a
q' :: m.p -> c' <= c && c <= b == c' <= b
```

So, for example, if \(a = 5\) and \(b = 6\), then \(c \leq 5 \land c \leq 6\). In this case, \(c = 5\), as \(5 \leq 5 \land 5 \leq 6\). If \(c' = 4\), then \(m :: c' <= c\).

### 5.3¶

**What is a coproduct of two objects in a poset?**

A coproduct \(c\) of \(a\) and \(b\) in the poset defined in 5.2
would have the morphisms \(i :: a \leq c\) and \(j :: b \leq c\). It
should also be the object where \(m :: c \leq c'\). In the example poset, it
would be the *smallest* number less than or equal to both a and b.

If \(a = 5\) and \(b = 6\), then the coproduct \(a \leq c \land b \leq c\). This would be \(c = 6\). If \(c' = 7\), then \(m :: c <= c'\).

### 5.4¶

**Implement the equivalent of Haskell Either as a generic type in your favorite
language (other than Haskell).**

```
from typing import Generic, TypeVar
T = TypeVar("T")
U = TypeVar("U")
class Either(Generic[T, U]):
pass
class Left(Either[T, U]):
def __init__(self, value: T) -> None:
self.value = value
class Right(Either[T, U]):
def __init__(self, value: U) -> None:
self.value = value
left = Left[str, int]("hello")
right = Right[str, int](10)
assert type(left.value) == str
assert type(right.value) == int
assert left.value == "hello"
assert right.value == 10
```

### 5.5¶

**Show that Either is a “better” coproduct than int equipped with two
injections:**

```
int i(int n) { return n; }
int j(bool b) { return b? 0: 1; }
```

**Hint: Define a function int m(Either const & e); that factorizes i and j.**

In this instance, `m :: Either int bool -> int`

```
int m(Either const & e) {
return (e.tag == Either::isLeft) ? e.left : e.right ? 0 : 1;
}
```