'

A

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 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


Слайд 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


Слайд 4

I. Categories


Слайд 5

Category Objects


Слайд 6

Category Objects Arrows or morphisms


Слайд 7

Category Objects Arrows Domain f dom(f)


Слайд 8

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


Слайд 9

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


Слайд 10

Category Objects Arrows Domain/Codomain


Слайд 11

Category Objects Arrows Domain/Codomain Composition f


Слайд 12

Category Objects Arrows Domain/Codomain Composition f g


Слайд 13

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


Слайд 14

Category Objects Arrows Domain/Codomain Composition f


Слайд 15

Category Objects Arrows Domain/Codomain Composition f h


Слайд 16

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


Слайд 17

Category Objects Arrows Domain/Codomain Composition Identity


Слайд 18

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


Слайд 19

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


Слайд 20

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


Слайд 21

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


Слайд 22

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


Слайд 23

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


Слайд 24

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


Слайд 25

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


Слайд 26

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


Слайд 27

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


Слайд 28

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


Слайд 29

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


Слайд 30

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


Слайд 31

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


Слайд 32

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


Слайд 33

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


Слайд 34

Sets & functions Objects Arrows Composition Identity


Слайд 35

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


Слайд 36

Zero


Слайд 37

One


Слайд 38

Two


Слайд 39

Three


Слайд 40

Class hierarchy IFruit IBanana AbstractBanana BananaImpl MockBanana Tool Spanner


Слайд 41

Class hierarchy Objects Arrows Composition Identity


Слайд 42

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


Слайд 43

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


Слайд 44

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


Слайд 45

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


Слайд 46

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


Слайд 47

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


Слайд 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] }


Слайд 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) }


Слайд 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] }


Слайд 51

Category of Garden Hoses [live code example]


Слайд 52

Categories embody the principle of strongly-typed composability


Слайд 53

II. Functors


Слайд 54

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


Слайд 55

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


Слайд 56

C F D Category Category Functor


Слайд 57

C F D Category Category Functor Cat Category of categories


Слайд 58

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


Слайд 59

C F D A B C g ? f f g


Слайд 60

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


Слайд 61

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


Слайд 62

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


Слайд 63

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


Слайд 64

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


Слайд 65

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


Слайд 66

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


Слайд 67

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


Слайд 68

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


Слайд 69

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


Слайд 70

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


Слайд 71

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


Слайд 72

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


Слайд 73

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


Слайд 74

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


Слайд 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)


Слайд 76

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


Слайд 77

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


Слайд 78

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


Слайд 79

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


Слайд 80

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


Слайд 81

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


Слайд 82

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


Слайд 83

Terminology homomorphism


Слайд 84

Terminology homomorphism Same


Слайд 85

Terminology homomorphism Same -shape-ism


Слайд 86

Terminology homomorphism “structure preserving map”


Слайд 87

Terminology homomorphism Functors are “category homomorphisms”


Слайд 88

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


Слайд 89

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


Слайд 90

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


Слайд 91

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


Слайд 92

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


Слайд 93

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


Слайд 94

Terminology endomorphism


Слайд 95

Terminology endomorphism Within


Слайд 96

Terminology endomorphism Within -shape-ism


Слайд 97

Terminology endomorphism “a mapping from something back to itself”


Слайд 98

Terminology endo “a mapping from something back to itself”


Слайд 99

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


Слайд 100

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


Слайд 101

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


Слайд 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 } } }


Слайд 103

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


Слайд 104

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


Слайд 105

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


Слайд 106

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


Слайд 107

III. Monoids


Слайд 108

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


Слайд 109

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


Слайд 110

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


Слайд 111

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


Слайд 112

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


Слайд 113

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


Слайд 114

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


Слайд 115

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


Слайд 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


Слайд 117

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


Слайд 118

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


Слайд 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


Слайд 120

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


Слайд 121

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


Слайд 122

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


Слайд 123

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


Слайд 124

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


Слайд 125

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


Слайд 126

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


Слайд 127

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


Слайд 128

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


Слайд 129

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


Слайд 130

Are chairs monoids?


Слайд 131

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


Слайд 132

Chair stack


Слайд 133

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


Слайд 134

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


Слайд 135

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


Слайд 136

Monoids embody the principle of weakly-typed composability


Слайд 137

IV. Products & sums


Слайд 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)


Слайд 139

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


Слайд 140

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


Слайд 141

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


Слайд 142

Terminology isomorphism


Слайд 143

Terminology isomorphism Equal


Слайд 144

Terminology isomorphism Equal -shape-ism


Слайд 145

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


Слайд 146

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


Слайд 147

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


Слайд 148

Isomorphism object object arrows


Слайд 149

Isomorphism Same as identity


Слайд 150

Isomorphism Same as identity


Слайд 151

These 4 Shapes Wiggles Set functions Set


Слайд 152

These 4 Shapes Wiggles


Слайд 153

These 4 Shapes Wiggles


Слайд 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


Слайд 155

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


Слайд 156

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


Слайд 157

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


Слайд 158

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


Слайд 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


Слайд 160

Sums ? Products!


Слайд 161

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


Слайд 162

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


Слайд 163

Terminology Coproducts Sums are also called


Слайд 164

V. Composable systems


Слайд 165

Growing a system Banana


Слайд 166

Growing a system


Слайд 167

Growing a system


Слайд 168

Growing a system Bunch


Слайд 169

Growing a system Bunch Bunch


Слайд 170

Growing a system Bunch Bunch Bunch


Слайд 171

Growing a system Bunch Bunch Bunch BunchManager


Слайд 172

Growing a system Bunch Bunch Bunch BunchManager AnyManagers


Слайд 173


Слайд 174


Слайд 175


Слайд 176

compose


Слайд 177


Слайд 178

compose


Слайд 179

etc…


Слайд 180

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


Слайд 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


Слайд 182

VI. Abstraction


Слайд 183

Spanner


Слайд 184

Spanner AbstractSpanner


Слайд 185

Spanner AbstractSpanner AbstractToolThing


Слайд 186

Spanner AbstractSpanner AbstractToolThing GenerallyUsefulThing


Слайд 187

Spanner AbstractSpanner AbstractToolThing GenerallyUsefulThing AbstractGenerallyUsefulThingFactory


Слайд 188

Spanner AbstractSpanner AbstractToolThing GenerallyUsefulThing AbstractGenerallyUsefulThingFactory WhateverFactoryBuilder


Слайд 189


Слайд 190

That’s not what abstraction means.


Слайд 191

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


Слайд 192

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


Слайд 193

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


Слайд 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) } }


Слайд 195

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


Слайд 196

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


Слайд 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…


Слайд 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) }


Слайд 199

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


Слайд 200

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


Слайд 201

Code is rewritten each time for trivially different requirements


Слайд 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))


Слайд 203

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


Слайд 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!


Слайд 205

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


Слайд 206

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


Слайд 207

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


Слайд 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:





Ссылка: