Examples of monoids/semigroups in programming

Question

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 their 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?

Doehne

I rolled back the changes to tags, because IMO the question is not at all about functional programming. – Doehne

Offtopic: How to fold a monoid using parallel computations? – Particiaparticipant

@Andrey If the monoid is commutative, you may just add up the values in arbitrary order, on arbitrary threads/processors/machines, until only one value remains (or you can make it remain 1 value per machine and somehow add them up only during read access, etc.). I'm going to use only commutative monoids. If the monoid is non-commutative, then you add up the values using a balanced tree built on the values list: levels are traversed sequentially, but the nodes at each level may be reduced in parallel. See also the works of Guy Blelloch on vector parallelism. – Doehne

Answer 1

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.

Snowinsummer

Thanks; could you tell something about the usefulness of tensor product? The article didn't provide any examples, and I'm not that hardcore at algebra as to think them up myself :) – Doehne

Answer 2

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.

Awful

Right, I completely forgot about duals and booleans! As for the Maybe monad, the example is essentially mentioned as "Any satisfying predicate". Monad endomorphisms are also a good idea. – Doehne

Answer 3

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.

Puree

The book mentions neither the term "monoid" nor "semigroup", so it is a great exercise to make these concepts explicit while following description of the algorithm. (i'm still struggling with it and wouldn't have even made the connection if not for this answer.) – Procter

Answer 4

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

Broomfield