Haskell/Monoids

Introduction

A monoid is any data type which has a "zero" value and a binary "append" operation satisfying certain laws. For example, in a list, the "zero" is [], while the "append" is ++.

In Haskell's Monoid type class, the "zero" is called mempty while the "append" is called mappend.

An example instance for integers might be

instance Monoid Integer where
 mempty=0
 mappend=(+)

A monoid must satisfy this law:

forall x, mappend mzero x = mappend x mzero = x
 

Sigfpe: blog post intuition on associativity

Many monoid related links

Examples

Usage in Cabal [1] [2]. "Package databases are monoids. Configuration files are monoids. Command line flags and sets of command line flags are monoids. Package build information is a monoid."

Usage in Xmonad. "xmonad configuration hooks are monoidal".

FingerTrees.

Homomorphisms

A function f :: A -> B between two monoids A and B is called a homomorphism if it preserves the monoid structure

 f empty           = empty
 f (x `mappend` y) = f x `mappend` f y

For example, length is a homomorphism between ([],++) and (Int,+)

 length []         = 0
 length (xs ++ ys) = length x + length y

Google Protocol Buffers example. The property that

   MyMessage message;
   message.ParseFromString(str1 + str2); 

is equivalent to

   MyMessage message, message2;
   message.ParseFromString(str1);
   message2.ParseFromString(str2);
   message.MergeFrom(message2); 

means that parse is a homomorphism:

   parse :: String -> Message
   parse []         = mempty
   parse (xs ++ ys) = parse xs `merge` parse ys

Well, not quite because parse can fail, but more or less.