# 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:

Ссылка: