Functional Examples 

from

Category Theory


@alissapajer

Overview


The aim of this talk

is to discuss ideas about programming

in the context of Category Theory.


These ideas can be applied to various languages.


Scala syntax will be explained in context.

What is a Program?

All useful code needs IO.

A program inputs a value and outputs a new value.


Examples of  Scala values:

42; "foobar"; List(1,3,5); Some(true); Baz("abc", Foo("xyz"))


What code does is perform value manipulations.

Can we describe code without talking about values?

Abstracting Over Values

Exploiting the commonalities of values


// in Scala, the type of a value is preceded by `:`

42: Int

"foobar": String

List(1,3,5): List[Int]

Some(true): Option[Boolean]

Baz("abc", Foo(-1)): Baz[String, Foo[Int]]


Computations are done at the value level,

but we can think on the type level.

Types Recap


Values are classified as types.


Types are the lowest level abstraction of a value.


A type is like ( * )

A type is an abstract placeholder.

What Can We Do With Types?

Construct functions between them!

// Int => List[Int]
def mkList(value: Int): List[Int] = List(value)


// List[Int] => Boolean
def big(li: List[Int]): Boolean = li.length > 2

Including functions with user-defined types
trait Cow { ... }
def moo(cow: Cow): String = { ... }

Scala Syntax Note


There are two equivalent ways to express

a function from A to B.


// A => B
def foo[A, B](a: A): B 

//A => B
def foo[A, B]: A => B

We will use both, depending on the situation.

Abstraction with Generics


// List[Int] => Option[String] => Either[String, Int]

def foobar(foo: List[Int])(bar: Option[String]): Either[String, Int]

Generic type parameters provide polymetric polymorphism.

// List[A] => Option[B] => Either[B, A]

def foobar[A, B](foo: List[A])(bar: Option[B]): Either[B, A]

We can increase the re-usability of code using generics.

But at the end of the day, it's still functions all the way down


What Can We Do With Functions?

Compose them!

// Int => List[Int]
def mkList(value: Int): List[Int] = List(value)
def mkBigList(value: Int): List[Int] = List(value, value, value)

// List[Int] => Boolean
def big(li: List[Int]): Boolean = li.length > 2


// f(big(a))
def comp(f: Int => List[Int])(a: Int): Boolean = (f andThen big)(a)

scala> comp(mkList _)(42)
res13: Boolean = false

scala> comp(mkBigList _)(42)
res14: Boolean = true
Without composition, functions are lonely islands.

So...


We have types


and functions


and function composition


and where does that leave us?

In the Context of a Category!

We have types.
We have composable functions between types.


TYPES + FUNCTIONS + LAWS = CATEGORY

Scala types and the functions between them
create a Category.

Before we talk about the laws,
let's think about what this means

This Is Amazing!


Every time we write code,
we're already in the context of a Category.


As long as we have types and functions at our disposal,

all of Category Theory applies.


Inside a forest of mathematical abstractions,

hundreds of years of thought, and here we are!



What Are These Laws?

(it's okay to look them up)

1. function composition is associative 

def f[A, B]: A => B
def g[B, C]: B => C
def h[C, D]: C => D

def left[A, D]: A => D = f andThen (g andThen h)
def right[A, D]: A => D = (f andThen g) andThen h
// left == right


2. for every type, we have an identity function such that 

def id[A](a: A): A = a
def f[A, B](a: A): B = { ... }
// id[B](f(x)) == f(id[A](x)) == f(x)
#thereIsOnlyOne

Generalization of a Category

1. Things (Types)

// Int, String, Foo[Bar, Baz]

2. Arrows between Things (Functions)

def foo(i: Int): Int = ???

3. Arrow Composition (Function Composition)

// if A => B and B => C, then A => C

4. Laws regarding Arrows


THINGS + ARROWS + LAWS = CATEGORY

Category Recap


"Category" describes the same

types and functions 

that we already know and love

and

that by no coincidence follow a couple intuitive laws.



Something Fresh

We have types and functions between types. What next?


Constructing fresh types from old:

case class Fresh[A](value: A) { ... }


Constructing fresh functions from old:

def freshF[A, B](f: A => B): Fresh[A] => Fresh[B] = {
  (fa: Fresh[A]) => Fresh(f(fa.value))
}

Is this useful?

New Types From Old

Let's create a type constructor Tree.

sealed trait Tree[A]

case class Leaf[A](value: A) extends Tree[A]
case class Branch[A](left: Tree[A], right: Leaf[A]) extends Tree[A]
case class Empty[A]() extends Tree[A]

New Functions From Old


// (A => B) => (Tree[A] => Tree[B])

def freshF[A, B](f: A => B): Tree[A] => Tree[B] = (ta: Tree[A]) => {
  ta match {
    case Empty() => Empty[B]()
    case Leaf(value) => Leaf(f(value))
    case Branch(left, Leaf(right)) =>
      Branch(freshF(f)(left), Leaf(f(right)))
  }
}

`freshF` is akin to a "function constructor"

Fresh Function Example


// (A => B) => (Tree[A] => Tree[B])

def freshF[A, B](f: A => B): Tree[A] => Tree[B]


scala> def plusHalf = freshF((a: Int) => a + 0.5)
plusHalf: Tree[Int] => Tree[Double]

scala> val tree: Tree[Int] = Branch(Branch(Leaf(5), Leaf(6)), Leaf(7))

scala> plusHalf(tree)
res3: Tree[Double] = Branch(Branch(Leaf(5.5),Leaf(6.5)),Leaf(7.5))

Structure: same.
Leaf values: different.

Endofunctor's Game

In zero gravity, there is no up or down.

So let's reorient ourselves.


What just happened?


1. We started with a Tree[Int]
2. We provided a function Int => Double
3. We returned a Tree[Double]

Endofunctors for Real


An Endofunctor turns every type into a fresh type 

// Int becomes Tree[Int]


and every function into a fresh function 

// (Int => Double) becomes (Tree[Int] => Tree[Double])

and all we need is
def freshF[A, B](f: A => B): Tree[A] => Tree[B]

Computational Contexts

def freshF[A, B](f: A => B): Tree[A] => Tree[B]


`freshF` gives us entry into

the computational context of Tree.


Once were "inside" we can perform computations.

How we enter the context is hidden to the end-user.


Lastly we return a new Tree context.

Terminology

An Endofunctor transforms a Category into itself.

A Functor transforms one Category into another.

(We've seen covariant Functors.)


TYPES + FUNCTIONS + LAWS = CATEGORY


CATEGORY + TRANSFORMATION + LAWS = FUNCTOR


And now, more laws!

Functor Law #1

def freshF[A, B](f: A => B): Tree[A] => Tree[B]


Functors preserve the identity function 

scala> def id[A](a: A): A = a
id: [A](a: A)A

scala> val tree = Branch(Leaf(4),Leaf(5))
tree: Branch[Int] = Branch(Leaf(4),Leaf(5))


scala> freshF(id[Int])(tree)
res8: Tree[Int] = Branch(Leaf(4),Leaf(5))

scala> id[Tree[Int]](tree)
res9: Tree[Int] = Branch(Leaf(4),Leaf(5))

#intuitive

Functor Law #2

def freshF[A, B](f: A => B): Tree[A] => Tree[B]


Functors preserve function composition 

scala> def incr: Int => Double = (a: Int) => a + 0.5
scala> def pos: Double => Boolean = (d: Double) => d > 0

scala> val tree = Branch(Leaf(-2),Leaf(2))


scala> freshF(incr andThen pos)(tree)
res22: Tree[Boolean] = Branch(Leaf(false),Leaf(true))

scala> (freshF(incr) andThen freshF(pos))(tree)
res25: Tree[Boolean] = Branch(Leaf(false),Leaf(true))

Mental Pictures of Kinds


A type is like ( * ) 

// Int, String, List[String], Foo[Bar, Baz[Int]]


A unary type constructor is like ( * -> * ) 

// type constructors: Tree, List, Option
// types: Tree[Int], List[String], Option[Bar]


A type constructor is like ( * -> * ... * -> * ) 

// Foo where the type is Foo[A1, A2, ..., An]

Meta Thoughts


We are thinking in terms of:

Types

Functions

Function Composition

Type Constructors

"Function Constructors"


What thoughts do you have when you think in this way?


Situational Determinism


The languages we use, and the contexts we use them in,

drive our thoughts.


We can put ourselves in a situation where we can

write the kind of code we want to write.

Continuing Onwards...



Now that we've thought about our thoughts,

let's have some more thoughts!

Abstracting Tree

trait Functor[F[_]] {
  def freshF[A, B](f: A => B): F[A] => F[B]  // aka map and fmap
}

implicit object FunctorTree extends Functor[Tree] {
  def freshF[A, B](f: A => B): Tree[A] => Tree[B] = { ... } //defined before
}
 
object Cat {
  def birds[F[_]](init: F[Int])(implicit func: Functor[F]): F[Boolean] =
    func.freshF((a: Int) => a > 5)(init)
}

scala> val tree: Tree[Int] = Branch(Leaf(3), Leaf(155))

scala> Cat.birds[Tree](tree)
res1: Tree[Boolean] = Branch(Leaf(false),Leaf(true))

But Which Functor?

The `birds` function calls `freshF` on a Functor

 it doesn't yet have.


object Cat {
  def birds[F[_]](init: F[Int])(implicit func: Functor[F]): F[Boolean] =
    func.freshF((a: Int) => a > 5)(init)
}

Note:
We could make the Int => Boolean function a parameter of `birds` and even abstract over the types.

Kinds


  A unary type constructor is like ( * -> * ) 

sealed trait Tree[_] { ... }

A Functor is like ( ( * -> *) -> * ) 
trait Functor[F[_]] { ... }

In order to create a Functor,
you need a unary type constructor (e.g. Tree)

Recap


We've seen values, types, type constructors, and Functors.

And we've seen laws.


Implementing the needed methods (e.g. `freshF`) isn't enough.

The methods must adhere to the laws.

Types Are Not Enough


Types can fail us, because we can write a `freshF`

that compiles but breaks the laws.


How on Earth can we begin to enforce these laws?

Proving Laws


Really the question is:

How can we prove that our property holds for *every* value?


We certainly cannot check every value.



Verification Method #1


1. Write a function to test if the law holds, for any given value.


We test if Tree preserves function composition:

def comp[A, B, C](f1: A => B, f2: B => C)(treeA: Tree[A]): Boolean = {
  val c1 = freshF(f1 andThen f2)(treeA)
  val c2 = (freshF(f1) andThen freshF(f2))(treeA)
  c1 == c2
} 

scala> comp((a: Int) => a + 0.5, (d: Double) => d > 6)(Leaf(4))
res1: Boolean = true
You should *never* see this return false (given a sane equals)

Verification Method #2


2. Think about corner cases.


What happens if I compose an identity function with itself?

Does the law hold for the Empty case?


Test the corner cases manually.



Verification Method #3


3. Use a testing framework that

supports checking universal properties

through value generation.

(e.g. ScalaCheck)

Everything isn't a Functor

And that's okay!


If the thing isn't a Functor,

leave a comment explaining why.


We cannot have a Functor that breaks the Functor laws,

because then it's not a Functor.


What is Category Theory?


Category Theory is a rigorous framework for abstraction.


Category Theory defines law-abiding structures that the programmer can implement.


You don't need to know what you have in your hands,

you only need to know some properties that the thing has.

To the Future and Beyond


Category Theory is dense with unexplored abstractions.


We've only begun to apply Category Theory ideas to our programs.


There is so much more to come!




Questions?