Coproducts

Here are a bunch of constructions that share a similar property:

  • The union of two sets is the smallest set that contains both of them.
  • The maximum of two numbers is the smallest number that’s greater than or equal to both of them.
  • The least common multiple of two numbers is the smallest number that’s a multiple of both them.
  • The proposition “A or B” is the one with the least assumptions needed to prove either A or B.

We can get all these concepts by reversing all the arrows in the categorical product diagram:

\begin{tikzpicture}
\begin{scope}[scale = 3]
\node (A) at (0,0) {$A$};
\node (B) at (2,0) {$B$};
\node (X) at (1,0) {$X$}
edge [<-] (A)
edge [<-] (B);
\node (Y) at (1,-1) {$Y$}
edge [<-] (A)
edge [<-] (B)
edge [<-, dashed] (X);
\end{scope}
\end{tikzpicture}

It says that X is an object with morphisms from A and B such that given any object Y with morphisms from A and B, there exists a morphism from X to Y. We call X the coproduct of A and B.

Just as with the product, we can also generalize the coproduct from partial orders to categories and get useful structures.

\begin{tikzpicture}
\begin{scope}[scale = 3]
\node (A) at (0,0) {$A$};
\node (B) at (2,0) {$B$};
\node (X) at (1,0) {$X$}
edge [<-] node [above,l] {$p$} (A)
edge [<-] node [above,l] {$q$} (B);
\node (Y) at (1,-1) {$Y$}
edge [<-] node [below left,l] {$r$} (A)
edge [<-] node [below right,l] {$s$} (B)
edge [<-, dashed] node [right,l] {$!$} (X);
\end{scope}
\end{tikzpicture}

This says that X is an object with morphisms from A and B such that given any object Y with morphisms from A and B, there exists a unique morphism from X to Y making the diagram commute—that is, if we apply the morphism marked p and then !, we get the same result as applying r; similarly, if we apply q and then !, we get the same result as applying s.

In the category of sets and functions, the categorical product gives us the disjoint union of sets:

An element of A+B is either an element of A or an element of B. In JavaScript, variables have a type that’s a sum over every possible type: it can be an int or a string or a Date object or a function or whatever we want.

We can write a contract for the coproduct of n contracts, where the coproduct of 0 contracts is a contract for the empty set: no item passes the contract.

var makeCoproduct = function (cs) {
  arrOf(func)(cs);
  return function (x) {
    makeProduct([nat32, id])(x);
    if (x[0] >= cs.length) {
      throw new TypeError('Expected a tag less than ' + cs.length);
    }
    return cs[x[0]](x[1]);
  };
};

The contract makeCoproduct([str, nat32]) will accept values of the form [0, s] where s is a string or [1, n] where n is a natural number.

Advertisements

2 Comments to “Coproducts”

  1. “In the category of sets and functions, the categorical product gives us the disjoint of sets:” — do you mean “the coproduct gives us the disjoint union of sets”?

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: