Category Theory is not only for mathematicians
Thessaloniki, Voxxed Days 2018
...it is also for Software Developers!
~$ whoami
Thomas Kaliakos
Software Engineer
��
@tkaliakos
thomaska
λ
Agenda
History - Why Category Theory is relevant
Programming is structuring logic
- Composition
- Abstraction
History of programming languages popularity
source: https://en.wikipedia.org/wiki/History_of_programming_languages#First_programming_languages
(If you remember this, probably you are not that young)
Strategy pattern in UML
"Science is knowledge which we understand so well that we can teach it to a computer; and if we don't fully understand something, it is an art to deal with it."�...
"Programming is the art of telling another human being what one wants the computer to do."
�Donald Knuth
Why not use the most well known language to communicate ideas...?
Maths!
Even in Maths there are many ways to structure logic
- Formal logic
- Type Theory
- Category Theory
Or maybe not?
Curry - Howard - Lambek Correspondence
�Natural deduction (logic) ~
Simply typed λ Calculus ~
Category theory
Curry-Howard Correspondence
Interlude: Types are cool!
Using types can be very expressive
import scala.util.Try�
def parseInt(s :String) : Try[Int] = { � Try{s.trim.toInt}�}
def parseInt (s: String): Int = {� s.trim.toInt�}
...
try {� parseInt("invalidString")�} catch {� case e: Exception => -1�}
Using types can be very expressive (2)
def safeHead(ss :List[String]) : Option[String] = {� ss match {� case h::t => Some(h)� case Nil => None� }�}
def safeHead(ss: List[String]): String = {� ss match {� case h::t => h� case Nil => null� }�}
But most importantly can help narrowing down the stuff that can go wrong
def isItWeekendYet(day: String): Boolean = { � day match {� case "Saturday" | "Sunday" => true� case _ => false� }�}
def isItWeekendYet(day: DayOfTheWeek): Boolean = {� day match {� case Saturday | Sunday => true� case _ => false� }�}
sealed trait DayOfTheWeek�case object Monday extends DayOfTheWeek� ...�case object Sunday extends DayOfTheWeek
2∞
27
But most importantly can help narrowing down the stuff that can go wrong in our program (2)
Information flow
Program 1
Test 1
Test 2
Information flow
Program 2
Types
Types
Types
Types
How is everything combined?
- Functional programming is about writing programs using pure functions
- Category theory gives us a way to structure (or "compose") pure functions
- Programming languages with expressive type system make it easy to materialize those abstractions
What is a "pure function"?
Referential Transparency:
If you replace an expression with its bound value, the result does not change
What is a "pure function"? (2)
val s = "low ".toUpperCase
val sTwice = s + s
// ss = LOW LOW
val s = "low ".toUpperCase
val sTwice = "low ".toUpperCase + "low ".toUpperCase
// ss = LOW LOW
What is a "pure function"? (3)
val it = List (1, 2, 3, 4).iterator
val next = it.next()
val res = next + next
// res = 2
val it = List (1, 2, 3, 4).iterator
val res = it.next() + it.next()
// res = 3
What happens with IO?
import scala.io.StdIn
val str = StdIn.readLine()
val res = str + str
// res = VoxxedVoxxed
// Stdin:�// Voxxed�// Days
import scala.io.StdIn
val res = StdIn.readLine() + StdIn.readLine()
// res = VoxxedDays
We can have IO in pure FP
import cats.effect.IO�import scala.io.StdIn�import cats.implicits._
val str = IO(StdIn.readLine())�val res = (str, str).mapN(_ + _)�
// In the end of the world!�// ...�res.unsafeRunSync()
// will read from stdin twice!
Recap
- A Side effect is something that breaks Referential transparency
- Pure Functions do not have side effects
- IO can be done in a purely functional way
- Pure FP means local reasoning, which means compositionality!
What is a Category?
Category
_.toString()
_.toString() compose _ == "2"
Int
String
Boolean
_ == "2"
Option(_)
Option[String]
Category (2)
a
b
d
c
Category C
Category (3)
a
b
d
c
Category C
f
ida
g o f
g
idc
idb
idd
h o f
h
Category (4)
a
b
d
c
ida o f = f o ida= f��
(f o g) o h = f o (g o h) = f o g o h
Category C
f
ida
h o g
g
idc
idb
idd
h
g o f
h o g o f
Category (5)
Category of Types and Functions
def id[A](a:A) = a�
_.toString()
ida
_.toString() compose _ == "2"
idc
idb
idd
Int
String
Boolean
_ == "2"
Option(_)
Option[String]
Monoid?
Is there a pattern here?
- String concatenation: "str1" + "str2" + "str2"
and the empty string ("")
- Integer addition: 1 + 2 + 4�and number zero (0)�
- Integer multiplication: 1 * 2 * 4�and number one (1)
- List concatenation: List(1, 2) ++ List(3, 4) ++ List(5,6)�and the empty list (Nil)
Monoid (2)
In Set theory:
- A set �
- An associative binary operator � (eg "+")
- A Unit (identity - eg "0")
2
9
0
7
4
8
Monoid (3)
a
ida
f
g
Monoid (4)
+0
+4
+2
Int
id(a) = a + 0�
+6
Monoid (5)
trait Monoid[A] {� val id: A
� def compose(a: A, b: A) : A
}
val intMonoid = new Monoid[Int] {
val id = 0
def compose(a: Int, b: Int): Int = a + b
}
Monoid (6)
You have definitely seen them!
val listSum = List(1, 2, 3, 4).fold(0)((a,b) => a + b)
def foldNew[A](list: List[A], m:Monoid[A]): A = { � list match => {� case Nil => m.id� case h::t => m.compose(h, foldNew(t, m))
}
}
Monoid (7)
case class Crate(weight: Int, canBeStacked: Boolean)
val crateMonoid = new Monoid[Crate] {
override val id = Crate(0, true)
override def compose(a: Crate, b: Crate) = {
Crate(a.weight + b.weight,
a.canBeStacked && b.canBeStacked)
}
}
Functors!
Adding "context" into an existing type
Context ��Type | Something might be or not be there | Something we might get in the future | Something might have exploded or not |
Boolean | Option[Boolean] | Future[Boolean] | Try[Boolean] |
Integer | Option[Integer] | Future[Integer] | Try[Integer] |
String | Option[String] | Future[String] | Try[String] |
How do we use all this functions when we use a "Container"
�def stringLength(str: String): Int = str.length
def isEven(num: Int): Boolean = num % 2 == 0
def toString(num: Int): String = num.toString
With map!
Functors are essentially type constructors!
�trait Functor[F[_]] {
def map[A, B] (f: A=>B) (v: F[A]) => F[B]
}
Functors
"A mapping between categories that preserves structure"
a
b
idb
ida
idFb
idFa
D
C
Ff
f
Fb
Fa
F
Functors (2)
a
b
idb
ida
idFb
idFa
D
C
Ff
f
The laws must be satisfied here too!
F(f o g) = Ff o Fg
F id = id F�
Fb
Fa
Functors (3)
a
b
idb
ida
idFb
idFa
D
C
_.map(_.toString)
_.toString
Int
String
ListF
List[Int]
List[String]
Fb
Fa
Conclusions
- Develop deep intuitions about abstractions
- Powerful vocabulary to communicate
- Takes time to built
- See how algebraic structures relate to each other
Where to go next? (1)
Where to go next? (2)
https://www.youtube.com/watch?v=Ss149MsZluI
https://www.youtube.com/watch?v=x3GLwl1FxcA
We 're hiring!
https://www.ovoenergy.com/careers/vacancies
Special mention
This is a job for...
Thank you!
Questions?