[Haskell-cafe] category design approach for inconvenient concepts

[Jay Sulzberger]

On Tue, 18 Dec 2012, Christopher Howard wrote:

> On 12/17/2012 06:30 PM, Richard O'Keefe wrote:
>>
>> On 18/12/2012, at 3:45 PM, Christopher Howard wrote:
>>
>> It's basically the very old idea that an Abstract Data Type
>> should be a nice algebra: things that look as though they
>> ought to fit together should just work, and rearrangements
>> of things ought not to change the semantics in surprising
>> ways (i.e., Don't Be SQL).
>>
>>
>>
>> Categories contain two things:
>>     "objects"
>> and "arrows" that connect objects.  Some important things about arrows:
>>  - for any object x there must be an identity id<x> : x -> x
>>  - any two compatible arrows must compose in one and only one way:
>>    f : x -> y & g : y -> z  =>  g . f : x -> z
>>  - composition must be associative (f . g) . h = f . (g . h)
>>    when the arrows fit together.
>>
>> Of course for any category there is a dual category,
>> so what I'm about to say doesn't really make sense,
>> but there's sense in it somewhere:  the things you are
>> trying to hook together with your <.> operator seem to me more
>> like objects than arrows, and it does not seem as if
>> they hook together in one and only one way, so it's not so
>> much _associativity_ being broken, as the idea of <.> being
>> a composition in the first place.
>>
>>
>
> 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.

Much discussion that I have seen of "categories and Haskell" is
imprecise.  It is often possible to convey some fact, or point of
view, using imprecise language, but in many cases, the
communication will fail, unless the reader has a solid
understanding of the basics.  Getting this understanding requires
studying harsh and, often, off putting, textbooks.

I will say two things:

1. Usually, to understand category theory a firm grasp of the
concept "structure" is required.

2. To connect categories with Haskell requires some apparatus,
which apparatus should be laid out precisely, at least once in
the exposition.

ad 1: By "a structure" I mean what Bourbaki calls "a structure".
       See:

   http://en.wikipedia.org/wiki/Mathematical_structure
   [page was last modified on 7 August 2012 at 17:15]

   http://en.wikipedia.org/wiki/Structure_%28mathematical_logic%29
   [page was last modified on 15 December 2012 at 19:36]

   http://en.wikipedia.org/wiki/Algebraic_structure
   [page was last modified on 11 December 2012 at 02:51]

ad 2: The tutorial should carefully distinguish these different
things:

       a. the text of a Haskell program
       b. the binary of the now compiled program
       c. the running of the program
       d. the input output behavior of the program

Each of these gives rise to at least one category, and there are
various functors among these categories.

Set theory, say ZFC style, and New Crazy Type Theory, offer two
different Backround Mechanisms to explicate the notion of
"structure".  There are similarities between these two Grand
Theories, but there are also political differences.

ad seeming vagueness of the notions object and morphism: This
vagueness, which is felt by all students at first, is often
explicated/excused by saying that the notions are "more abstract"
than say, the notions of "integer" and "addition of integers" and
"multiplication of integers".  This way of speaking is not
entirely wrong, but I think it mainly wrong and misleading.
Bourbaki somewhere says something like:

   Recent mathematics characteristically differs from older
   mathematics in that our axiom systems usually have more than
   one model, whereas in the old mathematics, theories usually had
   only one model.

Here is how this explicates the sentence:

    The theory of rings is more abstract than the theory of
    addition and multiplication of the integers.

We all know the integers.  The integers form a set, with such
elements as 0, 1, 17, -345, and so on.  We have learned two
operations on this single set: addition and multiplication.  This
understanding is a "concrete" understanding of a single concrete
object, which does indeed have parts, such as -345, and the
operation +, for example, but all the statements we might make
can, in some sense, be settled by looking at this single
structure and its various parts.  Or so we feel.  (Note in the
sentence in which there are two occurences of the word
"concrete", the two occurences must have different sense.)

But the theory of rings is quite a different theory.  There are
many different structures which are studied in the theory of
rings.  For example the ring of integers is one such structures.
There is also the ring of complex numbers.  There is also the
ring of 2 x 2 matrices over the integers.  Another ring is the
ring of 3 x 3 matrices over all polynomials in 6 indeterminates,
say x0, x1, x2, x3, x4, x5.  What do these objects have in
common, as far as the theory of rings is concerned?  Well, they
are all rings, for whose formal mathematical definition see a
textbook or Wikipedia.  Here is one free textbook on abstract
algebra which gives the formal definition of a ring in Chapter 3:

   http://www.math.miami.edu/~ec/book/

Dangerous Bend: For the theory of programming languages, often
the student will demand a higher degree of a style of precision
that is offered by many abstract algebra textbooks.  Some do meet
this demand.

Let us give some examples of "structures":

1. A pair of sets is a pair (A,B) both A and B being sets and
with A being a subset of B.  There are many such things.

2. A monoid is a set M with a binary operation * and a constant
1.  The axioms are (a*b)*c = a*(b*c), all a,b,c in M and 1*a =
a*1, all a in M.

3. A category is a pair of sets (Obj,Mor) with these operations:

    a. given any m \in Mor we have head(m) an object in Obj,
       and tail(m) an object Obj
    b. given any a \in Obj we have an object id(a) in Mor, with
       head(id(a)) = a and tail(id(a)) = a.
    c. given any two m, n \in Mor, if we have
       head(m) = tail(n) we have a third morphism m*n with
       tail(m*n) = tail(m) and head(m*n) = head(n).
    c'.Given any two m, n \in Mor, m*n is only defined in case
       the condition in c is met.
    d. Let m,n,o \in Mor.  Suppose that m*n and n*o are defined,
       that is, by c and c', head(m) = tail(n) and head(n) = tail(o).
       Then head(m*n) = tail(o) and head(m) = tail(n*o) and further
       (m*n)*o = m*(n*o)

4. A graph with loops everywhere is the same thing as a category
    except we have no binary operation *.  Such structures are not
    as famous as rings or categories, but nonetheless, they are a
    well defined set of structures.

Now sometimes it is said:

    And the theory of categories is more abstract than the theory
    of rings.

This is again partly right and partly wrong.  Part of what is
right is something like this:

    The set of rings with ring homorphisms form a category, with
    every ring being an object, and every homorphims of rings
    being a morphism.  So there is an important, and patent to the
    student in the first class in abstract algebra, category
    associated to the set of rings.  Similarly the set of groups
    and group homorphisms form a category in a similar equally
    patent way.  So might continue our rise "in abstraction" by
    studying the collection of categories.  Which collection is at
    a higher level than the collection of rings, or say, groups.

To return to Bourbaki's statement:

    A category is anything which satisfies the definition above.
    And so there are many categories.  The objects and morphisms
    need not be sets in any sense.  For example there is a
    category with one object, call it o, and one morphism, call it
    m.  Then if we define

    head(m) = o
    tail(m) = o
    id(o) = m
    m*m = m

    we have a category.  Note that o is not a set, it is just
    something we have called "o".  So m is certainly not a map of
    sets, because we have no set to be the head of m, nor any set
    to be the tail of m.

Important: Many times categories have a second "lower level"
structure, like the category of rings.  That is, every object in
the category of rings is a set with various operations defined on
the set.  But sometimes a particular category is not given to us
with such a lower level structure, like our small category with
only one object and one morphism as defined above.

Here is one book which mainly deals with categories where "the
objects are sets" and where the category itself "respects the
sets":

   http://katmat.math.uni-bremen.de/acc/acc.pdf

Just to give categories whose objects are not sets, we note that
every partially ordered set is a category.  For one such the set
of positive integers under divisibility is a poset, and so a
category.  But an integer is not a set, and so the morphism "17
divides 51" does not hand us a map of sets.  If we take our set
of objects to be again the positive integers, with the morphisms
being all finite matrices with real entries, and for an a x b
matrix m, define head(m) = b and tail(m) = a, and with
composition being matrix multiplication, we have another category
where the objects are not sets.

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

Your puzzlement is justified, and I will not respond now.

I will repeat that we must, to begin our study, distinguish
these things:

       a. the text of a Haskell program
       b. the binary of the now compiled program
       c. the running of the program
       d. the input output behavior of the program

oo--JS.


PS. I have likely mixed up heads and tails and the convention
about which way composition of morphisms is written on the page,
for which mixups I beg your forbearance.