Monoids

for

Programmers

(Scala flavor)

Vlad Patryshev, 2013

See common pattern?

• 2+3==5; 0+n==n+0==n
• 6*7==42; 1*n==n*1==n
• max(10, 100) == 100; max(Int.MinValue, x) == x
• "ab"+"cd"=="abcd"; ""+"ef"=="ef"; "gh"+""=="gh"
• List(1,2)+List(3,4)==List(1,2,3,4); Nil+List(5,6)==List(5,6); List(7,8)++Nil==List(7,8)
• Set(1,2,3)+Set(2,4)==Set(1,2,3,4); Set.Empty+Set(5,6)==Set(5,6)

You see Monoids!

• 2+3==5; 0+n==n+0==n
• 6*7==42; 1*n==n*1==n
• max(10, 100) == 100; max(Int.MinValue, x) == x
• "ab"+"cd"=="abcd"; ""+"ef"=="ef"; "gh"+""=="gh"
• List(1,2)+List(3,4)==List(1,2,3,4); Nil+List(5,6)==List(5,6); List(7,8)++Nil==List(7,8)
• Set(1,2,3)+Set(2,4)==Set(1,2,3,4); Set.Empty+Set(5,6)==Set(5,6)

Monoid Rules

1) a Op b = c

2) Zero Op a = a Op Zero = a

signatures:

Op: (T, T) => T

Zero: () => T // or rather just T

​

but wait, there's more!

Monoid Rules - associativity

(a Op b) Op c == a Op (b Op c)

Not everything is associative

5-(3-2) != (5-3)-2

avg(10, avg(30, 50)) != avg(avg(10, 30), 50)

Magma - like monoid, but no associativity and no unit

• Tuples: (a, (b, c)) is not the same as ((a,b), c)
• Binary trees:

​

Monoid Rules - associativity

(a1 Op (a2 Op (a3 Op (a4...))))

aka fold

(Zero /: a) (x Op y)

Can regroup and run in parallel: thanks to associativity!

​

This is what empowers Map/Reduce

Mappings between Monoids

f: A → B

f(Zero_A) = Zero_B

f(x Op_A y) = f(x) Op_B f(y)

​

e.g.

• log(1)=0; log(a*b)=log(a)+log(b)
• twice(n)=2*n; twice(0)=0, twice(n+m)=twice(n)+twice(m)
• length("")=0; length(s1+s2)=length(s1)+length(s2)
• sum(Nil)=0; sum(list1+list2)=sum(list1)+sum(list2)
• prod(Nil)=1; prod(list1+list2)=prod(list1)*prod(list2)
• maxOf(Nil)=Int.MinValue; maxOf(list1+list2)=max(maxOf(list1)),maxOf(list2))

​

Free Monoid

​

take any function, f: A → B

​

this is equivalent to specifying...

f': List[A] → B

where

f'(Nil) = Zero_B

f'(list1 + list2) = f'(list1) Op_B f'(list2)

​

List[A] is a Free Monoid on A

any type

a monoid

Free Monoid - example

Suppose we have...

​

object WeekDay extends Enumeration {� val Mon, Tue, Wed, Thu, Fri, Sat, Sun = Value�}

and a function

WeekDay=>Int = (Mon->1, Tue->1, Wed->1, Thu->1, Fri->1, Sat->0, Sun->0)

If we have a monoid (Int, 0, +), we can automatically extend this mapping to List[WeekDay]->Int

which counts the number of working days.

​

Reduce

reduce: List[A] → A

with properties:

• reduce(Nil) = Zero_A
• reduce(list1+list2) = reduce(list1) Op_A reduce(list2)

​

(This defines an algebra over the functor List[_].)

​

This is exactly what we did on the previous page, reduce.

That's almost it

Monoids are simple, are not they?

​

Let's throw in more properties...

​

Commutative Monoids

a Op b == b Op a

​

e.g.

• 2+3==3+2
• max(2.72, 3.14) == max(3.14, 2.72)

​

but not these:

• "hello" + "world" != "world" + "hello"
• List(1,2,3)+List(4,5,6) != List(4,5,6)+List(1,2,3)

Commutative Monoids

How can we create one?

​

e.g.

​

"abracadabra" -> "aaaaabbcdrr"

​

Order does not matter; numbers matter.

​

Free commutative monoid on A: a collection of possibly duplicates, order does not matter.

​

It is called Bag[A]

Commutative Monoids

Bag[A]

​

{

"partridges in a pear tree": 1,

"turtle doves": 2,

"french hens": 3,

"calling birds": 4,

"golden rings": 5

//etc

}

​

Commutative Monoids

How about sets?!

​

​

Commutative Monoids...

How about sets?!

​

x Op x == x : x is idempotent

​

Set('a','b','c') + Set('b','c','d') = Set('a','b','c','d')

Commutative Monoids...

How about sets?!

​

x Op x == x : x is idempotent

​

Set('a','b','c') + Set('b','c','d') = Set('a','b','c','d')

​

Finite set is a free commutative monoid where all elements are idempotent (thank you, Shachaf, for the hint)

​

another example

• max(x, x) = x
• min(x, x) = x

The Whole Picture

Bigger Picture

(source: Alexander Bunkenburg, "The Boom Hierarchy")

​

Questions... really?

Thank you!

(and thanks to my friends on livejournal for their critique)

http://vpatryshev.blogspot.com/2009/06/why-monoids.html (this is Java)

http://blog.safaribooksonline.com/2013/05/15/monoids-for-programmers-a-scala-example/

​