[Haskell-cafe] category design approach for inconvenient concepts

[Richard O'Keefe]

On 19/12/2012, at 11:03 AM, 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.

Roughly speaking, Category Theory is the study of mathematical analogies
that work.  You notice that the symmetries of a cube have properties that
remind you of the properties of integer addition, and end up constructing
Group Theory to describe a huge range of things that can be modelled as
"things" acted on by "operations" to give other things, where the operations
follow particular laws.  And you get this astonishing range of theorems that
have lots of not-obviously-related applications.  Then you notice that
Group Theory and Lattice Theory and a bunch of other things seem to have
more analogies than you expected, and you abstract out what they have in
common (structured collections of things with transformations from one
structure to another that preserve various properties of the structured
collections).

What's the connection to Haskell programming?

Reusability.

Both Category Theory and Haskell push rather harder on abstraction than
most people are comfortable with, in order to get mathematical results in
the one case and functional code in the other that can be applied to lots
of problems.

The price of reusability is vagueness.

Let me offer an analogy.   At primary school I was introduced to the
greatest common divisor and Euclid's algorithm.  Here's this algorithm
that applies to integers and this is what it tells you.  And in a
program you might write gcd(x,y).  These days, I look at gcd and see
"oh yes, the meet in the 'divides' lattice" and write x/\y, where
the same symbol ("meet", /\) can be used for gcd, set intersection,
bitwise and, unification, ...) and I know more _laws_ that /\ obeys
than I did back then, but the integers have receded from view.

> The original link I gave
> <http://www.haskellforall.com/2012_08_01_archive.html> purposely skipped
> over any discussion of objects, morphisms, domains, and codomains. The
> author stated, in his first example, that "Haskell functions" are a
> category, and proceeded to describe function composition.

This mailing list often talks about the "Hask" category.
For example, in Orchard's blog (http://dorchard.wordpress.com) we find

	The Hask category

	The starting point of the idea is that programs in Haskell
	can be understood as providing definitions within some
	category, which we will call Hask.  Categories comprise
	a collection of objects and a collection of morphisms
	which are mappings between objects.  Categories come
	equipped with identity morphisms for every object and
	an associative composition operation for morphisms
	(see Wikipedia for a more complete, formal definition).
	For Hask, the objects are Haskell types, morphisms are
	functions in Haskell, identity morphisms are provided
	by the identity function, and composition is the usual
	function composition operation.

In Hask, Haskell functions are the *morphisms* of a category, not its
objects.  That's not to say that you couldn't have a category whose
objects were (in some sense) Haskell functions, just that it would be
a different category.  Rather confusingly, the "objects" of Hask are
*not* data values, they are data *types*.  This is just like the way
that in the category of sets, the objects are *sets*, not their
elements.

But of course category theory is too general for a neat summary like
"objects are sets or types and morphisms are functions between them".
No, objects are _whatever_ you choose to model as not-further-analysed
objects, and morphisms are _whatever_ connections between your objects
you choose to model as morphisms, so long as they obey the laws.

I am struggling with category theory myself.  I'll be learning about
some kind of mathematical structure, getting to grips with the elements
and the operations on the elements, and suddenly the book will move up
a level and instead of looking at patterns between elements, will look
at patterns of morphisms.  And to add insult to injury, the book will
claim that moving from one large space to an exponentially larger
(if not worse) space remote from the things I'm trying to understand
actually makes things _simpler_ to think about.  One of my colleagues
here divides people into "set theory people" and "category theory
people".  He and I both classify ourselves as "set theory people".
Maybe in another 50 years I'll be comfortable with category theory,
but by then I'll be dead.

Right now, the issues for you are

 - Haskell people care about category theory both because they tend
   to have a high tolerance for abstraction in the first place AND
   because of the practical benefits of highly reusable code

 - you don't have to understand it to use Haskell effectively

 - if you don't understand a tutorial about Haskell and category
   theory, the author might know a lot more than you, or might be
   even more confused about it than you are

 - even a set-theory person like me can get the idea of monoids
   and other algebraic things that can be modelled in Haskell,
   and using that kind of pattern can make your code cleaner/
   more general without having to worry about the theory behind it

 - information can often be modelled in more than one way;
   a good modelling is one that is useful for Orchard's "Four Rs"
   (Reading, 'Riting, Reasoning, and Running).  If some approach
   doesn't seem to help with these, I don't care how highly
   people think of that approach, it's not right for your problem.


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