# Difference between revisions of "Monoid"

From HaskellWiki

(Added a link to "How to Refold a Map.") |
RossPaterson (talk | contribs) (egs, introduce refs) |
||

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

+ | * functions from a type to itself, under composition | ||

− | + | The monoid interface enables a number of algorithms, including parallel algorithms and tree searches, e.g.: | |

+ | * The [http://www.haskell.org/ghc/dist/current/docs/libraries/base/Data-Monoid.html Data.Monoid] module | ||

* An introduction: [http://sigfpe.blogspot.com/2009/01/haskell-monoids-and-their-uses.html Haskell Monoids and their Uses] | * 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] | * [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 15:33, 26 January 2009

*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
- functions from a type to itself, under composition

The monoid interface enables a number of algorithms, including parallel algorithms and tree searches, e.g.:

- The Data.Monoid module
- 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: