[Haskell-cafe] category design approach for inconvenient concepts

[wren ng thornton]

On 12/18/12 5:03 PM, Christopher Howard wrote:
> Since I received the two responses to my question, I've been trying to
> think deeply about this subject, and go back and understand the core
> ideas. I think the problem is that I really don't have a clear
> understanding of the basics of category theory, and even less clear idea
> of the connection to Haskell programming. I have been reading every link
> I can find, but I'm still finding the ideas of "objects" and especially
> "morphisms" to be quite vague.

As others have mentioned, that "vagueness" is, in fact, intentional. 
There are two ways I can think of to help clear up the abstraction. The 
first is just to give a bunch of examples:

the category of sets (objects) and set-theoretic functions (morphisms)
the category of Haskell types and Haskell functions[1]
... (small) categories, and functors
... rings, and ring homomorphisms
... groups, and group homomorphisms
... vectors, and linear transformations
... natural numbers, and matrices
... elements of a poset, and the facts that one element precedes another
... nodes of a directed graph, and paths on that graph


The second approach is to compare it to something you're already 
familiar with. I'm sure you've encountered monoids before: they're just 
an associative operation on some carrier set, plus an element of that 
set which is the identity for the operation. Perhaps the most auspicious 
one to think about is multiplication, or concatenation of lists.

A category is nothing more than a generalization from monoids to 
"monoid-oids". That is, with monoids we give our operator the following 
type:

     (*) :: A -> A -> A

but sometimes things aren't so nice. Just think about matrix 
multiplication, or function composition. These are partial operations 
because they only work on some subset of A. The two As must air up in a 
nice way. Thus, what we really have is not one carrier, but a family of 
carriers which are indexed by their "input" end (domain) and their 
"output" end (codomain). Thus, we have the type:

     (*) :: A i j -> A j k -> A i k

or

     (*) :: A j k -> A i j -> A i k

where i, j, and k, are our indices. Which one of the above two types you 
get doesn't matter, it's just the difference between (<<<) and (>>>) in 
Haskell. Of course, now that we've indexed everything, we can't have 
just one identity element for the operation; instead, we need a whole 
family of identity elements:

     1 :: A i i

In a significant sense, the objects are really only there to serve as 
indices for the domain and codomain of a morphism. They need not have 
any other significance. A good example of this is when we compare two of 
the example categories above: linear transformations, vs matrices. For 
the category of vector spaces and linear transformations, the objects 
actually mean something: they're vector spaces. However, in the category 
of natural numbers and matrices, the natural numbers only serve to tell 
us the dimensions of the matrices so that we know whether we can 
multiply them together or not. Thus, these are different categories, 
even though they're the same in just about every regard.


[1] Note that this may not actually work out to be a category, but the 
basic idea is sound.


> But here I am
> confused: If "functions" are a category, this would seem to imply (by
> the phrasing) that functions are the objects of the category. However,
> since we compose functions, and only morphisms are composed, it would
> follow that functions are actually morphisms. So, in the "function"
> category, are functions objects or morphisms? If they are morphisms,
> then what are the objects of the category?

Objects in Haskell are types, and functions aren't types. But cherish 
that confusion for a bit, because it hints at a deeper thing going on 
here. In the simplest scenario, functions are the morphisms between 
objects (i.e., types). But what happens when we consider higher-order 
functions?

In Haskell we write things like:

     (A -> B) -> C
     D -> (E -> F)

Whereas, in category theory we would distinguish the first-order arrows 
from the higher-order arrows:

     B^A -> C
     D -> F^E

That is, we have an object B^A (read that as an exponent), and we have a 
class of morphisms A->B (sometimes this class is instead written 
Hom(A,B)). These are different things, though we willfully conflate them 
in functional programming. The B^A can be thought of as the class of all 
functions from A to B when we consider these functions as data; whereas 
the A->B can be thought of as the class of all functions from A to B 
when we consider these functions as procedures to be executed. Part of 
the reason we conflate these in functional programming is because we 
know that the one reflects the other. Whereas the reason category theory 
distinguishes them is because this sort of reflection isn't possible in 
all categories. Some categories have exponential objects, others don't.[2]

Thus, when you ask whether a function belongs to an object or to a 
Hom-set, the answer depends on what exactly you're talking about.


[2] There are reasons to make this distinction in programming as well. 
For one, not all programming languages allow higher-order functions. But 
more importantly, even for those that do, the compiler writers already 
have to make the distinction. Functions-as-data basically require us to 
use closures in some form or another. These closures are basically just 
records that we can pass around like any other data. But 
functions-as-procedures are just code pointers (or, rather, the location 
pointed to by them), they're just somewhere to jump to and start 
executing code. Clearly these are different things even if we can go 
back and forth by storing a code pointer in a record and by jumping to 
the address stored in a closure.

-- 
Live well,
~wren