Monoid
From HaskellWiki
(Difference between revisions)
(refer to uses) |
m (Links fixed) |
||
| (One intermediate revision not shown.) | |||
| Line 5: | Line 5: | ||
* numbers under addition or multiplication | * numbers under addition or multiplication | ||
* Booleans under conjunction or disjunction | * Booleans under conjunction or disjunction | ||
| - | * sets under union | + | * sets under union or intersection |
* functions from a type to itself, under composition | * functions from a type to itself, under composition | ||
| - | A Monoid class is defined in [http://www.haskell.org/ghc/ | + | Note that in most of these cases the operation is also commutative, but it need not be; concatenation and function composition are not commutative. |
| + | |||
| + | A Monoid class is defined in [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Monoid.html Data.Monoid], and used in [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Foldable.html Data.Foldable] and in the Writer monad. | ||
The monoid interface enables a number of algorithms, including parallel algorithms and tree searches, e.g.: | The monoid interface enables a number of algorithms, including parallel algorithms and tree searches, e.g.: | ||
Current revision
This article is a stub. You can help by expanding it.
A monoid is an algebraic structure with an associative binary operation that has an identity element. Examples include:
- lists under concatenation
- numbers under addition or multiplication
- Booleans under conjunction or disjunction
- sets under union or intersection
- functions from a type to itself, under composition
Note that in most of these cases the operation is also commutative, but it need not be; concatenation and function composition are not commutative.
A Monoid class is defined in Data.Monoid, and used in Data.Foldable and in the Writer monad.
The monoid interface enables a number of algorithms, including parallel algorithms and tree searches, e.g.:
- An introduction: Haskell Monoids and their Uses
- The blog article Monoids and Finger Trees
- Monad.Reader issue 11, "How to Refold a Map." (PDF), and a follow up
Generalizations of monoids feature in Category theory, for example:
