Functional examples from category theory: Slides


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.

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?

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.

Values are classified as types.

Types are the lowest level abstraction of a value.

A type is like ( * )

A type is an abstract placeholder.

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 = { ... }

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.
// 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


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.

We have types

and functions

and function composition

and where does that leave us?

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
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!

(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)

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" describes the same

types and functions 

that we already know and love

and

that by no coincidence follow a couple intuitive laws.

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?

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]

// (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"
// (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.

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]

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]

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.

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!

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

Functors preserve the identity function

scala> def id[A](a: A): A = aid: [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

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))



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] 

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?


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.

Now that we've thought about our thoughts,

let's have some more thoughts!

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))


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.


  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)

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 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?

Really the question is:

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

We certainly cannot check every value.


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)

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.


3. Use a testing framework that

supports checking universal properties

through value generation.

(e.g. ScalaCheck)

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.

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.

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!