In the previous chapter, we introduced a simple algebraic structure: the monoid. This was our first instance of a completely abstract, purely algebraic interface, and it led us to think about interfaces in a new way. A useful interface may be defined only by a collection of operations related by laws.
In this chapter, we’ll continue this mode of thinking and apply it to the problem of factoring out code duplication across some of the libraries we wrote in parts 1 and 2. We’ll discover two new abstract interfaces─Functor and Monad─and get more general experience with spotting these sorts of abstract structures in our code.1
In parts 1 and 2, we implemented several different combinator libraries. In each case, we proceeded by writing a small set of primitives and then a number of combinators defined purely in terms of those primitives, and we noted some similarities between derived combinators across the libraries we wrote. For instance, we implemented a map function for each data type to lift a function taking one argument into the context of some data type. For Gen, Parser, and Option, the type signatures were as follows:
extension [A](ga: Gen[A]) def map[B](f: A => B): Gen[B] extension [A](pa: Parser[A]) def map[B](f: A => B): Parser[B] extension [A](oa: Option[A]) def map[B](f: A => B): Option[B]