They're useful because knowing them allows for identifying and mechanically applying transformations to better leverage parallelism and easily implement incremental computations†.

I highly recommend this article and the section on monoid homomorphisms in particular, which covers why you should care about monoids and gives a practical example: https://fsharpforfunandprofit.com/posts/monoids-part2/#monoi...

If you've been programming for a while, I can guarantee you already intuitively understand the concept. Giving it a name allows you to automatically recognize and notice that you've already solved this problem before in another guise.

Alternatively, having named the concept, it's now chunked into your toolkit for use whenever applicable. Structuring your solution so you know it's a monoid allows leveraging all those benefits almost for free.

†With divide and conquer, add memoization and pay attention to the order of subproblems such that you can reuse earlier work, and if you can, we're nearly at dynamic programming. We can specify a bit more structure, to get semirings and collapse a whole heap of disparate seeming machine learning algorithms. But now I have gone too far afield.

A monoid is a concept from math. They have a set of objects (like the integers), and a binary operation (like addition or multiplication over integers). The operation is associative (like addition where the order you compute a set of additions doesn’t matter, you get the same sum). And there’s an identity element (in addition this would be 0).

For CS there are some nice results where the operation can be automatically parallelized. Useful for things like MapReduce if you need to run things at large scale, or in this case for distributing the work over the many shader units of a GPU.

https://web.archive.org/web/20200325013049/http://dave.fayr....

Functions form a monoid as well. Function composition is associative and id is the unit.

+ is a monoid. It adds to numbers together. (3+3)+4 = 3+(3+4)

But also concatenation is a monoid

"a" + ("b" + "c") = ("a" + "b") + "c".

Monoids have an empty thing you can add to anything.

E.g. 0 for + and "" for concatenation.

In Haskell, Monoids are abstracted out into a typeclass so that you can write code on any monoid. For example fold up a list of monoid elements into a single element.

The author defines a monoid early on, in terms of the three properties that someone else also posted.

I understand this definition but am still trying to make the leap to how it applies in the original article.

The action takes a state from Q, and a symbol from E, and returns a new state. ie f:QxE->Q. In the case when you have some "no op" action the semigroup action is actually a monoid action.

This all corresponds to the DFA moving through states as it "eats" the string.