Thumrongsak Kosiyatrakul
Thumrongsak Kosiyatrakul
What is a Monoid?
A set S equipped with a binary operation of type S × S → S denoted by ·, is a monoid if it satisfies the following conditions:
Associativity: for every elements 𝑎, 𝑏, and 𝑐 ∈ S: (𝑎 · 𝑏) · 𝑐 = 𝑎 · (𝑏 · 𝑐)
Identity Element: There exists an element 𝑒 ∈ S such that for every element 𝑎 ∈ S:
𝑒·𝑎=𝑎 and 𝑎·𝑒=𝑎
The above monoid can be represented by a triple (S, ·, 𝑒)
Thumrongsak Kosiyatrakul
Example: Monoid SumZ
Consider the set of integers (Z):
Z = {…,−2,−1,0,1,2,…}
Consider the binary operation + (addition) between integerss: +:Z×Z→Z
Addition is associative:
(𝑎+𝑏)+𝑐=𝑎+(𝑏+𝑐) forall𝑎,𝑏,𝑐∈Z
0 is the identity element:
0+𝑛=𝑛 and 𝑛+0=𝑛 forevery𝑛∈Z
(Z, +, 0) is a monoid and it is called the monoid SumZ Monads
Thumrongsak Kosiyatrakul
Example: Monoid ProductZ
(Z, +, 0) is not the only monoid related to the set of integers
Consider the binary operation ∗ (multiplication) between integers:
∗:Z×Z→Z Multiplication is associative:
(𝑎∗𝑏)∗𝑐=𝑎∗(𝑏∗𝑐) forall𝑎,𝑏,𝑐∈Z 1 is the identity element:
1∗𝑛=𝑛 and 𝑛∗1=𝑛 forevery𝑛∈Z (Z, ∗, 1) is a monoid and it is called the monoid ProductZ
Thumrongsak Kosiyatrakul
Example: Strings
Let Σ∗ be the set of all strings over a non-empty finite set of symbols Σ
Let 𝜀 denotes the empty string
Consider the binary operation ++ (concatenation):
++ : Σ∗ × Σ∗ → Σ∗
++ is associative:
(𝑎++𝑏)++𝑐=𝑎++(𝑏++𝑐) forall𝑎,𝑏,𝑐,∈Σ∗
𝜀 is the identity element:
𝜀++𝑠=𝑠 and 𝑠++𝜀=𝑠 forevery𝑠∈Σ∗
(Σ∗, ++, 𝜀) is monoid
Thumrongsak Kosiyatrakul
Example: Monoid List
Recall that a string is simply a list of characters
Let’s [𝑎] denotes the set of type 𝑎 and [] denotes the empty list
Since the concatenation operator (++) support of type of lists, ([𝑎], ++, []) is a monoid
This is called the monoid List
Thumrongsak Kosiyatrakul
Example: Monoid All
Consider the set of boolean values Bool = {True, False} and the conjunction operator ∧
The conjunctive operator (∧) is associative: 𝑝∧(𝑞∧𝑟)=(𝑞∧𝑞)∧𝑟 forall𝑝,𝑞,𝑟∈Bool
The identity element is True
𝑝∧True=𝑝 and True∧𝑝=𝑝 forevery𝑝∈Bool
(Bool, ∧, True) is a monoid called the monoid All
Thumrongsak Kosiyatrakul
Example: Monoid Any
Consider the set of boolean values Bool = {True, False} and the disjunction operator ∨
The conjunctive operator (∨) is associative 𝑝∨(𝑞∨𝑟)=(𝑞∨𝑞)∨𝑟 forall𝑝,𝑞,𝑟∈Bool
The identity element is False
𝑝∨False=𝑝 and False∨𝑝=𝑝 forevery𝑝∈Bool
(Bool, ∨, False) is a monoid called the monoid Any
Thumrongsak Kosiyatrakul
Example: Functions of type 𝑎 → 𝑎
Let F𝑎→𝑎 be the set of all functions of type 𝑎 → 𝑎 where 𝑎 can
be any types
Recall the function composition ◦
𝑔 ◦ 𝑓 ∈ F𝑎→𝑎 for every functions 𝑓,𝑔 ∈ F𝑎→𝑎 ◦ is associative:
h◦(𝑔◦𝑓)=(h◦𝑔)◦𝑓 forevery𝑓,𝑔,h∈F𝑎→𝑎 Let id𝑎 : 𝑎 → 𝑎 be the identity function (id𝑎 ∈ F𝑎→𝑎) and
id𝑎◦𝑓=𝑓 and 𝑓◦id𝑎=𝑓 forevery𝑓∈F𝑎→𝑎 (F𝑎→𝑎, ◦, id𝑎) is a monoid
Thumrongsak Kosiyatrakul
Example: Functions of type 𝑎 → 𝑏
LetF𝑎→𝑏 bethesetofallfunctionsoftype𝑎→𝑏where𝑎and𝑏 can be any types
𝑔 ◦ 𝑓 does not work because 𝑓 , 𝑔 ∈ F𝑎→𝑏 are not composable:
Codomain of 𝑓 has type 𝑏 Domain of 𝑔 has type 𝑎
But this does not mean F𝑎→𝑏 cannot be a monoid We just need the following:
Abinaryoperator△suchthatforall 𝑓,𝑔∈F𝑎→𝑏,𝑔△ 𝑓 ∈F𝑎→𝑏 (𝑔△ 𝑓 musthavetype𝑎→𝑏)
△ must be an associative operator
h△(𝑔△𝑓)=(h△𝑔)△𝑓 forall𝑓,𝑔,h∈F𝑎→𝑏 A function id? such that
id?△𝑓=𝑓 and 𝑓△id?=𝑓 forevery𝑓∈F𝑎→𝑏 What △ should be?
Thumrongsak Kosiyatrakul
Example: Functions of type 𝑎 → 𝑏
Since𝑔△ 𝑓 hastype𝑎→𝑏,aninputtothefunction𝑔△ 𝑓 must have type 𝑎
Given an element 𝑥 of type 𝑎 and functions 𝑓 and 𝑔 of type
𝑎 → 𝑏, what can we do with them?
Onewayistoapply 𝑓 and𝑔to𝑥andget 𝑓(𝑥)and𝑔(𝑥)
Now, what can we do with 𝑓 (𝑥) and 𝑔(𝑥) which have type 𝑏? We need an associative binary operator ⋄ of type 𝑏 × 𝑏 → 𝑏
(h△(𝑔△ 𝑓))(𝑥)=h(𝑥)⋄(𝑔△ 𝑓)(𝑥)
= h(𝑥) ⋄ (𝑔(𝑥) ⋄ 𝑓 (𝑥)) = (h(𝑥) ⋄ 𝑔(𝑥)) ⋄ 𝑓 (𝑥)
= (h △ 𝑔)(𝑥) ⋄ 𝑓 (𝑥) =((h△𝑔)△ 𝑓)(𝑥)
If we combine 𝑓 and 𝑔 this way and ⋄ is associative, △ is associative
Thumrongsak Kosiyatrakul
Example: Functions of type 𝑎 → 𝑏
What about the identity function id? of type 𝑎 → 𝑏
We need to make sure that
id?△𝑓=𝑓 and 𝑓△id?=𝑓 forevery𝑓∈F𝑎→𝑏
Let’s trace them:
(id?△𝑓)(𝑥)=id?(𝑥)⋄𝑓(𝑥) shouldbeequalto𝑓(𝑥)
(𝑓 △id?)(𝑥) = 𝑓(𝑥)⋄id?(𝑥) shouldbeequalto 𝑓(𝑥)
We need an element id?(𝑥) of type 𝑏 such that id?(𝑥)⋄ 𝑓(𝑥) = 𝑓(𝑥)⋄id? = 𝑓(𝑥)
What ⋄ and id? (𝑥) should be?
Thumrongsak Kosiyatrakul
Programming Help, Add QQ: 749389476
Example: Functions of type 𝑎 → 𝑏
To guarantee that a type 𝑏 has a associative binary operator ⋄, 𝑏 must be a monoid
Note only that if id?(𝑥) is the identity element of the monoid 𝑏: id?(𝑥)⋄𝑝=𝑝⋄id?(𝑥)=𝑝 forevery𝑝∈𝑏
Given a monoid (𝑏, ·, 𝑒)
(F𝑎→𝑏,λ𝑓 𝑔𝑥.𝑓(𝑥)·𝑔(𝑥),λ𝑥.𝑒)
is a monoid
Thumrongsak Kosiyatrakul
Monoids in Haskell
Recall our monoid (S, ·, 𝑒) Compared to Haskell:
S is a Monoid type in Haskell
· is the binary operator named mappend 𝑒 is the identity element named mempty
In the style of (S, ·, 𝑒), a monoid in Haskell is (a,mappend,mempty) where a is a type that is an instance of the Monoid typeclass
Example: Monoid List in Haskell ([a], ++, [])
ghci> mempty :: [Int]
ghci> mappend [1,2] [3,4] [1,2,3,4]
ghci> mempty :: [Char]
ghci> mappend “Hello” “!!!” “Hello!!!”
Thumrongsak Kosiyatrakul
Monoids in Haskell
As we discussed earlier, there are more than one type of monoids related to integers and boolean values
Haskell defines new types for these monoids in Data.Monoid Here are example of monoids SumZ, ProductZ, All, and Any
ghci> mempty :: Sum Int
Sum {getSum = 0}
ghci> mappend (Sum 5) (Sum 12)
Sum {getSum = 17}
ghci> mempty :: Product Int
Product {getProduct = 1}
ghci> mappend (Product 5) (Product 12) Product {getProduct = 60}
ghci> mempty :: All
All {getAll = True}
ghci> mappend (All True) (All False) All {getAll = False}
ghci> mempty :: Any
Any {getAny = False}
ghci> mappend (Any True) (Any False) Any {getAny = True}
Thumrongsak Kosiyatrakul
Monoid in Programming
Imagine if we want to check whether a character has one of three properties
We need one function for each property:
hasThis :: Char -> Bool
hasThis = …
hasThat :: Char -> Bool
hasThat = …
hasThose :: Char -> Bool
hasThose = …
Now, we can have one function to check all three properties:
check c = hasThis c || hasThat c || hasThose c
If we have another property to check, we can just simply add it into the definition of isTheChar:
check c = hasThis c || hasThat c || hasThose c || hasAnother c
Thumrongsak Kosiyatrakul
Monoid in Programming
Since functions are data in Haskell, we can have a list of functions:
properties = [hasThis, hasThat, hasThose]
Can we combine all functions in properties into one single function?
We cannot use function composition since predicates in our case are not composable:
The codomain of hasThis is Bool The domain of hasThat is Char
But we can create a function that combine them (just for our purpose):
disj :: (Char -> Bool) -> (Char -> Bool) -> (Char Bool)
disj p q = \c -> p c || q c
disj is a binary operator that takes two values of type Char -> Bool and returns a value of type Char -> Bool disj is associative because the disjunction operator (||) is associative
Thumrongsak Kosiyatrakul
Monoid in Programming
Let CB be the set of all functions of type Char -> Bool disj has type CB × CB → CB and it is associative Consider the function \x -> False where x has type Char:
Since \x -> False has type Char -> Bool, \x -> False is a member of CB
It also behaves like an identity respected to disj:
Definition: disj f g = \x -> f x || g x
disj f (\x -> False) = \c -> f c || (\x -> False) c = \c -> f c || False
= \c -> f c =f
disj (\x -> False) f = \c -> (\x -> False) c || f c = \c -> False || f c
= \c -> f c =f
(CB, disj, \x -> False) is a monoid Monads
Thumrongsak Kosiyatrakul
Monoid in Programming
Recall the monoid from the previous slide,
(CB, disj, \x -> False) and the definition of the disj
disj p q = \x -> p x || q x
Recall the monoid Any (Bool, ∨, False) which is equivalent to (Bool,||,False)
Focus on the definition of the function disj:
p and q are functions of type Char to Bool
p x and q x are joined by the binary operator || of the monoid Any
\x -> False is simply False, which is the identity element of the monoid Any
In other words, (CB, disj, \x -> False) is simply
(CB, \x -> mappend (p x) (q x), mempty) where mappend and mempty are binary operator and identity element of the monoid Any, respectively
Thumrongsak Kosiyatrakul
浙大学霸代写 加微信 cstutorcs
Monoid in Programming
In Haskell, a type constructor takes one or more type to construct a new type:
Either String Float
Since Char -> Bool is a type, -> is a type constructor
In Haskell, if type b is a monoid, the functional type a -> b is a monoid where
mempty of type a -> b is the mempty of the type b mappend is defined as
mappend f g = \x -> mappend (f x) (g x)
where the second mappend is the mappend of the type b
mappend of type a -> b is a binary operator that takes two values of type a -> b and returns a value of type a -> b
Definition of the mappend of type a -> b depends on the definition of the mappend of the monoid type b
Thumrongsak Kosiyatrakul
Monoid in Programming
Recall the the function disj combines two functions of type Char -> Bool and returns a function of type Char -> Bool
Bool itself is not a monoid but Any is a monoid (in Data.Monoid)
Note that Any is also a value constructor (function) of type Bool -> Any
ghci> :t Any
Any :: Bool -> Any ghci> :t Any True Any True :: Any
We can compose Any with our Char -> Bool functions:
ghci> :t Any . hasThis
Any . hasThis :: Char -> Any ghci> :t Any . hasThat
Any . hasThat :: Char -> Any ghci> :t Any . hasThose
Any . hasThose :: Char -> Any
Thumrongsak Kosiyatrakul
Monoid in Programming
Since Any is a monoid, we can combine those functions using mappend
ghci> :t mappend (Any . hasThis) (Any . hasThat) mappend (Any . hasThis) (Any . hasThat) :: Char -> Any
But why this is good for us?
The module Data.Foldable has a method named fold:
ghci> :t fold
fold :: (Foldable t, Monoid m) => t m -> m
Since lists is foldable, the fold function folds a list of monoids into one monoid
Thumrongsak Kosiyatrakul
Programming Help
Monoid in Programming
Recall the list of properties that we want to check
properties = [hasThis, hasThat, hasThose] ghci> :t properties
properties :: [Char -> Bool]
We can turn the properties into a list of functions from Char to the monoid Any as shown below:
ghci> :t map (Any .) properties
map (Any .) properties :: [Char -> Any]
Now, we can fold it into a single predicate:
ghci> :t fold $ map (Any .) properties
fold $ map (Any .) properties :: Char -> Any
Since fold $ map … is a common pattern, Haskell provides the function foldMap:
ghci> :t foldMap
foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m
Thumrongsak Kosiyatrakul
Monoid in Programming
Using foldMap:
ghci> :t foldMap (Any .) properties
foldMap (Any .) properties :: Char -> Any
Note that the result is a boolean value wrapped in Any
ghci> Any True
Any getAny = True ghci> Any False Any getAny = False
We can use the getAny function to extract the boolean value inside Any
ghci> getAny (Any True) True
Here is a new definition of the check function: check = getAny . foldMap (Any .) properties
where properties = [hasThis, hasThat, hasThose]
Simply modify properties if we want to add or remove a property
Thumrongsak Kosiyatrakul
Why Monoid are Useful
Build complexity out of simplicity:
Binary operator can be chained indefinitely because of the closure
It takes two elements of type 𝑎 and returns a type 𝑎 Decompose a complex behavior into a sequence of simple behavior and compose them back
We do not need to worry about the order of combining elements because of associativity
Simplicity is the key
Do things sequentially is simply function composition
Thumrongsak Kosiyatrakul