Why functional programming and category theory strongly matters

Why Functional Programming & Category Theory now strongly matters Piotr Paradziński, ScalaC @pparadzinski https://github.com/lemastero Lublin 2019.03.26

1. Algebraic Data Types (ADT) and basic FP 2. Abstract algebra, ADT, domain modeling 3. Functional pearl: Tutorial of expressivity and universality of fold, G. Hutton 4. Category Theory #1: Category & composition in software design 5. Functor in Category Theory and as FP abstractions: Functor 6. Functional pearl: Monads for functional programming, P. Wadler 7. FP abstractions Apply, Applicative, Flatmap, Monad 8. Effects 9. FP abstractions: Coyoneda trick, Comonads 10. FP abstractions vs OOP patterns 11. Curry-Howard-Lambek Isomorphism & hint about HoTT and Cubical TT 2

● ignore ChallangeX - your mind mind could collapse to black hole (unless u have X+ years XP in Scala FP) ● last man who know all Johann Goethe died 1832 feel free to ask (we have 2019) 3

FP (Clojure, Scheme) ● functions as first class citizens ○ pass functions as parameters to other functions ○ return functions from other functions ○ store functions in variables ● prefere immutability 4

Pure FP ● functions as first class citizens ○ pass functions as parameters to other functions ○ return functions from other functions ○ store functions in variables ● strict immutability (don’t change/update stuff, return copy with modifications) 5

Pure strongly typed FP (Haskell, Scala) ● functions as first class citizens ○ pass functions as parameters to other functions ○ return functions from other functions ○ store functions in variables ● immutability (don’t change/update stuff, return copy with modifications) ● express in type effects (non repeatable operations) ○ exceptions ○ read/write from disc, network, DB, etc ○ generate random numbers ○ get current time 6

Algebraic Data Types in Scala 7

product type (tuple, pair) - cartesian product case class Tuple[A, B](_1: A, _2: B) 8

product type (tuple, pair) - cartesian product case class Tuple[A, B](_1: A, _2: B) val foo = Tuple(42, "foo") val foo2 = (42, "foo") 9

product type (tuple, pair) - cartesian product case class Tuple[A, B](_1: A, _2: B) val foo = Tuple(42, "foo") val a42: Int = foo._1 val afoo: String = foo._2 10

sum type (either, xor) sealed trait Either[A,B] case class Left[A,B](a: A) extends Either[A,B] case class Right[A,B](b: B) extends Either[A,B] 11

sum type (either, xor) sealed trait Either[A,B] case class Left[A,B](a: A) extends Either[A,B] case class Right[A,B](b: B) extends Either[A,B] val error = Left("oh boy connection lost") val value = Right(42) 12

sum type (either, xor) sealed trait Either[A,B] case class Left[A,B](a: A) extends Either[A,B] case class Right[A,B](b: B) extends Either[A,B] val error = Left("oh boy connection lost") val value = Right(42) Left("truth") != Right("truth") // discriminated union 13

unit type (one, most boring type ever) case object Unit 14

unit type (one, most boring type ever) case object Unit val boring = Unit 15

unit type (one, most boring type ever) case object Unit val boring = Unit def foo: Unit = ??? // how many implementations? 16

void type (invented in Haskell to confuse Java devs) final abstract class Void private () 17

void type (invented in Haskell to confuse Java devs) final abstract class Void private () val a: Void = ??? // can we implement this ? 18

void type (invented in Haskell to confuse Java devs) final abstract class Void private () // Nothing is close enough replacement :) // discussion about different implementations: https://github.com/scalaz/scalaz/issues/1491 19

ADT = Abstract Data Types ● classes with only public getters - immutable ● consist only from product and sum types sealed trait Graph[A] case object Empty extends Graph[Nothing] case class Vertex[A](a: A) extends Graph[A] case class Overlay[A](lhs: Graph[A], rhs: Graph[A]) extends Graph[A] case class Connect[A](lhs: Graph[A], rhs: Graph[A]) extends Graph[A] Algebraic Graphs with Class - Andrey Mokhov 2017 eprint.ncl.ac.uk/file_store/production/239461/EF82F5FE-66E3-4F64-A1AC-A366D1961738.pdf 20

Abstract Algebra - Semigroup trait Semigroup[M] { def combine(lhs: M, rhs: M): M } ● associativity law: combine(a, combine(b, c)) == combine(combine(a, b), c) ● example: 7 + (3 + 14) == (7 + 3) + 14 21

Abstract Algebra - Monoid trait Monoid[M] extends Semigroup[M] { def empty: M def combine(lhs: M, rhs: M): M } ● associativity law: combine(a, combine(b, c)) == combine(combine(a, b), c) ● identity law: combine(a, empty) == combine(empty, a) == a 22

Abstract Algebra - Commutative Monoid trait Monoid[M] extends Semigroup[M] { def empty: M def combine(lhs: M, rhs: M): M } ● associativity law: combine(a, combine(b, c)) == combine(combine(a, b), c) ● identity law: combine(a, empty) == combine(empty, a) == a ● commutativity law: combine(a, b) == combine(b, a) 23

is product a Semigroup ? // (A * B) * C = (A * B) * C val isAssociative: Boolean = (("a", "b"), "c") == ("a", ("b", "c")) 24

product is Semigroup up to isomorphism // (A * B) * C = (A * B) * C def assoc1[A,B,C](abc: ((A,B), C)): (A, (B,C)) = { case((a,b), c) => (a, (b,c)) } def assoc2[A,B,C](abc: (A, (B,C))): ((A,B), C) = { case(a, (b,c)) => ((a,b), c) } val isAssociativeUpToIsomorphism: Boolean = (("a", "b"), "c") == assoc2(("a", ("b", "c"))) 25

(product, Unit) is Monoid up to isomorphism // (A * 1) = (1 * A) = A def leftId[A](x: (A, Unit)): A = x._1 def leftId_inv[A](a: A): (A, Unit) = (a, ()) def rightId[A](x: (Unit, A)): A = x._2 def rightId_inv[A](a: A): (Unit, A) = ((), a) 26

(product, Unit) is Monoid up to isomorphism // commutative // A * B = B * A def swap[A,B](abc: (A,B)): (B,A) = { case(a,b) => (b, a) } 27

(Unit, product) is Commutative Semigroup associativity (A * B) * C = (A * B) * C using def assoc((a,b),c) = (a, (b,c)) identity A * 1 = 1 * A = A (a, ()) ((), a) ~ a commutative A * B = B * A (a,b) is (b,a) using swap(a,b) = (b, a) so Abelian Semigroup ! (up to isomorphism) 28

Algebra of Types (Void, sum) is Abelian Semigroup associativity (A + B) + C = (A + B) + C Either((a,b),c) ~ Either(a, (b,c)) identity A + 1 = 1 + A = A Either(a, Void) ~ Either(a, Void) ~ a commutative A + B = B + A Either(a,b) is Either(b,a) so Abelian Semigroup ! (up to isomorphism) 29

Algebra of Types - distribution law and multiply 0 distribution law A * (B + C) = (A * B) + (A * C) (a, Either(b,c)) ~ Either((a, c), (b,c)) multiply by 0 A * 0 = 0 * A = 0 (a, Void) ~ (a, Void) ~ Void 30

Moar !11!!! about Algebra of ADT ● School of Haskell - Sum Types - Gabriel Gonzales ○ https://www.schoolofhaskell.com/school/to-infinity-and-beyond/pick-of-the-week/sum-types ● Category Theory 5.2 Algebraic data types - Bartosz Milewski (lists) ○ https://www.youtube.com/watch?v=w1WMykh7AxA ● London Haskell - The Algebra of Algebraic Data Types - Christ Taylor (lists, trees, zipper) ○ https://www.youtube.com/watch?v=YScIPA8RbVE ● The Derivative of a Regular Type is its Type of One-Hole Contexts ○ http://strictlypositive.org/diff.pdf 31

Modeling in FP using ADT vs modeling in OOP 32

ADT = Abstract Data Types ● classes with only public getters - immutable ● consist only from product and sum types 33

OOP model version 1 class Bar {} class Foo { def doMagic(bar: Bar): Int = ??? } 34

instance method ~ function with extra param // OOP class Bar {} class Foo { def doMagic(bar: Bar): Int = ??? } // FP case class Bar() case class Foo() def doMagic(foo: Foo, bar: Bar): Int = ??? 35

OOP model version 2 (assigning responsibilities) class Bar {} class Foo { def doMagic(bar: Bar): Int = ??? } // no doMagic should belong to Bar not Foo class Bar { def doMagic2(bar: Foo): Int = ??? } class Foo {} 36

OOP model 2 => FP model // OOP class Bar { def doMagic2(bar: Foo): Int = ??? } class Foo {} // FP case class Bar() case class Foo() def doMagic2(bar: Bar, foo: Foo): Int = ??? 37

FP model 1, model 2 case class Bar() case class Foo() // model 1 def doMagic(foo: Foo, bar: Bar): Int = ??? // model 2 def doMagic2(bar: Bar, foo: Foo): Int = ??? 38

state without methods allow you to change your mind about responsibility, without touching model case class Bar() case class Foo() // model 1 def doMagic(foo: Foo, bar: Bar): Int = ??? // model 2 def doMagic2(bar: Bar, foo: Foo): Int = doMagic(foo, bar) 39

discovered in 1975 in Scheme ● in context of actor model (and message passing is ~ calling object method) and running functions (~ lambda calculus): https://en.wikisource.org/wiki/Scheme:_An_Interpreter_for_Extended_Lambda_Calculus/Whole_text 40

OOP modeling vs FP - expression problem ● in OOP you cannot solve expression problem, otherwise than using Visitor pattern ● in FP one can use type class to solve it ● Tony Morris - The Expression Problem and Lenses ( next time :) ) ○ https://www.youtube.com/watch?v=UXLZAynA0sY ● Hacker News - The Expression Problem and its solutions ○ https://news.ycombinator.com/item?id=11683379 41

FP in Scala Lists and superpowers of fold http://www.cs.nott.ac.uk/~pszgmh/fold.pdf 42

Graham Hutton - A tutorial on the universality and expressiveness of fold fold - gives us superpowers ● writing proofs for functions on List without using induction ● define how to refactor list functions using fold fold has luxury houses: ● universal property ● fusion property fold is in general badass (great expressive power) 43

FP lists - definition sealed trait List[A] case object Nil extends List[Nothing] case class Cons[A](h: A, t: List[A]) extends List[A] // Haskell data List t = Nil | Cons :: List t 44

FP lists - sum def sum(xs: List[Int]): Int = { xs match { case Nil => 0 case Cons(head, tail) => head + sum(tail) } } 45

FP lists - product def product(xs: List[Int]): Int = { xs match { case Nil => 1 case Cons(head, tail) => head * product(tail) } } 46

FP lists - refactor common parts into - fold def fold[A,B](f: (A,B) => B, init: B, xs: List[A]): B = { xs match { case Nil => init case Cons(head, tail) => f(head, fold(f, init, tail)) } } 47

FP lists - fold def fold[A,B](f: (A,B) => B, init: B, xs: List[A]): B = { xs match { case Nil => init case Cons(head, tail) => f(head, fold(f, init, tail)) } } def sum(xs: List[Int]): Int = fold[Int, Int](_ + _, 0, xs) def product(xs: List[Int]): Int = fold[Int, Int](_ * _, 1, xs) 48

FP - fold universal property - those are equivalent def g(xs: List[B]): A = xs match { case Nil => v case Cons(h,t) => f(h,g(t)) } g(xs) == fold[B,A](f, v, xs) 49

FP - fold universal property - those are equivalent def g(xs: List[B]): A = xs match { case Nil => v case Cons(h,t) => f(h,g(t)) } g(bs) == fold[B,A](f, v, bs) … and definition g is unique 50

FP - fold universal property - those are equivalent def g(xs: List[B]): A = xs match { case Nil => v case Cons(h,t) => f(h,g(t)) } g(xs) == fold[B,A](f, v, xs) def product(xs: List[Int]): Int = xs match { case Nil => 1 case Cons(head, tail) => head * product(tail) } def product(xs: List[Int]): Int = fold[Int, Int](_ * _, 1, xs) 51

Challenge fold all the things ● define filter using fold ● define map using fold ● define reverse using fold 52

Challenge X fusion property ● express fusion property in Scala 53

fold .. can we make it more general? def fold[A,B](f: (A,B) => B, init: B, xs: List[A]): B = { xs match { case Nil => init case Cons(head, tail) => f(head, fold(f, init, tail)) } } 54

fold .. we can make and abstraction from it trait Foldable[F[_]] { def foldLeft[A, B](fa: F[A], b: B)(f: (B, A) => B): B } // F[_] is a type constructor 55

type constructor ascala> :k List List's kind is F[+A] scala> :k Int Int's kind is A scala> :k List[Int] List[Int]'s kind is A 56

Foldable for List trait Foldable[F[_]] { def foldLeft[A, B](fa: F[A], b: B)(f: (B, A) => B): B } val listFoldable: Foldable[List] = new Foldable[List] { def foldLeft[A, B](fa: List[A], b: B)(f: (B, A) => B): B = { fa.foldLeft(b)(f) } } 57

Foldable - folding using Monoid def fold[A](fa: F[A])(implicit A: Monoid[A]): A = foldLeft(fa, A.empty) { (acc, a) => A.combine(acc, a) } https://github.com/lemastero/scala_typeclassopedia#foldable Let’s take a look (wiki, Cats, Scalaz) 58

Abstract algebra - MOAR POWAH ! 59

Monoids - Graphic library - diagrams https://repository.upenn.edu/cgi/viewcontent.cgi?referer=&httpsredir=1&ar ticle=1773&context=cis_papers https://www.youtube.com/watch?v=X-8NCkD2vOw Monoids: Theme and Variations (Functional Pearl) Brent Yorgey 2012 Haskell Symposium 60

*-semirings, Kleene Algebra http://r6.ca/blog/20110808T035622Z.html (Haskell) A Very General Method of Computing Shortest Paths 2011, Russel O’Connor https://vimeo.com/96644096 (Scala) Regexes, Kleene Algebras, and Real Ultimate Power! 2014 flatMap, Erik Osheim 61

United monoids - efficient graph operations https://blogs.ncl.ac.uk/andreymokhov/an-algebra-of-graphs/ Algebra of Parametrised Graphs (Functional Pearl) Andrey Mokhov 2017 Haskell Symposium 62

Inverse semigroup - Checking parents match https://www.youtube.com/watch?v=d7JPz3Vq9YI https://www.youtube.com/watch?v=HGi5AxmQUwU Edward Kmett Lambda World 2018 63

Category Theory - Categories 64

Category ● objects: A, B, C, ... ● morphisms (arrows) f: A-> B ● ... 65

Category ● objects: A, B, C, ... ● morphisms (arrows) f: A-> B ● for every object there is identity morphism ○ id : A -> A ● ... 66

Category ● objects: A, B, C, ... ● morphisms (arrows) f: A-> B ● for every object there is identity morphism ○ id : A -> A ● composition for every morphisms f: A -> B, g: B -> C exists ○ (g . f) : A -> C 67

Category ● objects: A, B, C, ... ● morphisms (arrows) f: A-> B ● for every object there is identity morphism ○ id : A -> A ● composition for every morphisms f: A -> B, g: B -> C exists ○ (g . f) : A -> C ● associativity, for every morphisms f: A -> B, g: B -> C, h: C -> D ○ h . (g . f) = (g . h) . f 68

Category - identity, composition, associativity 71

Category of Scala types and functions objects - types morphisms - functions identity for A - identity[A] composition g f - f compose g PS did I miss any arrow or two? 72

When types and functions does not form Category? ● throwing exceptions def get[A](index: Int, xs: List[A]): A = xs(index) ● input output (network communication, disc read/write, DB calls, console) def readline(): String = scala.io.StdIn.readLine() ● changing/depending on external state that can be changed def now() = java.time.LocalDateTime.now() 73

Equation reasoning = superpowers from Category ● parallelism does not require PhD (you can write few parallel algorithms every day) ○ Umut Acar 2018 OSSPL https://www.cs.uoregon.edu/research/summerschool/summer18/topics.php ● writing unit tests is trivial (no mocks, no xUnit Patterns) ○ pass argument, check output ● understand == read types (no need for analyzing state somewhere, implementations of sub function) ● reusability is trivial 74

Category of RDBMS objects - tables morphisms - connect tables using FK identity for A - PK composition g f - combine FK conditions https://www.youtube.com/watch?v=fTporauBJEs Categorical Databases David I. Spivak 75

Category of states of UI and user actions objects - states of user interface of web application morphisms - user actions id morphism - user stare at screen :) composition - performing particular set of actions Is this a category? What if it is a CMS (Liferay, Joomla) with multiple users? 76

Category of rows in table with PK and <= ● entities in RDBMS with natural number as PK with <= ● entities in RDBMS with created_timestamp as PK <= ● entities in RDBMS with UUID as PK with <= Hint: those are Posets (Partially Ordered Sets) 77

OOP Challenge - Category of components and ? objects - software components morphisms - ??? Hints: - does Adapter pattern help? - does Facade pattern help? - what is reusable in reusable components? - is there a Category of microservices and ... 78

Challenge X 3-category of Scala types Given Category of Scala types (as objects) and functions (as morphisms). Define 3-category based on this. ● give example of 2-morphisms and composition of them ● give example of 3-morphisms and composition of them Hint ● Tom Leinster “An Introduction to n-Categories” https://www.youtube.com/watch?v=6bnU7_6CNa0 79

Composition in FP == composing functions ● composing in FP == composing functions ● but exceptions, mutable state, IO are handy: ○ showing stuff to user ○ talking to HTTP ○ reading configs from disc ○ reading/writing to NoSQL or DB…. ● what’s practical in Category definition? 80

Problem - simple OOP program - model case class Pet(name: String) case class Owner(id: Long, var pets: ListBuffer[Pet]) case class InvalidOwnerId(msg: String) extends RuntimeException(msg) 81

Problem - simple OOP program - storage case class PetRepository() { def updateOwner(o: Owner): () = ??? def getOwner(id: Long): Owner = { if (id < 0) throw InvalidOwnerId("Invalid id") // query DB/NoSQL/microservice ??? } } 82

Problem - simple OOP program - service def addPet(ownerId: Long, pet: Pet): Unit = { val repo = PetRepository() // probably from DI framework val owner = repo.getOwner(ownerId) owner.pets = owner.pets += pet repo.updateOwner(owner) } 83

Problem - OOP solution - depend on abstraction trait PetRepository { def updateOwner(o: Owner): () def getOwner(id: Long): Owner } 84

Problem - simple OOP program - concrete impl case class PetRepositoryJDBC() extends PetRepository { def updateOwner(o: Owner): () = ??? def getOwner(id: Long): Owner = { if (id < 0) throw InvalidOwnerId("Invalid id") ??? } } 85

Problem - OOP solution - depend on abstraction (testable) def addPet(ownerId: Long, pet: Pet, repo: PetRepository): () = { val owner = repo.getOwner(ownerId) owner.pets = owner.pets += pet repo.updateOwner(owner) } val repo: PetRepository = ??? // get by DI addPet(42, Pet("fluffy"), ???) 86

“Better Java” ● nice syntax for POJO/JavaBeans ● nice syntax for lambdas ● you can add methods to existing class, without touching them 87

FP solution 1 - immutability 1/2 case class Owner(id: Long, pets: List[Pet]) def addPet(ownerId: Long, pet: Pet, repo: PetRepository): () = { val owner = repo.getOwner(ownerId) val newPets = pet :: owner.pets val newOwner = owner.copy(pets = newPets) repo.updateOwner(newOwner) } 88

FP solution 1 - immutability 2/2 val repo: PetRepository = ??? // summon using Spring val uo = addPet(42, Pet("fluffy"), repo) 89

FP solution 2 - immutability + describe effect (1/2) case class UpdateOwner(newOwner: Owner, repo: PetRepository) def addPet(ownerId: Long, pet: Pet, repo: PetRepository): UpdateOwner = { val owner = repo.getOwner(ownerId) val newPets = pet :: owner.pets val newOwner = owner.copy(pets = newPets) UpdateOwner(newOwner, repo) } 90

FP solution 2 - immutability + describe effects 2/2 // our program don’t do anything it just descriptions stuff! val uo = addPet(42, Pet("fluffy"), repo) // at the end of the world (... in main) val repo: PetRepository = ??? // read config, create JDBC repo uo.repo.updateOwner(uo.newOwner) // do some changes 91

FP solution 2 - higher order functions (HOF) def addPet(ownerId: Long, pet: Pet, getOwner: Long => Owner, updateOwner: Owner => Unit): () = { val owner = getOwner(ownerId) val newPets = pet :: owner.pets val newOwner = owner.copy(pets = newPets) updateOwner(newOwner) } 92

FP solution 2 - higher order functions (HOF) def addPet(ownerId: Long, pet: Pet, getOwner: Long => Owner, updateOwner: Owner => Unit): () = { val owner = getOwner(ownerId) val newPets = pet :: owner.pets val newOwner = owner.copy(pets = newPets) updateOwner(newOwner) } ● could we return description? ● do we depend in here on Repository interface? 93

higher order functions (HOF) HOF == loose coupling for free !!! 4 life !!! for all !!! 94

FP tricks ● do not run - create description + at the end of the world - interpret it (Interpreter pattern?) ● do not modify state in place, use immutable objects/collections with update on copy ● use expressions (return interesting stuff) not statements (return boring stuff) ● use higher order functions (lambda expressions in Java) ● do not throw exceptions (wait I did not show that !) 95

FP tricks pros and cons ● Higher Order Functions ○ testability ○ loose coupling (and free beer if your name is Homer) ○ can be hard to understand without good naming ○ harder to find them (not attached to class instance, no IDE support) ● create description ○ testability ○ multiple interpreters (create documentation, tweak performance) ○ slower than running ○ can be harder to understand (why did not run) ● immutability ○ no concurrency bugs (live locks, dead locks, no heisenbus) ○ friendly for parallel computing ○ can be faster than mutable in place ○ can be slower than mutable in place 96

Functor in Category Theory Functor F: C -> D from Category C to Category D is a mapping of: ● objects: C -> D ● morphisms C -> D that preserve structure, meaning: ● F preserve identity F(id(x)) = id(F(a)) ● F preserve composition F(g . f) = F(g) . F(f) 98

Functor in Scala - interface trait Functor[F[_]] { def map[A, B](fa: F[A])(fun: A => B): F[B] } 99

Functor in Scala - Implementation for Identity case class Id[A](value: A) val idFunctor: Functor[Id] = new Functor[Id] { def map[A, B](wrapper: Id[A])(fab: A => B): Id[B] = { val a: A = wrapper.value val b: B = fab( a ) Id( b ) } } 100

List as Functor - custom implementation val listFunctorCust: Functor[List] = new Functor[List]() { def map[A, B](fa: List[A])(ab: A => B): List[B] = fa match { case Nil => Nil case head :: tail => ab(head) :: map(tail)(ab) } } 101

Option as Functor - custom implementation val optionFunctorCust: Functor[Option] = new Functor[Option]() { def map[A, B](opt: Option[A])(ab: A => B): Option[B] = opt match { case None => None case Some(v) => Some( ab(v) ) } } 102

List Functor - examples no typeclass sugar import cats.Functor import cats.implicits._ Functor[List].map(List(2, 3, 4))(isOdd) == List(false, true, false) Functor[Option].map(Option(42))(isOdd) == Option(false) val myId: Id[Int] = 42 Functor[Id].map(myId)(isOdd) == false 103

Option as Functor - Option already have map val optionFunctor: Functor[Option] = new Functor[Option]() { def map[A, B](fa: Option[A])(f: A => B): Option[B] = fa map f } 104

List as Functor - List already have map val listFunctor: Functor[List] = new Functor[List]() { def map[A, B](fa: List[A])(f: A => B): List[B] = fa map f } 105

List already has map - examples no typeclass sugar import cats.Functor import cats.implicits._ List(2, 3, 4).map(isOdd) == List(false, true, false) Option(42).map(isOdd) == Option(false) val myId: Id[Int] = 42 Functor[Id].map(myId)(isOdd) == false 106

…. so List Functor gives us more complicated way to invoke map function - doh! List(2, 3, 4).map(isOdd) == List(false, true, false) Option(42).map(isOdd) == Option(false) val myId: Id[Int] = 42 // and use useless types !!! Functor[Id].map(myId)(isOdd) == false 107

List Functor - derived methods FTW import cats.syntax.functor._ import cats.implicits._ List(2, 3, 4).void == List((), (), ()) List(2, 3, 4).as("foo") == List("foo", "foo", "foo") List(2, 3, 4).fproduct(isOdd) == List((2, false), (3, true), (4, false)) 108

Option Functor - derived methods FTW import cats.syntax.functor._ import cats.implicits.catsStdInstancesForOption Option(42).void == Option(()) Option(42).as("foo") == Option("foo") Option(42).fproduct(isOdd) == Option((42, false)) 109

Vector Functor - derived methods FTW import cats.syntax.functor._ import cats.implicits.catsStdInstancesForVector Vector(2, 3, 4).void == Vector((), (), ()) Vector(2, 3, 4).as("foo") == Vector("foo", "foo", "foo") Vector(2, 3, 4).fproduct(isOdd) == Vector((2, false), (3, true), (4, false)) 110

Functor must obey laws def identityLaw[A](fa: F[A]): Boolean = { map(fa)(identity) == fa } def compositionLaw[A, B, C](fa: F[A], f: A => B, g: B => C): Boolean = { map(map(fa)(f))(g) == map(fa)(f andThen g) } 111

Functor - identity law def identityLaw[A](fa: F[A]): Boolean = { // identity // F[A] =================> F[A] val l: F[A] = map(fa)(identity) val r: F[A] = fa l == r } 113

Functor - composition law def covariantComposition[A, B, C](fa: F[A], f: A => B, g: B => C): Boolean = { // f // F[A] ========> F[B] val l1: F[B] = map(fa)(f) // g // F[B] =========> F[C] val l2: F[C] = map(l1)(g) // f andThen g // F[A] ==============> F[C] val r: F[C] = map(fa)(f andThen g) l2 == r } 114

Functor in Scala vs Functor in Ct ● type constructor map objects (types): A -> F[A] F[_] ● map function maps morphisms (functions) f: A -> B ----> map(f): F[A] -> F[B] def map[A, B](fa: F[A])(fun: A => B): F[B] 115

Option is Functor in cat. of Scala types and funs identity[String] -> map(identity[String]) is identity for Option[String] ? map(apply . length) is the same as map(length) . map(apply) ? 116

Composing Functors import cats.Functor import cats.implicits.catsStdInstancesForList import cats.implicits.catsStdInstancesForOption val listOption = Functor[List] compose Functor[Option] import listOption.map map(List(Some(42), Some(15), None))(isOdd) == List(Some(false), Some(true), None) 117

Challenge - Lazy Functor type Thunk[A] = () => A val thunkFunctor: Functor[Thunk] = new Functor[Thunk] { def map[A, B](fa: Thunk[A])(f: A => B): Thunk[B] = ??? } 118

Challenge - Whatever Functor case class Const[A,B](a: A) def constFunctor[X]: Functor[Const[X, ?]] = new Functor[Const[X,?]] { def map[A, B](fa: Const[X, A])(f: A => B): Const[X, B] = ??? } 119

Challenge - Working back val predicateContravariant: Contravariant[Predicate] = new Contravariant[Predicate] { def contramap[A, B](pred: Predicate[A])(fba: B => A): Predicate[B] = Predicate[B](fba andThen pred.fun) } case class Predicate[A](fun: A => Boolean) ● define trait Contravariant ● define laws for Contravariant ● define Contravariant[? => X] ● why there is no Functor[? => X] 120

Challenge X - ekmett/discrimination in Scala ● Contravariant functors are used by Edward Kmett to implement discrimination sorting in linear time ● Github repo (Haskell) https://github.com/ekmett/discrimination/ ● video (dense Category Theory) https://www.youtube.com/watch?v=cB8DapKQz-I 121

Challenge X - Opposite twins trait Profunctor[P[_, _]] { def dimap[A,B,C,D](f: A => B, g: C => D): P[B, C] => P[A, D] def lmap[A,B,C](f: ???): ??? = dimap(f,identity[C]) def rmap[A,B,C](g: ???): ??? = dimap[A,A,B,C](identity[A], g) } trait Bifunctor[P[_,_]] { def bimap[A,B,C,D](f: A => B, g: C => D): P[A, C] => P[B, D] def first[A,B,C](f: ???): ??? = bimap(f, identity) def second[A,B,C](g: ???): ??? = bimap(identity, g) } ● fill missing types in definitions of Bifunctor and Profunctor (???) ● define laws for Bifunctor ● define laws for Profunctor ● can you extract common part from Profunctor and Bifunctor ● define instance for ○ Profunctor[? => ?] ○ Bifunctor[(?, ?)] ○ Bifunctor[Either(?,?)] 122

Challenge X - Ran Kan Fun trait Ran[G[_], H[_], A] { def runRan[B](f: A => G[B]): H[B] } def ranFunctor[G[_], H[_]]: Functor[Ran[G, H, ?]] = { new Functor[Ran[G, H, ?]] { def map[A, B](fa: Ran[G, H, A])(f: A => B): Ran[G, H, B] = ??? } } ● (warmup) replace all H occurences by G and implement ranFunctor ● implement ranFunctor (Functor for Right Kan Extension) 123

Monads https://www.youtube.com/watch?v=M258zVn4m2M Scala: Runar, Composable application architecture with reasonably priced monads https://www.youtube.com/watch?v=yjmKMhJOJos Haskell: Philip Wadler - The First Monad Tutorial 125

So you want to make another talk about Monads “It is doubtful that Monads have been discovered without the insight afforded by category theory.” Philip Wadler ● Monad tutorials timeline ○ https://wiki.haskell.org/Monad_tutorials_timeline ● why writing Monad tutorial is not such a bad idea ○ https://byorgey.wordpress.com/2009/01/12/abstraction-intuition-and-the-monad-tutorial-fallacy/ 126

Monads - ADT for simple expressions sealed trait Term case class Con(value: Int) extends Term case class Div(lhs: Term, rhs: Term) extends Term 128

Monads - evaluation for simple expressions def eval(term: Term): Int = term match { case Con(a) => a case Div(lhs, rhs) => eval(lhs) / eval(rhs) } 129

Monads - examples for evaluation val answer = Div( Div(Con(1972), Con(2)), Con(23) ) // 42 println(eval(answer)) val error = Div(Con(1), Con(0)) println( Try(eval(error)) ) // error 130

Monads - Variant 1 - Exceptions type Exception = String sealed trait M[A] case class Raise[A](exception: Exception) extends M[A] case class Return[A](a: A) extends M[A] 131

Monads - Variant 1 - Exceptions def eval(term: Term): M[Int] = term match { case Con(a) => Return(a) case Div(lhs, rhs) => eval(lhs) match { case Raise(e) => Raise(e) case Return(a) => eval(rhs) match { case Raise(e) => Raise(e) case Return(b) => if(b == 0) Raise("divide by zero") else Return(a / b) } } } 132

Monads - Variant 1 - Exceptions val answer = Div( Div(Con(1972), Con(2)), Con(23) ) println(eval(answer)) // Rerurn(42) val error = Div(Con(1), Con(0)) println( Try(eval(error)) ) // Raise("divide by zero") 133

Monads - Variant 2 - State type State = Int // Initial state => (coputed value, new state) type M[A] = State => (A,State) 134

Monads - Variant 2 - State def eval(term: Term): M[Int] = term match { case Con(a) => x => (a, x) case Div(lhs, rhs) => x => val (a,y) = eval(lhs)(x) val (b,z) = eval(rhs)(y) (a / b, z + 1) } 135

Monads - Variant 2 - State val answer = Div( Div(Con(1972), Con(2)), Con(23) ) println(eval(answer)) // (42, 2) 136

Monads - Variant 3 - Trace of execution type Output = String type M[A] = (Output, A) 137

Monads - Variant 3 - Trace of execution def line(t: Term, i: Int): String = s"eval ($t) <= $in" def eval(term: Term): M[Int] = term match { case Con(a) => (line(Con(a), a), a) case Div(lhs, rhs) => val (x,a) = eval(lhs) val (y,b) = eval(rhs) (x ++ y ++ line(Div(lhs, rhs), a/b), a / b) } 138

Monads - Variant 3 - Trace of execution val answer = Div( Div(Con(1972), Con(2)), Con(23) ) eval (Con(1972)) <= 1972 eval (Con(2)) <= 2 eval (Div(Con(1972),Con(2))) <= 986 eval (Con(23)) <= 23 eval (Div(Div(Con(1972),Con(2)),Con(23))) <= 42 println(eval(answer)._1) 139

Monads - Here comes the Monad! trait Monad[F[_]] { def unit[A](a: A): F[A] def flatMap[A,B](ma: F[A])(f: A => F[B]): F[B] } 140

Monads - fancy way to do what we already can! type Id[A] = A val idMonad: Monad[Id] = new Monad[Id] { def unit[A](a: A): Id[A] = a def flatMap[A, B](ma: Id[A])(f: A => Id[B]): Id[B] = f(ma) } 141

Monads - fancy way to do what we already can! type Id[A] = A val idMonad: Monad[Id] = new Monad[Id] { def unit[A](a: A): Id[A] = a def flatMap[A, B](ma: Id[A])(f: A => Id[B]): Id[B] = f(ma) } def eval[M[_]](term: Term)(implicit MM: Monad[M]): M[Int] = term match { case Con(a) => MM.unit(a) case Div(lhs, rhs) => MM.flatMap( eval(lhs) )(a => MM.flatMap( eval(rhs) )(b => MM.unit(a / b)) )} 142

Monads - fancy way to do what we already can! type Id[A] = A val idMonad: Monad[Id] = new Monad[Id] { def unit[A](a: A): Id[A] = a def flatMap[A, B](ma: Id[A])(f: A => Id[B]): Id[B] = f(ma) } def eval[M[_]](term: Term)(implicit MM: Monad[M]): M[Int] = term match { case Con(a) => MM.unit(a) case Div(lhs, rhs) => MM.flatMap( eval(lhs) )(a => MM.flatMap( eval(rhs) )(b => MM.unit(a / b)) )} println( eval(answer)(idMonad) ) 143

Monads - Variant 2 - Exceptions with MonadError type Exception = String sealed trait Validated[+A] case class Raise[A](exception: Exception) extends Validated[A] case class Return[A](a: A) extends Validated[A] 144

Monads - Variant 2 - Exceptions with MonadRaise type Exception = String sealed trait Validated[+A] case class Raise[A](exception: Exception) extends Validated[A] case class Return[A](a: A) extends Validated[A] trait MonadErr[F[_]] extends Monad[F] { def raise[A](e: Exception): F[A] } 145

Monads - Variant 2 - Exceptions with MonadRaise trait MonadErr[F[_]] extends Monad[F] { def raise[A](e: Exception): F[A] } val exceptionMonad: MonadErr[Validated] = new MonadErr[Validated] { def unit[A](a: A): Validated[A] = Return(a) def flatMap[A, B](ma: Validated[A])(f: A => Validated[B]): Validated[B] = ma match { case Raise(e) => Raise(e) case Return(a) => f(a) } def raise[A](e: Exception): Validated[A] = Raise(e) } 146

Monads - Variant 2 - Exceptions with MonadRaise def eval[M[_]](term: Term)(implicit MM: MonadErr[M]): M[Int] = term match { case Con(a) => MM.unit(a) case Div(lhs, rhs) => MM.flatMap( eval(lhs) )(a => MM.flatMap( eval(rhs) )(b => if(b == 0) MM.raise[Int]("divide by zero") else MM.unit(a / b) ))} println( eval(answer)(exceptionMonad) ) val error = Div(Con(1), Con(0)) 147

MonadRaise - so we have new abstraction trait MonadRaise[F[_]] extends Monad[F] { def raise[A](e: Exception): F[A] } trait FunctorRaise[F[_]] extends Monad[F] { def raise[A](e: Exception): F[A] } ● this is advanced abstraction from MTL: https://typelevel.org/cats-mtl/mtl-classes/functorraise.html 148

Monads - Variant 2 - Output with MonadTell type Output = String type Writer[A] = (Output, A) trait MonadTell[F[_]] extends Monad[F] { def tell(x: Output): F[Unit] } 149

Monads - Variant 2 - Output with MonadTell val writerMonadOut: MonadTell[Writer] = new MonadTell[Writer] { def unit[A](a: A): (Output, A) = ("", a) def flatMap[A, B](m: (Output, A))(k: A => (Output, B)): (Output, B) = { val (x,a) = m val (y,b) = k(a) (x ++ y, b) } def tell(x: Output): Writer[Unit] = (x, ()) } 150

Monads - Variant 2 - Output with MonadTell def eval[M[_]](term: Term)(implicit MM: MonadTell[M]): M[Int] = term match { case Con(a) => { val out1 = line(Con(a),a) val out2 = MM.tell(out1) MM.flatMap(out2)(_ => MM.unit(a)) } case Div(lhs, rhs) => MM.flatMap( eval(lhs) )(a => MM.flatMap( eval(rhs) )(b => { val out1 = line(Div(lhs, rhs), a/b) val out2 = MM.tell(out1) MM.flatMap(out2)(_ => MM.unit(a / b)) } ) ) } 151

Monads - Variant 2 - Output with MonadTell println(eval(answer)(writerMonadOut)) // (eval (Con(1972)) <= 1972 // eval (Con(2)) <= 2 // eval (Div(Con(1972),Con(2))) <= 986 // eval (Con(23)) <= 23 // eval (Div(Div(Con(1972),Con(2)),Con(23))) <= 42 // ,42) 152

New abstraction - FunctorTell trait MonadTell[F[_]] extends Monad[F] { def tell(x: Output): F[Unit] } trait FunctorTell[F[_]] extends Monad[F] { def tell(x: Output): F[Unit] } ● this is advanced abstraction from MTL: https://typelevel.org/cats-mtl/mtl-classes/functortell.htmlw 153

Challenge X - what about State case? ● Hint section 2.8, Philip Wadler, Monads for functional programming: http://homepages.inf.ed.ac.uk/wadler/papers/marktoberdorf/baastad.pdf 154

Papers … how to read them ??? ● next Philip Wadler goes into arrays updates and recursive descent parsers :) ● slow down: ○ read abstract, conclusions, maybe browse literature ○ browse for pictures, ○ find page with most complicated symbols - post on twitter with “interesting” :) ○ stare at it when you can’t sleep 155

Monad (definition) trait Monad[M[_]] extends Applicative[M] { def flatMap[A, B](ma: M[A])(f: A => M[B]): M[B] // derived methods def flatten[A](mma: M[M[A]]): M[A] = flatMap(mma)(identity) } 156

Monad for option - simple problem val optionMonad: Monad[Option] = new Monad[Option] { def flatMap[A, B](ma: Option[A])(f: A => Option[B]): Option[B] = { ma match { case Some(a) => f(a) case None => None } } def pure[A](a: A): Option[A] = Some(a) def ap[A, B](ff: Option[A => B])(fa: Option[A]): Option[B] = (ff,fa) match { case (Some(fab), Some(faa)) => Some(fab(faa)) case (_,_) => None } } 157

Challenge flatMap ● define flatMap using other methods: trait Monad[M[_]] extends Applicative[M] { def flatten[A](mma: M[M[A]]): M[A] = def flatMap[A, B](ma: M[A])(f: A => M[B]): M[B] = ??? } 158

Monads in Category Theory Monad is given by: ● an (endo)functor T : C -> C and ● mappings between functor T (natural transformations): η: I => T “eta” μ: TxT => T “mu” such that following diagrams works (diagrams commute) 159

Monads laws - associativity // fa.flatMap(f).flatMap(g) == fa.flatMap(a => f(a).flatMap(b => g(b)) def flatMapAssociativity[A,B,C](fa: M[A], f: A => M[B], g: B => M[C]): Boolean = { // flatMap(f) // M[A] =============> M[B] val l1: M[B] = flatMap(fa)(f) // flatMap(g) // M[B] =============> M[C] val l2: M[C] = flatMap(l1)(g) val r1: A => M[C] = a => flatMap(f(a))(b => g(b)) // flatMap(f flatMap g) // M[A] ======================> M[C] val r2: M[C] = flatMap(fa)(r1) l2 == r2 } 160

Monads laws - left identity // pure(a).flatMap(f) == f(a) def leftIdentity[A,B,C](a: A, f: A => M[B], g: B => M[C]): Boolean = { // pure // A =======> M[A] val l1: M[A] = pure(a) // flatMap // M[A] ==========> M[B] val l2: M[B] = flatMap(l1)(f) // A =======> M[B] val r: M[B] = f(a) l2 == r } 161

Monads laws - right identity // fa.flatMap(pure) == fa def rightIdentity[A,B,C](a: A, fa: M[A], g: B => M[C]): Boolean = { // flatMap // M[A] ==========> M[A] val l: M[A] = flatMap(fa)(pure) val r: M[A] = fa l == r } 162

Challenge X - how Monad laws in FP relate to CT 163

Challenge X - Mambonad Kings Ran trait Ran[G[_], H[_], A] { def runRan[B](f: A => G[B]): H[B] } def ranMonad[G[_], H[_]]: Monad[Ran[G, H, ?]]= ??? ● this monad is called Codensity: https://github.com/scalaz/scalaz/blob/series/7.3.x/core/src/main/scala/scalaz/Codensity.scala 164

Challenge - Monad all the things ● write monad instance for all things ○ Option ○ List ○ Either ○ Thunk ○ Tuple(A, ?), Tuple(?, A), Tuple(A,A) 165

Challenge - Monad all the things - Continuation ● write monad instance for Continuation trait Cont[M[_],A] { def run[Z](f: A => M[Z]): M[Z] } 166

Challenge - how Monad laws in FP relate to CT 167

Challenge - Free Monads sealed trait Free[F[_], A] case class Return[F[_], A](a: A) extends Free[F,A] case class Bind[F[_],I,A](i: F[I], k: I => Free[F,A]) extends Free[F,A] ● write a Monad instance for Free ● Daniel Spiewak, Free as in Monads: https://www.youtube.com/watch?v=aKUQUIHRGec ● Cats docs about Free Monads https://typelevel.org/cats/datatypes/freemonad.html ● ChallangeX: http://blog.higher-order.com/blog/2013/11/01/free-and-yoneda/ 168

Monads do not compose ● Functor, Apply, Applicatvie, Arrows -> compose ● Monads model sequential computation and do not compose ● Solutions ○ Monad transformers (transform inner monad, slow) ○ Free Monads ○ tagless final ○ ... 169

Final Tagless ● Death of Final Tagless, John A. DeGoes ○ https://skillsmatter.com/skillscasts/13247-scala-matters ● FP to the Max Fun(c) 2018.7, John A. DeGoes ○ https://www.youtube.com/watch?v=sxudIMiOo68 170

Applicative Functors trait Apply[F[_]] extends Functor[F] { def apply[A, B](ff: F[A => B])(fa: F[A]): F[B] } trait Applicative[F[_]] extends Apply[F] { def pure[A](value: A): F[A] } 172

Applicative Functors ● in Category Theory lax monoidal functor ● Monad is a Monoid in (Monoidal) Category of endofunctors with Functor composition as tensor ● Applicative is a Monoid in (Monoidal) Category of endofunctors with Day convolution as tensor 173

Applicative and Apply - classic approach trait Apply[F[_]] extends Functor[F] { def apply[A, B](ff: F[A => B])(fa: F[A]): F[B] } trait Applicative[F[_]] extends Apply[F] { def pure[A](value: A): F[A] } 174

Applicative and Apply - variations + derived methods trait Apply[F[_]] extends Functor[F] { def apply[A, B](ff: F[A => B])(fa: F[A]): F[B] def product[A, B](fa: F[A], fb: F[B]): F[(A, B)] = ap(map(fa)(a => (b: B) => (a, b)))(fb) } trait Applicative[F[_]] extends Apply[F] { def pure[A](value: A): F[A] def liftA2[A, B, Z](abc: (A, B) => Z)(fa: F[A], fb: F[B]): F[Z] = apply(map(fa)(abc.curried))(fb) override def map[A, B](fa: F[A])(f: A => B): F[B] = ap(pure(f))(fa) } 175

Applicative - instance for Option val optionApplicative: Applicative[Option] = new Applicative[Option] { def pure[A](a: A): Option[A] = Some(a) def ap[A, B](ff: Option[A => B])(fa: Option[A]): Option[B] = (ff,fa) match { case (Some(fab), Some(faa)) => Some(fab(faa)) case (_,_) => None } } 176

Applicative - examples Option import cats.Applicative import cats.implicits.catsStdInstancesForOption val add3: Int => Int = a => a + 3 Applicative[Option].pure(42) == Some(42) Applicative[Option].ap(Some(add3))(Some(39)) == Some(42) 177

Applicative - examples Option - where is culprit import cats.Applicative import cats.implicits.catsStdInstancesForList val list = List(1, 2) val listFuns: List[Int => Int] = List(a => a + 3, a => a * a) Applicative[List].ap(listFuns)(list) mustBe List(4,5,1,4) Applicative[List].pure("Minsc") mustBe List("Boo") 178

Functor - Apply - Applicative - Monad hierarchy (1/3) trait Functor[F[_]] { def map[A, B](x: F[A])(f: A => B): F[B] } trait Apply[F[_]] extends Functor[F] { def ap[A, B](ff: F[A => B])(fa: F[A]): F[B] } trait Applicative[F[_]] extends Apply[F] { def pure[A](value: A): F[A] } trait Monad[F[_]] extends Applicative[F] { def flatMap[A, B](ma: F[A])(f: A => F[B]): F[B] } 179

Functor - Apply - Applicative - Monad hierarchy (2/3) Functor def map[A, B](x: F[A])(f: A => B): F[B] Apply def ap[A, B](ff: F[A => B])(fa: F[A]): F[B] Applicative def pure[A](value: A): F[A] Monad def flatMap[A, B](ma: F[A])(f: A => F[B]): F[B] 180

Functor - Apply - Applicative - Monad hierarchy (3/3) Functor def map[A, B] (fa: F[A]) (f: A => B): F[B] Apply def ap[A, B] (fa: F[A]) (ff: F[A => B]) : F[B] Applicative def pure[B] (b: B): F[A] Monad def flatMap[A, B](fa: F[A]) (f: A => F[B]): F[B] ● more abstractions in this way on Tony Morris blog: http://blog.tmorris.net/posts/scala-type-class-hierarchy/index.html 181

Applicative - parallel Monad - sequential ● Monads have sequential semantics - you cannot do parallel processing when you use flatMap ● Applicatives do not have such limitations, if you want parallel semantics you should prefere Applicative instance than Monad (even that Monad one have more methods). Matters in: cats-effect https://typelevel.org/cats-effect/) ● Monads knows more about F inside, you can do more with them, but you must pay price: composition, parallel semantics 182

Applicative - composition import cats.Applicative import cats.implicits.catsStdInstancesForList import cats.implicits.catsStdInstancesForOption val listOpt = Applicative[List] compose Applicative[Option] val list1 = List(Some(2), None) val list2 = List(Some(10), Some(2)) listOpt.map2(list1, list2)(_ + _) == List(Some(12), Some(4), None, None) 183

Challenge Applicative ● write Applicative instance for ValidatedNel: case class Nel[A](head: A, tail: Nel[A]) sealed trait ValidatedNel[A] case class SuccessVN[A](value: A) extends ValidatedNel[A] case class Errors[A](errors: Nel[Throwable]) extends ValidatedNel[A] ● (harder) add type parameter instead of Throwable 184

Challenge - Monads are Applicative ● write Applicative instance for every thing you know is a Monad: ○ Option[A] ○ Tuple[A,?], Tuple[?,A] ○ Either[A,?], Either[?,A] ○ Thunk () => A ○ State S => (A,S) ○ Reader Ctx => A ○ Writer A => (A, L) 185

Traversable - Foldable + Functor trait Traverse[F[_]] extends Functor[F] with Foldable[F] { def traverse[G[_] : Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]] } ● map flatMap like function and change the way how effects are stacked 187

Traversable - example - traverse import cats.implicits._ val xs1: Vector[Int] = Vector(1, 2, 3) xs1.traverse(a => Option(a)) == Some(Vector(1, 2, 3)) 188

Traversable - derived method sequence trait Traverse[F[_]] extends Functor[F] with Foldable[F] { def traverse[G[_] : Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]] def sequence[G[_]: Applicative, A](fga: F[G[A]]): G[F[A]] = traverse(fga)(ga => ga) } 189

Traversable - example - sequence import cats.implicits._ val xs1: List[Option[Int]] = List(Some(1), Some(2), None) xs1.sequence == None val xs2: List[Option[Int]] = List(Some(1), Some(2), Some(42)) xs2.sequence == Some(List(1,2,42)) 190

Challenge Traversable - map ● implement map for Traverse trait Traverse[F[_]] extends Functor[F] with Foldable[F] { def traverse[G[_] : Applicative, A, B](fa: F[A])(f: A => G[B]): G[F[B]] override def map[A, B](fa: F[A])(f: A => B): F[B] = ??? } 191

Traversable - classic paper ● more in: The Essence of the Iterator Pattern, J. Gibbons, B. Oliveira ○ https://www.cs.ox.ac.uk/jeremy.gibbons/publications/iterator.pdf 192

MOAR !11!!!! Andrey Morkhov, 2019, submitted to ICFP 2019 - choose only one of two effects trait Selective[F[_]] extends Applicative[F] { def handle[A, B](fab: F[Either[A, B]], ff: F[A => B]): F[B] def select[A, B, C](fab: F[Either[A, B]], fac: F[A => C], fbc: F[B => C]): F[C] } 193

trait Dijkstra[S,A] { def runWp[R](f: (S,A) => R): S => R } implicit def dijakstraMonad[S]: Monad[Dijkstra[S, ?]] = new Monad[Dijkstra[S, ?]] { def pure[A](a: A): Dijkstra[S,A] = new Dijkstra[S,A] { def runWp[R](f: (S, A) => R): S => R = s => f(s,a) } def flatMap[A,B](ma: Dijkstra[S,A])(f: A => Dijkstra[S,B]): Dijkstra[S,B] = new Dijkstra[S,B] { def runWp[R](g: (S, B) => R): S => R = ma.runWp{ case (s,a) => f(a).runWp(g)(s) } } } 194

Computational Context - other intuition for Monads ● Option - may not have value ● Either, ValidatedNel, Try, Future - may fail ● Future, Cats Effect IO, Twitter Future - take time to compute ● List, Vector - may have multiple values ● Tuple - value with some context ● Const - always have the same value ● Reader, Function[Config, ?] - require some context to be computed ● Map - is indexed by ● State - computing changes some state ● Writer - produce some data when computed ● Id - no computational context 195

Algebraic effects, handlers ● Theory using Category Theory to deal with effects ● Lectures (math limited to algebra) Andrej Bauer, Algebraic Effects and Handlers https://www.cs.uoregon.edu/research/summerschool/summer18/ ● wiki with publications: https://github.com/yallop/effects-bibliography ● impl in Scala looks scary :) 196

Coyoneda Trick Trick that allow pretend that any type constructor is a functor, as long as at the end we can move it to something that is a Functor. 197

Coyoneda Trick - type with constructor trait Coyoneda[F[_], A] { type Z def fb: F[Z] def f: Z => A } 198

Coyoneda Trick - liftCoyoneda create Coyo for F object Coyoneda { def apply[F[_],AA,BB](ff: BB => AA, ffb: F[BB]): Coyoneda[F,AA] = new Coyoneda[F,AA] { type Z = BB def fb: F[Z] = ffb def f: Z => AA = ff } def liftCoyoneda[F[_], A](fa: F[A]): Coyoneda[F, A] = Coyoneda[F, A, A](identity[A], fa) } 199

Coyoneda Trick - we can map implicit def coyoFunctor[F[_]]: Functor[Coyoneda[F, ?]] = new Functor[Coyoneda[F, ?]] { def map[A, AA](fa: Coyoneda[F, A])(ff: A => AA): Coyoneda[F, AA] = new Coyoneda[F, AA] { type Z = fa.Z def f: Z => AA = fa.f andThen ff def fb: F[Z] = fa.fb } } 200

Coyoneda Trick - we can change F def hoistCoyoneda[F[_], G[_], A, C](fab : F~>G])(coyo: Coyoneda[F, A]): Coyoneda[G, A] = new Coyoneda[G, A] { type Z = coyo.Z def f: Z => A = coyo.f def fb: G[Z] = fab(coyo.fb) } 201

Coyoneda Trick - we can change F def hoistCoyoneda[F[_], G[_], A, C](fab : F~>G])(coyo: Coyoneda[F, A]): Coyoneda[G, A] = new Coyoneda[G, A] { type Z = coyo.Z def f: Z => A = coyo.f def fb: G[Z] = fab(coyo.fb) } 202

Coyoneda Trick - using Functor[F] get back F trait Coyoneda[F[_], A] { type Z def fb: F[Z] def f: Z => A // .. def lowerCoyoneda(implicit fun: Functor[F]): F[A] = fun.map(fb)(f) } 203

Coyoneda Trick Now we can pretend every type constructor is a Functor, if we can transform it to proper Functor at some point in the future :) 204

Challenge X Yo - Reverse engineering machines Translate to Scala: Dan Piponi, Reverse Engineering Machines with the Yoneda Lemma: http://blog.sigfpe.com/2006/11/yoneda-lemma.html 205

Comonad - definition trait Comonad[F[_]] extends Functor[F] { def extract[A](w: F[A]): A def duplicate[A](wa: F[A]): F[F[A]] // derived methods def extend[A, B](w: F[A])(f: F[A] => B): F[B] = map(duplicate(w))(f) } ● get value (in Monads pure -> put value inside) ● add one more layer (in Monads flatten -> remove one layer) 207

Category Theory - duality ● every concept has dual ● we create Opposite Category where ○ objects the same ○ morphisms have reversed arrows ● dual concepts ○ monad <-> comonad ○ initial object <-> terminal object ○ product <-> coproduct ○ limit <-> colimit 208

Category Theory - duality initial object one, unique morphism to every other terminal object one, unique morphism from every other Bartosz Milewski, Products and Coproducts bartoszmilewski.com/2015/01/07/products-and-coproducts/ 209

void type - absurd final abstract class Void private () { def absurd[A]: A } 210

Comonad - definition with co-methods trait CoFlatmap[F[_]] extends Functor[F] { def coflatmap[A, B](w: F[A])(f: F[A] => B): F[B] } trait Comonad[F[_]] extends CoFlatmap[F] { def coPure[A](w: F[A]): A def coFlatten[A](wa: F[A]): F[F[A]] override def coflatmap[A, B](w: F[A])(f: F[A] => B): F[B] = map(coFlatten(w))(f) } 211

Comonads - Id case class Id[A](value: A) val idComonad = new Comonad[Id] { def map[A, B](x: Id[A])(f: A => B): Id[B] = Id(f(x.value)) def extract[A](w: Id[A]): A = w.value def duplicate[A](wa: Id[A]): Id[Id[A]] = Id(wa) } idComonad.extract(Id(42)) == 42 idComonad.map(Id("foo"))(_.length) == Id(3) idComonad.duplicate(Id(42)) == Id(Id(42)) 212

Comonads - CoReader case class CoReader[R, A](extract: A, context: R) def coReader[R] = new Comonad[CoReader[R, ?]] { def map[A, B](x: CoReader[R, A])(f: A => B): CoReader[R, B] = CoReader(f(x.extract), x.context) def extract[A](w: CoReader[R, A]): A = w.extract def duplicate[A](wa: CoReader[R, A]): CoReader[R, CoReader[R, A]] = CoReader(wa, wa.context) } val cor = CoReader(extract = 42, context = "foo") extract(cor) == 42 map(cor)(_ * 10) == CoReader(extract = 420, context = "foo") duplicate(cor) == CoReader(extract = CoReader(extract = 42, context = "foo"), context = "foo") 213

Comonads - NonEmptyList case class Nel[A](head: A, tail: Option[Nel[A]]) { def map[B](f: A => B): Nel[B] = Nel(f(head), tail.map(in => in.map(f))) } val nelComonad: Comonad[Nel] = new Comonad[Nel] { def extract[A](na: Nel[A]): A = na.head def duplicate[A](na: Nel[A]): Nel[Nel[A]] = Nel(na, na.tail.map(n => duplicate(n))) def map[A, B](na: Nel[A])(f: A => B): Nel[B] = Nel(f(na.head), na.tail.map(in => in.map(f))) override def extend[A,B](na: Nel[A])(f: Nel[A] => B): Nel[B] = duplicate(na).map(f) } 214

Comonads - NonEmptyList examples val nel = Nel(1, Some(Nel(2, Some(Nel(3, None))))) nelComonad.extract(nel) == 1 nelComonad.map(nel)(_ * 10) == Nel(10, Some(Nel(20, Some(Nel(30, None))))) val n2 = Nel(2, Some(Nel(3, None))) val n3 = Nel(3, None) nelComonad.duplicate(nel) == Nel(nel, Some(Nel(n2, Some(Nel(n3, None))))) 215

Comonads - model co-inductive process ● Streams ● web servers (routing) ● Generators ● calculating irrational number with increased accurrency 216

Comonads - Co-Freedom ● Write comonad instance for following class case class Cofree[A, F[_]](extract: A, sub: F[Cofree[A, F]])(implicit functor: Functor[F]) 217

Challenge - Calculate PI ● Write comonad that generate square root of 2 with increasing accuracy ● … generate pi digits :) 218

Challenge - Comonad game ● Write comonad that generate will be base for main loop of console program ● Write some game to guess Category Theory abstractions using above comonad 219

Challenge X - Co-game of life ● Implement Game of Life using Comonads Hint: google it! ( e.g. https://chrispenner.ca/posts/conways-game-of-life.html) People use much more than Comonads (Zipper, Representable functors, etc) and that is even more fun! 220

Comonads more !1!!! ● John De Goes: Streams for (Co)Free! https://www.youtube.com/watch?v=wEVfJSi2J5o&t=955s (link targets specific video with so called John’ Laws of Clean Functional Code, whole talk is pure gold) ● Runar blog posts about Comonads ○ http://blog.higher-order.com/blog/2015/06/23/a-scala-comonad-tutorial/ ○ http://blog.higher-order.com/blog/2015/10/04/scala-comonad-tutorial-part-2/ ● Phil Freeman - The Future is Comonadic! (PureScript, use Day convolution to compose) all Phil Freeman is awesome but in Haskell or Purescript ○ https://www.youtube.com/watch?v=EoJ9xnzG76M ● Comonadic notions of computations ○ http://math.ut.ee/luebeck2006/TLW2006.pdf (slides - easier to understand) ○ https://www.sciencedirect.com/science/article/pii/S1571066108003435 221

Category Theory “patterns” vs OOP Design Patterns ● abstractions from math are not patterns, they are libraries if language has expressive enough type system - higher kinded types - Haskell, Scala, Idris, PureScript ○ Scala: Cat, Scalaz ○ Haskell: Profunctor, Contravariant, Monad, Free Some notable attempts: ● Relation between Category Theory abstractions and OOP Design Patterns by Mark Seemann: https://blog.ploeh.dk/2017/10/04/from-design-patterns-to-category-theory/ ● Implemenation of Design Patterns in Scala by Li Haoyi: http://www.lihaoyi.com/post/OldDesignPatternsinScala.html 222

Curry-Howard-Lambek iso ~ compu. trinitarianism ● Abstract algebra of ADT is just the beginning ● Logic (Proof theory), Programming (type theory), Category Theory are talking about the same concepts using different names and tools :) ● names ○ propositions as types ○ proofs as programs ○ Curry-Howard-Lambek isomorphism ○ computational trinitarianism ● Bartosz Milewski, CT 8.2 Type algebra, Curry-Howard-Lambek isomorphism ○ https://www.youtube.com/watch?v=iXZR1v3YN-8 ● Philip Wadler, Propositions as Types ○ video: https://www.youtube.com/watch?v=IOiZatlZtGU ○ publication: https://homepages.inf.ed.ac.uk/wadler/papers/propositions-as-types/propositions-as-types.pdf 223

Curry-Howard-Lambek isomorphism logic true false and or implication types () Void (a,b) Either(a,b) A => B CT terminal initial product coproduct exponential ● nLab (wiki about Category Theory used by mathematicians) ○ very very long list of those similar concepts: ○ https://ncatlab.org/nlab/show/computational+trinitarianism 224

GIMME MOAR !!1!11111 ● Bartosz Milewski ○ video playlists (Haskell + Category Theory) Functor, Kleisli, CCC, Comonads, Adjuctions, Representable, Yoneda, Limits, Ends, F-Alebras, Lambek Theorem, Profunctors ○ youtube.com/user/DrBartosz/playlists Category Theory I, Category Theory II, Category Theory III ○ https://bartoszmilewski.com/ blog, even more ● mpliquist Functional Structures in Scala ○ https://www.youtube.com/playlist?list=PLFrwDVdSrYE6dy14XCmUtRAJuhCxuzJp0 ○ Functor, Applicative, Monad, Traverse, Semigroup, Foldable, OptionT, Reader, ReaderT ● Red Book ○ https://www.manning.com/books/functional-programming-in-scala ○ how to design using FP, best explanation ever ● Haskell FP Course https://github.com/data61/fp-course ● https://github.com/lemastero/scala_typeclassopedia (wiki of everything Category Theory related, pictures for laws, advanced concepts) 225

RedBook: watch, read everything by Runar Functional Programming in Scala Paul Chiusano, Rúnar Bjarnason https://www.manning.com/books/functional-programming-in-scala 226

Bartosz Milewski: beautiful and easy explanations! Blog: https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/ Book: (in pdf and dead tree format, thanks to Igal Tabachnik): https://github.com/hmemcpy/milewski-ctfp-pdf Video lectures: https://www.youtube.com/playlist?list=PLbgaMIhjbmEnaH_LTkxLI7FMa2HsnawM_ (there are 2 more series :) of videos) 227

Sources of images ● https://knowyourmeme.com/memes/people/snoop-dogg ● https://giphy.com/gifs/sloth-xNrM4cGJ8u3ao ● https://www.strengthsensei.com/gigant-seria-na-wielkie-plecy/ ● https://imgur.com/gallery/Dq5SI ● https://analyzingtv.wordpress.com/2016/02/03/top-gear/ ● https://www.youtube.com/watch?v=9LDea8s4yZE ● https://floofytimes.wordpress.com/animals-covering-their-face-with-their-paws/ ● https://www.ncl.ac.uk/engineering/staff/profile/andreymokhov.html#background ● http://ozark.hendrix.edu/~yorgey/ ● https://en.wikipedia.org/wiki/Johann_Wolfgang_von_Goethe ● https://www.nasa.gov/connect/chat/black_hole_chat.html ● https://health.howstuffworks.com/wellness/men/sweating-odor/what-is-in-sweat.htm ● https://www.ebaumsworld.com/pictures/16-baby-mind-blown-gifs/84662736/ ● https://livebook.manning.com/#!/book/functional-programming-in-scala/about-this-book/0 ● https://www.youtube.com/watch?v=4jKpGddmArs ● https://mic.com/articles/122598/here-s-how-the-marvel-cinematic-universe-s-heroes-connect-in-one-surprising-map#.WHH0Daoj m ● http://www.cultjer.com/army-ready-to-shoot-arrows-the-battle-of-the-five-armies ● https://bartoszmilewski.com/2014/11/04/category-the-essence-of-composition/ ● https://twitter.com/impurepics?lang=en ● https://www.engadget.com/2012/06/10/know-your-lore-why-garrosh-hellscream-shouldnt-die/ ● https://www.youtube.com/watch?v=aKUQUIHRGec ● https://www.kegworks.com/blog/18-homer-simpson-beer-quotes-that-will-never-stop-being-funny/ ● https://en.wikipedia.org/wiki/Minsc 228

● PR’s to Scalaz 7 ○ github.com/scalaz/scalaz/pull/2020 Day convolution (0,5 year fight transalte from Haskell) ○ github.com/scalaz/scalaz/pull/2028 Strong Profunctor laws - they were none ○ github.com/scalaz/scalaz/pull/2029 Density comonad (abstraction - no practical applications yet) ● PR’s to Cats ○ github.com/typelevel/cats/pull/2640 Strong Profunctor laws (based on CT replace ad hoc ones) ● PR’s to Haskell Profunctors ○ github.com/ekmett/profunctors/pull/65 broken link (this is how you start!) ○ github.com/ekmett/profunctors/pull/66 small fix in docs for Strong Profunctor laws ● type_classopedia - wiki about Category Theory abstraction in Scala ○ github.com/lemastero/scala_typeclassopedia ● other OSS work: resources about effects, programming language theory, streaming benchmarks ○ Sclaz ZIO github.com/scalaz/scalaz-zio/pulls?utf8=%E2%9C%93&q=+author%3Alemastero Hackaton @ ScalaC ○ yallop/effects-bibliography github.com/yallop/effects-bibliography/pulls?utf8=✓&q=+author%3Alemastero add Idris Effects, Scala Eff Monad) wiki about effects by Jeremy Yallop (University of Cambridge) ○ steshaw.org/plt/ (github.com/steshaw/plt/pulls?utf8=✓&q=+author%3Alemastero) add 7Sketches, TAC Journal ○ monix/streaming-benchmarks github.com/monix/streaming-benchmarks/pull/1 updated benchmarks ○ cohomolo-gy/haskell-resources github.com/cohomolo-gy/haskell-resources/pull/3 add Haskell papers ○ lauris/awesome-scala github.com/lauris/awesome-scala/pull/425 add ZIO, update Monix, RxScala ○ passy/awesome-recurion-schemas github.com/passy/awesome-recursion-schemes/pull/22 add droste 229

The harder you work, the luckier you get. Forget the sky, you are the limit. Work hard. Dream fiercely. random quotes from internet memes, transpiled by lemastero Thank you :) 230

but wait there's more …. HoTT, UF, CTT ● Vladimir Voevodsky 2006/2009 propose Univalent foundations - new approach to foundations of mathematics (used to be Set theory - but paradoxes) ● Homotopy Type Theory (HoTT = Homotopy T. + Type T.) is branch of Type Theory, used by proof assistants, mix Higher Category Theory ● Category Theory was encoded in Coq (proof assistant, Coq itself is very advanced FP language, more that Scala, Haskell) ● Category Theory encodend in FP using Coq https://arxiv.org/abs/1505.06430 ● … different approach using UF: https://github.com/UniMath/UniMath/tree/master/UniMath/CategoryTheory ● Cubical Type Theory - new development in type theory and some say Type Theory is more applicable than Category Theory! 231

Why functional programming and category theory strongly matters

In this document

More Related Content

What's hot

Similar to Why functional programming and category theory strongly matters

Recently uploaded

Why functional programming and category theory strongly matters