6 ms·

Why are monoidal categories interesting?

67 points by weinzierl 8y ago

yakshaving_jgt 8y ago
I always enjoy a good Julia Evans article, and this one is no different. She has a very approachable, personable way of explaining technical things, which is missing from many monoid (and related) tutorials. I'm confused by this opening line though: > Monoidal categories are also called “tensor categories” and I think that term is a little less confusing Why is that? What is special about the word "monoid" that makes it more or less confusing than "tensor"?
- LudwigNagasena 8y ago
  >If you have been around functional programming for a bit, you might see the word “monoid” and “categories” and wonder “oh, is julia writing about monads, like in Haskell”? I am not!!
  - yakshaving_jgt 8y ago
    …I don't think that answers the question. Monoids don't come from Haskell. You'll see monoids discussed in Haskell plenty, sure, but the math precedes the programming language by at least a few decades.
    - maccam912 8y ago
      Probably true, but I know some upper level math through programming, and I associate "monoid" with Haskell and an abstract concept, but "tensor" with tensorflow and a more concrete idea.
- fraffo 8y ago
  Bc you obtain them as the result of tensor product between the cathegory algebra and the monoidal algebra, i think
- phlakaton 8y ago
  To the contrary, when I think "monoid" I think good old nonnegative integers and addition, or positive integers and multiplication, or any of a half-dozen really easy-to-understand examples. Tensors... what the heck are those? Like matrices, but _more_ complicated, you say? Thanks, but I'll stick with my basic monoids over here. :-) The confusion between monoids and monads is perhaps unfortunate (even if the similarity is quite intentional, because technically monads are a particular kind of monoid), but easily sorted out and not much worse than having to distinguish between the nuts in your pantry and the Nutella.
  - throwawaymath 8y ago
    > Tensors... what the heck are those? Like matrices, but _more_ complicated, you say? Thanks, but I'll stick with my basic monoids over here. :-) A tensor isn't actually a multidimensional array, just as a linear map isn't actually a matrix. Defining tensors as the multidimensional abstraction of scalars, vectors and matrices to n indices is anti-pedagogical, though regrettably common because it's computationally useful. Learning tensors this way is like learning linear algebra primarily by doing matrix multiplication. It hollows out all of what's actually going on by focusing on notation and symbol pushing. What you're comparing here is the heavily symbol-laden, notation-encumbered definition of a tensor with the elegant abstraction of a momoid. If you'd like to compare them on the merits of their abstraction, an alternative definition of "tensor" would be better. The object is not its representation. For example: a tensor is a multilinear map between a product of vector spaces and another vector space. So T: V_{1} x V_{2} x ... x V_{n} --> W is a tensor. Furthermore, every tensor T is itself an element of a tensor product. An example of a tensor product is R^{nk}, which is the nk-dimensional real space you obtain by taking the tensor direct product of the n- and k- dimensional real spaces, R^{n} ⊗ R^{k}. In this way the tensor product is an abstraction of the familiar Cartesian product in which the dimension of two spaces is multiplied instead of the cardinality of two sets. This definition makes it easier to understand why the objects of a monoidal category can be considered tensors. A monoidal category is a category C where the functor ⊗ is defined such that C x C --> C. Note the similarity of this definition with my alternative definition of a tensor - no multidimensional arrays are required! You're just moving up one level of generality from linear maps and Cartesian products. Technically speaking, the monoidal category functor is actually an abstraction the tensor product, the way the tensor product is an abstraction of the Cartesian product. Whereas many monoidal categories admit a Cartesian product, some monoidal categories (like the category of vector spaces) admit a tensor product. Edit - Sorry for the bracket notation used in subscripts and superscripte, I was thinking in LaTeX...
- mbid 8y ago
  Just to add to the confusion: Monoidal categories are the appropriate notion of "monoid object" in the category of categories; unit and associativity law are replaced by coherent natural isomorphisms (see "categorification"). So that's where the "monoidal" comes from.
- throwawaymath 8y ago
  I don't actually agree with the author that it's less confusing, but I'll abbreviate my other comment to answer your direct question. A tensor is a multilinear map from a product of n vector spaces to another vector space. Every tensor is an element of a tensor product, which is (loosely speaking) a vector space you obtain by multiplying the dimension of two other vector spaces. So for example, the real space R^nk is the tensor product obtained from combining R^n and R^k. To be more explicit, what you're doing is obtaining a new n by k matrix for every pair of vectors of R^n and R^k. In other words, take the Cartesian product of R^n and R^k. Then take every possible pair of vectors of the Cartesian product and combine them to form an n by k matrix. Now you have a tensor product, and each individual element of your tensor product is a tensor. Going back to the abstract: a monoidal category is a category C of objects equipped with a functor defined ⊗: * C x C -> C*. If you take the category of vector spaces or the category of modules (like vector spaces, but defined over rings instead of fields) and define your monoidal functor to be the tensor product, you turn them into tensor categories. Monoidal categories actually sit at a higher level of abstraction than tensor products, so I don't agree this makes monoidal categories less confusing. In fact it diminishes the abstraction of monoidal categories by forcing you to think of the monoidal operation as the tensor product instead of something which is more general. On the other hand if you're familiar with (and prefer) the computationally-oriented definition of tensors as multidimensional arrays, this framing of monoidal categories might ground them somewhat so they're more accessible.
- dbranes 8y ago
  It looks like she wants to talk about symmetric monoidal categories, not just monoidal categories, for that’s where the calculus of string diagrams is actually useful. Tensor categories is another word for symmetric monoidal categories, indeed it’s less of a mouthful, and perhaps more “intuitive” - it’s conventional to write the symmetric monoidal structure as a tensor product.
heinrichhartman 8y ago
I have high regards for Julia, but I am a little sad to see so little meat behind this promising title. As we find out at the very end: > I don’t know whether this particular thing really has anything to do with programming, I just remembered I thought it was cool. Also, I don't really get the main point: > tensor [Monoidal] categories are about proving (or defining) things with pictures You could say that about Category theory as a whole already. E.g. "A product is a space which makes this diagram 'universally' commutative.". No?
- skywhopper 8y ago
  Julia often writes pieces that are just partial captures of a few steps in figuring something interesting out, and which don't come to a conclusion per se. So I don't really understand your critique. I'm not seeing this as any different than her typical articles, except that in this case I know next to nothing about the topic and so from the start I was lost. Her first sentence and her second paragraph address your complaints, anyway. We didn't "find out" that this was just her talking about something cool at the end. Not only did she intro the piece with saying as much, but that's the premise of her entire blog!
leshow 8y ago
> I don’t know whether this particular thing really has anything to do with programming, I just remembered I thought it was cool. There's so many cool things related to programming & monoids. For example, monoids are parallelizeable. Since they are associative, you can group monoids arbitrarily, then use their monoidal operation to get your final result, think MapReduce, or a parallel fold operation. Sorting operations are monoidal (think merge sort), sums, products, so many cool things. There is a huge amount of application to computing.
- mlthoughts2018 8y ago
  I am probably wrong, but I think all the examples you mention only rely on associativity, and you’re essentially talking about why fold / reduce can be parallelized (literally a parallel reduction). For example, just make up some associative operation with no identity element. Imagine a string binary operator that prepends the character ‘a’ to the second operand, then concatenates them. f(‘foo’, ‘bar’) = ‘fooabar’ x `f` y `f` z = ‘{x}a{y}a{z}’ = x `f` (y `f` z) = (x `f` y) `f` z but no string e can result in e `f` x == x, so there’s no identity and so no monoid arises from this.
  - leshow 8y ago
    There is a requirement for identity, take sorting for example, you need to be able to sort the empty set. It's a monoidal operation. The same is true for folds: fold(xs) = fold(xs ++ []) = fold(xs) ++ fold([]) fold(xs) = fold([] ++ xs) = fold([]) ++ fold(xs)
    - mlthoughts2018 8y ago
      There is no monoid type requirement for fold. See the type signature in Haskell (where Monoid happens to be used for fold despite not being necessary) vs Scala (which does not require a monoid) for example. Applying fold to an empty argument has nothing to do with monoidal identities, for example you could just specify what the “seed” result should be (like with Python’s reduce function).
dxbydt 8y ago
6 years ago, when HN was way more relaxed & laidback, someone posted my story about monoids. It stayed on the HN front page for like a whole day !!! (which these days is next to impossible) Anyways, here’s that monoid parable - https://news.ycombinator.com/item?id=5179410 https://news.ycombinator.com/item?id=5179410
drablyechoes 8y ago
Fun fact: a monoid is a category with one object.
- JadeNB 8y ago
  A monoid is (realisable as) the set of morphisms of a category with one object ….

67 points by weinzierl 8y ago

I always enjoy a good Julia Evans article, and this one is no different. She has a very approachable, personable way of explaining technical things, which is missing from many monoid (and related) tutorials. I'm confused by this opening line though: > Monoidal categories are also called “tensor categories” and I think that term is a little less confusing Why is that? What is special about the word "monoid" that makes it more or less confusing than "tensor"?

LudwigNagasena 8y ago
>If you have been around functional programming for a bit, you might see the word “monoid” and “categories” and wonder “oh, is julia writing about monads, like in Haskell”? I am not!!
- yakshaving_jgt 8y ago
  …I don't think that answers the question. Monoids don't come from Haskell. You'll see monoids discussed in Haskell plenty, sure, but the math precedes the programming language by at least a few decades.
  - maccam912 8y ago
    Probably true, but I know some upper level math through programming, and I associate "monoid" with Haskell and an abstract concept, but "tensor" with tensorflow and a more concrete idea.
fraffo 8y ago
Bc you obtain them as the result of tensor product between the cathegory algebra and the monoidal algebra, i think
phlakaton 8y ago
To the contrary, when I think "monoid" I think good old nonnegative integers and addition, or positive integers and multiplication, or any of a half-dozen really easy-to-understand examples. Tensors... what the heck are those? Like matrices, but _more_ complicated, you say? Thanks, but I'll stick with my basic monoids over here. :-) The confusion between monoids and monads is perhaps unfortunate (even if the similarity is quite intentional, because technically monads are a particular kind of monoid), but easily sorted out and not much worse than having to distinguish between the nuts in your pantry and the Nutella.
- throwawaymath 8y ago
  > Tensors... what the heck are those? Like matrices, but _more_ complicated, you say? Thanks, but I'll stick with my basic monoids over here. :-) A tensor isn't actually a multidimensional array, just as a linear map isn't actually a matrix. Defining tensors as the multidimensional abstraction of scalars, vectors and matrices to n indices is anti-pedagogical, though regrettably common because it's computationally useful. Learning tensors this way is like learning linear algebra primarily by doing matrix multiplication. It hollows out all of what's actually going on by focusing on notation and symbol pushing. What you're comparing here is the heavily symbol-laden, notation-encumbered definition of a tensor with the elegant abstraction of a momoid. If you'd like to compare them on the merits of their abstraction, an alternative definition of "tensor" would be better. The object is not its representation. For example: a tensor is a multilinear map between a product of vector spaces and another vector space. So T: V_{1} x V_{2} x ... x V_{n} --> W is a tensor. Furthermore, every tensor T is itself an element of a tensor product. An example of a tensor product is R^{nk}, which is the nk-dimensional real space you obtain by taking the tensor direct product of the n- and k- dimensional real spaces, R^{n} ⊗ R^{k}. In this way the tensor product is an abstraction of the familiar Cartesian product in which the dimension of two spaces is multiplied instead of the cardinality of two sets. This definition makes it easier to understand why the objects of a monoidal category can be considered tensors. A monoidal category is a category C where the functor ⊗ is defined such that C x C --> C. Note the similarity of this definition with my alternative definition of a tensor - no multidimensional arrays are required! You're just moving up one level of generality from linear maps and Cartesian products. Technically speaking, the monoidal category functor is actually an abstraction the tensor product, the way the tensor product is an abstraction of the Cartesian product. Whereas many monoidal categories admit a Cartesian product, some monoidal categories (like the category of vector spaces) admit a tensor product. Edit - Sorry for the bracket notation used in subscripts and superscripte, I was thinking in LaTeX...
mbid 8y ago
Just to add to the confusion: Monoidal categories are the appropriate notion of "monoid object" in the category of categories; unit and associativity law are replaced by coherent natural isomorphisms (see "categorification"). So that's where the "monoidal" comes from.
throwawaymath 8y ago
I don't actually agree with the author that it's less confusing, but I'll abbreviate my other comment to answer your direct question. A tensor is a multilinear map from a product of n vector spaces to another vector space. Every tensor is an element of a tensor product, which is (loosely speaking) a vector space you obtain by multiplying the dimension of two other vector spaces. So for example, the real space R^nk is the tensor product obtained from combining R^n and R^k. To be more explicit, what you're doing is obtaining a new n by k matrix for every pair of vectors of R^n and R^k. In other words, take the Cartesian product of R^n and R^k. Then take every possible pair of vectors of the Cartesian product and combine them to form an n by k matrix. Now you have a tensor product, and each individual element of your tensor product is a tensor. Going back to the abstract: a monoidal category is a category C of objects equipped with a functor defined ⊗: * C x C -> C*. If you take the category of vector spaces or the category of modules (like vector spaces, but defined over rings instead of fields) and define your monoidal functor to be the tensor product, you turn them into tensor categories. Monoidal categories actually sit at a higher level of abstraction than tensor products, so I don't agree this makes monoidal categories less confusing. In fact it diminishes the abstraction of monoidal categories by forcing you to think of the monoidal operation as the tensor product instead of something which is more general. On the other hand if you're familiar with (and prefer) the computationally-oriented definition of tensors as multidimensional arrays, this framing of monoidal categories might ground them somewhat so they're more accessible.
dbranes 8y ago
It looks like she wants to talk about symmetric monoidal categories, not just monoidal categories, for that’s where the calculus of string diagrams is actually useful. Tensor categories is another word for symmetric monoidal categories, indeed it’s less of a mouthful, and perhaps more “intuitive” - it’s conventional to write the symmetric monoidal structure as a tensor product.

heinrichhartman 8y ago

I have high regards for Julia, but I am a little sad to see so little meat behind this promising title. As we find out at the very end: > I don’t know whether this particular thing really has anything to do with programming, I just remembered I thought it was cool. Also, I don't really get the main point: > tensor [Monoidal] categories are about proving (or defining) things with pictures You could say that about Category theory as a whole already. E.g. "A product is a space which makes this diagram 'universally' commutative.". No?

skywhopper 8y ago
Julia often writes pieces that are just partial captures of a few steps in figuring something interesting out, and which don't come to a conclusion per se. So I don't really understand your critique. I'm not seeing this as any different than her typical articles, except that in this case I know next to nothing about the topic and so from the start I was lost. Her first sentence and her second paragraph address your complaints, anyway. We didn't "find out" that this was just her talking about something cool at the end. Not only did she intro the piece with saying as much, but that's the premise of her entire blog!

leshow 8y ago

> I don’t know whether this particular thing really has anything to do with programming, I just remembered I thought it was cool. There's so many cool things related to programming & monoids. For example, monoids are parallelizeable. Since they are associative, you can group monoids arbitrarily, then use their monoidal operation to get your final result, think MapReduce, or a parallel fold operation. Sorting operations are monoidal (think merge sort), sums, products, so many cool things. There is a huge amount of application to computing.

mlthoughts2018 8y ago
I am probably wrong, but I think all the examples you mention only rely on associativity, and you’re essentially talking about why fold / reduce can be parallelized (literally a parallel reduction). For example, just make up some associative operation with no identity element. Imagine a string binary operator that prepends the character ‘a’ to the second operand, then concatenates them. f(‘foo’, ‘bar’) = ‘fooabar’ x `f` y `f` z = ‘{x}a{y}a{z}’ = x `f` (y `f` z) = (x `f` y) `f` z but no string e can result in e `f` x == x, so there’s no identity and so no monoid arises from this.
- leshow 8y ago
  There is a requirement for identity, take sorting for example, you need to be able to sort the empty set. It's a monoidal operation. The same is true for folds: fold(xs) = fold(xs ++ []) = fold(xs) ++ fold([]) fold(xs) = fold([] ++ xs) = fold([]) ++ fold(xs)
  - mlthoughts2018 8y ago
    There is no monoid type requirement for fold. See the type signature in Haskell (where Monoid happens to be used for fold despite not being necessary) vs Scala (which does not require a monoid) for example. Applying fold to an empty argument has nothing to do with monoidal identities, for example you could just specify what the “seed” result should be (like with Python’s reduce function).

dxbydt 8y ago

6 years ago, when HN was way more relaxed & laidback, someone posted my story about monoids. It stayed on the HN front page for like a whole day !!! (which these days is next to impossible) Anyways, here’s that monoid parable - https://news.ycombinator.com/item?id=5179410 https://news.ycombinator.com/item?id=5179410

drablyechoes 8y ago

Fun fact: a monoid is a category with one object.

JadeNB 8y ago
A monoid is (realisable as) the set of morphisms of a category with one object ….