By the end of part 2, we were getting comfortable with considering data types in terms of their algebras─that is, the operations they support and the laws that govern those operations. Hopefully, you will have noticed that the algebras of very different data types tend to share certain patterns in common. In this chapter, we’ll begin identifying these patterns and taking advantage of them.
This chapter will be our first introduction to purely algebraic structures. We’ll consider a simple structure, the monoid,1 which is defined only by its algebra. Aside from satisfying the same laws, instances of the monoid interface may have little or nothing to do with one another. Nonetheless, we’ll see how this algebraic structure is often all we need to write useful, polymorphic functions.
We choose to start with monoids because they’re simple, ubiquitous, and useful. Monoids come up all the time in everyday programming, whether we’re aware of them or not. Working with lists, concatenating strings, and accumulating the results of a loop are often phrased in terms of monoids. We’ll see how monoids are useful in two ways: they facilitate parallel computation by giving us the freedom to break our problem into chunks that can be computed in parallel, and they can be composed to assemble complex calculations from simpler pieces.