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"?
>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!!
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.
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.
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.
> 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...
You can think of a tensor as "an element of a tensor product" (just like a vector is "an element of a vector space") and look at the definition of a tensor product via its universal property, it basically turns bilinear maps into linear maps. This universal property is elegant and immediately gives the Hom-tensor adjunction, but to show that tensor products satisfying it actually exist you'll need an explicit construction, which can be done by quotienting a free module. This explicit construction might look unintuitive at first, but you're really quotienting by the minimal relations required for the "bilinearity" property of tensors to work out
I think this is a fantastic definition of what tensors are for mathematicians, but I think it is likely to be not very helpful for someone whose perspective is:
> Tensors... what the heck are those? Like matrices, but _more_ complicated, you say? Thanks, but I'll stick with my basic monoids over here. :-)
If matrices are the limit of your tolerance for complication, bilinear maps probably aren't intuitive tools for you.
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.
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.
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.
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!
> 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.
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.
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).
Back to my first post, I don't think it's not wrong to describe these operations as monoidal. Or to say that a monoidal operation implies something can be run in parallel, this whole thing feels a bit pedantic.
edit: I don't know how you can say monoids for lists have nothing to do w/ empty lists considering the definition is literally:
`foldMap` and `fold` in Haskell only require Monoid because there are many common cases where you're folding over a monoidal type; they are simply conveniences. The alternative is to always define things in terms of `foldr` which is more "fundamental" (since its type represents a church encoding of the underlying type) which, as you note, does not require a Monoid.
All that said, as another commentor noted, most of the time people actually want to talk about Monoids and not Semigroups, because identities are extremely convenient for accumulating results, and all Semigroups can be upgraded to Monoids (in Haskell this is as easy as changing type `a` to `Maybe a` for any Semigroup `a`). Arrays or counters are easy examples. You can of course use specifically designated "seed" values and argue Monoids aren't necessary but you're probably going to start adding code that does stuff like "if value == seed then ..." -- and at that point you probably are dealing with a Monoid, whether you recognize it or not. Again, the easiest example would be in Haskell, where you say "I can combine these things of type `a`. But I can't always produce a result, so instead I want `Maybe a`, and occasionally I'll produce Nothing instead, and then..." -- and that's exactly the Monoid you get by upgrading any Semigroup.
So you are correct that fold has no a priori requirement for a Monoid, but in practice you probably will want monoidal composition semantics a lot of the time.
What you have described is a semigroup. Sometimes an application might naturally involve semigroups and sure, they share the benefits of associativity with monoids. Semigroups generalise monoids, which are one step further up on the ladder to full groups.
Monoids occur more frequently in practice both because it's often practically useful and semantically meaningful to have an "empty" value (the identity) when accumulating results. So even if the application has an underlying semigroup structure, you might sometimes want to use a sum type to add an identity and make it into a monoid:
"Any semigroup S may be turned into a monoid simply by adjoining an element e not in S and defining e • s = s = s • e for all s ∈ S."
So from a programming point of view, the monoid is a handier pattern than the semigroup, and you can almost always turn a semigroup into a monoid if that would make things more convenient.
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)
28 comments
[ 3.2 ms ] story [ 64.2 ms ] threadI'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"?
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.
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.
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...
> Tensors... what the heck are those? Like matrices, but _more_ complicated, you say? Thanks, but I'll stick with my basic monoids over here. :-)
If matrices are the limit of your tolerance for complication, bilinear maps probably aren't intuitive tools for you.
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.
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.
> 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?
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!
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.
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.
but no string e can result in e `f` x == x, so there’s no identity and so no monoid arises from this.The same is true for folds:
https://philipnilsson.github.io/Badness10k/algebraic-pattern...
Back to my first post, I don't think it's not wrong to describe these operations as monoidal. Or to say that a monoidal operation implies something can be run in parallel, this whole thing feels a bit pedantic.
edit: I don't know how you can say monoids for lists have nothing to do w/ empty lists considering the definition is literally:
Which is exactly what I posted beforeAll that said, as another commentor noted, most of the time people actually want to talk about Monoids and not Semigroups, because identities are extremely convenient for accumulating results, and all Semigroups can be upgraded to Monoids (in Haskell this is as easy as changing type `a` to `Maybe a` for any Semigroup `a`). Arrays or counters are easy examples. You can of course use specifically designated "seed" values and argue Monoids aren't necessary but you're probably going to start adding code that does stuff like "if value == seed then ..." -- and at that point you probably are dealing with a Monoid, whether you recognize it or not. Again, the easiest example would be in Haskell, where you say "I can combine these things of type `a`. But I can't always produce a result, so instead I want `Maybe a`, and occasionally I'll produce Nothing instead, and then..." -- and that's exactly the Monoid you get by upgrading any Semigroup.
So you are correct that fold has no a priori requirement for a Monoid, but in practice you probably will want monoidal composition semantics a lot of the time.
Monoids occur more frequently in practice both because it's often practically useful and semantically meaningful to have an "empty" value (the identity) when accumulating results. So even if the application has an underlying semigroup structure, you might sometimes want to use a sum type to add an identity and make it into a monoid:
"Any semigroup S may be turned into a monoid simply by adjoining an element e not in S and defining e • s = s = s • e for all s ∈ S."
So from a programming point of view, the monoid is a handier pattern than the semigroup, and you can almost always turn a semigroup into a monoid if that would make things more convenient.
There are a couple of articles here that make a weak case for the applicability of semigroups in software: https://blog.ploeh.dk/2017/11/27/semigroups/
Four Solutions to a Trivial Problem - Guy Steele Jr. https://www.youtube.com/watch?v=ftcIcn8AmSY (using a monoid-cached tree)
Anyways, here’s that monoid parable - https://news.ycombinator.com/item?id=5179410