FizzBuzz fun: Exploring Functional Programming Design Patterns : Monoids

In this post, we will continue from where we left off in a previous article in this series, "FizzBuzz Fun in Scala: Combining Functions," and explore where further abstraction leads us in terms of functional programming design patterns. Our goal is to show that, despite their intimidating name, Monoids are a logical, reusable design pattern that emerges when reducing list-like structures to a single value—a task quite common in everyday development. As for Scala 3, we will also utilize contextual abstractions instead of Scala 2 implicits, to combine more complex structures from smaller ones.

Combining values using a single abstraction

Below is the code we will start with. If you would like to understand this code better please see the FizzBuzz fun in Scala: Combining functions post.

// Commenting the Scala 3 version / Scala CLI directive
//> using scala 3.3.1

def combine[A](
    f1: A => Option[String],
    f2: A => Option[String]
): A => Option[String] =
  a =>
    (f1(a), f2(a)) match
      case (Some(s1), Some(s2)) => Some(s1 + s2)
      case (None, Some(s2))     => Some(s2)
      case (Some(s1), None)     => Some(s1)
      case (None, None)         => None

val fizzbuzzAt: Int => String =
  extension (word: String)
    def every(n: Int): Int => Option[String] = i =>
      if i % n == 0 then Some(word) else None

  val wordShouts = List(
    "Fizz".every(3),
    "Buzz".every(5)
  )
  val combined = wordShouts.fold(_ => None)(combine)
  val fizzbuzz: Int => String = i =>
    combined(i).getOrElse(i.toString)
  fizzbuzz
end fizzbuzzAt

def fizzbuzz(n: Int): List[String] =
  LazyList
    .from(1)
    .map(fizzbuzzAt)
    .take(n)
    .toList
end fizzbuzz

@main def fizzbuzz(): Unit =
  fizzbuzz(20).foreach(fb => print(fb + ","))
end fizzbuzz

💡

Code can be run using Scala CLI. Save a copy of a complete example in e.g. FizzBuzz.scala and run it like: scala-cli run FizzBuzz.scala. In this article, a complete runnable example can be recognised by a //> using scala 3.3.1 directive near the top of the file.

We will begin by zooming in on how we 'combined' multiple functions with the type signature Int => Option[String] into a single one:

def combine[A](
    f1: A => Option[String],
    f2: A => Option[String]
): A => Option[String] =
  a =>
    (f1(a), f2(a)) match
      case (Some(s1), Some(s2)) => Some(s1 + s2)
      case (None, Some(s2))     => Some(s2)
      case (Some(s1), None)     => Some(s1)
      case (None, None)         => None

which is used as:

val combined = wordShouts.fold(_ => None)(combine)

In the `fold` we seem to have two related functions so let's define them together:

trait Combiner[B]:
  def zero: B
  def combine(b1: B, b2: B): B

The zero function enables us to define an element that 'does not count' when combining elements. The combine function allows us to merge elements of the same type into another element of the same type. For example, consider integers: we could combine them using addition, in which case the zero element would be 0; alternatively, we could combine them using multiplication, in which case the zero element would be 1.

Looking at the type signature of combine:

def combine[A](
    f1: A => Option[String],
    f2: A => Option[String]
): A => Option[String]

We can see that B in Combiner[B] in this case would be of type A => Option[String], so the instance for our type of Combiner would look like this:

new Combiner[A => Option[String]]:
  override def zero: A => Option[String] = ???
  override def combine(
        a1: A => Option[String],
        a2: A => Option[String]
    ): A => Option[String] = ???
end Combiner

Declaring the instance in an object (later we will group more Combiner instances together) we get:

object Combiner:
  def myCombiner[A] = new Combiner[A => Option[String]]:
    override def zero: A => Option[String] = ???
    override def combine(
        a1: A => Option[String],
        a2: A => Option[String]
    ): A => Option[String] = ???
end Combiner

To implement zero we can have a look at the fold usage above. For the combine method we can have a look at our original combine function:

object Combiner:
  def myCombiner[A] = new Combiner[A => Option[String]]:
    override def zero: A => Option[String] =
      _ => None
    override def combine(
        a1: A => Option[String],
        a2: A => Option[String]
    ): A => Option[String] =
      a =>
        (a1(a), a2(a)) match
          case (Some(s1), Some(s2)) => Some(s1 + s2)
          case (None, Some(s2)) => Some(s2)
          case (Some(s1), None) => Some(s1)
          case (None, None) => None
end Combiner

This Combiner we can then use to implement our original combine function:

import Combiner.*
def combine[A](
    f1: A => Option[String],
    f2: A => Option[String]
): A => Option[String] =
  myCombiner.combine(f1, f2)

At this point, our solution works again and we can remove our combine function entirely. Our `fold` then becomes:

  val combined =
    wordShouts.fold(_ => None)(myCombiner.combine)

Or:

  val combined =
    wordShouts.fold(myCombiner.zero)(myCombiner.combine)

Since the Combiner type has all the behaviour required for fold ideally we would write:

val combined = wordShouts.fold(myCombiner)

Which we can do using an extension method:

extension[A] (as: List[A])
  def foldWith(c: Combiner[A]): A =
    as.fold(c.zero)(c.combine)

val combined = wordShouts.foldWith(myCombiner)

Note: using fold as a name for the extension method sadly does not seem to work so I renamed it to foldWith. I did delve deeper into this on why this is.

Combine all the things!

At this point, you might be wondering, "Why go through all this trouble?". The answer lies in the fact that the two functions we defined in Combiner are precisely the arguments we provide to a fold. A fold represents the operation of combining elements within a collection while accounting for cases where the collection has no elements. This is something we do frequently. In functional programming, this type is commonly referred to by its mathematical name: a monoid.

If we rename our definition of Combiner to Monoid, then this is precisely how a Monoid is defined:

trait Monoid[A]:
  def zero: A
  def combine(b1: A, b2: A): A

Let's stick with Combiner for now and I'll revisit monoids further down in this post.

Let's have a closer look at our current instance of Combiner:

  def myCombiner[A] = new Combiner[A => Option[String]]:
    override def zero: A => Option[String] =
      _ => None
    override def combine(
        a1: A => Option[String],
        a2: A => Option[String]
    ): A => Option[String] =
      a =>
        (a1(a), a2(a)) match
          case (Some(s1), Some(s2)) => Some(s1 + s2)
          case (None, Some(s2))     => Some(s2)
          case (Some(s1), None)     => Some(s1)
          case (None, None)         => None

The code accomplishes several tasks:

1. The pattern matching on the Option type essentially combines Options, which is not directly related to combining functions.

2. The addition of Strings, s1 + s2, can also be regarded as 'combining'.

3. The Combiner is generic in its argument, but its return type is specific to Option[String].

Currently, our Combiner instance appears to be combining functions, Options, and Strings simultaneously. Let's attempt to separate each of these into its own Combiner:

  def stringCombiner = new Combiner[String]:
    override def zero: String = ???
    override def combine(a1: String, a2: String): String = ???

  def optionCombiner[A] = new Combiner[Option[A]]:
    override def zero: Option[A] = ???
    override def combine(a1: Option[A], a2: Option[A]): Option[A] = ???

  def functionCombiner[A, B] = new Combiner[A => B]:
    override def zero: A => B = ???
    override def combine(f1: A => B, f2: A => B): A => B = ???

Since we started with combining functions, let's start with functionCombiner:

def functionCombiner[A, B] =
  new Combiner[A => B]:
    override def zero: A => B = a => ???
    override def combine(f1: A => B, f2: A => B): A => B =
      a =>
        val b1 = f1(a)
        val b2 = f2(a)
        ??? // combine b1 and b2

We need a way to combine Bs, otherwise we cannot possibly continu. Do we have a way of combining Bs? Certainly, if pass one:

def functionCombiner[A, B](bc: Combiner[B]) =
  new Combiner[A => B]:
    override def zero: A => B = a => bc.zero
    override def combine(f1: A => B, f2: A => B): A => B =
      a =>
        val b1 = f1(a)
        val b2 = f2(a)
        bc.combine(b1, b2)
    end combine
end functionCombiner

In our myCombiner B is an Option[String]:

def myCombiner[A] = new Combiner[A => Option[String]]: ...

To implement our combiner, we need a way of combining Options. Let's start with Option[String] first:

  def optionStringCombiner = new Combiner[Option[String]]:
    override def zero: Option[String] = None
    override def combine(
        a1: Option[String],
        a2: Option[String]
    ): Option[String] =
      (a1, a2) match
        case (Some(s1), Some(s2)) => Some(s1 + s2)
        case (None, Some(s2))     => Some(s2)
        case (Some(s1), None)     => Some(s1)
        case (None, None)         => None

Here, similar to what we did for the functionCombiner, we can generalize by passing a Combiner for a generic parameter:

def optionCombiner[A](ac: Combiner[A]) =
  new Combiner[Option[A]]:
    override def zero: Option[A] = None
    override def combine(
        maybeA1: Option[A],
        maybeA2: Option[A]
    ): Option[A] =
      (maybeA1, maybeA2) match
        case (Some(a1), Some(a2)) => Some(ac.combine(a1, a2))
        case (None, Some(a2))     => Some(a2)
        case (Some(a1), None)     => Some(a1)
        case (None, None)         => None

The final piece of the puzzle involves combining strings. The stringCombiner is easy compared to the other combiners we have already implemented:

  def stringCombiner = new Combiner[String]:
    override def zero: String = ""
    override def combine(a1: String, a2: String): String = a1 + a2

If we now define the optionsStringCombiner in terms of the optionCombiner and stringCombiner we get:

def optionStringCombiner = optionCombiner(stringCombiner)

Our original myCombiner, of type Combiner[A => Option[String]] becomes:

def myCombiner[A] =
  functionCombiner[A, Option[String]](
    optionCombiner(
      stringCombiner
    )
  )

To recap what we have done:

We defined a trait called Combiner to combine elements.
We created an instance of this class that enables us to combine 'word shouts'. We modelled shouting words as functions: Int => Option[String], meaning that given a number, we may or may not shout a word.
We defined this instance using three more atomic instances: one that knows how to combine Strings, one that knows how to combine Options, and one that knows how to combine functions.
We also defined an extension method for the List class that takes this Combiner instance and performs the actual combining.

All together:

// Commenting the Scala 3 version / Scala CLI directive
//> using scala 3.3.1

trait Combiner[A]:
  def zero: A
  def combine(a1: A, a2: A): A

object Combiner:
  def myCombiner[A] =
    functionCombiner[A, Option[String]](
      optionCombiner(
        stringCombiner
      )
    )

  def stringCombiner = new Combiner[String]:
    override def zero: String = ""
    override def combine(a1: String, a2: String): String =
      a1 + a2

  def optionCombiner[A](ac: Combiner[A]) =
    new Combiner[Option[A]]:
      override def zero: Option[A] = None
      override def combine(
          maybeA1: Option[A],
          maybeA2: Option[A]
      ): Option[A] =
        (maybeA1, maybeA2) match
          case (Some(a1), Some(a2)) =>
            Some(ac.combine(a1, a2))
          case (None, Some(a2)) => Some(a2)
          case (Some(a1), None) => Some(a1)
          case (None, None)     => None

  def functionCombiner[A, B](bc: Combiner[B]) =
    new Combiner[A => B]:
      override def zero: A => B = a => bc.zero
      override def combine(f1: A => B, f2: A => B): A => B =
        a =>
          val b1 = f1(a)
          val b2 = f2(a)
          bc.combine(b1, b2)
      end combine
  end functionCombiner

end Combiner

import Combiner.*

val fizzbuzzAt: Int => String =
  extension (word: String)
    def every(n: Int): Int => Option[String] = i =>
      if i % n == 0 then Some(word) else None

  extension [A](as: List[A])
    def foldWith(c: Combiner[A]): A =
      as.fold(c.zero)(c.combine)

  val wordShouts = List(
    "Fizz".every(3),
    "Buzz".every(5)
  )
  val combined = wordShouts.foldWith(myCombiner)
  val fizzbuzz: Int => String = i =>
    combined(i).getOrElse(i.toString)
  fizzbuzz
end fizzbuzzAt

def fizzbuzz(n: Int): List[String] =
  LazyList
    .from(1)
    .map(fizzbuzzAt)
    .take(n)
    .toList
end fizzbuzz

@main def fizzbuzz(): Unit =
  fizzbuzz(20).foreach(fb => print(fb + ","))
end fizzbuzz

Contextual abstraction using given instances and using clauses

Scala 2's implicits enabled removing all the explicit wiring of our Combiners. In Scala 3 this is now done using given instances and using clauses. All our Combiner instances can be declared with the given keyword, and wherever we need an instance of Combiner to be available we use the using keyword.

Here is the complete implementation; afterwards, I will highlight the most important parts.

// Commenting the Scala 3 version / Scala CLI directive
//> using scala 3.3.1

trait Combiner[A]:
  def zero: A
  def combine(a1: A, a2: A): A

object Combiner:

  given stringCombiner: Combiner[String] with
    override def zero: String = ""
    override def combine(a1: String, a2: String): String =
      a1 + a2

  given optionCombiner[A](using ac: Combiner[A]): Combiner[Option[A]] with
      override def zero: Option[A] = None
      override def combine(
          maybeA1: Option[A],
          maybeA2: Option[A]
      ): Option[A] =
        (maybeA1, maybeA2) match
          case (Some(a1), Some(a2)) =>
            Some(ac.combine(a1, a2))
          case (None, Some(a2)) => Some(a2)
          case (Some(a1), None) => Some(a1)
          case (None, None)     => None

  given functionCombiner[A, B] (using
                                cb: Combiner[B]
                               ): Combiner[A => B] with
      override def zero: A => B = a => cb.zero
      override def combine(f1: A => B, f2: A => B): A => B =
        a =>
          val b1 = f1(a)
          val b2 = f2(a)
          cb.combine(b1, b2)
      end combine
  end functionCombiner
end Combiner

import Combiner.given

val fizzbuzzAt: Int => String =
  extension (word: String)
    def every(n: Int): Int => Option[String] = i =>
      if i % n == 0 then Some(word) else None

  extension [A](as: List[A])
    def foldWith(using c: Combiner[A]): A =
      as.fold(c.zero)(c.combine)

  val wordShouts = List(
    "Fizz".every(3),
    "Buzz".every(5)
  )
  val combined = wordShouts.foldWith
  val fizzbuzz: Int => String = i =>
    combined(i).getOrElse(i.toString)
  fizzbuzz
end fizzbuzzAt

def fizzbuzz(n: Int): List[String] =
  LazyList
    .from(1)
    .map(fizzbuzzAt)
    .take(n)
    .toList
end fizzbuzz

@main def fizzbuzz(): Unit =
  fizzbuzz(20).foreach(fb => print(fb + ","))
end fizzbuzz

Highlights:

The Combiner object contains all given instances of Combiner :


object Combiner:
  given stringCombiner: Combiner[String] with
  ...
  given optionCombiner[A](using ac: Combiner[A]): Combiner[Option[A]] with
  ...
  given functionCombiner[A, B] (using cb: Combiner[B]): Combiner[A => B] with
  ...
end Combiner

given instances must be explicitly imported ('import Combiner.*' does not import them!):

import Combiner.given

All elements can be folded into a single element, if a Combiner instance for A is given:

extension [A](as: List[A])
  def foldWith(using c: Combiner[A]): A =
    as.fold(c.zero)(c.combine)

This fold needs a Combiner for Int => Option[String]:
- functionCombiner's type matches but needs a Combiner for Option[String]
- optionCombiner's type matches but needs a Combiner for String
- stringCombiner's type matches and does not need anything more

As such a 'complete' function combiner instance is given and will be used to fold all shouts into a single function:

val combined = wordShouts.foldWith

Reuse with cats

in Scala 3 type classes are traits with one or more parameters whose implementations are provided as giveninstances. So Combiner is now a type class. As I mentioned earlier, the Combiner type class is known in category theory as a Monoid (which does come with some 'laws' which allow these structures to be well suited for parallelization but this is out of the scope of this article and for details I'll refer to the references at the end):

trait Monoid[A]:
  def zero: A
  def combine(b1: A, b2: A): A

The cats library also defines this type class.

Let's now try to reuse the Monoid type class from cats.

Note the changes below:

The cats lib dependency is declared and can be used: //> using lib org.typelevel::cats-core:2.10.0
The cats Monoid type class is now used instead of Combiner
The zero function is renamed to empty to match cats' names.
The Combiner object is renamed to CombinerInstances
The foldWith extension method is replaced with the Monoid.combineAll method on (a superclass of) List so. This method looks for a monoid that can combine the elements in the list of type List[Int => Option[String]]. This line is where most of the 'action' happens.

// Commenting the Scala 3 version / Scala CLI directive
//> using scala 3.3.1
//> using lib org.typelevel::cats-core:2.10.0
import cats.Monoid

object CombinerInstances:

  given stringCombiner: Monoid[String] with
    override def empty: String = ""
    override def combine(a1: String, a2: String): String =
      a1 + a2

  given optionCombiner[A](using ac: Monoid[A]): Monoid[Option[A]] with
      override def empty: Option[A] = None
      override def combine(
          maybeA1: Option[A],
          maybeA2: Option[A]
      ): Option[A] =
        (maybeA1, maybeA2) match
          case (Some(a1), Some(a2)) =>
            Some(ac.combine(a1, a2))
          case (None, Some(a2)) => Some(a2)
          case (Some(a1), None) => Some(a1)
          case (None, None)     => None

  given functionCombiner[A, B] (using
                                cb: Monoid[B]
                               ): Monoid[A => B] with
      override def empty: A => B = _ => cb.empty
      override def combine(f1: A => B, f2: A => B): A => B =
        a =>
          val b1 = f1(a)
          val b2 = f2(a)
          cb.combine(b1, b2)
      end combine
  end functionCombiner

end CombinerInstances

import CombinerInstances.given

val fizzbuzzAt: Int => String =
  extension (word: String)
    def every(n: Int): Int => Option[String] = i =>
      if i % n == 0 then Some(word) else None

  val wordShouts = List(
    "Fizz".every(3),
    "Buzz".every(5)
  )
  val combined = Monoid.combineAll(wordShouts)
  val fizzbuzz: Int => String = i =>
    combined(i).getOrElse(i.toString)
  fizzbuzz
end fizzbuzzAt

def fizzbuzz(n: Int): List[String] =
  LazyList
    .from(1)
    .map(fizzbuzzAt)
    .take(n)
    .toList
end fizzbuzz

@main def fizzbuzz(): Unit =
  fizzbuzz(20).foreach(fb => print(fb + ","))
end fizzbuzz

It turns out that the instances we defined ourselves are quite common, and cats also provides these monoid instances. For example, the monoid instance we defined for String can be imported using:

import cats.instances.string.given

Once this is done we do not need our instance in MonoidInstances anymore. The same can be done for the Option and function instances. So in the end we can delete all of our custom instances including the CombinerInstances object because it has become empty:

// Commenting the Scala 3 version / Scala CLI directive
//> using scala 3.3.1
//> using lib org.typelevel::cats-core:2.10.0
import cats.Monoid

import cats.instances.string.given
import cats.instances.option.given
import cats.instances.function.given

val fizzbuzzAt: Int => String =
  extension (word: String)
    def every(n: Int): Int => Option[String] = i =>
      if i % n == 0 then Some(word) else None

  val wordShouts = List(
    "Fizz".every(3),
    "Buzz".every(5)
  )
  val combined = Monoid.combineAll(wordShouts)
  val fizzbuzz: Int => String = i =>
    combined(i).getOrElse(i.toString)
  fizzbuzz
end fizzbuzzAt

def fizzbuzz(n: Int): List[String] =
  LazyList
    .from(1)
    .map(fizzbuzzAt)
    .take(n)
    .toList
end fizzbuzz

@main def fizzbuzz(): Unit =
  fizzbuzz(20).foreach(fb => print(fb + ","))
end fizzbuzz

This is the final version of Fizzbuzz in this article. As a side bar, note how we ended with 10 lines less than what we started with when rolling our own monoids manually.

Conclusion

In conclusion, this article demonstrates how monoids emerge as a reusable design pattern when reducing list-like structures to a single value. By building upon the FizzBuzz example, we explored the process of defining and assembling reusable monoid instances, and eventually transitioned to using the Cats library for simplification and reuse.

Finally, here are some references if you would like to delve deeper into Monoids or functional programming in Scala:

The Scala red book (note there is also a second edition for Scala 3)
FP Tower has a very elegant and natural way of introducing Monoids in its course materials. As far as courses go this is one of the most engaging courses I ever took online. (Not free. Scala 2 at the time of writing.)
Monoid documentation of the cats library
Another explanation of what a Monoid is using FizzBuzz on reddit