Personal tools

Monoid

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(Added another link)
m (Links fixed)
(5 intermediate revisions by 3 users not shown)
Line 1: Line 1:
 
{{Stub}}
 
{{Stub}}
   
A monoid is an algebraic structure with a single, associative binary operation and an identity element.
+
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
   
== See also ==
+
Note that in most of these cases the operation is also commutative, but it need not be; concatenation and function composition are not commutative.
* An introduction: [http://sigfpe.blogspot.com/2009/01/haskell-monoids-and-their-uses.html Haskell Monoids and their Uses]:
+
* [http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-Monoid.html The Data.Monoid module]
+
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.:
  +
* An introduction: [http://sigfpe.blogspot.com/2009/01/haskell-monoids-and-their-uses.html Haskell Monoids and their Uses]
 
* The blog article [http://apfelmus.nfshost.com/monoid-fingertree.html Monoids and Finger Trees]
 
* The blog article [http://apfelmus.nfshost.com/monoid-fingertree.html Monoids and Finger Trees]
* [[Category theory]]
+
* [http://haskell.org/sitewiki/images/6/6a/TMR-Issue11.pdf Monad.Reader issue 11, "How to Refold a Map."] (PDF), and a [http://haskell.org/haskellwiki/The_Monad.Reader/Discuss_Issue11 follow up]
  +
  +
Generalizations of monoids feature in [[Category theory]], for example:
 
* [http://www.cs.ru.nl/~heunen/publications/2006/arrows/arrows.pdf Arrows, like Monads, are Monoids] (PDF)
 
* [http://www.cs.ru.nl/~heunen/publications/2006/arrows/arrows.pdf Arrows, like Monads, are Monoids] (PDF)

Revision as of 13:56, 7 February 2012

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.:

Generalizations of monoids feature in Category theory, for example: