Tab Completion

I'm Tab Atkins Jr, and I wear many hats. I work for Google on the Chrome browser as a Web Standards Hacker. I'm also a member of the CSS Working Group, and am either a member or contributor to several other working groups in the W3C. You can contact me here.
Listing of All Posts

Basic Category Theory Terms

Last updated:

Magma: A set of objects that can be "added" or "combined" in some way, so that if you add any two of them the result is also in the set. That's it.

Semigroup: A magma whose "addition" operation obeys associativity: (a + b) + c must give the same answer as a + (b + c). For example, strings form a semigroup with concatenation as their "addition" operator: ("foo" + "bar") + "baz" = "foobarbaz", etc. So do the integers under the min() operation.

Monoid: A semigroup with a "zero" element: something that, when "added" to any element in the group, produces that other element again. For example, the empty string is the "zero" element in the string/concat monoid. The integers with min() aren't a monoid, but they become one if you add infinity as the "zero" element. Lots of interesting things are monoids; it's a very simple and useful constraint to satisfy. If you satisfy "monoid", you get a free version of the reduce function using your operation.

Group: A monoid where every element has an opposite or "negative" version, so that if you "add" an element and its opposite, you get the "zero" element. Strings with concatenation are not a group - concatenation only ever produces larger strings, not smaller ones, so you can't ever take a string like "foo" and add another string to it to get the empty string. On the other hand, integer/addition is a group - the opposite of each member is just the negative integer corresponding to it.

An Alternate Path to a Group

There's an alternate way to get from magma to group. You add different properties along the way, but when they're all combined they add up to the same thing that the previous path did. However, these properties are harder for most things to satisfy, and so they're not generally as useful; most of the things you use that'll satisfy any of these do so because they're all the way to a group already.

Quasigroup: This one's a little subtle. It's a magma, but the operation has the property that you can transform any element of the set to any other element by combining it with an appropriate third element. It has to do so whether the first element is the left or right argument, but the element you choose to combine it with can be different in the two cases.

The integers with subtraction form a quasigroup - if I want to transform "2" into "5", I can do it with 2 − -3 = 5 and 7 − 2 = 5. (So do the integers with addition, but they satisfy so many of these definitions that they're not very interesting to talk about.) On the other hand, strings with concatenation are not a quasigroup - while you can transform some strings, like "foo" to "foobar", you can't generally do it both ways (nothing satisfies the equation X + "foo" = "foobar"), and there are some strings you can't transform between at all.

Loop: A quasigroup with a "zero" element, which transforms an element into itself regardless of which side it starts on. Integer/subtraction is not a loop: X − 0 = X, which is what we want, but 0 − X = -X, which isn't what we want (and no other number satisfies either side, obviously.) I can't come up with a good example of something that's a loop but not a group right now.

Group: Ah, back to group. Along this path, a group is a loop with associativity.

Going Further

Abelian or Commutative X: Any of the above types might have an operation which is commutative - it doesn't matter which order the arguments are. Integer/min is an abelian monoid, because min(1, 10) = 10 and min(10, 1) = 10.

(a limited set of Markdown is supported)