A


The Presentation inside:

Slide 0

Category Theory for beginners Melbourne Scala User Group Feb 2015 @KenScambler A B C


Slide 1

Abstract maths… for us? Dizzyingly abstract branch of maths “Abstract nonsense”? Programming = maths Programming = abstraction Really useful to programming!


Slide 2

The plan Basic Category Theory concepts New vocabulary (helpful for further reading) How it relates to programming Category Theory as seen by maths versus FP


Slide 3

A bit of background 1940s Eilenberg, Mac Lane invent Category Theory 1958 Monads discovered by Godement In programming: 1990 Moggi, Wadler apply monads to programming 2006 “Applicative Programming with Effects” McBride & Paterson 2006 “Essence of the Iterator Pattern” Gibbons & Oliveira


Slide 4

I. Categories


Slide 5

Category Objects


Slide 6

Category Objects Arrows or morphisms


Slide 7

Category Objects Arrows Domain f dom(f)


Slide 8

Category Objects Arrows Domain/Codomain f cod(f) dom(f)


Slide 9

Category Objects Arrows Domain/Codomain dom(g) cod(g) g


Slide 10

Category Objects Arrows Domain/Codomain


Slide 11

Category Objects Arrows Domain/Codomain Composition f


Slide 12

Category Objects Arrows Domain/Codomain Composition f g


Slide 13

Category Objects Arrows Domain/Codomain Composition f g g ? f


Slide 14

Category Objects Arrows Domain/Codomain Composition f


Slide 15

Category Objects Arrows Domain/Codomain Composition f h


Slide 16

Category Objects Arrows Domain/Codomain Composition f h h ? f


Slide 17

Category Objects Arrows Domain/Codomain Composition Identity


Slide 18

Category Compose ? : (B ? C) ? (A ? B) ? (A ? C) Identity id : A ? A


Slide 19

Category Laws Associative Law (f ? g) ? h = f ? (g ? h ) Identity Laws f ? id = id ? f = f


Slide 20

Associative law (f ? g) ? h = f ? (g ? h ) f g h (g ? h) (f ? g)


Slide 21

Associative law (f ? g) ? h = f ? (g ? h ) f g h (g ? h) (f ? g)


Slide 22

Associative law (f ? g) ? h = f ? (g ? h ) f g h (g ? h) (f ? g)


Slide 23

Associative law (f ? g) ? h = f ? (g ? h ) f g h (g ? h) (f ? g)


Slide 24

Associative law (f ? g) ? h = f ? (g ? h ) f g h (g ? h) (f ? g)


Slide 25

Associative law (f ? g) ? h = f ? (g ? h ) f g h (g ? h) (f ? g)


Slide 26

Associative law (f ? g) ? h = f ? (g ? h ) f g h (g ? h) (f ? g)


Slide 27

Identity laws f ? id = id ? f = f f id id


Slide 28

Identity laws f ? id = id ? f = f f id id


Slide 29

Identity laws f ? id = id ? f = f f id id


Slide 30

Identity laws f ? id = id ? f = f f id id


Slide 31

Examples Infinite categories Finite categories Objects can represent anything Arrows can represent anything As long as we have composition and identity!


Slide 32

Sets & functions Person String Integer bestFriend length name age +1


Slide 33

Sets & functions Infinite arrows from composition +1? length ? name bestFriend ? bestFriend bestFriend ? bestFriend ? bestFriend +1? age? bestFriend


Slide 34

Sets & functions Objects Arrows Composition Identity


Slide 35

Sets & functions Objects = sets (or types) Arrows = functions Composition = function composition Identity = identity function


Slide 36

Zero


Slide 37

One


Slide 38

Two


Slide 39

Three


Slide 40

Class hierarchy IFruit IBanana AbstractBanana BananaImpl MockBanana Tool Spanner


Slide 41

Class hierarchy Objects Arrows Composition Identity


Slide 42

Class hierarchy Objects = classes Arrows = “extends” Composition = “extends” is transitive Identity = trivial


Slide 43

Class hierarchy Partially ordered sets (posets) Objects = elements in the set Arrows = ordering relation ? Composition = ? is transitive Identity = trivial


Slide 44

World Wide Web www.naaawcats.com No dogs allowed! www.robodogs.com See here for more robots www.coolrobots.com BUY NOW!!!!


Slide 45

World Wide Web Objects = webpages Arrows = hyperlinks Composition = Links don’t compose Identity


Slide 46

World Wide Web Graphs Objects = nodes Arrows = edges Composition = Edges don’t compose Identity


Slide 47

“Free Category” from graphs! Objects = nodes Arrows = paths (0 to many edges) Composition = aligning paths end to end Identity = you’re already there


Slide 48

Categories in code trait Category[Arrow[_,_]] { def compose[A,B,C]( c: Arrow[B,C], d: Arrow[A,B]): Arrow[A,C] def id[A]: Arrow[A,A] }


Slide 49

Category of Types & Functions object FnCat extends Category[Function1] { def compose[A,B,C]( c: B => C, d: A => B): A => C = { a => c(d(a)) } def id[A]: A => A = (a => a) }


Slide 50

Category of Garden Hoses sealed trait Hose[In, Out] { def leaks: Int def kinked: Boolean def >>[A](in: Hose[A, In]): Hose[A, Out] def <<[A](out: Hose[Out, A]): Hose[In, A] }


Slide 51

Category of Garden Hoses [live code example]


Slide 52

Categories embody the principle of strongly-typed composability


Slide 53

II. Functors


Slide 54

Functors Functors map between categories Objects ? objects Arrows ? arrows Preserves composition & identity


Slide 55

Functor laws Composition Law F(g ? f) = F(g) ? F(f) Identity Law F(idA) = idF(A)


Slide 56

C F D Category Category Functor


Slide 57

C F D Category Category Functor Cat Category of categories


Slide 58

C F D Category Category Functor Cat Category of categories Objects = categories Arrows = functors Composition = functor composition Identity = Identity functor


Slide 59

C F D A B C g ? f f g


Slide 60

C F D A B C g ? f f g F(A)


Slide 61

C F D A B C g ? f f g F(A) F(B)


Slide 62

C F D A B C g ? f f g F(A) F(B) F(C)


Slide 63

C F D A B C g ? f f g F(A) F(B) F(C) F(f)


Slide 64

C F D A B C g ? f f g F(A) F(B) F(C) F(f) F(g)


Slide 65

C F D A B C g ? f f g F(A) F(B) F(C) F(f) F(g) F(g ? f)


Slide 66

g ? f f g F(f) F(g) F(g ? f) Composition Law F(g ? f) = F(g) ? F(f)


Slide 67

g ? f f g F(f) F(g) F(g ? f) Composition Law F(g ? f) = F(g) ? F(f)


Slide 68

g ? f f g F(f) F(g) F(g ? f) Composition Law F(g ? f) = F(g) ? F(f)


Slide 69

g ? f f g F(f) F(g) F(g ? f) Composition Law F(g ? f) = F(g) ? F(f)


Slide 70

g ? f f g F(f) F(g) F(g ? f) Composition Law F(g ? f) = F(g) ? F(f)


Slide 71

g ? f f g F(f) F(g) F(g ? f) Composition Law F(g ? f) = F(g) ? F(f)


Slide 72

g ? f f g F(f) F(g) F(g ? f) Composition Law F(g ? f) = F(g) ? F(f)


Slide 73

g ? f f g F(f) F(g) F(g ? f) Composition Law F(g ? f) = F(g) ? F(f)


Slide 74

g ? f f g F(f) F(g) Composition Law F(g ? f) = F(g) ? F(f) F(g) ? F(f)


Slide 75

g ? f f g F(f) F(g) Composition Law F(g ? f) = F(g) ? F(f) F(g) ? F(f) F(g ? f)


Slide 76

Identity law F(idA)= idF(A) A


Slide 77

Identity law F(idA)= idF(A) A idA


Slide 78

Identity law F(idA)= idF(A) A idA F(idA)


Slide 79

Identity law F(idA)= idF(A) A


Slide 80

Identity law F(idA)= idF(A) A F(A)


Slide 81

Identity law F(idA)= idF(A) A F(A) idF(A)


Slide 82

Identity law F(idA)= idF(A) A F(A) idF(A) A idA F(idA)


Slide 83

Terminology homomorphism


Slide 84

Terminology homomorphism Same


Slide 85

Terminology homomorphism Same -shape-ism


Slide 86

Terminology homomorphism “structure preserving map”


Slide 87

Terminology homomorphism Functors are “category homomorphisms”


Slide 88

Functors in code trait Functor[F[_]] { def map[A,B](fa: F[A], f: A => B): F[B] }


Slide 89

Functors in code trait Functor[F[_]] { def map[A,B](fa: F[A], f: A => B): F[B] } Objects to objects


Slide 90

Functors in code trait Functor[F[_]] { def map[A,B](fa: F[A], f: A => B): F[B] } Arrows to arrows


Slide 91

Functors in code trait Functor[F[_]] { def map[A,B]: (A => B) => (F[A] => F[B]) } Arrows to arrows


Slide 92

Functors laws in code fa.map(f).map(g) == fa.map(g compose f)


Slide 93

Functors laws in code fa.map(a => a) == fa


Slide 94

Terminology endomorphism


Slide 95

Terminology endomorphism Within


Slide 96

Terminology endomorphism Within -shape-ism


Slide 97

Terminology endomorphism “a mapping from something back to itself”


Slide 98

Terminology endo “a mapping from something back to itself”


Slide 99

Endofunctors In Scala, all our functors are actually endofunctors. Type F Category Category Endofunctor Type


Slide 100

Endofunctors Luckily, we can represent any functor in our type system as some F[_] Type F Category Category Endofunctor Type


Slide 101

List Functor sealed trait List[+A] case class Cons(head: A, tail: List[A]) extends List[A] case object Nil extends List[Nothing]


Slide 102

List Functor sealed trait List[+A] { def map[B](f: A => B): List[B] = this match { case Cons(h,t) => Cons(f(h), t map f) case Nil => Nil } } }


Slide 103

List Functor potatoList .map(mashEm) .map(boilEm) .map(stickEmInAStew)


Slide 104

List Functor userList .map(_.name) .map(_.length) .map(_ + 1) .map(_.toString)


Slide 105

Other functors trait Tree[A] trait Future[A] trait Process[A] trait Command[A] X => A (X, A) trait Option[A]


Slide 106

Functors Fundamental concept in Category Theory Super useful Everywhere Staple of functional programming Write code that’s ignorant of unnecessary context


Slide 107

III. Monoids


Slide 108

Monoids Some set we’ll call M Compose • : M ? M ? M Identity id : M


Slide 109

Monoid Laws Associative Law (f • g) • h = f • (g • h ) Identity Laws f • id = id • f = f


Slide 110

Category Laws Associative Law (f ? g) ? h = f ? (g ? h ) Identity Laws f ? id = id ? f = f


Slide 111

Monoids Compose • : M ? M ? M Identity id : M


Slide 112

Category Compose ? : (B ? C) ? (A ? B) ? (A ? C) Identity id : A ? A


Slide 113

Category with 1 object Compose ? : (A ? A) ? (A ? A) ? (A ? A) Identity id : A ? A


Slide 114

Category with 1 object Compose ? : M ? M? M Identity id : M


Slide 115

Monoids are categories Each arrow is an element in the monoid Only one object


Slide 116

Monoids are categories Objects = placeholder singleton Arrows = elements of the monoid Composition = • Identity = id Only one object Each arrow is an element in the monoid


Slide 117

M H N Monoid Monoid Monoid homomorphism (SM, •M, idM) (SN, •N, idN)


Slide 118

M H N Monoid Monoid Monoid homomorphism (SM, •M, idM) (SN, •N, idN) Mon Category of monoids


Slide 119

M H N Monoid Monoid Monoid homomorphism (SM, •M, idM) (SN, •N, idN) Mon Category of monoids Objects = monoids Arrows = monoid homomorphisms Composition = function composition Identity = Identity function


Slide 120

M H N SM SN “structure-preserving map” Set Set function h Sets Where h preserves composition & identity


Slide 121

Example String length is a monoid homomorphism from (String, +, "") to (Int, +, 0)


Slide 122

Preserves identity Preserves composition "".length == 0 (str1 + str2).length = str1.length + str2.length


Slide 123

Monoids in code trait Monoid[M] { def compose(a: M, b: M): M def id: M }


Slide 124

Monoids in code def foldMonoid[M: Monoid]( ms: Seq[M]): M = { ms.foldLeft(Monoid[M].id) (Monoid[M].compose) }


Slide 125

Int / 0 / + import IntAddMonoid._ foldMonoid[Int](Seq( 1,2,3,4,5,6)) ? 21


Slide 126

Int / 1 / * import IntMultMonoid._ foldMonoid[Int](Seq( 1,2,3,4,5,6)) ? 720


Slide 127

String / "" / + foldMonoid[String](Seq( "alea", "iacta", "est")) ? ”aleaiactaest"


Slide 128

Endos / id / ? def mash: Potato => Potato def addOne: Int => Int def flipHorizontal: Shape => Shape def bestFriend: Person => Person


Slide 129

A=>A / a=>a / compose foldMonoid[Int => Int](Seq( _ + 12, _ * 2, _ - 3)) ? (n: Int) => ((n + 12) * 2) - 3


Slide 130

Are chairs monoids?


Slide 131

Chair Composition = You can’t turn two chairs into one Identity =


Slide 132

Chair stack


Slide 133

Chair stack Composition = stack them on top Identity = no chairs


Slide 134

Chair Stack is the free monoid of chairs Protip: just take 0-to-many of anything, and you get a monoid for free


Slide 135

…almost Real monoids don’t topple; they keep scaling


Slide 136

Monoids embody the principle of weakly-typed composability


Slide 137

IV. Products & sums


Slide 138

Algebraic Data Types List[A] - Cons(A, List[A]) - Nil Option[A] - Some(A) - None BusinessResult[A] - OK(A) - Error Wiggles - YellowWiggle - BlueWiggle - RedWiggle - PurpleWiggle Address(Street, Suburb, Postcode, State)


Slide 139

Algebraic Data Types Cons(A ? List[A]) + Nil Some(A) + None OK(A) + Error YellowWiggle + BlueWiggle + RedWiggle + PurpleWiggle Street ? Suburb ? Postcode ? State


Slide 140

Algebraic Data Types A ? List[A] + 1 A + 1 A + 1 4 Street ? Suburb ? Postcode ? State


Slide 141

Algebraic Data Types A ? List[A] + 1 A + 1 A + 1 4 Street ? Suburb ? Postcode ? State isomorphic


Slide 142

Terminology isomorphism


Slide 143

Terminology isomorphism Equal


Slide 144

Terminology isomorphism Equal -shape-ism


Slide 145

Terminology isomorphism “Sorta kinda the same-ish” but I want to sound really smart - Programmers


Slide 146

Terminology isomorphism “Sorta kinda the same-ish” but I want to sound really smart - Programmers


Slide 147

Terminology isomorphism One-to-one mapping between two objects so you can go back-and-forth without losing information


Slide 148

Isomorphism object object arrows


Slide 149

Isomorphism Same as identity


Slide 150

Isomorphism Same as identity


Slide 151

These 4 Shapes Wiggles Set functions Set


Slide 152

These 4 Shapes Wiggles


Slide 153

These 4 Shapes Wiggles


Slide 154

There can be lots of isos between two objects! If there’s at least one, we can say they are isomorphic or A ? B


Slide 155

Products A ? B A B first second Given the product of A-and-B, we can obtain both A and B


Slide 156

Sums A + B A B left right Given an A, or a B, we have the sum A-or-B


Slide 157

Opposite categories C Cop A B C g ? f f g A B C fop ? gop fop gop Isomorphic!


Slide 158

A B C g ? f f g A B C f ? g f g Just flip the arrows, and reverse composition!


Slide 159

A A?B B A product in C is a sum in Cop A sum in C is a product in Cop A+B B A C Cop


Slide 160

Sums ? Products!


Slide 161

Terminology dual An object and its equivalent in the opposite category are to each other.


Slide 162

Terminology Co-(thing) Often we call something’s dual a


Slide 163

Terminology Coproducts Sums are also called


Slide 164

V. Composable systems


Slide 165

Growing a system Banana


Slide 166

Growing a system


Slide 167

Growing a system


Slide 168

Growing a system Bunch


Slide 169

Growing a system Bunch Bunch


Slide 170

Growing a system Bunch Bunch Bunch


Slide 171

Growing a system Bunch Bunch Bunch BunchManager


Slide 172

Growing a system Bunch Bunch Bunch BunchManager AnyManagers


Slide 173


Slide 174


Slide 175


Slide 176

compose


Slide 177


Slide 178

compose


Slide 179

etc…


Slide 180

Using composable abstractions means your code can grow without getting more complex Categories and Monoids capture the essence of composition in software!


Slide 181

Look for Monoids and Categories in your domain where you can You can even bludgeon non-composable things into free monoids and free categories


Slide 182

VI. Abstraction


Slide 183

Spanner


Slide 184

Spanner AbstractSpanner


Slide 185

Spanner AbstractSpanner AbstractToolThing


Slide 186

Spanner AbstractSpanner AbstractToolThing GenerallyUsefulThing


Slide 187

Spanner AbstractSpanner AbstractToolThing GenerallyUsefulThing AbstractGenerallyUsefulThingFactory


Slide 188

Spanner AbstractSpanner AbstractToolThing GenerallyUsefulThing AbstractGenerallyUsefulThingFactory WhateverFactoryBuilder


Slide 189


Slide 190

That’s not what abstraction means.


Slide 191

Code shouldn’t know things that aren’t needed.


Slide 192

def getNames(users: List[User]): List[Name] = { users.map(_.name) }


Slide 193

def getNames(users: List[User]): List[Name] = { println(users.length) users.map(_.name) } Over time…


Slide 194

def getNames(users: List[User]): List[Name] = { println(users.length) if (users.length == 1) { s”${users.head.name} the one and only" } else { users.map(_.name) } }


Slide 195

“Oh, now we need the roster of names! A simple list won’t do.”


Slide 196

def getRosterNames(users: Roster[User]): Roster[Name] = { users.map(_.name) }


Slide 197

def getRosterNames(users: Roster[User]): Roster[Name] = { LogFactory.getLogger.info(s”When you party with ${users.rosterTitle}, you must party hard!") users.map(_.name) } Over time…


Slide 198

def getRosterNames(users: Roster[User]): Roster[Name] = { LogFactory.getLogger.info(s"When you party with ${users.rosterTitle}, you must party hard!") if (users.isFull) EmptyRoster("(everyone) ") else users.map(_.name) }


Slide 199

When code knows too much, soon new things will appear that actually require the other stuff.


Slide 200

Coupling has increased. The mixed concerns will tangle and snarl.


Slide 201

Code is rewritten each time for trivially different requirements


Slide 202

def getNames[F: Functor](users: F[User]): F[Name] = { Functor[F].map(users)(_.name) } getNames(List(alice, bob, carol)) getNames(Roster(alice, bob, carol))


Slide 203

Not only is the abstract code not weighed down with useless junk, it can’t be! Reusable out of the box!


Slide 204

Abstraction is about hiding unnecessary information. This a good thing. We actually know more about what the code does, because we have stronger guarantees!


Slide 205

We’ve seen deep underlying patterns beneath superficially different things A?B A+B


Slide 206

Just about everything ended up being in a category, or being one.


Slide 207

There is no better way to understand the patterns underlying software than studying Category Theory.


Slide 208

Further reading Awodey, “Category Theory” Lawvere & Schanuel, “Conceptual Mathematics: an introduction to categories” Jeremy Kun, “Math ? Programming” at http://jeremykun.com/ Gabriel Gonzalez “Haskell for all” http://www.haskellforall.com/2012/08/the-category-design-pattern.html http://www.haskellforall.com/2014/04/scalable-program-architectures.html


×

HTML:





Ссылка: