Duality and How to Delete Half (minus ɛ) of Your Code

Categories and How to Delete 96% (minus ɛ) of Your Code

Who?

Greg Pfeil

Ross Baker (@rossabaker)
Chris McKinley (@fnowarn) – spoke on Thursday!
Kris Nuttycombe (@nuttycom)
Paul Snively (@paul_snively) – speaking at 3:00 in this room!

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

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!

the build

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-free" % "1.3.1")))

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

the imports

import cats._
import cats.arrow._
import cats.data._
import cats.free._
import cats.implicits._

of course …

\begin{tikzcd} cata \end{tikzcd}

folds

package shadow {

trait Recursive[T, F[_]] {
  def cata[A](φ: F[A] => A): T => A
}

folds (example)

// toInt Zero == 0
// toInt Succ(Succ(Succ(Zero))) == 3
sealed trait Natural
final case object Zero               extends Natural
final case class Succ(prev: Natural) extends Natural

object Natural {
  implicit val recursive = new Recursive[Natural, Option] {
    def cata[A](φ: Option[A] => A) = ???
  }

  val toInt = recursive.cata[Int] {
                case None    => 0
                case Some(i) => i + 1
              }
}

folds

\begin{tikzcd} cata \end{tikzcd}

and unfolds

package shadow {

trait Recursive[T, F[_]] {
  def cata[A](φ: F[A] => A): T => A
}

trait Corecursive[T, F[_]] {
  def ana[A](φ: A => F[A]): A => T
}

and unfolds

\begin{tikzcd} cata \ar[rr] & & ana \end{tikzcd}

with variations

package shadow {

trait Recursive[T, F[_]] {
  def histo[A]
    (φ: F[Cofree[F, A]] => A)(implicit F: Functor[F])
      : T => A

  def cata[A]
    (φ: F[          A ] => A): T => A

  def para[A]
    (φ: F[(T,       A)] => A)(implicit F: Functor[F])
      : T => A
}

with variations

\begin{tikzcd} histo \ar[rr, crossing over] & & futu &
\ cata \ar[uu] \ar[dd] \ar[rr, crossing over] & & ana \ar[uu, crossing over] & \ \ para \ar[rr] & & apo \ar[from=uu, crossing over] & \end{tikzcd}

and monads

package shadow {

trait Recursive[T, F[_]] {
  def  cata[             A]
    (φ: F[A] =>   A ): T =>   A

  def cataM[M[_]: Monad, A]
    (φ: F[A] => M[A])(implicit F: Traverse[F])
      : T => M[A]
}

and monads

\begin{tikzcd} & histoM \ar[from=dd] \ar[rr] & & futuW
histo \ar[rr, crossing over] \ar[ur] & & futu \ar[ur] & \ & cataM \ar[dd] \ar[rr] & & anaW \ar[uu] \ar[dd] \ cata \ar[uu] \ar[dd] \ar[rr, crossing over] \ar[ur] & & ana \ar[uu, crossing over] \ar[ur] & \ & paraM \ar[rr] & & apoW \ para \ar[rr] \ar[ur] & & apo \ar[from=uu, crossing over] \ar[ur] & \end{tikzcd}

and beyond

package shadow {
  sealed trait ≈>[F[_, _], G[_, _]] {
    def apply[A, B](fab: F[A, B]): G[A, B]
  }

trait Recursive[T, F[_]] {
  def cata[A      ]
    (φ: F[A]       => A): T => A
}
trait RecursiveK[T[_], F[_[_], _]] {
  def cataK[A[_]   ]
    (φ: F[A, ?]    ~> A): T ~> A
}
trait RecursiveB[T[_, _], F[_[_, _], _, _]] {
  def cataB[A[_, _]]
    (φ: F[A, ?, ?] ≈> A): T ≈> A
}

and beyond

\begin{tikzcd}[cramped, column sep=small] & histoMK \ar[from=dd] \ar[rr] & & futuWK & & histoM \ar[from=dd] \ar[rr] & & futuW & & histoMA \ar[from=dd] \ar[rr] & & futuWA
histoK \ar[rr, crossing over] \ar[ur] & & futuK \ar[ur] & & histo \ar[rr, crossing over] \ar[ur] & & futu \ar[ur] & & histoA \ar[rr, crossing over] \ar[ur] & & futuA \ar[ur] & \ & cataMK \ar[dd] \ar[rr] & & anaWK \ar[uu] \ar[dd] & & cataM \ar[dd] \ar[rr] & & anaW \ar[uu] \ar[dd] & & cataMA \ar[dd] \ar[rr] & & anaWA \ar[uu] \ar[dd] \ cataK \ar[uu] \ar[dd] \ar[rr, crossing over] \ar[ur] & & anaK \ar[uu, crossing over] \ar[ur] & & cata \ar[uu] \ar[dd] \ar[rr, crossing over] \ar[ur] & & ana \ar[uu, crossing over] \ar[ur] & & cataA \ar[uu] \ar[dd] \ar[rr, crossing over] \ar[ur] & & anaA \ar[uu, crossing over] \ar[ur] & \ & paraMK \ar[rr] & & apoWK & & paraM \ar[rr] & & apoW & & paraMA \ar[rr] & & apoWA \ paraK \ar[rr] \ar[ur] & & apoK \ar[from=uu, crossing over] \ar[ur] & & para \ar[rr] \ar[ur] & & apo \ar[from=uu, crossing over] \ar[ur] & & paraA \ar[rr] \ar[ur] & & apoA \ar[from=uu, crossing over] \ar[ur] & \end{tikzcd}

Other dimensions

Look, at this point, any time I want to add something new, I have to implement like 24 variants of it. This is insane. You know when you look at a library and expect an operation to exist, but it seems to not … so you keep looking, because you know it must be there. This is why it’s not there – someone wants to add a case, they add that case, and leave out the other 23. I mean, even if they could see the pattern through the project, who’s going to implement something 23 times in order to maintain the pattern?

<raises hand> ME!

Yeah, and this is my own curse, I get it. But what if we could avoid implementing it 24 times? Right? Do you think people writing Go ask this question? I mean, this is why we have type parameters, right? We’ve already solved this problem in a bunch of cases. This bugs us enough to fix.

Or have we hit the sweet spot, where we’ve abstracted just enough, but no more?

Besides the many already covered, there are at least two other dimensions that have come up in working with recursion schemes. We’re not going to cover these today, but I just wanted to point out that even with all of this complication, we’re still dealing with a simplification. Duplication looms large.

Elgot

package shadow {

trait Recursive[T, F[_]] {
  def para[A](φ: F[(T, A)] => A)(implicit F: Functor[F])
      : T => A

  def epara[A](φ: (T, F[A]) => A)(implicit F: Functor[F])
      : T => A
}

comonad transformers

package shadow {

final case class EnvT[E, F[_], A](run: (E, F[A]))

trait Recursive[T, F[_]] {
  def  para[      A]
    (φ: F[(T,        A)] => A)
    (implicit F: Functor[F])
      : T => A

  def paraT[W[_], A]
    (φ: F[EnvT[T, W, A]] => A)
    (implicit F: Functor[F], W: Comonad[W])
      : T => A
}

Getting Back

So look at this. It’s a mess – this kind of thing used to make me feel ill. But I’ve found a bunch of ways to bring it back under control!

\begin{tikzcd}[cramped, column sep=small] & histoMK \ar[from=dd] \ar[rr] & & futuWK & & histoM \ar[from=dd] \ar[rr] & & futuW & & histoMA \ar[from=dd] \ar[rr] & & futuWA
histoK \ar[rr, crossing over] \ar[ur] & & futuK \ar[ur] & & histo \ar[rr, crossing over] \ar[ur] & & futu \ar[ur] & & histoA \ar[rr, crossing over] \ar[ur] & & futuA \ar[ur] & \ & cataMK \ar[dd] \ar[rr] & & anaWK \ar[uu] \ar[dd] & & cataM \ar[dd] \ar[rr] & & anaW \ar[uu] \ar[dd] & & cataMA \ar[dd] \ar[rr] & & anaWA \ar[uu] \ar[dd] \ cataK \ar[uu] \ar[dd] \ar[rr, crossing over] \ar[ur] & & anaK \ar[uu, crossing over] \ar[ur] & & cata \ar[uu] \ar[dd] \ar[rr, crossing over] \ar[ur] & & ana \ar[uu, crossing over] \ar[ur] & & cataA \ar[uu] \ar[dd] \ar[rr, crossing over] \ar[ur] & & anaA \ar[uu, crossing over] \ar[ur] & \ & paraMK \ar[rr] & & apoWK & & paraM \ar[rr] & & apoW & & paraMA \ar[rr] & & apoWA \ paraK \ar[rr] \ar[ur] & & apoK \ar[from=uu, crossing over] \ar[ur] & & para \ar[rr] \ar[ur] & & apo \ar[from=uu, crossing over] \ar[ur] & & paraA \ar[rr] \ar[ur] & & apoA \ar[from=uu, crossing over] \ar[ur] & \end{tikzcd}

comonadic folds

The first step is plain-ol’ Scala. Nothing tricky here –

package shadow {

trait Recursive[T, F[_]] {
  def histo[A]
    (φ: F[Cofree[F, A]] => A)(implicit F: Functor[F])
      : T => A

  def cata[A]
    (φ: F[          A ] => A)
      : T => A

  def para[A]
    (φ: F[(T,       A)] => A)(implicit F: Functor[F])
      : T => A
}

comonadic folds

package shadow {

trait Recursive[T, F[_]] {
  type Compose[F[_], G[_], A] = F[G[A]]

  def gcata[W[_]: Comonad, A]
    (k: Compose[F, W, ?] ~> Compose[W, F, ?],
     φ: F[W[A]] => A)
      : T => A

  def cata[A](φ: F[A] => A) =
    gcata[Id, A](FunctionK.id, φ)
  def histo[A]
    (φ: F[Cofree[F, A]] => A)(implicit F: Functor[F]) =
    gcata[Cofree[F, ?], A](distCofree, φ)
  def para[A](φ: F[(T, A)] => A) =
    gcata[(T, ?), A](distTuple, φ)

  def distCofree
      : Compose[F, Cofree[F, ?], ?] ~> Compose[Cofree[F, ?], F, ?] = ???
  def distTuple: Compose[F, (T, ?), ?] ~> Compose[(T, ?), F, ?] = ???
}

comonadic folds

\begin{tikzcd}[cramped, column sep=small] & histoMK \ar[from=dd] \ar[rr] & & futuWK & & histoM \ar[from=dd] \ar[rr] & & futuW & & histoMA \ar[from=dd] \ar[rr] & & futuWA
histoK \ar[rr, crossing over] \ar[ur] & & futuK \ar[ur] & & histo \ar[rr, crossing over] \ar[ur] & & futu \ar[ur] & & histoA \ar[rr, crossing over] \ar[ur] & & futuA \ar[ur] & \ & cataMK \ar[dd] \ar[rr] & & anaWK \ar[uu] \ar[dd] & & cataM \ar[dd] \ar[rr] & & anaW \ar[uu] \ar[dd] & & cataMA \ar[dd] \ar[rr] & & anaWA \ar[uu] \ar[dd] \ cataK \ar[uu] \ar[dd] \ar[rr, crossing over] \ar[ur] & & anaK \ar[uu, crossing over] \ar[ur] & & cata \ar[uu] \ar[dd] \ar[rr, crossing over] \ar[ur] & & ana \ar[uu, crossing over] \ar[ur] & & cataA \ar[uu] \ar[dd] \ar[rr, crossing over] \ar[ur] & & anaA \ar[uu, crossing over] \ar[ur] & \ & paraMK \ar[rr] & & apoWK & & paraM \ar[rr] & & apoW & & paraMA \ar[rr] & & apoWA \ paraK \ar[rr] \ar[ur] & & apoK \ar[from=uu, crossing over] \ar[ur] & & para \ar[rr] \ar[ur] & & apo \ar[from=uu, crossing over] \ar[ur] & & paraA \ar[rr] \ar[ur] & & apoA \ar[from=uu, crossing over] \ar[ur] & \end{tikzcd}

comonadic folds

\begin{tikzcd}[cramped, column sep=small] & cataMK \ar[rr] & & anaWK & & cataM \ar[rr] & & anaW & & cataMA \ar[rr] & & anaWA
cataK \ar[rr, crossing over] \ar[ur] & & anaK \ar[ur] & & cata \ar[rr, crossing over] \ar[ur] & & ana \ar[ur] & & cataA \ar[rr, crossing over] \ar[ur] & & anaA \ar[ur] & \ \end{tikzcd}

comonadic folds

\begin{tikzcd} & cataMK \ar[from=dd] \ar[rr] & & anaWK
cataK \ar[rr, crossing over] \ar[ur] & & anaK \ar[ur] & \ & cataM \ar[dd] \ar[rr] & & anaW \ar[uu] \ar[dd] \ cata \ar[uu] \ar[dd] \ar[rr, crossing over] \ar[ur] & & ana \ar[uu, crossing over] \ar[ur] & \ & cataMB \ar[rr] & & anaWB \ cataB \ar[rr] \ar[ur] & & anaB \ar[from=uu, crossing over] \ar[ur] & \end{tikzcd}

duality

Now that we have a category abstraction, we can add another category … Op.

package shadow {

trait Recursive[T, F[_]] {
  def cata[A](φ: F[A] => A): T => A
}
trait Corecursive[T, F[_]] {
  def  ana[A](φ: A => F[A]): A => T
}

type Op[⟶[_, _], A, B] = B ⟶ A

// A => B ⟷ Function1[A, B]
// B => A ⟷ Op[Function1, A, B]

duality

package shadow {

trait Recursive[⟶[_, _], T, F[_]] {
  def cata[A](φ: F[A] ⟶ A): T ⟶ A
}
object dual {
  type Corecursive[⟶[_, _], T, F[_]] =
    Recursive[Op[⟶, ?, ?], T, F]
}

But we now have a problem with naming …

duality

\begin{tikzcd} histo \ar[rr, crossing over] & & futu &
\ cata \ar[uu] \ar[dd] \ar[rr, crossing over] & & ana \ar[uu, crossing over] & \ \ para \ar[rr] & & apo \ar[from=uu, crossing over] & \end{tikzcd}

duality

\begin{tikzcd}
cataK & & & \ \ cata \ar[uu] \ar[dd] & & & \ \ cataB & & & \end{tikzcd}

kind polymorphism

package shadow {

trait Recursive[⟶[_, _], T, F[_]] {
  def  cata[A      ](φ: F[A]       ⟶ A): T ⟶ A
}

trait RecursiveK[⟶[_[_], _[_]], T[_], F[_[_], _]] {
  def cataK[A[_]   ](φ: F[A, ?]    ⟶ A): T ⟶ A
}

trait RecursiveB[⟶[_[_, _], _[_, _]], T[_, _], F[_[_, _], _, _]] {
  def cataB[A[_, _]](φ: F[A, ?, ?] ⟶ A): T ⟶ A
}

kind polymorphism

package shadow {

trait Recursive[⟶[_, _], T, F[_]] {
  def  cata[A      ](φ: F[A]       ⟶ A): T ⟶ A
}

package shadow {

trait Recursive[⟶[_ <: AnyKind, _ <: AnyKind],
                T <: AnyKind,
                F[_ <: AnyKind] <: AnyKind] {
  def cata[A <: AnyKind](φ: F[A] ⟶ A): T ⟶ A
}

kind polymorphism

\begin{tikzcd}
cataK & & & \ \ cata \ar[uu] \ar[dd] & & & \ \ cataB & & & \end{tikzcd}

kind polymorphism

\begin{tikzcd} cata \end{tikzcd}

abstraction

package shadow {

trait Recursive[⟶[_ <: AnyKind, _ <: AnyKind],
                ⟹[_ <: AnyKind, _ <: AnyKind],
                P[_ <: AnyKind, _ <: AnyKind, _ <: AnyKind],
                T <: AnyKind,
                F[_ <: AnyKind] <: AnyKind] {
  def gcata[W[_ <: AnyKind] <: AnyKind, A <: AnyKind]
    (k: P[F, W, ?] ⟹ P[W, F, ?], φ: F[A] ⟶ A)
      : T ⟶ A
}

problems

compiler support
type inference
library support
compile-time cost
cognitive load

all you need

Thanks to …

}}}}}}}}}}}}}}}}}

Formation (@formation_ai),
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,

Scale and Alexy Khrabrov (@ChiefScientist), and

so many others inside and outside the Scala community.

sellout/category-parametric-talk – scale

Files

README.org

Latest commit

History

README.org

File metadata and controls

Duality and How to Delete Half (minus ɛ) of Your Code

Categories and How to Delete 96% (minus ɛ) of Your Code

Who?

Recursion Schemes

the build

the imports

of course …

folds

folds (example)

folds

and unfolds

and unfolds

with variations

with variations

and monads

and monads

and beyond

and beyond

Other dimensions

Elgot

comonad transformers

Getting Back

comonadic folds

comonadic folds

comonadic folds

comonadic folds

comonadic folds

categories

categories

categories

duality

duality

duality

duality

kind polymorphism

kind polymorphism

kind polymorphism

kind polymorphism

abstraction

problems

all you need

Thanks to …