6 ms·

Categories – What’s the Point?

89 points by johnbender 13y ago

lisper 13y ago
Aarrgghh! > there are only two universal properties Yeah? So what are they??? Hm, Wikipedia (http://en.wikipedia.org/wiki/Universal_property http://en.wikipedia.org/wiki/Universal_property) thinks there are a lot more than two: "This article gives a general treatment of universal properties. To understand the concept, it is useful to study several examples first, of which there are many: all free objects, direct product and direct sum, free group, free lattice, Grothendieck group, product topology, Stone–Čech compactification, tensor product, inverse limit and direct limit, kernel and cokernel, pullback, pushout and equalizer."
- dill_day 13y ago
  There are two universal properties in the sense that a universal property is either defined in terms of a "terminal morphism" or (dually) an "initial morphism" (see the Formal Definition in the wiki article) -- the examples are particular instantiations of this general definition.
- j2kun 13y ago
  All in due time, my friend. That list is a list of examples of universal properties being used to define things. As such, it's a testament to how mindbogglingly convenient universal properties are.
nilkn 13y ago
I encourage anyone interested in learning more about this sort of thing to read this article on the "category design pattern" by Gabriel Gonzalez, the author of the pipes library for Haskell: http://www.haskellforall.com/2012/08/the-category-design-pattern.html http://www.haskellforall.com/2012/08/the-category-design-pat...
ww520 13y ago
I don't mean disrespect but the article is pretty empty on explaining what Category Theory is. May be it's just a prelude to a series of other articles but I didn't get that until the very end. Kind of disappointing.
- rhizome 13y ago
  I think the title question is being asked of initiates.
mercuryrising 13y ago
I really like this quote (from [0], an intro to Category Theory)- "[Category Theory] allows one to see the forest rather than the individual trees, and offers the possibility for study of the structure of the entire forest, in preparation for the next stage of abstraction - comparing forests." One of the things I've noticed when programming and dealing with abstractions is how your problem gets translated to the tools of your language (what feels natural to a language). Some problems are easier in one language than another. Imagine your language being a shadow puppet, and your problem you'd like to solve is a light source. When you put your language in front of the problem, can you still see a shadow? Today most programming languages will, but if instead of binary filter with your hands, imagine your hands were some weird grayscale thing (like a monochrome LCD). Wherever the light shines through the most, you need to put a bit more work into solving the problem. Low level languages seem to be much better at watching and reacting to state changes and making decisions on those states (because of the speed of the language, you could do 100s of checks on pins and combinations of pins and get good performance on something like an Arduino). In something like Python, those little checks become more costly. You might need to rethink your problem to get to your solution. You need to abstract from the trees, and get to the forest. The valid solution you had before because of your perspective has changed, and now you need a new approach. I think a lot of that has to do with finding a pattern in your problem. If you can find a pattern, you can probably make it recursive, write a couple steps and maybe a helper function, and you're done. Problem solved. Take the fibonacci sequence in Haskell (from [1]): fib = 0:1:[a+b | (a,b) <- zip fib (tail fib)] Start with 0 and 1, this is the pattern you use to build the fibonacci sequence. You use the sequence itself to build itself (no extra variables, you get them all in a list just starting because it evaluates itself). Get the 100th element with fib!!100. It references itself in itself, there's no states to look at, just build the sequence, when you want a value it does the legwork. The Fibonacci sequence in other languages is a little more terse - you need to define some special cases (if 0, if 1), rather than really just building the sequence starting from 0 and 1 then apply thing your pattern. Now take something like Fizzbuzz - Python makes this extremely easy, whereas in Haskell it seems a little unnatural (at least for me, although they're pretty similar solutions) [2]. fizzbuzzers = [(3,"fizz"), (5,"buzz"), (7, "baz")] for x in range(1, 110): string = '' for num, word in fizzbuzzers: if not x%num: string += word print string if string else x [0] - http://shuklan.com/haskell/lec12.html#/0/2 http://shuklan.com/haskell/lec12.html#/0/2 [1] - http://www.haskell.org/haskellwiki/Haskell_Tutorial_for_C_Programmers http://www.haskell.org/haskellwiki/Haskell_Tutorial_for_C_Pr... [2] - http://www.haskell.org/haskellwiki/Haskell_Quiz/FizzBuzz/Solution_Acontorer http://www.haskell.org/haskellwiki/Haskell_Quiz/FizzBuzz/Sol...
contingencies 13y ago
Haha. I thought to my uninitiated mind: "What's the difference between categories and sets?" and found this: Some attempts have been made by category theory to usurp the foundations of mathematics from set theory. That is, rather than taking sets as the most fundamental building block of the mathematical world, give that role to categories. Sets themselves form a category. http://www.connections.xamuel.com/Category+Theory-vs-Set+Theory.html http://www.connections.xamuel.com/Category+Theory-vs-Set+The... Sounds to me as an uninitiated programmer like set theory had issues when wielded in the nether regions of modern mathematical theory, and category theory is the kludge that followed. Maybe I should have done maths; yet when most fascinated by its theories under the influence of a three letter traditional psychoactive, a former IBM employee and multi-decade pure mathematics researcher literally begged me not to, declaring it an enending path that wastes decades of people's lives. Ho hum.
- nilkn 13y ago
  A category is a collection of objects with a notion of morphism between said objects. Morphisms are really not defined much beyond that; it is all left rather abstract, though there are some basic laws that must be satisfied. Categories are relatively uninteresting without functors. Functors are more or less mappings or transformations between categories. Category theory by some accounts initiated in the foundations of algebraic topology. In that subject, one wishes to codify some of the aspects of a high-dimensional shape or geometric object in algebraic terms. The hope is that the algebraic image of the shape is easier to understand than the shape itself. The mapping of shapes into their algebraic "shadows" is a functor. For instance, you can take a torus and look at the collection of all closed loops drawn on the surface of the torus. Now identify two loops as the same if one can be smoothly deformed into the other by moving it along the surface of the torus. Long story short, this gives the set of such loops a structure known as a group. There is a very extensive theory developed around groups, so you might surmise that you could partially classify shapes by looking at this associated group (called the fundamental group or first homotopy group). This mapping from geometric objects to groups of loops drawn on them is a functor from the category of topological spaces to the category of groups. This is the beginning of homotopy theory. As for your comment on sets, there is the category Set which consists of all sets. That is, the objects of Set are sets and, given two sets X and Y, the morphisms between X and Y in Set are simply the functions f : X -> Y. An interesting technical point here (which is related to your quote) is that Set itself cannot be a set, as there is no set of all sets within Zermelo-Fraenkel set theory (the most common axiomatic formulation of set theory). Rather, there is a notion of class, and one says that the collection of all sets forms a class rather than a set.
minopret 13y ago
I think for most people the point of category theory can be one of these: http://en.wikipedia.org/wiki/Don%27t_repeat_yourself http://en.wikipedia.org/wiki/Don%27t_repeat_yourself ; or http://en.wikipedia.org/wiki/Algebraic_topology http://en.wikipedia.org/wiki/Algebraic_topology ; or http://en.wikipedia.org/wiki/Abstract_nonsense http://en.wikipedia.org/wiki/Abstract_nonsense ...but probably it's not so helpful to insist on more than one of these at a time. And I think it would be good if more writers would realize that.
kens 13y ago
I've tried to learn category theory off and on for many years and have gotten pretty much nowhere. From my perspective it's the worst area of mathematics as far as effort in vs benefit/understanding out. Have other people encountered this or am I just a bonehead?
- j2kun 13y ago
  OP here. I personally had a lot of trouble when trying to learn category theory on my own. Part of the reason for this is that the need for category theory comes from a lot of other abstract mathematics being unified under the category theoretic lens. I didn't have much of that background my first few times, and I think that was one of the major reasons I didn't succeed in understanding it. After a few years of graduate school, with lots of colleagues working on the same material as me, it has gradually become much easier. The best text I've seen so far is Paolo Aluffi's "Algebra: Chapter 0". It's an algebra textbook meant for first year graduate students in pure mathematics, but it was the major factor in clarifying category theory for me. Of course, the book also contains pretty much all topics in abstract algebra from basic groups to abelian categories. So if you're not pegging to be a research mathematician, chances are the book is not worth your time. Part of my goal with this series is to demystify the subject as it was demystified for me, and to incorporate as many concrete applications to programming concepts as I can. I hope you find some value in what I produce :)
  - kens 13y ago
    Thanks for the book recommendation. I'll take a look at your series, and maybe read Algebra: Chapter 0 when I'm feeling ambitious.
- btilly 13y ago
  Mathematicians can be roughly divided into algebraists and analysts. My biased impression is that algebraists focus on kinds of manipulations that have proven effective in the past, while analysts focus on specific mental models of a system, and then the necessary calculations flow from those models. There are a lot of areas of math that have no obvious connection to abstract algebra or real analysis (for instance combinatorics, logic, number theory...) yet the vast majority of mathematicians will know what you mean when you ask whether they are an algebraist or an analyst, and will know how they should be classified. In fact if I see a mathematician eating corn on the cob, I can generally tell which they are without asking. (Analysts eat in spirals, analysts in rows. My best guess for why is that analysts pay attention to the cue from how their teeth eat corn, while algebraists follow the visual cue from the lines on the corn.) This classification is a matter of taste. Any professional mathematician is adept at both areas of mathematics, but will have a clear preference. Category theory serves as an excellent litmus test. It seems to have a magnetic attraction for algebraists, and a similar repulsion for analysts. At its heart, category theory is an abstraction of common patterns of algebraic manipulation where the details of what you are manipulating become entirely irrelevant. (Indeed you can often replace one type of thing with an apparently unrelated type of thing. Such as a geometric problem about toruses with an algebraic question about pairs of integers.) Speaking personally, I learned enough category theory to pass all of the courses I had to take, but words like "category", "monad" "cohomology" and "functor" are red flags warning me that I'm about to be uninterested in the rest of the discussion. But YMMV.
gruseom 13y ago
Are there cases of category theory yielding results in a more traditional branch of mathematics? That would seem to be a litmus test of sorts.
- j2kun 13y ago
  Yes of course. Pretty much all of algebraic geometry (the study of curves and surfaces defined by families of polynomial equations) owes its current life force to the sweeping reforms it undertook by utilizing category theory in the '50s and '60s. There are a number of conjectures (most notably, the Weil conjectures) whose proofs are attributed directly to the use of category theory.
qznc 13y ago
I recently heard "Category theory tells you which parts are easy" from a mathematician working with Haskell Monads. Repeatedly, this turns out to be true (confirmation bias?). He generalized a algorithm by using an abstract data type (a Monad of course) instead of a specific number type. Now the algorithm can be applied e.g. to probability distributions as well. The category theory tells you about bind and lift. However, the hard part is generalizing the algorithm, because you have fewer assumptions now. For another example, greatest common divisor is a simple algorithm for numbers. Try generalizing it so you could also use polynomials instead of integers.
malkarouri 13y ago
Why should there be a point? Can't it be point-free? (Sorry, somebody had to say it..)

89 points by johnbender 13y ago

Aarrgghh! > there are only two universal properties Yeah? So what are they??? Hm, Wikipedia (http://en.wikipedia.org/wiki/Universal_property http://en.wikipedia.org/wiki/Universal_property) thinks there are a lot more than two: "This article gives a general treatment of universal properties. To understand the concept, it is useful to study several examples first, of which there are many: all free objects, direct product and direct sum, free group, free lattice, Grothendieck group, product topology, Stone–Čech compactification, tensor product, inverse limit and direct limit, kernel and cokernel, pullback, pushout and equalizer."

dill_day 13y ago
There are two universal properties in the sense that a universal property is either defined in terms of a "terminal morphism" or (dually) an "initial morphism" (see the Formal Definition in the wiki article) -- the examples are particular instantiations of this general definition.
j2kun 13y ago
All in due time, my friend. That list is a list of examples of universal properties being used to define things. As such, it's a testament to how mindbogglingly convenient universal properties are.

nilkn 13y ago

I encourage anyone interested in learning more about this sort of thing to read this article on the "category design pattern" by Gabriel Gonzalez, the author of the pipes library for Haskell: http://www.haskellforall.com/2012/08/the-category-design-pattern.html http://www.haskellforall.com/2012/08/the-category-design-pat...

ww520 13y ago

I don't mean disrespect but the article is pretty empty on explaining what Category Theory is. May be it's just a prelude to a series of other articles but I didn't get that until the very end. Kind of disappointing.

rhizome 13y ago
I think the title question is being asked of initiates.

mercuryrising 13y ago

I really like this quote (from [0], an intro to Category Theory)- "[Category Theory] allows one to see the forest rather than the individual trees, and offers the possibility for study of the structure of the entire forest, in preparation for the next stage of abstraction - comparing forests." One of the things I've noticed when programming and dealing with abstractions is how your problem gets translated to the tools of your language (what feels natural to a language). Some problems are easier in one language than another. Imagine your language being a shadow puppet, and your problem you'd like to solve is a light source. When you put your language in front of the problem, can you still see a shadow? Today most programming languages will, but if instead of binary filter with your hands, imagine your hands were some weird grayscale thing (like a monochrome LCD). Wherever the light shines through the most, you need to put a bit more work into solving the problem. Low level languages seem to be much better at watching and reacting to state changes and making decisions on those states (because of the speed of the language, you could do 100s of checks on pins and combinations of pins and get good performance on something like an Arduino). In something like Python, those little checks become more costly. You might need to rethink your problem to get to your solution. You need to abstract from the trees, and get to the forest. The valid solution you had before because of your perspective has changed, and now you need a new approach. I think a lot of that has to do with finding a pattern in your problem. If you can find a pattern, you can probably make it recursive, write a couple steps and maybe a helper function, and you're done. Problem solved. Take the fibonacci sequence in Haskell (from [1]): fib = 0:1:[a+b | (a,b) <- zip fib (tail fib)] Start with 0 and 1, this is the pattern you use to build the fibonacci sequence. You use the sequence itself to build itself (no extra variables, you get them all in a list just starting because it evaluates itself). Get the 100th element with fib!!100. It references itself in itself, there's no states to look at, just build the sequence, when you want a value it does the legwork. The Fibonacci sequence in other languages is a little more terse - you need to define some special cases (if 0, if 1), rather than really just building the sequence starting from 0 and 1 then apply thing your pattern. Now take something like Fizzbuzz - Python makes this extremely easy, whereas in Haskell it seems a little unnatural (at least for me, although they're pretty similar solutions) [2]. fizzbuzzers = [(3,"fizz"), (5,"buzz"), (7, "baz")] for x in range(1, 110): string = '' for num, word in fizzbuzzers: if not x%num: string += word print string if string else x [0] - http://shuklan.com/haskell/lec12.html#/0/2 http://shuklan.com/haskell/lec12.html#/0/2 [1] - http://www.haskell.org/haskellwiki/Haskell_Tutorial_for_C_Programmers http://www.haskell.org/haskellwiki/Haskell_Tutorial_for_C_Pr... [2] - http://www.haskell.org/haskellwiki/Haskell_Quiz/FizzBuzz/Solution_Acontorer http://www.haskell.org/haskellwiki/Haskell_Quiz/FizzBuzz/Sol...

contingencies 13y ago

Haha. I thought to my uninitiated mind: "What's the difference between categories and sets?" and found this: Some attempts have been made by category theory to usurp the foundations of mathematics from set theory. That is, rather than taking sets as the most fundamental building block of the mathematical world, give that role to categories. Sets themselves form a category. http://www.connections.xamuel.com/Category+Theory-vs-Set+Theory.html http://www.connections.xamuel.com/Category+Theory-vs-Set+The... Sounds to me as an uninitiated programmer like set theory had issues when wielded in the nether regions of modern mathematical theory, and category theory is the kludge that followed. Maybe I should have done maths; yet when most fascinated by its theories under the influence of a three letter traditional psychoactive, a former IBM employee and multi-decade pure mathematics researcher literally begged me not to, declaring it an enending path that wastes decades of people's lives. Ho hum.

nilkn 13y ago
A category is a collection of objects with a notion of morphism between said objects. Morphisms are really not defined much beyond that; it is all left rather abstract, though there are some basic laws that must be satisfied. Categories are relatively uninteresting without functors. Functors are more or less mappings or transformations between categories. Category theory by some accounts initiated in the foundations of algebraic topology. In that subject, one wishes to codify some of the aspects of a high-dimensional shape or geometric object in algebraic terms. The hope is that the algebraic image of the shape is easier to understand than the shape itself. The mapping of shapes into their algebraic "shadows" is a functor. For instance, you can take a torus and look at the collection of all closed loops drawn on the surface of the torus. Now identify two loops as the same if one can be smoothly deformed into the other by moving it along the surface of the torus. Long story short, this gives the set of such loops a structure known as a group. There is a very extensive theory developed around groups, so you might surmise that you could partially classify shapes by looking at this associated group (called the fundamental group or first homotopy group). This mapping from geometric objects to groups of loops drawn on them is a functor from the category of topological spaces to the category of groups. This is the beginning of homotopy theory. As for your comment on sets, there is the category Set which consists of all sets. That is, the objects of Set are sets and, given two sets X and Y, the morphisms between X and Y in Set are simply the functions f : X -> Y. An interesting technical point here (which is related to your quote) is that Set itself cannot be a set, as there is no set of all sets within Zermelo-Fraenkel set theory (the most common axiomatic formulation of set theory). Rather, there is a notion of class, and one says that the collection of all sets forms a class rather than a set.

minopret 13y ago

I think for most people the point of category theory can be one of these: http://en.wikipedia.org/wiki/Don%27t_repeat_yourself http://en.wikipedia.org/wiki/Don%27t_repeat_yourself ; or http://en.wikipedia.org/wiki/Algebraic_topology http://en.wikipedia.org/wiki/Algebraic_topology ; or http://en.wikipedia.org/wiki/Abstract_nonsense http://en.wikipedia.org/wiki/Abstract_nonsense ...but probably it's not so helpful to insist on more than one of these at a time. And I think it would be good if more writers would realize that.

kens 13y ago

I've tried to learn category theory off and on for many years and have gotten pretty much nowhere. From my perspective it's the worst area of mathematics as far as effort in vs benefit/understanding out. Have other people encountered this or am I just a bonehead?

j2kun 13y ago
OP here. I personally had a lot of trouble when trying to learn category theory on my own. Part of the reason for this is that the need for category theory comes from a lot of other abstract mathematics being unified under the category theoretic lens. I didn't have much of that background my first few times, and I think that was one of the major reasons I didn't succeed in understanding it. After a few years of graduate school, with lots of colleagues working on the same material as me, it has gradually become much easier. The best text I've seen so far is Paolo Aluffi's "Algebra: Chapter 0". It's an algebra textbook meant for first year graduate students in pure mathematics, but it was the major factor in clarifying category theory for me. Of course, the book also contains pretty much all topics in abstract algebra from basic groups to abelian categories. So if you're not pegging to be a research mathematician, chances are the book is not worth your time. Part of my goal with this series is to demystify the subject as it was demystified for me, and to incorporate as many concrete applications to programming concepts as I can. I hope you find some value in what I produce :)
- kens 13y ago
  Thanks for the book recommendation. I'll take a look at your series, and maybe read Algebra: Chapter 0 when I'm feeling ambitious.
btilly 13y ago
Mathematicians can be roughly divided into algebraists and analysts. My biased impression is that algebraists focus on kinds of manipulations that have proven effective in the past, while analysts focus on specific mental models of a system, and then the necessary calculations flow from those models. There are a lot of areas of math that have no obvious connection to abstract algebra or real analysis (for instance combinatorics, logic, number theory...) yet the vast majority of mathematicians will know what you mean when you ask whether they are an algebraist or an analyst, and will know how they should be classified. In fact if I see a mathematician eating corn on the cob, I can generally tell which they are without asking. (Analysts eat in spirals, analysts in rows. My best guess for why is that analysts pay attention to the cue from how their teeth eat corn, while algebraists follow the visual cue from the lines on the corn.) This classification is a matter of taste. Any professional mathematician is adept at both areas of mathematics, but will have a clear preference. Category theory serves as an excellent litmus test. It seems to have a magnetic attraction for algebraists, and a similar repulsion for analysts. At its heart, category theory is an abstraction of common patterns of algebraic manipulation where the details of what you are manipulating become entirely irrelevant. (Indeed you can often replace one type of thing with an apparently unrelated type of thing. Such as a geometric problem about toruses with an algebraic question about pairs of integers.) Speaking personally, I learned enough category theory to pass all of the courses I had to take, but words like "category", "monad" "cohomology" and "functor" are red flags warning me that I'm about to be uninterested in the rest of the discussion. But YMMV.

gruseom 13y ago

Are there cases of category theory yielding results in a more traditional branch of mathematics? That would seem to be a litmus test of sorts.

j2kun 13y ago
Yes of course. Pretty much all of algebraic geometry (the study of curves and surfaces defined by families of polynomial equations) owes its current life force to the sweeping reforms it undertook by utilizing category theory in the '50s and '60s. There are a number of conjectures (most notably, the Weil conjectures) whose proofs are attributed directly to the use of category theory.

qznc 13y ago

I recently heard "Category theory tells you which parts are easy" from a mathematician working with Haskell Monads. Repeatedly, this turns out to be true (confirmation bias?). He generalized a algorithm by using an abstract data type (a Monad of course) instead of a specific number type. Now the algorithm can be applied e.g. to probability distributions as well. The category theory tells you about bind and lift. However, the hard part is generalizing the algorithm, because you have fewer assumptions now. For another example, greatest common divisor is a simple algorithm for numbers. Try generalizing it so you could also use polynomials instead of integers.

malkarouri 13y ago

Why should there be a point? Can't it be point-free? (Sorry, somebody had to say it..)