Examples of monoids/semigroups in programming

It is well-known that monoids are stunningly ubiquitous in programing. They are so ubiquitous and so useful that I, as a 'hobby project', am working on a system that is completely based on th开发者_C百科eir properties (distributed data aggregation). To make the system useful I need useful monoids :)

I already know of these:

• Numeric or matrix sum
• Numeric or matrix product
• Minimum or maximum under a total order with a top or bottom element (more generally, join or meet in a bounded lattice, or even more generally, product or coproduct in a category)
• Set union
• Map union where conflicting values are joined using a monoid
• Intersection of subsets of a finite set (or just set intersection if we speak about semigroups)
• Intersection of maps with a bounded key domain (same here)
• Merge of sorted sequences, perhaps with joining key-equal values in a different monoid/semigroup
• Bounded merge of sorted lists (same as above, but we take the top N of the result)
• Cartesian product of two monoids or semigroups
• List concatenation
• Endomorphism composition.

Now, let us define a quasi-property of an operation as a property that holds up to an equivalence relation. For example, list concatenation is quasi-commutative if we consider lists of equal length or with identical contents up to permutation to be equivalent.

Here are some quasi-monoids and quasi-commutative monoids and semigroups:

• Any (a+b = a or b, if we consider all elements of the carrier set to be equivalent)
• Any satisfying predicate (a+b = the one of a and b that is non-null and satisfies some predicate P, if none does then null; if we consider all elements satisfying P equivalent)
• Bounded mixture of random samples (xs+ys = a random sample of size N from the concatenation of xs and ys; if we consider any two samples with the same distribution as the whole dataset to be equivalent)
• Bounded mixture of weighted random samples
• Let's call it "topological merge": given two acyclic and non-contradicting dependency graphs, a graph that contains all the dependencies specified in both. For example, list "concatenation" that may produce any permutation in which elements of each list follow in order (say, 123+456=142356).

Which others do exist?

Quotient monoid is another way to form monoids (quasimonoids?): given monoid M and an equivalence relation ~ compatible with multiplication, it gives another monoid. For example:

• finite multisets with union: if A* is a free monoid (lists with concatenation), ~ is "is a permutation of" relation, then A*/~ is a free commutative monoid.

• finite sets with union: If ~ is modified to disregard count of elements (so "aa" ~ "a") then A*/~ is a free commutative idempotent monoid.

• syntactic monoid: Any regular language gives rise to syntactic monoid that is quotient of A* by "indistinguishability by language" relation. Here is a finger tree implementation of this idea. For example, the language {a³ⁿ:n natural} has Z₃ as the syntactic monoid.

Quotient monoids automatically come with homomorphism M -> M/~ that is surjective.

A "dual" construction are submonoids. They come with homomorphism A -> M that is injective.

Yet another construction on monoids is tensor product.

Monoids allow exponentation by squaring in O(log n) and fast parallel prefix sums computation. Also they are used in Writer monad.

The Haskell standard library is alternately praised and attacked for its use of the actual mathematical terms for its type classes. (In my opinion it's a good thing, since without it I'd never even know what a monoid is!). In any case, you might check out http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Monoid.html for a few more examples:

• the dual of any monoid is a monoid: given a+b, define a new operation ++ with a++b = b+a
• conjunction and disjunction of booleans
• over the Maybe monad (aka "option" in Ocaml), first and last. That is,

  first (Just a) b = Just a
  first Nothing b = b

  and likewise for last

The latter is just the tip of the iceberg of a whole family of monoids related to monads and arrows, but I can't really wrap my head around these (other than simply monadic endomorphisms). But a google search on monads monoids turns up quite a bit.

A really useful example of a commutative monoid is unification in logic and constraint languages. See section 2.8.2.2 of 'Concepts, Techniques and Models of Computer Programming' for a precise definition of a possible unification algorithm.

Good luck with your language! I'm doing something similar with a parallel language, using monoids to merge subresults from parallel computations.

Arbitrary length Roman numeral value computation. https://gist.github.com/4542999