10 Monoids

 

This chapter covers

  • Using purely algebraic structures
  • Understanding monoids and fold operations
  • Using balanced folds to perform parallel computations in chunks
  • Higher-kinded types and foldable data structures
  • Composing monoids to perform complex calculations

By the end of part 2, we were getting comfortable considering data types in terms of their algebras. In particular, we were concerned with the operations they support and the laws that govern those operations. By now, you will have noticed that the algebras of very different data types tend to share specific patterns in common. In this chapter, we begin identifying these patterns and taking advantage of them.

This chapter is our first introduction to purely algebraic structures. As an example, we’ll begin by considering a simple structure known as the monoid, which is defined only by its algebra. The name monoid might sound intimidating at first, but it is merely a mathematical term that in category theory refers to a category with one object. Besides 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.

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.6.1 Assembling more complex monoids

10.6.2 Using composed monoids to fuse traversals

Summary