Addition categorically!

See “Computational Category Theory” by Rydeheard and Burstall for implementation, in ML, of the algorithms in elementary category theory. Following their lead, we present data types in Haskell that can be used to implement basic algorithms in category theory. We use a category in which addition (of integers) can be performed to ground the discussion. You will also need familiarity with types, type variables and classes in Haskell (see website) to proceed. Some of the basic algorithms will be illustrated using these datatypes in later posts, hopefully.

One can use types in Haskell to represent objects in a category. To simplify the discussion, assume that all the objects are of the same kind in a given category. We use a lowercase letter as o, p to represent objects. Arrows between objects o and p' are represented as a (o,p). The source of the arrow is o, and the tail of the arrow is p.

Consider the category in which objects are created from integers, and arrows exist between pair of objects o and o+1 to start. In this category, there is a unique arrow between a pair of objects if one exists. Composition of two arrows (o,o+1) and (o+1, o+2) is is new arrow from (o,o+2). In general, the composition of arrows (o,o+i), (o+i,o+j) is an arrow (o,o+j) where i < j. The identity arrow on object o is the identity function that returns the arrow (o,o). In this category, we can test a pair of objects for equality, o is not equal to o+1. However, in a general category, pairs of objects cannot be tested for equality. This category can be built as a data type in Haskell. The data type for an object is declared as below.

data Obj o = Obj o deriving (Show, Eq)

The declaration allows us to create objects out of basic types such as Obj 1 and Obj "1", two different objects. It is up to the program to create objects where the argument to Obj constructor is only an integer. Objects created such are referred to as integer objects which cannot be compared to other types of objects like string objects Obj "1".

The arrow from object a to object b is (a, b). Because the arrow between any two objects is unique, a label on the arrow is not necessary. Instead, we declare the type for an arrow in this restricted case.

data Arrow o = Arrow (Obj o) (Obj o) deriving (Show, Eq)

The identity arrow on the object returns the identity arrow and is specified as the following function.

id1 (Obj o) = Arrow (Obj o) (Obj o)

Composition of arrows (a,b) and (b,c) is a arrow (a, c). Note that a pair of arrows can only be composed when the tail of the first arrow is the head of the second arrow. The arrow (a,c) can be considered the number c-a. There are multiple representations of an integer. For instance, id1(o) for any object o refers to the number 0. The general strategy to compose two arrows (a,b), (c,d) is to check if the object b is the same as object c, in which case from a new arrow, else return an error. Maybe type is used for error. The result of the composition is a Maybe Arrow.

comp1 :: (Eq o) => Arrow o -> Arrow o -> Maybe (Arrow o)
comp1 (Arrow a b) (Arrow c d)
  | b == c = Just (Arrow a d)
  | otherwise = Nothing

The addition is now equivalent to the composition of functions. Obj j can be thought of as number j. However, addition is to performed using composition; therefore, we need to associate arrows with integers. Numbers 1 and 3can be represented as arrows((Obj 1), (Obj 2)) and ((Obj 2), (Obj 5)). Composing them gives us the arrow ((Obj 1), (Obj 5)) which means the number 4. Composing ((Obj 1), (Obj 2)) with ((Obj 3), (Obj 4)) is not allowed therefore the function returns Nothing. There are pairs of arrows that represent 1, 3 and are not composable. One can think of an arrow from i to j where i > j as a negative number with the value j-i. Therefore, this category can handle negative numbers.

Think of this category as a virtual machine, expression 3+4 is translated by a compiler into machine instruction compose (Arrow (Obj 1) (Obj 4)) (Arrow (Obj 4) (Obj 8)). The machine knows how to compose arrows and returns the results Arrow (Obj 1) (Obj 8) which is another representation for number 7. The result of the composition is an evaluation of the expression 3+4.

This example allows for only one arrow between a pair of objects; if there are more arrows within a pair, there is a need to label the arrows. The datatype NewArrow can be used to create arrows with labels or code. NewArrow (Obj 1) "1" (Obj 2) creates an arrow with label 1. Similarly NewArrow (Obj 1) (\x -> x) (Obj 2) creates an arrow with a function as the label. Function types cannot be printed (Show is not inherited) though in Haskell.

data NewArrow o a = NewArrow (Obj o) a (Obj o) deriving (Show, Eq)

Addition can be accomplished in a different category as well. This category contains only a single object () and arrows, one for each number. NewArrow (Obj ()) "111" (Obj ()) represent number 3 in unary. The composition of two arrows can be written as a new arrow with a label which a concatenation of the two labels. This simple category on a single object is also known as a monoid.