Hacker News new | past | comments | ask | show | jobs | submit login
Categories – What’s the Point? (jeremykun.com)
89 points by johnbender on Apr 16, 2013 | hide | past | web | favorite | 26 comments

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:


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

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.

Did the pure math researcher beg you to stay away from pure, applied or both types of math?

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.

I think the title question is being asked of initiates.


> there are only two universal properties

Yeah? So what are they???

Hm, Wikipedia (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."

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.

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.

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.

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.

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.

I think for most people the point of category theory can be one of these: http://en.wikipedia.org/wiki/Don%27t_repeat_yourself ; or http://en.wikipedia.org/wiki/Algebraic_topology ; or 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.

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?

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.

Great comment. You make it sound like analysts have more imagination—was that intentional?

When I studied math I was definitely, in your taxonomy, an algebraist. But if I went back to it now I'm pretty sure I would be an analyst. I say that because my approach to software has evolved in an analogous way. Also I eat corn-on-the-cob in rows :)

I'd love to properly re-learn all the math I learned before. The way I did it at the time was mostly just symbol manipulation, and that way of thinking no longer interests me.

You make it sound like analysts have more imagination—was that intentional?

Not intentional. I was trying to be fair, but my interests are clearly on the analysis side, and that shows.

An analyst starts with an object and then looks for things he can prove about the object. An algebraist starts with the proof, and then looks for objects for which the proof is valid. Both methods have advantages and disadvantages. An analyst can get bogged down in the details of the object he studies. An algebraist has the tendency to make trivial statements complicated. It is rare to take a result from the algebraic side and apply it in your concrete situation that you get something that wasn't already immediately obvious. Personally I lean to the analytic side, although the algebraic approach can be helpful if you apply it judiciously and take care to only generalize when this has an advantage and not just for the sake of generalization. If you look at the history of mathematics, most of the good stuff has analyst roots, and was only later incorporated in an algebraic framework. Though this could easily be my bias for what is good stuff.

Even traditionally algebraic subjects can be often approached analytically. For example if you do group theory by starting with group actions, it gets an analytic feel (and in my opinion, everything becomes much clearer). The reverse is also true, that's how many of the algebraic subjects initially started: take a bunch of proofs from the analytic side, and see for which classes of objects they remain valid.

In programming you have something similar. Programmers that try to generalize their code as much as possible are algebraists. Dependency injection is an example. Programmers that say "YAGNI" are analysts. If you like interfaces and design patterns you're probably an algebraist. If you like bottom up programming you're probably an analyst. If you like Haskell, you're probably an algebraist. If you like Lisp you're probably an analyst.

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 :)

Thanks for the book recommendation. I'll take a look at your series, and maybe read Algebra: Chapter 0 when I'm feeling ambitious.

Why should there be a point? Can't it be point-free?

(Sorry, somebody had to say it..)

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

[1] - http://www.haskell.org/haskellwiki/Haskell_Tutorial_for_C_Pr...

[2] - http://www.haskell.org/haskellwiki/Haskell_Quiz/FizzBuzz/Sol...

A more Python-similar Haskell FizzBuzz is at http://www.haskell.org/haskellwiki/Fizzbuzz

I think that's the cleanest method.

The thing I really like about the Haskell Fibonacci and that Python FizzBuzz is the ease of scale. Want the next value of fib? Grab it. Want to put more restrictions on fizzbuzz? Add them to this list.

You build the sequence with only the necessary amount of starting information (0:1 for fib, ( (3, "fizz"), (7, "buzz") ), and generate the rest as you need. These are the (I think) most beautiful solutions to problems.

That's more extensible. I think that's the perennial problem with FizzBuzz, whether decides the spec demands generalizability or simplicity.

    fizzbuzzers = [(3,"fizz"), (5,"buzz"), (7, "baz")]
    fizzbuzz k = 
      let str = concat [s | (n,s) <- fizzbuzzers, k `mod` n == 0]
      if str == "" then show k else str
    putStrLn $ intercalate "\n" $ map fizzbuzz [1..110]
It's not that bad.

Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact