10 ms·

Category theory for beginners

122 points by lelf 12y ago

alfonsodev 12y ago
is there any video/audio that complements this slides ?
- throw7 12y ago
  That is my question. I'm not sure how I'm supposed to learn anything from a powerpoint presentation (the worst way to convey any type of information).
- kenbot 12y ago
  Hopefully! We'll find out soon. Fingers crossed.
keslag 12y ago
As a beginner, I can assure you that without someone explaining the point of the arrows, this is most certainly not for beginners.
- aidos 12y ago
  Right, so can someone explain what the hell these slides mean? I studied a lot of abstract mathematics at uni but I wasn't exposed to category theory, and these slides aren't helpful. They start off with objects, what are they? Are they sets? I'm going to assume they're sets. Then the arrows represent mappings, something like a function that takes an input and maps to stuff in one of those other objects (set of objects?). Then the codomain is the set of objects you can get to by calling that function on the domain of objects. Am I in the right ball-park here?
  - tel 12y ago
    Heh, not quite. Treat objects and arrows abstractly like you're building a graph. Actual meaning can be applied later. A category is thus a set (or proper class) of objects, O, and a set (or proper class) of arrows, A along with two mappings dom and cod from A -> O. The laws are first that for any object (o in O) there exists an arrow (id(o) in A) such that dom(id(o)) = o and cod(id(o)) = o and second that if you have two arrows (f, g in A) such that cod(f) = dom(g) then there is defined their composition (compose(f,g) in A) such that dom(compose(f,g)) = dom(f) and cod(compose(f,g)) = cod(g). You can draw all that as the objects and arrows and things these slides display. So far this just gives you a graph-like structure. The "category laws" ensure coherence of the category and state that (compose(f, id(x)) = f) when defined, (compose(id(x), g) = g) when defined, and that compose is associative. From an abstract algebraic POV this is almost like saying that A is a monoid which ought to (correctly) suggest that most of the interesting structure of a category is carried by the arrows. Now, if you want to talk about specific categories you can do what you were doing. For instance, the category of sets, Set, is the category where you take O to be the proper class of all sets and A to be the functions between them. Immediately, you'll find that dom(.)/cod(.) are the domain and codomain of your functions, id(.) locates the identity function on a set, and compose(.,.) composes functions. As a more interesting example you could consider Grp the category where O is all groups and A is all group homomorphisms. This is a subcategory of Set obviously and it also comes with much more interesting structure. For instance, an important category theoretic statement about Grp is that Grp has a "zero object", which is to say that (a) there exists an object init such that there is a unique arrow from init to any other object, (b) there exists an object fin such that there is a unique arrow from any other object to fin, and (c) init = fin. http://en.wikipedia.org/wiki/Zero_object_%28algebra%29 http://en.wikipedia.org/wiki/Zero_object_%28algebra%29
    - deleted 12y ago
      [deleted]
  - xyzzyz 12y ago
    Ah, the joys of learning math from slides without the talk the slides were helpers to. The objects here are not necessarily sets, and the arrows are not necessarily functions -- this is actually one of the points of category theory, to abstract the notion of morphism away from set theory. This becomes necessary, when in your regular mathematical life you encounter morphisms which are not strictly functions, but nevertheless in many ways behave as such. Best example would be the homotopy classes of maps between topological spaces. Homotopy classes do not map points from domain space to codomain space, but nevertheless you can compose them, there's a homotopy class of identity, which acts as an identity on composition, sometimes there are homotopy classes that are inverses and so on. If this sounds complicated and unnatural, that's because it is: it is pointless to learn category theory before learning where and how it is useful. This is completely opposite order than in which it was conceived, and totally misses the purpose the category theory, which is to make everything clearer, to reduce the number of notions, to make it easier to notice analogous behavior between separate concepts, to reduce number of repeating arguments. Learning what a morphism or functor or natural transformation is, without having tens of examples of these notions, only increases the number of concepts without a corresponding increase in understanding. My advice is, if you want to learn category theory, learn algebraic topology first, or at least abstract algebra (groups, rings, modules, fields). Otherwise, you'll see very little purpose, and very little use.
    - nrinaudo 12y ago
      I disagree with your last point, to some extent. While not strictly necessary, learning a bit of category theory makes FP abstractions such as functors and monoids a bit more accessible. I can't disagree with the fact that learning category for that sole purpose sounds like a lot of work for too little benefit, though.
    - ww2 12y ago
      Good point but examples can also be drawn from other fields like programming rather than from mathematics. So far I found that the link below is very enlightening. http://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/ http://bartoszmilewski.com/2014/10/28/category-theory-for-pr...
  - enord 12y ago
    They are arrows. Arrows and objects are the primitives of category theory, just like sets and set membership are the primitives of set theories (well most of them anyway). A category that captures the notion of sets and maps can be described in terms of arrows, objects and some semantic rules about which arrows (here interpreted as maps) connect which objects (here interpreted as sets). Wiki on the "Category of sets [and maps]" -> http://en.wikipedia.org/wiki/Category_of_sets http://en.wikipedia.org/wiki/Category_of_sets Other rules about arrows between objects describe categories that capture other mathematical concepts.
- nrinaudo 12y ago
  I think it's "explained" when you go from slide 6 to 7. Slide 6: objects are points in space. Slide 7: arrows are ways of transforming objects into other objects. I'm no expert, but from my understanding, there is nothing more to be said (other than stating the composition / identity laws): you're at a level of abstraction where you cannot say anything more. Objects. Arrows. An arrow goes from an object to another. If it's any help, you can think of them as mathematical functions, where the origin point is the function's domain and its destination point the function's range (called co-domain in category theory, because why not). Bear in mind that while this example is correct, that's all it is: a concrete example of an abstract notion. If it feels simplistic, that's because it is. Arrows are a trivial notion. It gets more complicated when you study different kinds of arrows (homomorphism, isomorphism, whateverism), or arrows in "concrete" categories (functors are arrows in the category of categories, natural transformations are arrows between functors...).
  - ryanobjc 12y ago
    But is this the best pedagogical approach to teaching this area? In the book "Conceptual Mathematics" the concrete example is finite sets and mapping between finite sets. That is way more understandable than 'objects' and 'how to go from one object to another'. It's just too abstract for a general audience I believe.
    - nrinaudo 12y ago
      It's the only one that does not require knowledge of other fields - not everyone knows set theory (although yes, almost everyone here probably knows enough). Conceptual Mathematics needs concrete example to explain the algebra of function composition, and more importantly to prove certain properties and theorems. This presentation's goals are far more modest and the abstract approach allows it to not take up 700 slides. That being said, I don't think I'd have been able to go through this presentation in its entirety if I hadn't had some previous exposure to the field. So while I disagree with you for discussion's sake, I secretly think you're right.
      - ryanobjc 12y ago
- orbifold 12y ago
  All you really know about arrows, is that you can compose them if the tip of the first arrow fits into the tail of the second arrow, that is the first arrow is from A to B and the second from B to C, in a way that is associative, which means that if you have three arrows, it doesn't matter in which way you compose compose them. Moreover for every object A, there is an identity arrow. Composition with that does yield the original arrow. The point of those axioms is that they are satisfied by lots of different mathematical structures and idealized physical situations as well (Feynman diagrams, Chemical reaction networks, Knot-/Braid diagrams etc.). For how this relates to computation, you can look at http://math.ucr.edu/home/baez/qg-fall2006/index.html#computation http://math.ucr.edu/home/baez/qg-fall2006/index.html#computa... for example. It is a bit more subtle than one would think at first, as in functional programming languages with "first class" functions, those are not not actually arrows, but objects. More precisely the type (A -> B) in Haskell, or (A=>B) in Scala, is a notation for an internal hom object. The more interesting ideas arise when you then study how different such categories relate to each other, you then come up with Functors and how Functors between Categories are related to each other, those are called Natural Transformations. The original motivation for the invention of category theory was the study of natural transformations in homological algebra and algebraic topology. In the preceding years people had come up with several alternative functors (Cohomology / Homology on certain topological spaces) and they needed a way to talk about in what way those constructions were equivalent to each other.
enord 12y ago
This is a top-down approach starting with CT fundamentals and connecting them to CS concepts/patterns after 150 slides. The air is thinner near the top of the abstraction ladder and more or less unbreathable for people who don't spend considerable time in the Ivory Tower.
- muaddirac 12y ago
  I think if I were attempting to make it more accessible for beginners, I would start with a concrete example of a category (like Set) and introduce the concepts in what is, for most people (programmers in particular) familiar territory, and then attempt to show how abstracting those concepts is useful and applicable in other situations.
cheatsheet 12y ago
I scanned through the first 50 slides or so. I've read and drawn out the first few chapters to myself of "Categories for the Working Mathematician", so for me - this was a very nice presentation that graphically illustrated the key forms and key semantics. I look forward to reading the code parts. But I have to agree with other posters - it took a lot of studying to get to the point where I can understand your slides. I think by the time you can read mathematics like this, it is because you already understand it verbosely. As for people who don't agree that this is for beginners, I don't think you will be able to feel like you get it until you sit down with the work and stare at it a lot until it makes sense to you. It sounds stupid and silly, but that's the only way I can really communicate how to learn this stuff with a feeling of adequate understanding. The simplicity and elegance of the pictures do not adequately convey how difficult this stuff is to comprehend, especially if your mathematical foundation involves reasoning about real things. It is descriptive of abstract layers of terms, and the relationships they construct. Category theory is essentially the math of maths.
Xophmeister 12y ago
See also Bartosz Milewski's very nice WIP blog series[1] on category theory for programmers. [1] http://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/ http://bartoszmilewski.com/2014/10/28/category-theory-for-pr...
losvedir 12y ago
These slides do the same misleading thing all the other slides I've looked at do: show examples where there are only an arrow or two between objects. I still don't really understand category theory, but one breakthrough I had was when I realized that two objects can (and often do) have LOTS (or even infinite) arrow between them. For example, in a category of "types", each object could be a type (e.g.: int, float, list(int), etc.), and each arrow could be a function between those types. With that example, just think of all the arrows between, say, string -> int! There's "length()", "md5()", "to_i()", etc. And don't even get me started on the "identity" arrows of string back to itself (upcase, downcase, strip, etc). We're talking gazillions of arrows.
- tfgg 12y ago
  So, on slide 33, the "+1" and "bestFriend" arrows are identities of Int and Person? On slide 35 it says that identity is associated with the identity function, but to me that means a function that returns what you give it, rather than "+1", which gives you the next number. So the identity of Person just means any function with the type signature Person->Person?
  - orbifold 12y ago
    No, the identity id:A->A is characterized by the property that for all arrows f:B->A and g:A->C (P1) id . f = f and (P2) g . id = g, in particular it is unique, since if id':A->A had the same property, then id' = id . id' = id, where the first equality follows by (P1) and the second by (P2').
    - tfgg 12y ago
      Ok, I think I got the wrong idea that the identity was any arrow pointing back on to an object. Thanks.
- cheatsheet 12y ago
  I just sort of abstract over the specifics of the implementation of arrows and assume there is an arrow that denotes the 'kind' of arrow. Does it express a monotonic function (order preserving), does it express a non monotonic function (permutation of elements, ordering of computation of 'typical' threads). It groups functional operations into kinds that you can make assertions about after a selection of the operations have been performed. Haskell does - add :: Integer -> Integer -> Integer so the compiler can check all the branches of code to ensure that statement is invariant.
im3w1l 12y ago
Could someone explain slide 90-92 to me? I know what map does and I know what a functor is, but I don't know scala, so I can't understand what the slides are saying.
- kasey_junk 12y ago
  A trait is a (possibly abstract) type definition. So trait Functor is defining a type definition for something called Functor. Functor[F[_]] to the right of the name indicate that the type Functor is paramterized across a "higher kinded type" (ie it is generic and the thing it is generic against is in turn generic). For this definition we will refer to that higher kinded type as F[_]. def defines a method on the type. So def map means that the type Functor has a method map on it. map[A, B] means that the function map is generic across 2 different types and we will label them A & B. Map takes 2 parameters the first is the higher kinded type F parameterized to A (F of A) and the second is a function that transforms any A to a B. Map returns F parameterized to B. Slide 92 defines it slightly differently. Map is a function with no parameters that returns a function with the first (and only parameter) is a function from A to B and it returns a function from F[A] to F[B].
- hibikir 12y ago
  Tricky Scala bits: The return type is at the end of the function definition, preceded by : . It's optional if there is an implementation provided, as Scala can do type inference. The => is a shorthand for defining a function type. String => Int is a function that takes a String, and returns an Int. [A,B] is saying that the function is a generic function, with some generic types named A and B, that will be resolved at compile time. Not unlike generics in many other languages. so def map[A,B] (fa: F[A], f: A=>B) : F[B] means that we are defining a function map, that takes a Functor of A fa, and a function from A to B, and returns a functor of type F[B]. Slide 92 writes it differently: def map[A,B] : (A=>B) => (F[A] => F[B]) Here, map returns a function that takes a function from A to B, and returns another function, that turns a Functor of A into a functor of B. Now, knowing functors and scala, I don't find those slides that illuminating anyway. I did not think that I'd ever say this about anything, but here it goes. I think Scalaz's implementation is easier to understand.
- 12y ago
cfeduke 12y ago
If I didn't have a couple years of shipping Scala code into production I'm not certain I'd understand the slides by themselves. (Having audio and/or video to go along with the slides would be a great help!) I don't have a math background, but write a lot of Scala anyway. These slides filled in the blanks in a lot of places for me though largely because I could relate to how I've written code. This is an excellent resource and its piqued my interest in learning more about category theory.
j2kun 12y ago
The best exposition I've found for demystifying category theory is the first few chapters of Paolo Aluffi's Algebra: Chapter 0 [1]. The central emphasis is on universal properties, which I see most treatments for beginners de-emphasize or ignore (as these slides do). From my experience, universal properties are the main tool for unifying and abstracting concepts into the language of categories. Aluffi uses category theory to unify the treatment of groups, rings, modules, linear algebra, and then goes on to more abstract category theory. I have also written a bit on this [2], regrettably choosing ML as the language of implementation. [1]: http://www.amazon.com/Algebra-Chapter-Graduate-Studies-Mathematics/dp/0821847813 http://www.amazon.com/Algebra-Chapter-Graduate-Studies-Mathe... [2]: http://jeremykun.com/2013/04/24/introducing-categories/ http://jeremykun.com/2013/04/24/introducing-categories/
- pekk 12y ago
  What's wrong with ML as the language for this?
  - j2kun 12y ago
    Nothing in principle (I wrote the articles, after all). I just found it to be clunky. In particular, the signature and structure system made it needlessly difficult to express what I thought were simple things. And it was difficult to find resources due to standard ML not being widely used.
    - alex-g 12y ago
      Is your work at all based on Rydeheard and Burstall's "Computational Category Theory"? They also do category theory in ML.
- imh 12y ago
  I'm a big fan of that book, but there were a few too many important proofs "left as exercise for reader" for my taste.
  - ch0wn 12y ago
akeck 12y ago
If two categories are related by a functor, does that imply that the first category is isomorphic to the second category? (I'm very new to this topic, but I have an applied math background.)
- j2kun 12y ago
  That's half of it. If you have another functor going the other way, with some properties on how the two functors relate, then you get what's called an equivalence of categories. [1] Basically, you need both ways to compose the two functors to be "equivalent" to the identity functor in each category (equivalent as shown by a reversible natural transformation). [1]: http://en.wikipedia.org/wiki/Equivalence_of_categories http://en.wikipedia.org/wiki/Equivalence_of_categories
ryanobjc 12y ago
This is an ok introduction, but for a much much better introduction check out the book "Conceptual Mathematics". It does a little better than using abstract words like 'objects' (which has a particular connotation for programmers).
- nrinaudo 12y ago
  It also takes bloody ages getting to the "good" parts like monoids and functors :)
runT1ME 12y ago
I am a bit confused, I had thought there could not be multiple isomorphisms from object A to object B. I thought an Iso was an epi and mono, doesn't that mean the arrows must all be the same? Thanks in advance if someone wants to go through all the ways I'm misunderstanding. :)
- nrinaudo 12y ago
  if f is an isomorphism between A and B, it simply means that there exists f-1 such that f(f-1) = idB and f-1(f) = idA. I don't think anything in this definition allows us to conclude that there can only be one such f between A and B. Indeed, if A and B are sets of identical cardinality, I'm pretty sure you can create n! isomorphims between the two (where n=|A|). Drawing a picture of of two sets with two elements each should let you see it.
  - runT1ME 12y ago
    Oh. I think I was confused, arrows can be equal (extensionally so), but not the 'same'.
- orbifold 12y ago
  A group is a category with a single object and whose morphisms are all isomorphisms. There are plenty of groups, so you can't be right :). A morphisms can however have at most one inverse.
commutativering 12y ago
A serious question, and one not meant to cause offense: why is category theory being pushed so aggressively? I've seen numerous "Category Theory for Dummies"-style posts here over the years that all imply CT is somehow extremely relevant to working programmers in ways that other branches of mathematics like analysis or abstract algebra apparently aren't. Considering that most programmers have never rigorously studied even formal logic or set theory, both of which are directly applicable to formal methods, electrical engineering, and relational database theory, wouldn't those subjects be better studied first? Instead of clicking through a 209-slide PowerPoint presentation you likely won't be able understand, I suggest reading these free books on those subjects: http://www.fecundity.com/codex/forallx.pdf http://www.fecundity.com/codex/forallx.pdf http://i.stanford.edu/~ullman/focs.html http://i.stanford.edu/~ullman/focs.html http://www.people.vcu.edu/~rhammack/BookOfProof/ http://www.people.vcu.edu/~rhammack/BookOfProof/
- cschneid 12y ago
  Its riding the haskell bandwagon to some degree. By borrowing ideas from category theory they have some really nice abstractions in practical code. But then it gets more confusing so you want to loop back and see what the actual definition of a "monoid" is, or understand "functors". Even if haskell's idea of functor isn't 1 to 1 with category theory's.
  - bstamour 12y ago
    The only thing I can think of that's wrong with Haskell's functors is that they're more specifically endofunctors, or am I missing something else?
    - jberryman 12y ago
      And Hask is arguably not a proper category
      - bstamour 12y ago
        Can you expand on this? I'm genuinely curious.
serve_yay 12y ago
As thankful as I am that this was made and published, I find only slides with no talk very difficult to try to learn from. I kinda wish slideshare wasn't a thing :/
kenbot 12y ago
Hi everyone, author here. One thing to remember is that each slide had a lot of verbal explanation around it, so I'm not surprised that it's confusing by itself! We took a video, so hopefully it turns out OK so we can put it online.

122 points by lelf 12y ago

alfonsodev 12y ago

is there any video/audio that complements this slides ?

throw7 12y ago
That is my question. I'm not sure how I'm supposed to learn anything from a powerpoint presentation (the worst way to convey any type of information).
kenbot 12y ago
Hopefully! We'll find out soon. Fingers crossed.

keslag 12y ago

As a beginner, I can assure you that without someone explaining the point of the arrows, this is most certainly not for beginners.

aidos 12y ago
Right, so can someone explain what the hell these slides mean? I studied a lot of abstract mathematics at uni but I wasn't exposed to category theory, and these slides aren't helpful. They start off with objects, what are they? Are they sets? I'm going to assume they're sets. Then the arrows represent mappings, something like a function that takes an input and maps to stuff in one of those other objects (set of objects?). Then the codomain is the set of objects you can get to by calling that function on the domain of objects. Am I in the right ball-park here?
- tel 12y ago
  Heh, not quite. Treat objects and arrows abstractly like you're building a graph. Actual meaning can be applied later. A category is thus a set (or proper class) of objects, O, and a set (or proper class) of arrows, A along with two mappings dom and cod from A -> O. The laws are first that for any object (o in O) there exists an arrow (id(o) in A) such that dom(id(o)) = o and cod(id(o)) = o and second that if you have two arrows (f, g in A) such that cod(f) = dom(g) then there is defined their composition (compose(f,g) in A) such that dom(compose(f,g)) = dom(f) and cod(compose(f,g)) = cod(g). You can draw all that as the objects and arrows and things these slides display. So far this just gives you a graph-like structure. The "category laws" ensure coherence of the category and state that (compose(f, id(x)) = f) when defined, (compose(id(x), g) = g) when defined, and that compose is associative. From an abstract algebraic POV this is almost like saying that A is a monoid which ought to (correctly) suggest that most of the interesting structure of a category is carried by the arrows. Now, if you want to talk about specific categories you can do what you were doing. For instance, the category of sets, Set, is the category where you take O to be the proper class of all sets and A to be the functions between them. Immediately, you'll find that dom(.)/cod(.) are the domain and codomain of your functions, id(.) locates the identity function on a set, and compose(.,.) composes functions. As a more interesting example you could consider Grp the category where O is all groups and A is all group homomorphisms. This is a subcategory of Set obviously and it also comes with much more interesting structure. For instance, an important category theoretic statement about Grp is that Grp has a "zero object", which is to say that (a) there exists an object init such that there is a unique arrow from init to any other object, (b) there exists an object fin such that there is a unique arrow from any other object to fin, and (c) init = fin. http://en.wikipedia.org/wiki/Zero_object_%28algebra%29 http://en.wikipedia.org/wiki/Zero_object_%28algebra%29
  - deleted 12y ago
    [deleted]
- xyzzyz 12y ago
  Ah, the joys of learning math from slides without the talk the slides were helpers to. The objects here are not necessarily sets, and the arrows are not necessarily functions -- this is actually one of the points of category theory, to abstract the notion of morphism away from set theory. This becomes necessary, when in your regular mathematical life you encounter morphisms which are not strictly functions, but nevertheless in many ways behave as such. Best example would be the homotopy classes of maps between topological spaces. Homotopy classes do not map points from domain space to codomain space, but nevertheless you can compose them, there's a homotopy class of identity, which acts as an identity on composition, sometimes there are homotopy classes that are inverses and so on. If this sounds complicated and unnatural, that's because it is: it is pointless to learn category theory before learning where and how it is useful. This is completely opposite order than in which it was conceived, and totally misses the purpose the category theory, which is to make everything clearer, to reduce the number of notions, to make it easier to notice analogous behavior between separate concepts, to reduce number of repeating arguments. Learning what a morphism or functor or natural transformation is, without having tens of examples of these notions, only increases the number of concepts without a corresponding increase in understanding. My advice is, if you want to learn category theory, learn algebraic topology first, or at least abstract algebra (groups, rings, modules, fields). Otherwise, you'll see very little purpose, and very little use.
  - nrinaudo 12y ago
    I disagree with your last point, to some extent. While not strictly necessary, learning a bit of category theory makes FP abstractions such as functors and monoids a bit more accessible. I can't disagree with the fact that learning category for that sole purpose sounds like a lot of work for too little benefit, though.
  - ww2 12y ago
    Good point but examples can also be drawn from other fields like programming rather than from mathematics. So far I found that the link below is very enlightening. http://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/ http://bartoszmilewski.com/2014/10/28/category-theory-for-pr...
- enord 12y ago
  They are arrows. Arrows and objects are the primitives of category theory, just like sets and set membership are the primitives of set theories (well most of them anyway). A category that captures the notion of sets and maps can be described in terms of arrows, objects and some semantic rules about which arrows (here interpreted as maps) connect which objects (here interpreted as sets). Wiki on the "Category of sets [and maps]" -> http://en.wikipedia.org/wiki/Category_of_sets http://en.wikipedia.org/wiki/Category_of_sets Other rules about arrows between objects describe categories that capture other mathematical concepts.
nrinaudo 12y ago
I think it's "explained" when you go from slide 6 to 7. Slide 6: objects are points in space. Slide 7: arrows are ways of transforming objects into other objects. I'm no expert, but from my understanding, there is nothing more to be said (other than stating the composition / identity laws): you're at a level of abstraction where you cannot say anything more. Objects. Arrows. An arrow goes from an object to another. If it's any help, you can think of them as mathematical functions, where the origin point is the function's domain and its destination point the function's range (called co-domain in category theory, because why not). Bear in mind that while this example is correct, that's all it is: a concrete example of an abstract notion. If it feels simplistic, that's because it is. Arrows are a trivial notion. It gets more complicated when you study different kinds of arrows (homomorphism, isomorphism, whateverism), or arrows in "concrete" categories (functors are arrows in the category of categories, natural transformations are arrows between functors...).
- ryanobjc 12y ago
  But is this the best pedagogical approach to teaching this area? In the book "Conceptual Mathematics" the concrete example is finite sets and mapping between finite sets. That is way more understandable than 'objects' and 'how to go from one object to another'. It's just too abstract for a general audience I believe.
  - nrinaudo 12y ago
    It's the only one that does not require knowledge of other fields - not everyone knows set theory (although yes, almost everyone here probably knows enough). Conceptual Mathematics needs concrete example to explain the algebra of function composition, and more importantly to prove certain properties and theorems. This presentation's goals are far more modest and the abstract approach allows it to not take up 700 slides. That being said, I don't think I'd have been able to go through this presentation in its entirety if I hadn't had some previous exposure to the field. So while I disagree with you for discussion's sake, I secretly think you're right.
    - ryanobjc 12y ago
orbifold 12y ago
All you really know about arrows, is that you can compose them if the tip of the first arrow fits into the tail of the second arrow, that is the first arrow is from A to B and the second from B to C, in a way that is associative, which means that if you have three arrows, it doesn't matter in which way you compose compose them. Moreover for every object A, there is an identity arrow. Composition with that does yield the original arrow. The point of those axioms is that they are satisfied by lots of different mathematical structures and idealized physical situations as well (Feynman diagrams, Chemical reaction networks, Knot-/Braid diagrams etc.). For how this relates to computation, you can look at http://math.ucr.edu/home/baez/qg-fall2006/index.html#computation http://math.ucr.edu/home/baez/qg-fall2006/index.html#computa... for example. It is a bit more subtle than one would think at first, as in functional programming languages with "first class" functions, those are not not actually arrows, but objects. More precisely the type (A -> B) in Haskell, or (A=>B) in Scala, is a notation for an internal hom object. The more interesting ideas arise when you then study how different such categories relate to each other, you then come up with Functors and how Functors between Categories are related to each other, those are called Natural Transformations. The original motivation for the invention of category theory was the study of natural transformations in homological algebra and algebraic topology. In the preceding years people had come up with several alternative functors (Cohomology / Homology on certain topological spaces) and they needed a way to talk about in what way those constructions were equivalent to each other.

enord 12y ago

This is a top-down approach starting with CT fundamentals and connecting them to CS concepts/patterns after 150 slides. The air is thinner near the top of the abstraction ladder and more or less unbreathable for people who don't spend considerable time in the Ivory Tower.

muaddirac 12y ago
I think if I were attempting to make it more accessible for beginners, I would start with a concrete example of a category (like Set) and introduce the concepts in what is, for most people (programmers in particular) familiar territory, and then attempt to show how abstracting those concepts is useful and applicable in other situations.

cheatsheet 12y ago

I scanned through the first 50 slides or so. I've read and drawn out the first few chapters to myself of "Categories for the Working Mathematician", so for me - this was a very nice presentation that graphically illustrated the key forms and key semantics. I look forward to reading the code parts. But I have to agree with other posters - it took a lot of studying to get to the point where I can understand your slides. I think by the time you can read mathematics like this, it is because you already understand it verbosely. As for people who don't agree that this is for beginners, I don't think you will be able to feel like you get it until you sit down with the work and stare at it a lot until it makes sense to you. It sounds stupid and silly, but that's the only way I can really communicate how to learn this stuff with a feeling of adequate understanding. The simplicity and elegance of the pictures do not adequately convey how difficult this stuff is to comprehend, especially if your mathematical foundation involves reasoning about real things. It is descriptive of abstract layers of terms, and the relationships they construct. Category theory is essentially the math of maths.

Xophmeister 12y ago

See also Bartosz Milewski's very nice WIP blog series[1] on category theory for programmers. [1] http://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/ http://bartoszmilewski.com/2014/10/28/category-theory-for-pr...

losvedir 12y ago

These slides do the same misleading thing all the other slides I've looked at do: show examples where there are only an arrow or two between objects. I still don't really understand category theory, but one breakthrough I had was when I realized that two objects can (and often do) have LOTS (or even infinite) arrow between them. For example, in a category of "types", each object could be a type (e.g.: int, float, list(int), etc.), and each arrow could be a function between those types. With that example, just think of all the arrows between, say, string -> int! There's "length()", "md5()", "to_i()", etc. And don't even get me started on the "identity" arrows of string back to itself (upcase, downcase, strip, etc). We're talking gazillions of arrows.

tfgg 12y ago
So, on slide 33, the "+1" and "bestFriend" arrows are identities of Int and Person? On slide 35 it says that identity is associated with the identity function, but to me that means a function that returns what you give it, rather than "+1", which gives you the next number. So the identity of Person just means any function with the type signature Person->Person?
- orbifold 12y ago
  No, the identity id:A->A is characterized by the property that for all arrows f:B->A and g:A->C (P1) id . f = f and (P2) g . id = g, in particular it is unique, since if id':A->A had the same property, then id' = id . id' = id, where the first equality follows by (P1) and the second by (P2').
  - tfgg 12y ago
    Ok, I think I got the wrong idea that the identity was any arrow pointing back on to an object. Thanks.
cheatsheet 12y ago
I just sort of abstract over the specifics of the implementation of arrows and assume there is an arrow that denotes the 'kind' of arrow. Does it express a monotonic function (order preserving), does it express a non monotonic function (permutation of elements, ordering of computation of 'typical' threads). It groups functional operations into kinds that you can make assertions about after a selection of the operations have been performed. Haskell does - add :: Integer -> Integer -> Integer so the compiler can check all the branches of code to ensure that statement is invariant.

im3w1l 12y ago

Could someone explain slide 90-92 to me? I know what map does and I know what a functor is, but I don't know scala, so I can't understand what the slides are saying.

kasey_junk 12y ago
A trait is a (possibly abstract) type definition. So trait Functor is defining a type definition for something called Functor. Functor[F[_]] to the right of the name indicate that the type Functor is paramterized across a "higher kinded type" (ie it is generic and the thing it is generic against is in turn generic). For this definition we will refer to that higher kinded type as F[_]. def defines a method on the type. So def map means that the type Functor has a method map on it. map[A, B] means that the function map is generic across 2 different types and we will label them A & B. Map takes 2 parameters the first is the higher kinded type F parameterized to A (F of A) and the second is a function that transforms any A to a B. Map returns F parameterized to B. Slide 92 defines it slightly differently. Map is a function with no parameters that returns a function with the first (and only parameter) is a function from A to B and it returns a function from F[A] to F[B].
hibikir 12y ago
Tricky Scala bits: The return type is at the end of the function definition, preceded by : . It's optional if there is an implementation provided, as Scala can do type inference. The => is a shorthand for defining a function type. String => Int is a function that takes a String, and returns an Int. [A,B] is saying that the function is a generic function, with some generic types named A and B, that will be resolved at compile time. Not unlike generics in many other languages. so def map[A,B] (fa: F[A], f: A=>B) : F[B] means that we are defining a function map, that takes a Functor of A fa, and a function from A to B, and returns a functor of type F[B]. Slide 92 writes it differently: def map[A,B] : (A=>B) => (F[A] => F[B]) Here, map returns a function that takes a function from A to B, and returns another function, that turns a Functor of A into a functor of B. Now, knowing functors and scala, I don't find those slides that illuminating anyway. I did not think that I'd ever say this about anything, but here it goes. I think Scalaz's implementation is easier to understand.
12y ago

cfeduke 12y ago

If I didn't have a couple years of shipping Scala code into production I'm not certain I'd understand the slides by themselves. (Having audio and/or video to go along with the slides would be a great help!) I don't have a math background, but write a lot of Scala anyway. These slides filled in the blanks in a lot of places for me though largely because I could relate to how I've written code. This is an excellent resource and its piqued my interest in learning more about category theory.

j2kun 12y ago

The best exposition I've found for demystifying category theory is the first few chapters of Paolo Aluffi's Algebra: Chapter 0 [1]. The central emphasis is on universal properties, which I see most treatments for beginners de-emphasize or ignore (as these slides do). From my experience, universal properties are the main tool for unifying and abstracting concepts into the language of categories. Aluffi uses category theory to unify the treatment of groups, rings, modules, linear algebra, and then goes on to more abstract category theory. I have also written a bit on this [2], regrettably choosing ML as the language of implementation. [1]: http://www.amazon.com/Algebra-Chapter-Graduate-Studies-Mathematics/dp/0821847813 http://www.amazon.com/Algebra-Chapter-Graduate-Studies-Mathe... [2]: http://jeremykun.com/2013/04/24/introducing-categories/ http://jeremykun.com/2013/04/24/introducing-categories/

pekk 12y ago
What's wrong with ML as the language for this?
- j2kun 12y ago
  Nothing in principle (I wrote the articles, after all). I just found it to be clunky. In particular, the signature and structure system made it needlessly difficult to express what I thought were simple things. And it was difficult to find resources due to standard ML not being widely used.
  - alex-g 12y ago
    Is your work at all based on Rydeheard and Burstall's "Computational Category Theory"? They also do category theory in ML.
imh 12y ago
I'm a big fan of that book, but there were a few too many important proofs "left as exercise for reader" for my taste.
- ch0wn 12y ago

akeck 12y ago

If two categories are related by a functor, does that imply that the first category is isomorphic to the second category? (I'm very new to this topic, but I have an applied math background.)

j2kun 12y ago
That's half of it. If you have another functor going the other way, with some properties on how the two functors relate, then you get what's called an equivalence of categories. [1] Basically, you need both ways to compose the two functors to be "equivalent" to the identity functor in each category (equivalent as shown by a reversible natural transformation). [1]: http://en.wikipedia.org/wiki/Equivalence_of_categories http://en.wikipedia.org/wiki/Equivalence_of_categories

ryanobjc 12y ago

This is an ok introduction, but for a much much better introduction check out the book "Conceptual Mathematics". It does a little better than using abstract words like 'objects' (which has a particular connotation for programmers).

nrinaudo 12y ago
It also takes bloody ages getting to the "good" parts like monoids and functors :)

runT1ME 12y ago

I am a bit confused, I had thought there could not be multiple isomorphisms from object A to object B. I thought an Iso was an epi and mono, doesn't that mean the arrows must all be the same? Thanks in advance if someone wants to go through all the ways I'm misunderstanding. :)

nrinaudo 12y ago
if f is an isomorphism between A and B, it simply means that there exists f-1 such that f(f-1) = idB and f-1(f) = idA. I don't think anything in this definition allows us to conclude that there can only be one such f between A and B. Indeed, if A and B are sets of identical cardinality, I'm pretty sure you can create n! isomorphims between the two (where n=|A|). Drawing a picture of of two sets with two elements each should let you see it.
- runT1ME 12y ago
  Oh. I think I was confused, arrows can be equal (extensionally so), but not the 'same'.
orbifold 12y ago
A group is a category with a single object and whose morphisms are all isomorphisms. There are plenty of groups, so you can't be right :). A morphisms can however have at most one inverse.

commutativering 12y ago

A serious question, and one not meant to cause offense: why is category theory being pushed so aggressively? I've seen numerous "Category Theory for Dummies"-style posts here over the years that all imply CT is somehow extremely relevant to working programmers in ways that other branches of mathematics like analysis or abstract algebra apparently aren't. Considering that most programmers have never rigorously studied even formal logic or set theory, both of which are directly applicable to formal methods, electrical engineering, and relational database theory, wouldn't those subjects be better studied first? Instead of clicking through a 209-slide PowerPoint presentation you likely won't be able understand, I suggest reading these free books on those subjects: http://www.fecundity.com/codex/forallx.pdf http://www.fecundity.com/codex/forallx.pdf http://i.stanford.edu/~ullman/focs.html http://i.stanford.edu/~ullman/focs.html http://www.people.vcu.edu/~rhammack/BookOfProof/ http://www.people.vcu.edu/~rhammack/BookOfProof/

cschneid 12y ago
Its riding the haskell bandwagon to some degree. By borrowing ideas from category theory they have some really nice abstractions in practical code. But then it gets more confusing so you want to loop back and see what the actual definition of a "monoid" is, or understand "functors". Even if haskell's idea of functor isn't 1 to 1 with category theory's.
- bstamour 12y ago
  The only thing I can think of that's wrong with Haskell's functors is that they're more specifically endofunctors, or am I missing something else?
  - jberryman 12y ago
    And Hask is arguably not a proper category
    - bstamour 12y ago
      Can you expand on this? I'm genuinely curious.

serve_yay 12y ago

As thankful as I am that this was made and published, I find only slides with no talk very difficult to try to learn from. I kinda wish slideshare wasn't a thing :/

kenbot 12y ago

Hi everyone, author here. One thing to remember is that each slide had a lot of verbal explanation around it, so I'm not surprised that it's confusing by itself! We took a video, so hopefully it turns out OK so we can put it online.