10 Monoids

 

This chapter covers

  • Introducing purely algebraic structures
  • Discussing monoids
  • Introducing typeclasses

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.

10.1 What is a monoid?

10.2 Folding lists with monoids

10.3 Associativity and parallelism

10.4 Example: Parallel parsing

10.5 Typeclasses

10.6 Foldable data structures

10.7 Composing monoids

10.7.1 Assembling more complex monoids

10.7.2 Using composed monoids to fuse traversals

10.8 Conclusion

Summary

10.9 Exercise answers