When Less is More and More is Less - Trade-Offs in Algebra

Explore the algebraic structures of semigroups and semilattices in functional programming during this 21-minute conference talk from YOW! 2016. Delve into how these mathematical concepts, related to monoids, can be applied by programmers. Learn about their uses, familiar concretions, and the trade-offs involved in choosing the right algebraic structure for specific programming tasks. Examine examples using Haskell, including numbers under addition, functions, and foldable structures like lists and Maybe types. Discover the importance of laws in these structures and how they relate to real-world applications such as CRDTs (Conflict-free Replicated Data Types). Gain insights into promoting semigroups, understanding idempotence, and working with bounded join-semilattices, using practical examples like set union laws.

Intro
Monoid typeclass
Example: Numbers under addition
Example: Functions
Foldable example: List
Foldable example: Maybe
Laws are important
Example: NonEmpty Lists
Example: Positive Integers
Introducing Semigroup
Semigroup instances
Every Monoid is a Semigroup
Why not Foldable?
Some Foldables...
Promoting Semigroups
Example: Maximum
What can we do with a semilattice?
Laws = power
Idempotence
CRDTs
Bounded Join-semilattice
Example: Set union laws
Wrapping up