The Monoiad

an epic journey through monoids

mono+oid means one … oid?

TODO:

compile this
show large graph of algebraic structures, then zoom in to monoid
monoid is kind of the powerhouse – massive strength to weight ratio, very common, not too complex, but has enough laws to be interesting.
add diagrams showing relations like Rig, Duoid, and larger groups of relations
add slides for subcategories? (can always skip over them for time)
split up language extensions through the talk?
flesh out speaker notes with transcription

preface

Greg Pfeil

Ross Baker (@rossabaker) – speaking at 16:20!
Kris Nuttycombe (@nuttycom)
Paul Snively (@paul_snively)

Hiring Scala & Haskell devs (and many other roles) – if you find anything in this talk intriguing, you should talk to me about applying. Don’t let this talk dissuade you at all, though – understanding this is by no means a prerequisite for any position we have. (But my co-workers have certainly helped me work through some of these ideas).

resources

this talk – https://github.com/sellout/category-parametric-talk/monoiad/
Cheshire – https://github.com/sellout/cheshire
Caterwaul – https://github.com/sellout/caterwaul

boilerplate

inThisBuild(Seq(
  scalaOrganization := "org.typelevel",
  scalaVersion := "2.12.4-bin-typelevel-4",
  scalacOptions := Seq(
    "-language:higherKinds"),
  libraryDependencies := Seq(
    "org.typelevel" %% "cats-core" % "1.3.1",
    "org.typelevel" %% "spire"     % "0.16.0")))
addCompilerPlugin(
  "org.spire-math" %% "kind-projector" % "0.9.8")

import cats.{Functor, Id}
import cats.arrow.{FunctionK}
import cats.data.{Nested}
import cats.implicits._
import scala.{Function, Function1}
import spire.math.{Natural}

package monoiad {

epic poetry

in media res

epic poetry

in media res
a cyclic journey

epic poetry

in media res
a cyclic journey
vast landscape

epic poetry

in media res
a cyclic journey
vast landscape
dactylic hexameter

epic poetry

in media res
a cyclic journey
vast landscape
~~dactylic hexameter~~

epic poetry

in media res
a cyclic journey
vast landscape
~~dactylic hexameter~~
a descent into hell

The Monoiad

monoid: a category with a single object

-ad: an epic poem, usually with a cyclical journey of discovery

monad: a monoid in the category of endofunctors

What’s a monoid?

in abstract algebra

trait Monoid[A] {
  def product(x: A, y: A): A
  def unit: A
}

in abstract algebra

package object laws {

trait Monoid[A] {
  def product(x: A, y: A): A
  def unit: A

  def associativity(x: A, y: A, z: A): Boolean =
    product(product(x, y), z) == product(x, product(y, z))
  def leftIdentity(x: A): Boolean =
    product(unit, x) == x
  def rightIdentity(x: A): Boolean =
    product(x, unit) == x
}

def fold[A](as: List[A])(implicit A: Monoid[A]) =
  as.foldLeft(A.unit)(A.product(_, _))

where the product is closed (total), associative, and the unit is both the left and right identity of the product

Ok, that’s everything. You totally get monoids now. Thanks for coming.

Some examples?

`Boolean`

implicit val conjunctionMonoid =
  new Monoid[Boolean] {
    def product(a: Boolean, b: Boolean) = a && b
    def unit = true
  }
// true && (false && true) == false == (true && false) && true
// false && true == false == true && false

implicit val disjunctionMonoid =
  new Monoid[Boolean] {
    def product(a: Boolean, b: Boolean) = a || b
    def unit = false
  }
// true || (false || true) == true == (true || false) || true
// true || false == true == false || true

`Int`

implicit val additiveMonoid =
  new Monoid[Int] {
    def product(a: Int, b: Int) = a + b
    def unit = 0
  }
// 4 + (2 + 3) == 9 == (4 + 2) + 3
// 7 + 0 == 7 == 0 + 7

implicit val multiplicativeMonoid =
  new Monoid[Int] {
    def product(a: Int, b: Int) = a * b
    def unit = 1
  }
// 4 * (2 * 3) == 24 == (4 * 2) * 3
// 7 * 1 == 7 == 1 * 7

`Int` (continued)

implicit val joinMonoid =
  new Monoid[Int] {
    def product(a: Int, b: Int) = a max b
    def unit = Int.MinValue
  }
// 12.max(7.max(32)) == 32 == 12.max(7).max(32)
// 26.max(Int.MinValue) == 26 == Int.MinValue.max(26)

implicit val meetMonoid =
  new Monoid[Int] {
    def product(a: Int, b: Int) = a min b
    def unit = Int.MaxValue
  }
// 12.min(7.min(32)) == 7 == 12.min(7).min(32)
// 26.min(Int.MaxValue) == 26 == Int.MaxValue.min(26)

`String`

implicit val concatenationMonoid =
  new Monoid[String] {
    def product(a: String, b: String) = a ++ b
    def unit = ""
  }
// "mon" ++ ("oi" ++ "ad") == "monoiad" == ("mon" ++ "oi") ++ "ad"
// "foo" ++ "" == "foo" == "" ++ "foo"

Why do we care?

concepts that transcend languages
monoids are at a “sweet spot”
concurrency

generalizing

So, all of these things fit that trait I put up before, but let’s take a step back.

A ⊗ A → A η → A

∀x, y, z ∈ A (x ⊗ y) ⊗ z ≅ x ⊗ (y ⊗ z) η ⊗ x ≅ x ≅ x ⊗ η

(a, ⊗, μ)

This definition is a bit more abstract, and so maybe it can help us think of cases that aren’t quite instances of that type class.

And we weaken the equality of our laws to isomorphism. And what is isomorphism?

final case class Iso[A, B](apply: A => B, unapply: B => A)
    extends Function1[A, B]

Iso[String, List[Char]](_.toList, _.mkString(""))

"monoiad" != ['m', 'o', 'n', 'o', 'i', 'a', 'd']

now we can do this …

package object types {

trait Monoid[A] {
  def product(x: A, y: A): A
  def unit: A

  def associativity(x: A, y: A, z: A): Boolean =
    product(product(x, y), z) == product(x, product(y, z))
  def leftIdentity(x: A): Boolean =
    product(unit, x) == x
  def rightIdentity(x: A): Boolean =
    product(x, unit) == x
}

at the type level

trait TMonoid {
  type Product[_, _]
  type Identity

  def associativity[A, B, C]
      : Product[Product[A, B], C] => Product[A, Product[B, C]]
  def leftIdentity[A]
      : Product[Identity, A] => A
  def rightIdentity[A]
      : Product[A, Identity] => A
}

at the type level

final class Cartesian extends TMonoid {
  type Product[A, B] = (A, B)
  type Identity = Unit

  def associativity[A, B, C] =
    (p: ((A, B), C)) => (p._1._1, (p._1._2, p._2))
  def leftIdentity[A] = (p: (Unit, A)) => p._2
  def rightIdentity[A] = (p: (A, Unit)) => p._1
}

at the type level

final class Cocartesian extends TMonoid {
  type Product[A, B] = Either[A, B]
  type Identity = Nothing

  def associativity[A, B, C]
      : Either[Either[A, B], C] => Either[A, Either[B, C]] = ???
  def leftIdentity[A]: Either[Nothing, A] => A = ???
  def rightIdentity[A]: Either[A, Nothing] => A = ???
}

in category theory

trait Category[⟶[_, _]] {
  def compose[A, B, C](f: B ⟶ C, g: A ⟶ B): A ⟶ C
  def identity[A]: A ⟶ A
}

package object instances {

implicit val setCategory = new Category[Function1] {
  def compose[A, B, C](f: B => C, g: A => B): A => C =
    (x: A) => f(g(x))
  def identity[A]: A => A = (x: A) => x
}

a category with one object

(stolen from Emily Riehl’s Category Theory in Context)

monoid object in a monoidal category

monoids all the way down

Let’s take a step back to (*, Tuple2, Unit) and our original type class definition:

trait Monoid[A] {
  def product(x: A, y: A): A
  def unit: A
}

monoids all the way down

but now let’s use the “proper” definition I mentioned …

package unit {

trait Monoid[A] {
  def product(x: A, y: A): A
  def unit: Unit => A
}

monoids all the way down

and tweak it once more …

package tuple {

trait Monoid[A] {
  def product: (A, A) => A
  def unit: Unit => A
}

monoids all the way down

trait Monoid[A] {
  def product: (A, A) => A
  def unit: Unit => A
}

final class Cartesian extends TMonoid {
  type Product[A, B] = (A, B)
  type Identity = Unit
}

monoids all the way down

Do you notice anything?

The argument to each function is respectively the Product and Unit of our type-level Cartesian instance.

So, we can make that explicit …

package object tmonoid {

trait Monoid[T <: TMonoid, A] {
  def product: T#Product[A, A] => A
  def unit: T#Identity => A
}

implicit val conjunction = new Monoid[Cartesian, Boolean] {
  def product = (p: (Boolean, Boolean)) => p._1 && p._2
  def unit = Function.const(true)(_: Unit)
}

implicit def cocartesian[A] = new Monoid[Cocartesian, A] {
  def product: Either[A, A] => A = {
    case Left(a) => a
    case Right(a) => a
  }
  def unit = scala.Predef.identity(_: Nothing)
}

So now we have some notion of “a monoid object in a type-level monoid”, yeah?

monoidal categories

trait MonoidalCategory {
  type Arrow[_, _]
  type Product[_, _]
  type Identity
}

monoid object in a monoidal category

package object category {

trait Monoid[T <: MonoidalCategory, A] {
  def product: T#Arrow[T#Product[A, A], A]
  def unit: T#Arrow[T#Identity, A]
}

implicit val conjunction = new Monoid[Cartesian, Boolean] {
  def product = (p: (Boolean, Boolean)) => p._1 && p._2
  def unit = Function.const(true)(_: Unit)
}

implicit def cocartesian[A] = new Monoid[Cocartesian, A] {
  def product = (_: Either[A, A]) match {
    case Left(a) => a
    case Right(a) => a
  }
  def unit = scala.Predef.identity(_: Nothing)
}

other monoidal categories

`Op`

final class Op[T <: MonoidalCategory] extends MonoidalCategory {
  type Arrow[A, B] = T#Arrow[B, A]
  type Product[A, B] = T#Product[A, B]
  type Identity = T#Identity
}

implicit def comonoid[A] = new Monoid[Op[Cartesian], A] {
  def product: A => (A, A) = x => (x, x)
  def unit: A => Unit = Function.const(())(_)
}

This is mostly useful in a language with linear types. So, a comonoid (or in general, any co-thing) is a monoid in the opposite (or dual) category.

type constructors

Unfortunately, Scala doesn’t make it easy to abstract over all of these things, but we can use some consistent naming to approximate it.

([*] → *, Nested, Id)

Nested[F[_], G[_], A] ≅ F[G[A]] Identity[A] ≅ A

Nested[Nested[List, Set, ?], Maybe, ?] ≅ Nested[List, Nested[Set, Maybe, ?], ?] // ≅ List[Set[Maybe[A]]] Nested[Identity, List, ?] ≅ List ≅ Nested[List, Identity, ?]

trait TMonoid {
  type Product[_, _]
  type Identity
}

trait TMonoidF {
  type Product[_[_], _[_], _]
  type Identity[_]
}

We will stare at this slide for a while … maybe bounce between it and TMonoid a few times to understand the parallel.

final class Monadic extends TMonoidF {
  type Product[F[_], G[_], A] = Nested[F, G, A] // F[G[A]]
  type Identity[A] = Id[A]
}
// Nested[Id, F, ?] =:= F =:= Nested[F, Id, ?]
//         Id[F[_]] =:= F =:= F[Id[_]]

`Monad`

“a monad is a monoid in the category of endofunctors”

trait MonoidalCategoryF {
  type Arrow[_[_], _[_]]
  type Product[_[_], _[_], _]
  type Identity[_]
}
trait MonoidF[C <: MonoidalCategoryF, F[_]] {
  def product: C#Arrow[C#Product[F, F, ?], F]
  def unit: C#Arrow[C#Identity, F]
}
type Monad[M[_]] = MonoidF[Monadic, M]
// def product: M[M[A]] => M[A] // join
// def unit: Id[A] => M[A]      // pure
def flatMap[M[_]: Functor: Monad, A, B]
  (ma: M[A])(f: A => M[B])(implicit M: Monad[M]): M[B] =
  M.product(Nested(ma.map(f)))

And here, we’ll have to specialize MonoidF to Monad, and then show how flatMap can be implemented … and explain why we get map “for free”.

Too Many Monoids!

They’re easy to create out of thin air.

def firstExcept[A: cats.Eq](exception: A) =
  new Monoid[Cartesian, A] {
    def op = (a: A, b: A) => if (a === exception) b else a
    def identity = exception
  }

def lastExcept[A: cats.Eq](exception: A) =
  new Monoid[Cartesian, A] {
    def op = (a: A, b: A) => if (b === exception) a else b
    def identity = exception
  }

Basically, anything you might pass to foldRight.

“strengthening” monoids

digraph "" {
  rankdir=BT
  bgcolor=transparent

  Monoid [style=bold]

  Semigroup -> magma
  quasigroup -> magma [color=orange]
  loop -> quasigroup [color=red]
  CommutativeSemigroup -> Semigroup [color=blue]
  Monoid -> Semigroup [color=red]
  Band -> Semigroup [color=purple]
  CommutativeMonoid -> CommutativeSemigroup [color=red]
  CommutativeMonoid -> Monoid [color=blue]
  Semilattice -> CommutativeSemigroup [color=purple]
  Semilattice -> Band [color=blue]
  Group -> Monoid [color=orange]
  Group -> loop
  CommutativeGroup -> Group [color=blue]
  CommutativeGroup -> CommutativeMonoid [color=orange]
  BoundedSemilattice -> Semilattice [color=red]
  BoundedSemilattice -> CommutativeMonoid [color=purple]
}

associativity – black
identity – red
commutativity – +, *, max (but not String concatenation) – blue
idempotency – max, mix (but not +, *) – purple
invertible – + for ℤ (but not for ℕ) – orange

renaming monoids

Monad (kind polymorphism)
Alternative (quantified constraints)
Comonoid

relating monoids

As we’ve already seen, you often have multiple instances for a single type. This is a pretty contentious aspect of type classes. There are a number of approaches for dealing with this, and I’m not here to advocate for any of them in particular. But I am here to show that they’re not just “different” instances, but rather a set of instances that have particular relationshps to each other.

`algebra.Rig`

A ring without “negation” (i.e., no subtraction)

trait TRig {
  type Add[_, _]
  type Zero
  type Multiply[_, _]
  type One

  final class Additive extends TMonoid {
    type Product[A, B] = Add[A, B]
    type Identity = Zero
  }
  final class Multiplicative extends TMonoid {
    type Product[A, B] = Multiply[A, B]
    type Identity = One
  }
}

`algebra.Rig`

trait RigCategory extends TRig {
  type Arrow[_, _]

  def distribute[A, B, C]
      : Arrow[Multiply[A, Add[B, C]],
              Add[Multiply[A, B], Multiply[A, C]]]
  def leftAnnihilate[A]: Arrow[Multiply[Zero, A], Zero]
  def rightAnnihilate[A]: Arrow[Multiply[A, Zero], Zero]
}

Set

final class SetCategory extends RigCategory {
  type Arrow[A, B] = Function1[A, B]
  type Add[A, B] = Either[A, B]
  type Zero = Nothing
  type Multiply[A, B] = (A, B)
  type One = Unit

  def distribute[A, B, C]
      : (A, Either[B, C]) => Either[(A, B), (A, C)] = {
    case (a, Left(b)) => Left((a, b))
    case (a, Right(c)) => Right((a, c))
  }  
  def leftAnnihilate[A] = (p: (Nothing, A)) => p._1
  def rightAnnihilate[A] = (p: (A, Nothing)) => p._2
}

`algebra.BoundedLattice`

A pair of bounded semilattices, where each distributes over the other, and each identity annihilates the other. You can actually extract two rigs out of this – one each with the meet and join being either position.

trait BoundedLattice[C <: MonoidalCategory, L] {
  def meet: C#Arrow[C#Product[L, L], L]
  def minimum: C#Arrow[C#Identity, L]
  def join: C#Arrow[C#Product[L, L], L]
  def maximum: C#Arrow[C#Identity, L]

  final class Meet extends TMonoid {
    def op = meet
    def identity = maximum
  }
  final class Join extends TMonoid {
    def op = join
    def identity = minimum
  }
}

duoids

trait TDuoid {
  type DiamondP[_, _]
  type DiamondI
  type StarP[_, _]
  type StarI

  final class Diamond extends TMonoid {
    type Product[A, B] = DiamondP[A, B]
    type Identity = DiamondI
  }
  final class Star extends TMonoid {
    type Product[A, B] = StarP[A, B]
    type Identity = StarI
  }
}

duoids

trait DuoidalCategory[⟶[_, _]] extends Category[⟶] with TDuoid {
  def swap[A, B, C, D]: DiamondP[StarP[A, B], StarP[C, D]] ⟶ StarP[DiamondP[A, C], DiamondP[B, D]]
  def split: DiamondI ⟶ StarP[DiamondI, DiamondI]
  def merge: DiamondP[StarI, StarI] ⟶ StarI
  def switch: DiamondI ⟶ StarI
}

Endofunctors

trait TDuoid {
  type DiamondP[_, _]
  type DiamondI
  type StarP[_, _]
  type StarI

  final class Diamond extends TMonoid {
    type Product[A, B] = DiamondP[A, B]
    type Identity = DiamondI
  }
  final class Star extends TMonoid {
    type Product[A, B] = StarP[A, B]
    type Identity = StarI
  }
}

Endofunctors

trait TDuoidF {
  type DiamondP[_[_], _[_], _]
  type DiamondI[_]
  type StarP[_[_], _[_], _]
  type StarI[_]

  final class Diamond extends TMonoidF {
    type Product[F[_], G[_], A] = DiamondP[F, G, A]
    type Identity[A] = DiamondI[A]
  }
  final class Star extends TMonoidF {
    type Product[F[_], G[_], A] = StarP[F, G, A]
    type Identity[A] = StarI[A]
  }
}

Endofunctors

final abstract class Day[F[_], G[_], C] {
  type A; type B
  def fa: F[A]; def gb: G[B]
  def f: (A, B) => C
}
// map2[A, B, C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C]

class Endofunctor extends DuoidalCategoryF {
  type Arrow[F[_], G[_]] = FunctonK[F, G]
  type DiamondP[F[_], G[_], A] = Day[F, G, A]
  type DiamondI[A] = Unit => A
  type StarP[F[_], G[_], A] = Nested[F, G, A]
  type StarI[A] = Id[A]

Endofunctors

  def swap[F[_], G[_], H[_], I[_]] =
    λ[FunctionK[Day[Nested[F, G, ?], Nested[H, I, ?], ?],
                Nested[Day[F, H, ?], Day[G, I, ?], ?]]](???)
  def split =
    λ[FunctionK[Function1[Unit, ?],
                Nested[Function1[Unit, ?],
                        Function1[Unit, ?], ?]]](???)
  def merge = λ[FunctionK[Day[Id, Id, ?], Id]](
    day => day.f(day.fa, day.gb))
  def switch =
    λ[FunctionK[Function1[Unit, ?], Id]](_(()))
}

other duoids

parallel & sequential applicative instances
overlay & connect algebraic graph operations

etc.

bimonoids
meadow
tropical semiring
boolean algebra(?)

and back home again

trait Category[⟶[_, _]] {
  def compose[A, B, C](f: B ⟶ C, g: A ⟶ B): A ⟶ C
  def identity[A]: A ⟶ A
}

and back home again

trait Category[⟶[_, _]] {
  def compose[A, B, C](f: B ⟶ C, g: A ⟶ B): A ⟶ C
  def identity[A]: A ⟶ A
}

trait Monoid[A] {
  def product(x: A, y: A): A
  def unit: A
}

and back home again

final abstract class CategoryOp[⟶[_, _], A, B] {
  type Z
  def f: Z ⟶ B; def g: A ⟶ Z
}

trait Category[⟶[_, _]] {
  def compose[A, B]: CategoryOp[⟶, A, B] => A ⟶ B
  def identity[A]: A ⟶ A
}

trait Monoid[A] {
  def product: (A, A) => A
  def unit: A
}

Summary

}}}}

a monoid is some closed associative operation with an identity
monoids show up everywhere (and way too often)
we can best understand “important” monoids in terms of
- what additional properties they have
- how they relate to other monoids
monoids are often hidden behind other interpretations

Thanks!

Nathan Faubion for the typo that led to the name/structure of this talk.
Erik Osheim (@non), for kind-projector, algebra, and spire
Andrey Mokhov – https://blogs.ncl.ac.uk/andreymokhov/united-monoids/
many others for feedback on this talk, as well as helping me learn all this in the first place

References

Functional Programming in Scala
this talk – https://github.com/sellout/category-parametric-talk/monoiad/
Cheshire – https://github.com/sellout/cheshire
Caterwaul – https://github.com/sellout/caterwaul
Seven Sketches in Compositionality – https://arxiv.org/pdf/1803.05316.pdf
Category Theory in Context – https://golem.ph.utexas.edu/category/2016/11/category_theory_in_context.html
nLab – https://ncatlab.org/nlab

Seven Skteches is a book on CT that’s focused specifically on monoidal categories (in the context of “enriched CT”

Files

scala.org

Latest commit

History

scala.org

File metadata and controls

The Monoiad

preface

resources

boilerplate

epic poetry

epic poetry

epic poetry

epic poetry

epic poetry

epic poetry

The Monoiad

What’s a monoid?

in abstract algebra

in abstract algebra

Some examples?

Boolean

Int

Int (continued)

String

Why do we care?

generalizing

now we can do this …

at the type level

at the type level

at the type level

in category theory

a category with one object

monoid object in a monoidal category

monoids all the way down

monoids all the way down

monoids all the way down

monoids all the way down

monoids all the way down

categories

monoidal categories

monoid object in a monoidal category

other monoidal categories

Op

type constructors

Monad

Too Many Monoids!

“strengthening” monoids

renaming monoids

relating monoids

algebra.Rig

algebra.Rig

Set

algebra.BoundedLattice

duoids

duoids

Endofunctors

Endofunctors

Endofunctors

Endofunctors

other duoids

etc.

and back home again

and back home again

and back home again

Summary

Thanks!

References

`Boolean`

`Int`

`Int` (continued)

`String`

`Op`

`Monad`

`algebra.Rig`

`algebra.Rig`

`algebra.BoundedLattice`