Why are monoidal categories interesting?
jvns.ca
jvns.ca
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.
f(‘foo’, ‘bar’) = ‘fooabar’
x `f` y `f` z = ‘{x}a{y}a{z}’
= x `f` (y `f` z)
= (x `f` y) `f` z
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/
The same is true for folds:
fold(xs) = fold(xs ++ []) = fold(xs) ++ fold([])
fold(xs) = fold([] ++ xs) = fold([]) ++ fold(xs)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.
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:
-- Identity laws
x <> mempty = x
mempty <> x = x
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
> 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!
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"?
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.
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. :-)
If matrices are the limit of your tolerance for complication, bilinear maps probably aren't intuitive tools for you.
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...
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.