Haskell/Monoids

From Wikibooks, the open-content textbooks collection

This module is a stub. You can help Haskell by expanding it.

Contents 1 Introduction 2 Examples 3 Homomorphisms 4 See also

[edit] Introduction

Sigfpe: blog post intuition on associativity

Many monoid related links

[edit] 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.

[edit] 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) = xs `merge` ys

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

[edit] See also