Monoid_Haskell Notes 9

I. Identity Element

In the mathematical world, 0 is the additive identity, 1 is the multiplicative identity (identity element), for example:

> 0 + 3
3
> 3 + 0
3
> 1 * 3
3
> 3 * 1
3

The common point of both is participating in operations, but not changing the other operand:

In mathematics, an identity element or neutral element is a special type of element of a set with respect to a binary operation on that set, which leaves other elements unchanged when combined with them.

(Excerpted from Identity element)

Identity element is defined on binary operations in a set, when combined with identity element for operations, other elements remain unchanged (operation result is still that element). Subdivided into left identity (e * a = a) and right identity (a * e = a), if both are satisfied it's called identity element, also called monoid element (learned this in discrete mathematics)

In Haskell, there are similar things (called Monoid), for example ++ operation encountering []:

> [] ++ "abc"
"abc"
> "abc" ++ []
"abc"

++ is a binary operation defined on List, and [] satisfies identity element property

II. Monoid

In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element.

(Excerpted from Monoid)

Monoid, a concept in abstract algebra, refers to an algebraic structure with an associative binary operation and an identity element. Formal (rigorous) description as follows:

A monoid is a set M with a binary operation *: M × M → M, satisfying the following axioms: Associativity: For any a, b, c in M, (a*b)*c = a*(b*c) Identity: There exists an element e in M, such that for any a in M, a*e = e*a = a

(Excerpted from Monoid)

Need a binary function that obeys associativity, and a value that serves as the identity element for that function, these two constitute Monoid

Monoid typeclass

Located in Data.Monoid module:

class Semigroup a => Monoid a where
    mempty  :: a
    mappend :: a -> a -> a
    mappend = (<>)
    mconcat :: [a] -> a
    mconcat = foldr mappend mempty

(Excerpted from GHC.Base)

P.S. Note, (<>) is defined by Semigroup class, mappend = (<>) declares that mappend and <> are completely equivalent

Requires Monoid (monoid) must first be Semigroup (semigroup, specifically see last part), where mempty is the identity element, mappend is that binary function

mappend is the binary function required by monoid definition that obeys associativity, name is not very appropriate (although contains append, but doesn't mean must implement append-like action), it accepts two monoid values, and returns another monoid value

mconcat accepts a list of monoid values, then folds (fold, or called reduce) them through mappend into one monoid value, given default implementation, generally don't need to implement yourself, unless there's a more suitable implementation method (such as more efficient way)

Monoid laws

Monoid class also needs to obey some rules, as follows:

mempty `mappend` x = x
x `mappend` mempty = x
(x `mappend` y) `mappend` z = x `mappend` (y `mappend` z)

First two guarantee mempty is identity element, third shows binary function mappend satisfies associativity

III. Monoid instances

List

instance Semigroup [a] where
  (<>) = (++)

instance Monoid [a] where
  mempty  = []
  mconcat xss = [x | xs <- xss, x <- xs]

(Excerpted from GHC.Base)

As we thought, List and ++ operation defined on List with empty List identity element, constitute monoid

Verify with Monoid laws:

> mempty `mappend` "hoho"
"hoho"
> "hoho" `mappend` mempty
"hoho"
> "a" `mappend` "b" `mappend` "c"
"abc"
> "a" `mappend` ("b" `mappend` "c")
"abc"

mempty is identity element, mappend also satisfies associativity, so List is a qualified Monoid instance

P.S. If want to know what mempty specifically is, do this:

> mempty :: [a]
[]
> mempty :: Ordering
EQ
> mempty :: ()
()

Note, need to specify a concrete type for mempty (such as [a] or [Int] :: *, not [] :: * -> *)

Product and Sum

Mentioned additive identity and multiplicative identity at the beginning identity element part, simultaneously they also satisfy associativity, so, numeric operations have two monoids, respectively addition with identity 0, and multiplication with identity 1

In other words, Num can have two different Monoid implementations, respectively binary function + with identity 0, and binary function * with identity 1. Facing this scenario again, so like creating ZipList, we created Sum and Product classes (located in Data.Monoid):

newtype Product a = Product { getProduct :: a }
  deriving (Eq, Ord, Read, Show, Bounded, Generic, Generic1, Num)
newtype Sum a = Sum { getSum :: a }
    deriving (Eq, Ord, Read, Show, Bounded, Generic, Generic1, Num)

P.S. About ZipList and newtype history, see newtype_Haskell Notes 8

Product's Monoid implementation as follows:

instance Num a => Semigroup (Product a) where
  (<>) = coerce ((*) :: a -> a -> a)

instance Num a => Monoid (Product a) where
  mempty = Product 1

Identity element is Product 1, binary function is coerce ((*) :: a -> a -> a), where coerce is used for type conversion (specifically see Data.Coerce), equivalent to:

Product x `mappend` Product y = Product (x * y)

Defined on Num, so identity element's value relates to concrete type:

> getProduct (mempty :: (Product Int))
1
> getProduct (mempty :: (Product Double))
1.0

Sum's implementation is similar to Product:

instance Num a => Semigroup (Sum a) where
  (<>) = coerce ((+) :: a -> a -> a)

instance Num a => Monoid (Sum a) where
  mempty = Sum 0

Try it out:

> getSum $ Sum 3 `mappend` (mconcat $ map Sum [1, 2, 3])
9

Any and All

Similar to Num, Bool values also have two monoids: || operation with identity False, && operation with identity True:

-- || operation with identity False
newtype Any = Any { getAny :: Bool }
  deriving (Eq, Ord, Read, Show, Bounded, Generic)

instance Semigroup Any where
  (<>) = coerce (||)

instance Monoid Any where
  mempty = Any False

-- && operation with identity True
newtype All = All { getAll :: Bool }
  deriving (Eq, Ord, Read, Show, Bounded, Generic)

instance Semigroup All where
  (<>) = coerce (&&)

instance Monoid All where
  mempty = All True

Any and All similarly located in Data.Monoid

Ordering

Ordering type definition is quite simple:

data Ordering = LT | EQ | GT

Corresponding Monoid implementation as follows:

instance Semigroup Ordering where
  LT <> _ = LT
  EQ <> y = y
  GT <> _ = GT

instance Monoid Ordering where
  mempty             = EQ

P.S. Different from other Monoid instances mentioned before, here mappend is freshly made, not directly using existing functions (before all took existing functions to verify, see if have monoid properties)

This function's behavior is, operation result takes left operand, unless left is EQ (at this time takes right). Looks somewhat strange, can understand as string (by dictionary order) comparison, for example compare "ab" "am" comparison result is LT, LT <> _ = LT means if current comparison result is LT, then continuing to compare afterwards result is still LT, for example compare "absolute" "america". Similarly, EQ <> y = y means if current result is EQ, remaining part's comparison result is final result, GT <> _ = GT means if current result is GT,后面 what doesn't matter, final result must be GT

Maybe

instance Semigroup a => Semigroup (Maybe a) where
  Nothing <> b       = b
  a       <> Nothing = a
  Just a  <> Just b  = Just (a <> b)

instance Semigroup a => Monoid (Maybe a) where
  mempty = Nothing

P.S. Note the type constraint here, requires a is a Semigroup, used to guarantee Just a <> Just b = Just (a <> b) can operate normally

So, Maybe's identity element is Nothing, operation is also freshly made, but quite clever, two Just a's operation result is operating on content, then putting back into Just, so requires content also supports this operation (<>), for example:

> Just (Sum 2) `mappend` Just (Sum 3)
Just (Sum {getSum = 5})
> Just [1, 2] `mappend` Just [3, 4]
Just [1,2,3,4]

If content doesn't support <> operation, cannot perform Maybe's operation:

> Just 2 `mappend` Just (3 :: Int)

<interactive>:195:1: error:
    ? No instance for (Monoid Int) arising from from a use of 'mappend'

IV. Foldable and Monoid

Monoid instances all support mappend behavior, can understand as "superposition", combining two Monoid instances through operation into one Monoid instance, additionally, also supports "folding" (mconcat), can fold a group of Monoid instances from head to tail through "superposition", thereby "folding" into one Monoid instance

A group of things can be "folded" to form one thing, this thing is "foldable", i.e. Foldable:

class Foldable t where
  {-# MINIMAL foldMap | foldr #-}
  foldMap :: Monoid m => (a -> m) -> t a -> m
  foldr :: (a -> b -> b) -> b -> t a -> b

(Excerpted from Data.Foldable)

P.S. Foldable is located in Data.Foldable module, function names conflict with List function names in Prelude, so generally import through alias, for example:

import qualified Data.Foldable as Foldable

According to class definition, only need to implement foldMap or foldr to become Foldable instance, from type declaration, foldMap is obviously oriented towards Monoid, while foldr is more general fold interface

Specifically, what foldMap does is using function a -> m to map Foldable structure (t a), getting a Foldable structure whose content is a group of Monoid composed, then through mconcat (or say mappend) fold this group of Monoid into one Monoid and return

Practical Application

What's the practical significance of implementing Foldable? Look at an example:

module BTree
( Tree(..)
, singleton
, add
, fromList
) where

import Data.Monoid
import Data.Foldable

data Tree a = EmptyTree | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)

singleton x = Node x EmptyTree EmptyTree

add x EmptyTree = singleton x
add x (Node a left right)
  | x == a = Node a left right
  | x > a = Node a left (add x right)
  | x < a = Node a (add x left) right

fromList xs = foldr add EmptyTree xs

This is a custom binary tree type (actually a binary search tree, the simplest and crudest kind, use it as binary tree for now), has basic binary tree construction functionality (singleton, add and fromList), implement a Monoid interface for it:

instance Monoid a =>  Monoid (Tree a) where
  mempty = EmptyTree
  a `mappend` EmptyTree = a
  EmptyTree `mappend` b = b
  (Node x xl xr) `mappend` (Node y yl yr) = Node (x `mappend` y) (xl `mappend` yl) (xr `mappend` yr)

Note, we require Tree a's a is also a Monoid instance, because need to do mappend on Node's content. This is similar to Maybe's Monoid implementation mentioned before

Try Monoid laws:

> let nodeA = Node (Sum 1) (singleton (Sum 2)) EmptyTree
> let nodeB = Node 5 (Node 3 (singleton 1) (singleton 6)) (Node 9 (singleton 8) (singleton 10))
> let nodeC = singleton (Sum 6)
> nodeA `mappend` nodeB `mappend` nodeC
Node (Sum {getSum = 12}) (Node (Sum {getSum = 5}) (Node (Sum {getSum = 1}) EmptyTree EmptyTree) (Node (Sum {getSum = 6}) EmptyTree EmptyTree)) (Node (Sum {getSum = 9}) (Node (Sum {getSum = 8}) EmptyTree EmptyTree) (Node (Sum {getSum = 10}) EmptyTree EmptyTree))
> nodeA `mappend` (nodeB `mappend` nodeC)
Node (Sum {getSum = 12}) (Node (Sum {getSum = 5}) (Node (Sum {getSum = 1}) EmptyTree EmptyTree) (Node (Sum {getSum = 6}) EmptyTree EmptyTree)) (Node (Sum {getSum = 9}) (Node (Sum {getSum = 8}) EmptyTree EmptyTree) (Node (Sum {getSum = 10}) EmptyTree EmptyTree))

3 trees structure as follows:

-- nodeA
1
  2
  empty
-- nodeB
5
  3
    1
    6
  9
    8
    10
-- nodeC
6

mappend result is:

12
  5
    1
    6
  9
    8
    10

Actually is summing corresponding positions, empty nodes play role of 0. Recall, how did we express the intent of "summing"?

"Summing" is expressed through Sum this Monoid instance, while Tree is merely a structure, numeric values are first wrapped by Sum one layer, adding summation semantics, then filled into Tree, possessing tree's structural meaning. Seems, there's something to it

Continue, implement Foldable interface, remember Foldable and Monoid relationship is intimate, so easy to make a class of Monoid instances become foldable:

instance Foldable.Foldable Tree where
  foldMap f EmptyTree = mempty
  foldMap f (Node x l r) = Foldable.foldMap f l `mappend`
                              f x `mappend`
                              Foldable.foldMap f r

Big move charging completed, first come a opening move:

let tree = fromList [7, 3, 1, 2, 6, 9, 8, 5]
> getAny $ Foldable.foldMap (\x -> Any $ x == 3) tree
True

Created a tree like this:

-- tree
5
  2
    1
    3
  8
    6
      empty
      7
    9

Completed containment judgment in one sentence: getAny $ Foldable.foldMap (\x -> Any $ x == 3) tree. Move came out too fast didn't see clearly? Slow motion breakdown:

0. Mapping function (\x -> Any $ x == 3) compares input value equality with 3, puts comparison result into Any

1. Traverse tree from bottom to top, use mapping function to convert values on each node, encountering empty node wrap into mempty, forming a Monoid tree (Any tree)

2. Fold Any tree, specific method is from bottom to top perform left mappend middle mappend right operation, Any's mappend is OR operation on values (||), encountering mempty corresponds to Any False, when reaching tree root, operation result is Any True

3. getAny takes out folding result True

P.S. Note, generating Any tree and traversing folding is performed simultaneously in one traversal, not traversing twice (first pass do mapping, second pass fold), above breakdown is just for easier understanding

After opening move, big move comes:

> Foldable.foldMap (\x -> [x]) tree
[1,2,3,5,6,7,8,9]

Wait, what happened?

Converted tree to array in one sentence, moreover, secretly sorted. Okay, somewhat exaggerated, sorting is done by binary search tree (when fromList add builds tree), so just converted tree to array, specifically:

0. Mapping function (\x -> [x]) puts input value into List (collects it)

1. Traverse tree from bottom to top, use mapping function to convert values on each node, encountering empty node wrap into mempty, forming a List tree

2. Fold List tree, specific method is from bottom to top perform left mappend middle mappend right operation, List's mappend is concatenation (++), encountering mempty corresponds to [], when reaching tree root, operation result is [all elements on tree]

3. Directly output folding result, is [all elements on tree]

Completed containment judgment in one sentence, completed tree element collection in one sentence, quite stunning operation

P.S. What about summing tree, multiplying, filtering elements? Too easy:

> getSum $ Foldable.foldMap Sum tree
41
> getProduct $ Foldable.foldMap Product tree
90720
> Foldable.foldMap (\x -> if x > 5 then [x] else []) tree
[6,7,8,9]

V. Groups, Semigroups and Monoids

From mathematical meaning perspective, all are algebraic structures formed by sets and binary operations:

• Semigroup: Set S and its binary operation ·:S×S→S. If · satisfies associativity, i.e.: ∀x,y,z∈S, have (x·y)·z=x·(y·z), then call ordered pair (S,·) semigroup

• Monoid: Set M and its binary operation *: M × M → M, this operation satisfies associativity, and identity element is also in the set

• Group: A group is a set G, together with an operation ·, it combines any two elements a and b to form another element, denoted a·b, requires this operation satisfies associativity and closure, set must have identity element, and each element has inverse element

P.S. Inverse element means, for each a in G, there exists an element b in G such that a·b = b·a = e, here e is identity element

Simply speaking:

• Semigroup: Specific set and binary operation defined on that set, this operation satisfies closure (binary operation result still in set) and associativity (left combination result equals right combination result)

• Monoid: Semigroup containing identity element

• Group: Monoid where each element has corresponding inverse element

From general to special, monoid is between semigroup and group, group is most special (somewhat counterintuitive). Looking反过来，semigroup is generalization of monoid (semigroup doesn't require having identity element), also generalization of group (semigroup doesn't require each element has inverse element):

A semigroup generalizes a monoid in that there might not exist an identity element. It also (originally) generalized a group (a monoid with all inverses) to a type where every element did not have to have an inverse, thus the name semigroup.

From syntax perspective, three relationships as follows:

class Semigroup a where
  -- Operation satisfying associativity (also satisfies closure)
  (<>) :: a -> a -> a

class Semigroup a => Monoid a where
  -- Identity element
  mempty  :: a
  -- Operation satisfying associativity (also satisfies closure)
  mappend :: a -> a -> a
  mappend = (<>)

class Monoid m => Group m where
  -- Operation for finding inverse element
  invert :: m -> m

Semigroup is an interface (typeclass), describes specific set, and an operation defined on that set, this operation satisfies associativity, all Semigroup instances have this behavior characteristic

Monoid is also an interface, describes specific set, and an operation satisfying associativity defined on that set, and identity element is also in the set

Group is similarly an interface, describes specific set, and an operation satisfying associativity defined on that set, not only has identity element, but also each element has inverse element

P.S. Additionally, monoid has certain connection with category theory, see Relationship with Category Theory

Reference Materials

• semigroups: Anything that associates