Simple math leads to powerful programming

Michael Arntzenius

http://www.rntz.net

What's a monoid, anyway?

  • A binary operator

  • that's associative

  • with an identity element.

Binary operator?

a · b

  • Integer addition, +

  • Set union, ∪

  • String concatenation, ⧺

  • Integer maximum

  • Division, /

Associative?

(a · b) · c = a · (b · c)

  • Integer addition, +

  • Set union, ∪

  • String concatenation, ⧺

  • Integer maximum

  • Division, /  (a/b)/c ≠ a/(b/c)

Identity element?

a · id = id · a = a

  • Integer addition, +, with 0

  • Set union, ∪, with {}

  • String concatenation, ⧺, with ""

  • Integer maximum   no least integer

  • Division, /  (a/b)/c ≠ a/(b/c)

Monoids:

Associative binary operators with identity.

More monoids

  • Matrix multiplication

  • Merging sorted lists (merge step in mergesort!)

  • Unix commands under |, with cat

  • Composing functions of type (A → A), with (λx.x)

  • Regular expressions under choice ("|" in (a|b))

  • CFGs under choice ("|" in A ::= B | C)

What are they good for?

  1. Functions for free

  2. Parallelization / MapReduce

  3. Starting point for exploring algebra

Functions for free

Write this: 

instance Monoid String where
    mappend = (++)       -- ++ is the operator
    mempty = ""          -- "" is the identity
Get this for free! 

mconcat ["monoids", " are ", "great"]
-- Evaluates to "monoids are great"

mconcat
can be parallelized

  • Split the list in half;

  • send each half to a different processor;

  • recurse!

  • Once both halves return, mappend their results together.

MapReduce

The reduce step is a distributed, parallel mconcat

Monoids:

  • Associative binary operators with identity

  • Turn up everywhere

  • Make the "reduce" in map-reduce go

Semilattices

What's a semilattice, anyway?

  • A binary operator

  • that's associative

  • and commutative

  • and idempotent

  • with an identity element.

What's a semilattice, anyway?

  • A monoid

  • that's commutative

  • and idempotent.

Some monoids

  • Integer addition, +, with 0

  • Set union, ∪, with {}

  • String concatenation, ⧺, with ""

  • Integer maximum   no least integer

  • Division, /  (a/b)/c ≠ a/(b/c)

Commutative?

a · b = b · a

  • Integer addition, +, with 0

  • Set union, ∪, with {}

  • String concatenation, ⧺, with ""

  • Integer maximum   no least integer

  • Division, /  (a/b)/c ≠ a/(b/c)

Idempotent?

a · a = a

  • Integer addition, +, with 0   1 + 1 = 2

  • Set union, ∪, with {}

  • String concatenation, ⧺, with ""

  • Integer maximum   no least integer

  • Division, /  (a/b)/c ≠ a/(b/c)

More semilattices

  • Natural numbers under maximum

  • Booleans under logical "or"

  • N-bit integers under bitwise "or"

  • Bloom filters under union

What are they good for?

  1. Functions for free

  2. Distributed programming
    (where they are called CvRDTs)

CvRDT?

Convergent replicated datatype

Used to implement eventually-consistent systems

Core idea: Allow changes in any order, possibly multiple times, yet guarantee the same result

That's all folks