Chapter 10. Monoids

 

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. Other than 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.

1 The name monoid comes from mathematics. In category theory, it means a category with one object. This mathematical connection isn’t important for our purposes in this chapter, but see the chapter notes for more information.

10.1. What is a monoid?

10.2. Folding lists with monoids

10.3. Associativity and parallelism

10.4. Example: Parallel parsing

10.5. Foldable data structures

10.6. Composing monoids

10.7. Summary

sitemap