Free Monoids: Monoids for Anything!

Monoid

trait Semigroup[A] {
  def combine(l: A, r: A): A
}

trait Monoid[A] extends Semigroup[A] {
  def empty: A
}

Int

implicit val intMonoid: Monoid[Int] =
  new Monoid[Int] {
    def combine(l: Int, r: Int): Int =
      l + r

    def empty: Int =
      0
  }

1 |+| 2 |+| 3
// res0: Int = 6

String

implicit val stringMonoid: Monoid[String] =
  new Monoid[String] {
    def combine(l: String, r: String): String =
      l + r

    def empty: String =
      ""
  }

"a" |+| "b" |+| "c"
// res1: String = "abc"

List

implicit def listMonoid[A]: Monoid[List[A]] =
  new Monoid[List[A]] {
    def combine(l: List[A], r: List[A]): List[A] =
      l ++ r

    def empty: List[A] =
      List.empty
  }

List("a") |+| List("b") |+| List("c", "d")
// res2: List[String] = List("a", "b", "c", "d")

A?

def monoid[A]: Monoid[A] =
  new Monoid[A] {
    def combine(l: A, r: A): A =
      ???

    def empty: A =
      ???
  }

A hint

What do you get when you combine an A with an A?

Another hint

“The Trick”

“The Trick”

“The Trick”

“The Trick”

object FreeMonoid {
  def in[A]: A => List[A] =
    a => List(a)

  def out[A, B](
      f: A => B
  )(implicit M: Monoid[B]): List[A] => B =
    _.foldLeft(M.empty)((b, a) => M.combine(b, f(a)))
}

Free All the Structures!

Free Boolean Algebra

Free Functor

Free Monad

Summary

• Free structures let you add structure to any type.
• The trick is to delay the operations of a structure, converting them to data.
• They are implemented as reified typeclasses, plus an injector (in).
• You can always go in, but you can’t always go out.

Thank you!

Adam Rosien @arosien

Inner Product LLC inner-product.com

Hire us to ☝︎
teach / mentor / join
your team!

References and Links: