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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
