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.