Monoids

A monoid is an algebraic structure that captures many

collection and aggregate types:

( ?, Z? )

The merge function ? is associative with zero Z?:

x ? Z? = Z? ? x = x

A parametric type (e.g. set(a)) is associated with a free

monoid that has a unit U?:

( ?, Z? , U? )

A free monoid is a collection monoid;

any other monoid is a primitive monoid.

Previous slide

Next slide

Back to first slide

View graphic version

Our calculus is based on monoids from abstract algebra. A monoid is an algebraic structure that captures most collection and aggregate types. Formally, a monoid is a pair of an associative function, called the merge function, and a value, which is the left and right identity of the merge function. A collection type, such as a set, requires an additional function, called the monoid unit, that constructs singleton values.