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

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.

On Tue, Dec 18, 2012 at 4:49 PM, Ertugrul Söylemez wrote:

These laws make morphisms isolated and composition lightweight as well as undisturbing. Now try to transfer these notions to a concrete category, for example the category of web servers: The objects are sets and a morphism f : A -> B is a function from A × Request to B.

Expanding on this point, we can "refactor" how we "present" this category, using laws from basic category theory, so that f :: (A, Request) -> B f :: A -> Request -> B f :: A -> (Request -> B) f :: (A -> Request) -> B (this one isn't very useful to a programmer) f :: a -> Request B (by lifting a concrete Request object into a functor of the form (Request a)) etc, are all "equivalent", insofar as they merely present different interfaces to the same data. Note that these are distinct as "presentations", but equivalent as categories ("isomorphic", up to decidability -- the one I said wasn't useful really isn't, because "as a matter of fact", we can't decidably analyze/deconstruct a function (g :: A -> Request) to produce a B). This should make architectural decisions easy (or hard) -- once you have decided to use a category at all, you merely have to choose the presentation for the category that satisfies other requirements.

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

On Thu, 20 Dec 2012, Oleksandr Manzyuk wrote:

...

the category of Haskell types and Haskell functions[1]

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

I would be curious to see this example carefully worked out. I often hear that Haskell types and Haskell functions constitute a category, but I have seen no rigorous definition.

I have no problems with the statement "Objects of the category Hask are Haskell types." Types are well-defined syntactic entities. But what is a morphism in the category Hask from a to b? Commonly, people say "functions from a to b" or "functions a -> b", but what does that mean? What is a function as a mathematical object? It is a plausible idea to say that a function from a to b is a closed term of type a -> b (and terms are again well-defined syntactic entities). How do we define composition? Presumably, by

f . g = \x -> f (g x)

This however already presupposes that we are dealing not with raw terms, but with their alpha-equivalence classes (otherwise the above is not well-defined as it depends on the choice of the variable x). Even if we mod out alpha-equivalence, so defined composition fails to be associative on the nose, up to equality of (alpha-equivalence classes of) terms. Apparently, we want to consider equivalence classes of terms modulo some finer equivalence relation. What is this equivalence relation? Some kind of definitional equality?

Apparently, this (rather non-trivial) exercise has already been carried out for the simply typed lambda-calculus. I'd be curious to see how that generalizes to Haskell (or some equivalent formal system).

Sasha

Yes. It would be well worth carefully carrying out your program for some approximation of a large part of Haskell as she lives in GHC. As mentioned earlier, we should not ignore the distinctions between 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 Attempting to force the hoped for clarification to operate only on one part of the whole at least four part structure is likely to not give us what we, ah, I, really want to see. There is some work directly dealing with part of the program: http://www.haskell.org/haskellwiki/Hask oo--JS.

-- Oleksandr Manzyuk http://oleksandrmanzyuk.wordpress.com

On Fri, Dec 21, 2012 at 4:40 AM, Alexander Solla wrote:

On Thu, Dec 20, 2012 at 12:53 PM, Oleksandr Manzyuk wrote:

...

I have no problems with the statement "Objects of the category Hask are Haskell types." Types are well-defined syntactic entities. But what is a morphism in the category Hask from a to b? Commonly, people say "functions from a to b" or "functions a -> b", but what does that mean? What is a function as a mathematical object? It is a plausible idea to say that a function from a to b is a closed term of type a -> b (and terms are again well-defined syntactic entities). How do we define composition? Presumably, by

f . g = \x -> f (g x)

This however already presupposes that we are dealing not with raw terms, but with their alpha-equivalence classes (otherwise the above is not well-defined as it depends on the choice of the variable x). Even if we mod out alpha-equivalence, so defined composition fails to be associative on the nose, up to equality of (alpha-equivalence classes of) terms. Apparently, we want to consider equivalence classes of terms modulo some finer equivalence relation. What is this equivalence relation? Some kind of definitional equality?

I don't see how associativity fails, if we mod out alpha-equivalence. Can you give an example? (If it involves the value "undefined", I'll have something concrete to add vis a vis "moral" equivalence)

If you compute (f . g) . h, you'll get \x -> (f . g) (h x) = \x -> (\x -> f (g x)) (h x), whereas f . (g . h) produces \x -> f ((g . h) x) = \x -> f ((\x -> g (h x)) x). As raw lambda-terms, these are distinct. They are equal if you allow beta-reduction in bodies of abstractions. That's what I meant when I said that we probably wanted to consider equivalence classes modulo some equivalence relation. That hypothetical relation should obviously preserve beta-reduction in the sense (\x -> e) e' = [e'/x]e. When we do equational reasoning about Haskell code, we apply certain rules. I think what I'm asking for is an explicit complete set of such rules. Note that sometimes you can also hear that the category of Haskell is a suitable cpo category. However, this is an answer to a slightly different question: what is the categorical model of Haskell? That is, what kind of categories can Haskell programs be interpreted in. What I'm after is a kind of universal syntactic Haskell category. I expect the situation to be similar to the simply typed lambda-calculus but more technically involved. The simply typed lambda-calculus can be interpreted in any cartesian closed category, but it is also possible to construct a cartesian closed category out of the simply typed lambda-calculus. As someone coming to Haskell and functional programming from category theory background, I'm probably paying to much attention to details that don't concern most practicing functional programmers... Sasha -- Oleksandr Manzyuk http://oleksandrmanzyuk.wordpress.com

On 12/18/2012 08:02 PM, Gershom Bazerman wrote:

On 12/17/12 9:45 PM, Christopher Howard wrote:

I don't think you're describing a "Category" in the sense of the Haskell Category typeclass. But that's ok! Just because some things are categories and are nice doesn't mean that we can't have other nice things that aren't necessarily categories. My first thought was something with multiple inputs and one output is often an Operad (http://en.wikipedia.org/wiki/Operad_theory) but associativity is still an issue. Also bear in mind that operads and categories are both *directional* whereas your notion of coupling doesn't seem to be (which has something to do with associativity failing, I'd imagine).

I think the example I gave was pretty messed up anyway, because I was trying to compose objects rather than morphisms. But that directional aspect you mentioned does seem significant... so I guess my main question is how that things that are more complex (like a multi-directional system built from pluggable components) could be represented in the Categorical manner. I'm looking for the Grand Unifying Theory to follow, if you will; I really like the idea that all parts of my program could be cleanly and systematically composed from smaller pieces, in some beautiful design patter. Many of the problems in my practical programming, however, are not like the examples I have seen (nice pipes or unidirectional calculations) but rather complex fitting together of components. E.g., space ships are made up of guns + engines + shields + ammo. Different kinds of space ships may use the same kind of guns (reusable components) but some wont. Some will have many guns, some will have none. And such like issues. Soylemez seems to have answered this issue directly in his reply. Unfortunately, I didn't understand most of what he wrote. :|

I also don't understand, e.g., what happens if I couple a thing with two connectors and one connector -- which connector from the first gets used, or are they interchangeable?

The example I gave was hastily put together and not well thought out. I was Just trying to come up with something that would convey the general idea. But perhaps each component would have a list of connectors, and the first ones in the list would be used first. When a new component was created from other components, the new list would be taken from the leftover connectors (if any). In real world use I would probably have multiple types of connectors, but I haven't thought that far ahead.

Going back even further, you've suggested a "Fail" to represent when the connectors don't match. Why not start with encoding connectors in types to begin with, so that it is a type error to not have matching connectors? Follow the logic of your idea, shape your types to match your representable states, and then see what algebraic structures naturally emerge.

Cheers, Gershom

Sounds good. Of course, I still haven't figured out what design pattern to fit said types into. :( -- frigidcode.com

I have also become intrigued and confused by this "category theory" and how it relates to Haskell. It has been stated many times that you don't need to understand category theory to utilize the Haskell language but all the concepts, patterns and every paper describing them seems to be written by someone who understands it. It really appears that to "innovate" in this community it helps to at least have a basic understanding of the theory. I have started working through this book "Conceptual Mathematics, A first introduction to categories" and so far it seems very understandable and interesting for mere mortals like myself. -- View this message in context: http://haskell.1045720.n5.nabble.com/category-design-approach-for-inconvenie... Sent from the Haskell - Haskell-Cafe mailing list archive at Nabble.com.