Category-parametric Programming

Who?

Greg Pfeil

Formation.ai – ML for customer relationships

Ross Baker (@rossabaker)
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).

Recursion Schemes

So, you may know me from such projects as Matryoshka (there’s a talk tomorrow at noon). And I ported that to Cats, calling it Turtles. The most common question I get now is

Recursion Schemes

andyscott/droste – Andy Scott (@andygscott)
vil1/recursion-schemes-cookbook – Valentin Kasas (@ValentinKasas)

Turtles is pretty much kaput. There is a new upstart – Droste – recursion schemes for Cats with dedicated and active maintainers. I’m one of them, but so far inactive. Andy Scott at Stripe is leading it.

I’m also working on a recursion scheme cookbook with one of the organizers(?) (member of the program committee?) here – Valentin Kasas.

But this talk isn’t about recursion schemes. At least not directly. But in a different way, it is, because it’s about everything, because it’s about … Categories!

Quote!

“Most if not all constructions in category theory are parametric in the underlying category, resulting in a remarkable economy of expression. […] This possibly leads to a new style of programming, which could be loosely dubbed as category-parametric programming.”

familiarity calibration

I’m just checking which of these things you may be more-or-less familiar with. So, keep your hands up for any slides you understand at a glance, and put them down for slides you don’t understand. This helps me figure out which other slides I should maybe move through quickly or explain more carefully. If you do find yourself bewildered by the end – that’s my fault, not yours. I will happily sit down with anyone to work through any and all of it. (And you can also find me on the Internet if you think of something after the conference has ended – my Twitter and email are on the bottom of every slide).

There is nothing about not knowing any of these that makes you a “worse” programmer than someone who does know them – different people are introduced to different ideas at different times. So, don’t feel like you should be familiar with these – just

the setup

sbt.version=1.2.3

inThisBuild(Seq(
  scalaOrganization := "org.typelevel",
  scalaVersion := "2.12.4-bin-typelevel-4",
  scalacOptions := Seq(
    "-language:higherKinds",
    "-Ykind-polymorphism"),
  libraryDependencies := Seq(
    "org.typelevel" %% "cats-core"   % "1.3.1",
    "org.typelevel" %% "cats-effect" % "1.0.0")))

addCompilerPlugin("org.spire-math" %% "kind-projector" % "0.9.8")

import cats.implicits._

package object CategoryParametric {

package object Calibration {

This is a literate presentation, so here is everything necessary for the rest of the code in this presentation to compile. There is really just one section of the code that requires dotty (or a Typelevel-branded scalac) – the rest should work fine with a current release of things.

`kind-projector`

Either[String, ?]

cats.arrow.FunctionK[List, ?[_]]

composition

def f: Boolean => Char
def g: String => Boolean

f <<< g

(a: String) => f(g(a))

higher-order functions

def map[A, B](fa: List[A])(f: A => B): List[B]



def flatMap[A, B](fa: List[A])(f: A => List[B]): List[B]

type classes

trait Functor[F[_]] {
  def map[A, B](fa: F[A])(f: A => B): F[B]
}

trait Monad[M[_]] extends cats.Applicative[M] {
  def flatMap[A, B](fa: M[A])(f: A => M[B]): M[B]
}

monoids

trait Monoid[A] {
  def empty: A
  def combine(a: A, b: A): A
}

I use Cats terminology in this talk, when it comes to the names of traits and types, but it should hopefully be understandable regardless of the terminology you’re familiar with – after all, names don’t matter … right?

composition

So, looking at the definition of Category, is there anything that’s missing?

Proper values!

The only values we have are the morphisms. And the only thing we can do to them is compose them.

Scala is not great at composition. It expects things to be applied, otherwise you have to provide it with lots of types to tell it what you want.

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

Why?

Why do we care about categories?

The same reason we might care about interfaces, or type classes – abstraction!

Even if we can’t have a fully abstract implementation, understanding the common abstraction can help us see larger similarities between things.

Category theory is the ultimate abstraction. Everything from every field of mathematics (like, type theory) maps to category theory. Not only can you see how ideas in your particular area relate to each other more clearly, but you can also see how your ideas map to ideas in other branches of mathematics.

Eugenia Cheng – Category Theory and Life

functors

\usetikzlibrary{cd}
\begin{tikzcd}
A \ar[r, "f"] \ar[d, "F"] & B \ar[d, "F"] \\
A_F \ar[r, "f_F"] & B_F
\end{tikzcd}

\usetikzlibrary{cd}
\begin{tikzcd}
A \ar[r, "f"] \ar[d, "F"] & B \ar[d, "F"] \\
A_F \ar[r, "map(f)"] & B_F
\end{tikzcd}

aligning `Functor`

trait Functor[F[_]] {
  def map[A, B](fa: F[A])(f: A => B): F[B]
}

trait Functorʹ[F[_]] {
  def map[A, B](f: A => B)(fa: F[A]): F[B]
}

trait Functorʹʹ[F[_]] {
  def map[A, B](f: A => B): F[A] => F[B]
}

generalizing endofunctors

trait Endofunctorʹ[⟹[_, _], F[_]] {
  def map[A, B](f: A ⟹ B): F[A] ⟹ F[B]
}

… to functors

trait Exofunctor[⟹[_, _], ⟾[_, _], F[_]] {
  def map[A, B](f: A ⟹ B): F[A] ⟾ F[B]
}

endofunctors

type Endofunctor[⟹[_, _], F[_]] = Exofunctor[⟹, ⟹, F]

type Functorʹʹʹ[F[_]] = Endofunctor[Function1, F]
// `map[A, B](f: A => B): F[A] => F[B]` is `map`

`Traverse`

type Traverse[M[_], F[_]] = Endofunctor[Kleisli[M, ?, ?], F]
// `map[A, B](f: A => M[B]): F[A] => M[F[B]]` is `traverse`

implicit def optionTraverse[M[_]: Applicative] =
  new Traverse[M, Option] {
    def map[A, B](f: Kleisli[M, A, B]) = null
  }

implicit def idTraverse[M[_]] = new Traverse[M, cats.Id] {
  def map[A, B](f: Kleisli[M, A, B]) = null
}

implicit val ioTraverse = new Traverse[cats.Id, cats.effect.IO] {
  def map[A, B](f: Kleisli[cats.Id, A, B]) = null
}

unify `Functor` and `Traverse`?

type Functorʹʹʹʹ[F[_]] = Traverse[cats.Id, F]
// `map[A, B](f: A => Id[B]): F[A] => Id[F[B]]` is `map`

exofunctors

type KleisliFunctor[M[_], F[_]] =
  Exofunctor[cats.data.Kleisli[M, ?, ?], Function1, F]

type FunctorFilter[F[_]] = KleisliFunctor[Option, F]
// `map[A, B](f: A => Option[B]): F[A] => F[B]` is `mapFilter`
type FlatMap[F[_]] = KleisliFunctor[F, F]
// `map[A, B](f: A => F[B]): F[A] => F[B]` is `flatMap`

type CokleisliFunctor[M[_], F[_]] =
  Exofunctor[cats.data.Cokleisli[M, ?, ?], Function1, F]

type CoflatMap[F[_]] = CokleisliFunctor[F, F]
// `map[A, B](f: F[A] => B): F[A] => F[B]` is `coflatMap`

duality

// from cats.data
final case class Op[⟹[_, _], A, B](run: B ⟹ A)

type Presheaf[⟹[_, _], F[_]] = Exofunctor[Op[⟹, ?, ?], ⟹, F]

type Contravariant[F[_]] = Presheaf[Function1, F]
// `map[A, B](f: B => A): F[A] => F[B]` is `contramap`

What category are we in?!

// from cats.data
final case class Op[⟹[_, _], A, B](run: B ⟹ A)

Op[Kleisli[F, ?, ?], A, B] // (A => F[B]) => (B => F[A])
Op[Function1, A, F[B]]     // (A => F[B]) => (F[B] => A)

Duality can be confusing if you don’t know what category you’re working in. For example, what is the dual of A ⇒ M[B]? If you’re in Scal, the category of Scala types, the dual would be M[B] ⇒ A. But if you’re in a Kleisli category, then the dual would be B ⇒ M[A].

I.e., in a Kleisli category, the M is part of the morphism, in Scal it’s part of the object.

subcategories

But … we can’t abstract over the constraint, so we”d have to explicitly create a new morphism type for each set of constraints.

final case class OrdFunction1
  [A: cats.kernel.Order, B: cats.kernel.Order]
  (run: A => B)

val setFunctor = new Exofunctor[OrdFunction1, Function1, Set] {
  def map[A, B](f: OrdFunction1[A, B]) = _.map(f.run)
}

val boolSet: Set[Boolean] =
  setFunctor.map(
    OrdFunction1[Int, Boolean](_ % 2 == 0))(
    Set(0, 1, 2, 3))

other kinds of functors

trait Exofunctorʹ[⟹[_   , _   ], ⟾[_   , _   ], F[_      ]] {
  def map[A   , B   ](f: A ⟹ B): F[A   ] ⟾ F[B   ]
}

functors in a functor category

trait ExofunctorK[⟹[_[_], _[_]], ⟾[_[_], _[_]], F[_[_], _]] {
  def map[A[_], B[_]](f: A ⟹ B): F[A, ?] ⟾ F[B, ?]
}

type Hoist[F[_[_], _]] =
  ExofunctorK[cats.arrow.FunctionK, cats.arrow.FunctionK, F]

bifunctors

trait Bifunctor[⟶[_, _], ⟹[_, _], ⟾[_, _], F[_, _]] {
  def map[A, B, C, D](f: A ⟶ C, g: B ⟹ D): F[A, B] ⟾ F[C, D]
}
type Bifunctorʹ[F[_, _]] =
  Bifunctor[Function1, Function1, Function1, F]
// `map[A, B, C, D](f: A => C, g: B => D): F[A, B] => F[C, D]`
//  is `bimap`

profunctors

type Profunctor[⟶[_, _], ⟹[_, _], F[_, _]] =
  Bifunctor[cats.data.Op[⟹, ?, ?], ⟶, Function1, F]

type Profunctorʹ[F[_, _]] = Profunctor[Function1, Function1, F]
// `map[A, B, C, D](f: C => A, g: B => D): F[A, B] => F[C, D]`
//  is `dimap`

type HomFunctor[⟹[_, _], F[_,_]] =
  Bifunctor[cats.data.Op[⟹, ?, ?], ⟹, ⟹, F]

type Profunctorʹʹ[F[_, _]] = HomFunctor[Function1, F]

What are the problems with this?

breaks inference
often wrapping and unwrapping
can make type class inheritance difficult
gives us (or at least me) a taste of something I want more of

Monoids

trait Monoid[A] {
  def empty: A
  def combine(x: A, y: A): A
}

case class MonoidLaws[A](monoid: Monoid[A]) {
  def associative(x: A, y: A, z: A) =
    monoid.combine(monoid.combine(x, y), z) ==
      monoid.combine(x, monoid.combine(y, z))
  def leftIdentity(x : A) = monoid.combine(monoid.empty, x) == x
  def rightIdentity(x : A) = monoid.combine(x, monoid.empty) == x
}

abstract over the category …

identity isn’t a morphism, though. And is op? How can we fix these?

trait Monoidʹʹ[⟹[_, _], A] {
  def identity: Unit ⟹ A
  def op: (A, A) ⟹ A
}

but it’s a monoidal category

A monoid in a “monoidal category” is an object with two particular morphisms …

trait CMonoid[⟹[_, _], I, ⊗[_, _], A] {
  def identity: I ⟹ A
  def op: (A ⊗ A) ⟹ A
}

type Monoidʹ[A] = CMonoid[Function1, Unit, Tuple2, A]

fixing a problem

but this new Monoidʹ looks a bit different than Cats’ version, right? We have to apply identity to (), and we have to apply ap to a single Tuple2, rather than to a pair of arguments. We can always add another wrapper:

trait ProperMonoidʹ[A] extends CMonoid[Function1, Unit, Tuple2, A] {
  def empty: A
  def combine(a: A, b: A): A

  final def identity = (_: Unit) => empty
  final def op = (tup: (A, A)) => combine(tup._1, tup._2)
}

And now we can define and use the Monoid we usually want, without losing the generality of CMonoid.

`?` ⇒ `?[_]`

Now we’re going to talk about a different kind of monoid …

trait CMonoidʹ[⟹[_   , _   ], I   , ⊗[_   , _      ], A   ] {
  def identity: I ⟹ A
  def op: (A ⊗ A) ⟹ A
}

`MonoidK`

trait CMonoidK[⟹[_[_], _[_]], I[_], ⊗[_[_], _[_], _], A[_]] {
  def identity: I ⟹ A
  def op: ⊗[A, A, ?] ⟹ A
}

a monad is “just” …

trait Monad[M[_]]
    extends CMonoidK[cats.arrow.FunctionK,
                     cats.Id,
                     cats.data.Nested,
                     M] {
  def pure[A](a: A): M[A]
  def join[A](fa: M[M[A]]): M[A]

  final def identity = λ[cats.arrow.FunctionK[cats.Id, M]](pure(_))
  final def op =
    λ[cats.arrow.FunctionK[cats.data.Nested[M, M, ?], M]](
      a => join(a.value))
}

Note that these instances are defined in terms of map2 and join, rather than ap and flatMap. That’s a trivial issue to get around, though.

What’s more complicated is that we know that every Monad implies an Applicative, and we usually show that by having Monad[M[_]] extends Applicative[M], but we have a problem here – identity matches up, but that would give us two distinct implementations of op!

and so is `Applicative`

final abstract class Day[F[_], G[_], C] {
  type A
  type B
  def fa: F[A]
  def gb: G[B]
  def f(a: A, b: B): C
}

trait Applicative[F[_]]
     extends CMonoidK[cats.arrow.FunctionK, cats.Id, Day, F] {
  def pure[A](a: A): F[A]
  def map2[A, B, C](fa: F[A], fb: F[B])(f: (A, B) => C): F[C]

  final def identity = λ[cats.arrow.FunctionK[cats.Id, F]](pure(_))
  final def op = λ[cats.arrow.FunctionK[Day[F, F, ?], F]](
    day => map2(day.fa, day.gb)(day.f))
}

a trick

I pulled a bit of a trick at the beginnig of this talk, and I wonder if anyone noticed. I’m going to do it again a bit more slowly, and raise your hand if you think you know what the trick is. I haven’t given away the answer yet, but I’ve shown a number of steps that lead to it.

Monoids

trait Monoidʹʹʹ[A] {
  def empty: A
  def combine(a: A, b: A): A
}

Category as Monoid (preface)

trait MonoidB
  [⟹[_[_, _], _[_, _]], I[_, _], ⊗[_[_, _], _[_, _], _, _],
   A[_, _]] {
  def identity: I ⟹ A
  def op: ⊗[A, A, ?, ?] ⟹ A
}

trait FunctionB[F[_, _], G[_, _]] {
  def apply[A, B](fab : F[A, B]): G[A, B]
}

final abstract class ComposeB[⟹[_, _], ⟾[_, _], A, B] {
  type Z
  def f: Z ⟹ B
  def g: A ⟾ Z
}

Category as Monoid

trait Categoryʹʹ[⟹[_, _]]
    extends MonoidB[FunctionB, cats.evidence.Is, ComposeB, ⟹] {
  def id[A]: A ⟹ A
  def compose[A, B, C](f: B ⟹ C, g: A ⟹ B): A ⟹ C

  def identity = new FunctionB[cats.evidence.Is, ⟹] {
    def apply[A, B](fab : cats.evidence.Is[A, B]) =
      fab.substitute[A ⟹ ?](id)
  }
  // λ[FunctionB[ComposeB[⟹, ⟹, ?, ?], ⟹]](compose(fab.f, fab.g))
  def op = new FunctionB[ComposeB[⟹, ⟹, ?, ?], ⟹] {
    def apply[A, B](fab : ComposeB[⟹, ⟹, A, B]) =
      compose(fab.f, fab.g)
  }
}

B = Bifunctor

But, what is a bifunctor? Different in category theory from Haskell / Scala. The B above is CT-ish, so, basically, any product category.

Kind Polymorphism

Requires Dotty or Typelevel

Thanks to Pascal & Miles.

trait CMonoid
    [⟹[_, _],
     I,
     ⊗[_, _],
     A] {
  def identity: I ⟹ A
  def op: (A ⊗ A) ⟹ A
}

package object KindPoly {

`AnyKind`

trait Monoid
    [⟹[_ <: AnyKind, _ <: AnyKind],
     I <: AnyKind,
     ⊗ <: AnyKind, // ⊗[_ <: AnyKind, _ <: AnyKind] <: AnyKind,
     A <: AnyKind] {
  def identity: I ⟹ A
  def op: ⊗ ⟹ A  // def op: (A ⊗ A) ⟹ A
}

We’d like to use the commented-out forms, but it isn’t available with the syntax provided by Scala’s kind-polymorphism. This is a weakness, because remember earlier we said that ⊗ is a bifunctor, but that isn’t enforced by this definition.

We can still define it with bifunctors, but we need to explicitly mention A twice in the ⊗ argument.

type ProperMonoid[A] = Monoid[Function1, Unit, (A, A), A]

That means we can inadvertantly specify non-monoids if we provide a bad ⊗ argument.

type FakeMonoid[A] = Monoid[Function1, Unit, List, A]

is in no way a valid monoid, but it’s not prevented by this definition. So, we can define a kind-polymorphic Monoid, but it means we have to be a bit careful with the definitions.

There’s another problem, in that the operations constrain I and ⊗ to the same kind, and ⟹ must match the kinds of I and A in its two parameters, but there is nothing saying that the two parameters of ⟹ must be of the same kind. But since ⟹ is meant to be a morphism in a category, and all objects in a category must be valid on either side of a morphism, the kinds are required to align – but, again, it’s not enforced.

So, by generalizing Monoid in this way, we’ve managed to unify many type classes

mono `Monoid`

But, at least in Scala, we’ve lost some precision. If we are careful about that third parameter, then we should be ok, but there’s a risk.

// Monoid
type ProperMonoid[A] = Monoid[Function1, Unit, (A, A), A]

// MonoidK
type MonoidK[F[_]] =
  Monoid[cats.arrow.FunctionK, cats.Id, cats.data.Tuple2K[F, F, ?],
         F]
type Applicative[F[_]] =
  Monoid[cats.arrow.FunctionK, cats.Id, Day[F, F, ?], F]
type Monad[M[_]] =
  Monoid[cats.arrow.FunctionK, cats.Id, cats.data.Nested[M, M, ?],
         M]

// MonoidB
type TypeCategory[⟹[_, _]] =
  Monoid[FunctionB, cats.evidence.Is, ComposeB[⟹, ⟹, ?, ?], ⟹]

mono `Functor`? 🚫

In the case of a kind-polymorphic functor – I can’t even figure out how to define it. In the first case, we can’t do the nested AnyKind on a type, and in the second case (using the same sort of trick from ⊗), we have no way to apply the F to A or B.

There may be some trick I’m unaware of to help with this.

trait Functor
    [⟹[_ <: AnyKind, _ <: AnyKind],
     ⟾[_ <: AnyKind, _ <: AnyKind],
     F[_ <: AnyKind] <: AnyKind] {
  def map[A <: AnyKind, B <: AnyKind](f: A ⟹ B): F[A] ⟾ F[B]
}

trait Functor
    [⟹[_ <: AnyKind, _ <: AnyKind],
     ⟾[_ <: AnyKind, _ <: AnyKind],
     F <: AnyKind] {
  def map[A <: AnyKind, B <: AnyKind](f: A ⟹ B): F ⟾ F
}

multiple type parameter lists

scala/bug#4719

F[_ <: AnyKind] <: AnyKind

final case class Tuple2K[F[_], G[_], A](first: F[A], second: G[A])

final case class Tuple2K[F[_], G[_]][A](first: F[A], second: G[A])

an exercise …

trait Category[⟹[_ <: AnyKind, _ <: AnyKind]] {
  def id[A <: AnyKind]: A ⟹ A
  def compose[A <: AnyKind, B <: AnyKind, C <: AnyKind]
    (g: B ⟹ C, f: A ⟹ B)
      : A ⟹ C
}

Questions?

Greg Pfeil

Formation.ai – ML for customer relationships

Thanks to

Erik Osheim (@d6) for kind-projector,
Pascal Voitot (@mandubian) for -Ykind-polymorphism

Miles Sabin (@milessabin) for Typelevel Scala

Rob Norris (@tpolecat)
Typelevel.org in general

Scala.io

so many others inside and outside the Scala community

Files

scala-io.org

Latest commit

History

scala-io.org

File metadata and controls

Category-parametric Programming

Who?

Recursion Schemes

Recursion Schemes

Quote!

familiarity calibration

the setup

kind-projector

composition

higher-order functions

type classes

monoids

categories

categories

Scal

Kleisli

composition

Why?

functors

aligning Functor

generalizing endofunctors

… to functors

endofunctors

Traverse

unify Functor and Traverse?

exofunctors

duality

What category are we in?!

subcategories

other kinds of functors

functors in a functor category

bifunctors

profunctors

What are the problems with this?

Monoids

abstract over the category …

but it’s a monoidal category

fixing a problem

? ⇒ ?[_]

MonoidK

a monad is “just” …

and so is Applicative

a trick

Monoids

Categories

Category as Monoid (preface)

Category as Monoid

Kind Polymorphism

AnyKind

mono Monoid

mono Functor? 🚫

multiple type parameter lists

an exercise …

Questions?

`kind-projector`

aligning `Functor`

`Traverse`

unify `Functor` and `Traverse`?

`?` ⇒ `?[_]`

`MonoidK`

and so is `Applicative`

`AnyKind`

mono `Monoid`

mono `Functor`? 🚫