A talk given at the Brisbane Functional Programming Group, on 23 October 2012.
Semigroups and monoids are really simple abstractions, but very common and surprisingly useful. In this talk, we'll explain what they are, and how they're related, with lots of examples. But we want more than just taxonomy from our abstractions, so we'll also show how semigroups and monoids allow us to generalise a range of algorithms. In particular, we'll show to exploit the relationship between semigroups and tree-shaped computations to make an amazingly flexible data structure.
This talk is mostly at an intermediate level, but we'll attempt to explain concepts as we go, and will include an introduction to Haskell type classes. There will hopefully be just enough mind expansion to keep the more advanced folk entertained, too.
The Haskell code shown in this talk is not consistent with the libraries distributed with the Haskell Platform, or available on Hackage. I made a number of changes, including simplifications to improve the flow of the talk, and refinements to better illustrate the monoid and semigroup abstractions and the relationships between them.
The major change was to introduce a separate Semigroup class, and to make the Monoid class a subclass of Semigroup. Changes to other classes and instances generally followed from this change.
The content this talk was largely inspired by, and derived from:
- the standard Monoid and Foldable libraries,
- the amazing FingerTree library, and the paper which describes it,
- a blog post by Heinrich Apfelmus.
There are lots of other libraries on Hackage which make use of monoids, semigroups and foldable structures.