Category Theory for Programmers: Exercises (Chapter 5)

Products and Coproducts

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

Similarly to the initial object, the terminal object has only one arrow going out to any other object. It also has only one arrow going in. So two terminal objects, i₁ and i₂ will be connected by two arrows, f and g, and, since each can only have one arrow going in, the composition of these arrows, g . f and f . g, must be equal to the identity arrows for i₁ and i₂ respectively.

2. What is a product of two objects in a poset?

It’s an initial object, i.e. it has an arrow going out of it to each object but no arrows going into it.

3. What is a coproduct of two objects in a poset?

It’s a terminal object, i.e. it has an arrow going into it from each object but no arrows going out of it.

4. Implement the equivalent of Haskell Either as a generic type in a language other than Haskell.

class CEither<T> {
    public readonly value: T;

    constructor(x: T) {
        this.value = x;
    }
}

class Left<T> extends CEither<T> {}
class Right<T> extends CEither<T> {}

type Either<A, B> = Left<A> | Right<B>;

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.

// Injection from integer object to the Either coproduct.
const i_ = (n: number) => {
    return new Left(n);
};

// Injection from the boolean object to the Either coproduct.
const j_ = (b: boolean) => {
    return new Right(b ? 0 : 1);
};

// Factorization of i & j that returns the integer value held
// by Left or Right.
const m = (e: Either<number, number>) => {
    return e.value;
};

6. Continuing the previous problem: How would you argue that int with the two injections i and j cannot be “better” than Either?

int cannot be better than Either because there are two ways to factorize i_ and j_ (m needs to be unique):

const m1 = (n: number) => {
    return new Left(n);
};

const m2 = (n: number) => {
    return new Right(n);
};

7. Still continuing: What about these injections?

int i(int n) {
  if (n > 0) return n;
  return n + 2;
}

int j(bool b) { return b? 0: 1 }

The same answer as for exercise 6…

8. Come up with an inferior candidate for a coproduct of int and bool that cannot be better than Either because it allows multiple acceptable morphisms from it to Either.

As illustrated by the above examples, any other candidate will be “worse” than Either since Either represents a disjoint union which is what the coproduct actually is in the Set category. So any other object will have more than one m function to Either because any element from the candidate can be tagged Left or Right.