# 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": StringList(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] => Booleandef 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 => Bdef foo[A, B](a: A): B //A => Bdef 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] => Booleandef 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 = falsescala> 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 => Bdef g[B, C]: B => Cdef h[C, D]: C => Ddef 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 = adef 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)Ascala> 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)

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,

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!