Difference between revisions of "Monoid"
Jump to navigation
Jump to search
(Added some links) |
Rimmington (talk | contribs) m (fixed "Arrows, like Monads, are Monoids" link) |
||
(7 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
{{Stub}} |
{{Stub}} |
||
− | A monoid is an algebraic structure with |
+ | 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. |
||
− | == See also == |
||
+ | |||
− | * [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] |
||
+ | * [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] |
||
− | * [[Category theory]] |
||
+ | |||
− | * [http://www.cs.ru.nl/~heunen/publications/2006/arrows/arrows.pdf Arrows, like Monads, are Monoids] (PDF) |
||
+ | Generalizations of monoids feature in [[Category theory]], for example: |
||
+ | * [http://www.researchgate.net/publication/235540658_Arrows_like_Monads_are_Monoids/file/d912f511ccdf2c1016.pdf Arrows, like Monads, are Monoids] (PDF) |
Revision as of 09:41, 18 February 2014
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: