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 learnyouahaskell.com 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.