I think of these programming constructs as Monoids rather than semigroups. A monoid is just a semigroup with an identity element:<p><a href="http://mathworld.wolfram.com/Monoid.html" rel="nofollow">http://mathworld.wolfram.com/Monoid.html</a><p>Most of his examples have an identity, giving a monoid.<p><pre><code> * (string, concat): identity ''
* numbers with addition/multiplication: identity 0/1
* numbers with min/max: Numbers in computers are
finite, so this is quite useful. stdint.h defines
INT32_MAX, INT32_MIN, etc.
* booleans with && / || : true / false
* function composition: identity function f(x) = x
* frequency map: {} or {A: 0, B:0, ...} depending on
how you define it
</code></pre>
Comparators: Is this a bug in the post? It doesn't seem to follow the pattern because the arity of the functions is different. In a semigroup or monoid all the elements are supposed to be drawn from the same set.<p>Other examples I can think of:<p><pre><code> * Python's dict with respect to member .update()
(if you think of it as an operator rather than
mutating member). Identity is {}
* Unix Pipes: identity 'cat' (note that the shell
supports point-free programming)</code></pre>
I'm not sure how useful this is in practice. For example, addition in actual computer languages isn't necessarily associative and compilers often can't treat them as associative.<p>Floating point numbers added in the wrong order can result in catastrophic cancellation. So for example, as far as JavaScript is concerned, numbers aren't associative.<p>Integers may overflow. Twos-complement addition is associative, but only because if you get the same bogus answer in the case of overflow. If you actually detect overflow, you may get overflow or not depending on the order in which you add the numbers.<p>Oftentimes we ignore these issues, but it seems like if you're talking about taking advantage of associative rules to reorder calculations, you have to think about it. Thinking in terms of semigroups instead of concrete datatypes seems like a likely source of bugs when your model makes assumptions that aren't actually true.
I really wish the applications section had more detail or perhaps an "editorial". I don't really follow the consequence of a frequency map being associative.
Might be slightly off topic but in the recently released Glasgow Haskell Compiler, semigroups are now built into the base library. No more dependencies when using it.
Incidentally the typical mathematical curriculum does not even bother with monoids and semigroups when it comes to the initial introduction. The introductory material jumps right into the definition of a group and then mentions on the side that removing a few key pieces leaves you with a monoid and a semigroup. Same with fields, rings, rigs, etc. The most constrained piece is introduced first and then dropping requirements leaves you with something less constrained for which you can prove fewer theorems.<p>I learned groups and fields first and then learned about the more relaxed versions. I'm not sure which approach is better though. Groups are certainly more fun to play with but monoids probably show up in more contexts.