Category theory for beginners

Explains the basic concepts of Category Theory, useful terminology to help understand the literature, and why it's so relevant to software engineering.

Published in: Engineering

Category theory for beginners from kenbot

Transcript

• 1. Category Theory for beginners Melbourne Scala User Group Feb 2015 @KenScambler A B C
• 2. Abstract maths… for us? Dizzyingly abstract branch of maths “Abstract nonsense”? Programming = maths Programming = abstraction Really useful to programming!
• 3. 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
• 4. 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
• 5. I. Categories
• 6. Category Objects
• 7. Category Objects Arrows or morphisms
• 8. Category Objects Arrows Domain f dom(f)
• 9. Category Objects Arrows Domain/Codomain f cod(f) dom(f)
• 10. Category Objects Arrows Domain/Codomain dom(g) cod(g) g
• 11. Category Objects Arrows Domain/Codomain
• 12. Category Objects Arrows Domain/Codomain Composition f
• 13. Category Objects Arrows Domain/Codomain Composition f g
• 14. Category Objects Arrows Domain/Codomain Composition f g g ∘ f
• 15. Category Objects Arrows Domain/Codomain Composition f
• 16. Category Objects Arrows Domain/Codomain Composition f h
• 17. Category Objects Arrows Domain/Codomain Composition f h h ∘ f
• 18. Category Objects Arrows Domain/Codomain Composition Identity
• 19. Category Compose ∘ : (B  C)  (A  B)  (A  C) Identity id : A  A
• 20. Category Laws Associative Law (f ∘ g) ∘ h = f ∘ (g ∘ h ) Identity Laws f ∘ id = id ∘ f = f
• 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. Associative law (f ∘ g) ∘ h = f ∘ (g ∘ h ) f g h (g ∘ h) (f ∘ g)
• 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. Identity laws f ∘ id = id ∘ f = f f id id
• 32. Examples Infinite categories Finite categories Objects can represent anything Arrows can represent anything As long as we have composition and identity!
• 33. Sets & functions Person String Integer bestFriend length name age +1
• 34. Sets & functions Infinite arrows from composition +1∘ length ∘ name bestFriend ∘ bestFriend bestFriend ∘ bestFriend ∘ bestFriend +1∘ age∘ bestFriend
• 35. Sets & functions Objects Arrows Composition Identity
• 36. Sets & functions Objects = sets (or types) Arrows = functions Composition = function composition Identity = identity function
• 37. Zero
• 38. One
• 39. Two
• 40. Three
• 41. Class hierarchy IFruit IBanana AbstractBanana BananaImpl MockBanana Tool Spanner
• 42. Class hierarchy Objects Arrows Composition Identity
• 43. Class hierarchy Objects = classes Arrows = “extends” Composition = “extends” is transitive Identity = trivial
• 44. Class hierarchy Partially ordered sets (posets) Objects = elements in the set Arrows = ordering relation ≤ Composition = ≤ is transitive Identity = trivial
• 45. World Wide Web www.naaawcats.com No dogs allowed! www.robodogs.com See here for more robots www.coolrobots.com BUY NOW!!!!
• 46. World Wide Web Objects = webpages Arrows = hyperlinks Composition = Links don’t compose Identity
• 47. World Wide Web Graphs Objects = nodes Arrows = edges Composition = Edges don’t compose Identity
• 48. “Free Category” from graphs! Objects = nodes Arrows = paths (0 to many edges) Composition = aligning paths end to end Identity = you’re already there
• 49. 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] }
• 50. 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) }
• 51. 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] }
• 52. Category of Garden Hoses [live code example]
• 53. Categories embody the principle of strongly-typed composability
• 54. II. Functors
• 55. Functors Functors map between categories Objects  objects Arrows  arrows Preserves composition & identity
• 56. Functor laws Composition Law F(g ∘ f) = F(g) ∘ F(f) Identity Law F(idA) = idF(A)
• 57. C F DCategory Category Functor
• 58. C F DCategory Category Functor CatCategory of categories
• 59. C F DCategory Category Functor CatCategory of categories Objects = categories Arrows = functors Composition = functor composition Identity = Identity functor
• 60. C F D A B C g ∘ f f g
• 61. C F D A B C g ∘ f f g F(A)
• 62. C F D A B C g ∘ f f g F(A) F(B)
• 63. C F D A B C g ∘ f f g F(A) F(B) F(C)
• 64. C F D A B C g ∘ f f g F(A) F(B) F(C) F(f)
• 65. C F D A B C g ∘ f f g F(A) F(B) F(C) F(f) F(g )
• 66. C F D A B C g ∘ f f g F(A) F(B) F(C) F(f) F(g ) F(g ∘ 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 ) F(g ∘ f) Composition Law F(g ∘ 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)
• 76. g ∘ f f g F(f) F(g ) Composition Law F(g ∘ f) = F(g) ∘ F(f) F(g) ∘ F(f) F(g ∘ f)
• 77. Identity law F(idA)= idF(A) A
• 78. Identity law F(idA)= idF(A) A idA
• 79. Identity law F(idA)= idF(A) A idA F(idA)
• 80. Identity law F(idA)= idF(A) A
• 81. Identity law F(idA)= idF(A) A F(A)
• 82. Identity law F(idA)= idF(A) A F(A) idF(A)
• 83. Identity law F(idA)= idF(A) A F(A) idF(A) A idA F(idA)
• 84. Terminology homomorphism
• 85. Terminology homomorphism Same
• 86. Terminology homomorphism Same-shape-ism
• 87. Terminology homomorphism “structure preserving map”
• 88. Terminology homomorphism Functors are “category homomorphisms”
• 89. Functors in code trait Functor[F[_]] { def map[A,B](fa: F[A], f: A => B): F[B] }
• 90. Functors in code trait Functor[F[_]] { def map[A,B](fa: F[A], f: A => B): F[B] } Objects to objects
• 91. Functors in code trait Functor[F[_]] { def map[A,B](fa: F[A], f: A => B): F[B] } Arrows to arrows
• 92. Functors in code trait Functor[F[_]] { def map[A,B]: (A => B) => (F[A] => F[B]) } Arrows to arrows
• 93. Functors laws in code fa.map(f).map(g) == fa.map(g compose f)
• 94. Functors laws in code fa.map(a => a) == fa
• 95. Terminology endomorphism
• 96. Terminology endomorphism Within
• 97. Terminology endomorphism Within -shape-ism
• 98. Terminology endomorphism “a mapping from something back to itself”
• 99. Terminology endo “a mapping from something back to itself”
• 100. Endofunctors In Scala, all our functors are actually endofunctors. Type F Category Category Endofunctor Type
• 101. Endofunctors Luckily, we can represent any functor in our type system as some F[_] Type F Category Category Endofunctor Type
• 102. List Functor sealed trait List[+A] case class Cons(head: A, tail: List[A]) extends List[A] case object Nil extends List[Nothing]
• 103. 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 } } }
• 104. List Functor potatoList .map(mashEm) .map(boilEm) .map(stickEmInAStew)
• 105. List Functor userList .map(_.name) .map(_.length) .map(_ + 1) .map(_.toString)
• 106. Other functors trait Tree[A] trait Future[A] trait Process[A] trait Command[A] X => A (X, A) trait Option[A]
• 107. Functors Fundamental concept in Category Theory Super useful Everywhere Staple of functional programming Write code that’s ignorant of unnecessary context
• 108. III. Monoids
• 109. Monoids Some set we’ll call M Compose • : M × M  M Identity id : M
• 110. Monoid Laws Associative Law (f • g) • h = f • (g • h ) Identity Laws f • id = id • f = f
• 111. Category Laws Associative Law (f ∘ g) ∘ h = f ∘ (g ∘ h ) Identity Laws f ∘ id = id ∘ f = f
• 112. Monoids Compose • : M × M  M Identity id : M
• 113. Category Compose ∘ : (B  C)  (A  B)  (A  C) Identity id : A  A
• 114. Category with 1 object Compose ∘ : (A  A)  (A  A)  (A  A) Identity id : A  A
• 115. Category with 1 object Compose ∘ : M  M M Identity id : M
• 116. Monoids are categories Each arrow is an element in the monoid Only one object
• 117. 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
• 118. M H N Monoid Monoid Monoid homomorphism (SM, •M, idM) (SN, •N, idN)
• 119. M H N Monoid Monoid Monoid homomorphism (SM, •M, idM) (SN, •N, idN) MonCategory of monoids
• 120. M H N Monoid Monoid Monoid homomorphism (SM, •M, idM) (SN, •N, idN) MonCategory of monoids Objects = monoids Arrows = monoid homomorphisms Composition = function composition Identity = Identity function
• 121. M H N SM SN “structure-preserving map” Set Set function h Sets Where h preserves composition & identity
• 122. Example String length is a monoid homomorphism from (String, +, "") to (Int, +, 0)
• 123. Preserves identity Preserves composition "".length == 0 (str1 + str2).length = str1.length + str2.length
• 124. Monoids in code trait Monoid[M] { def compose(a: M, b: M): M def id: M }
• 125. Monoids in code def foldMonoid[M: Monoid]( ms: Seq[M]): M = { ms.foldLeft(Monoid[M].id) (Monoid[M].compose) }
• 126. Int / 0 / + import IntAddMonoid._ foldMonoid[Int](Seq( 1,2,3,4,5,6))  21
• 127. Int / 1 / * import IntMultMonoid._ foldMonoid[Int](Seq( 1,2,3,4,5,6))  720
• 128. String / "" / + foldMonoid[String](Seq( "alea", "iacta", "est"))  ”aleaiactaest"
• 129. Endos / id / ∘ def mash: Potato => Potato def addOne: Int => Int def flipHorizontal: Shape => Shape def bestFriend: Person => Person
• 130. A=>A / a=>a / compose foldMonoid[Int => Int](Seq( _ + 12, _ * 2, _ - 3))  (n: Int) => ((n + 12) * 2) - 3
• 131. Are chairs monoids?
• 132. Chair Composition = You can’t turn two chairs into one Identity =
• 133. Chair stack
• 134. Chair stack Composition = stack them on top Identity = no chairs
• 135. Chair Stack is the free monoid of chairs Protip: just take 0-to-many of anything, and you get a monoid for free
• 136. …almost Real monoids don’t topple; they keep scaling
• 137. Monoids embody the principle of weakly-typed composability
• 138. IV. Products & sums
• 139. 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)
• 140. Algebraic Data Types Cons(A × List[A]) + Nil Some(A) + None OK(A) + Error YellowWiggle + BlueWiggle + RedWiggle + PurpleWiggle Street × Suburb × Postcode × State
• 141. Algebraic Data Types A × List[A] + 1 A + 1 A + 1 4 Street × Suburb × Postcode × State
• 142. Algebraic Data Types A × List[A] + 1 A + 1 A + 1 4 Street × Suburb × Postcode × State isomorphic
• 143. Terminology isomorphism
• 144. Terminology isomorphism Equal
• 145. Terminology isomorphism Equal-shape-ism
• 146. Terminology isomorphism “Sorta kinda the same-ish” but I want to sound really smart - Programmers
• 147. Terminology isomorphism “Sorta kinda the same-ish” but I want to sound really smart - Programmers
• 148. Terminology isomorphism One-to-one mapping between two objects so you can go back-and-forth without losing information
• 149. Isomorphism object object arrows
• 150. Isomorphism Same as identity
• 151. Isomorphism Same as identity
• 152. These 4 Shapes Wiggles Set functions Set
• 153. These 4 Shapes Wiggles
• 154. These 4 Shapes Wiggles
• 155. There can be lots of isos between two objects! If there’s at least one, we can say they are isomorphic or A ≅ B
• 156. Products A × BA B first seco nd Given the product of A-and-B, we can obtain both A and B
• 157. Sums A + BA B left right Given an A, or a B, we have the sum A-or-B
• 158. Opposite categories C Cop A B C g ∘ f f g A B C fop ∘ gop fop gop Isomorphic!
• 159. A B C g ∘ f f g A B C f ∘ g f g Just flip the arrows, and reverse composition!
• 160. 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
• 161. Sums ≅ Products!
• 162. Terminology dual An object and its equivalent in the opposite category are to each other.
• 163. Terminology Co-(thing) Often we call something’s dual a
• 164. Terminology Coproducts Sums are also called
• 165. V. Composable systems
• 166. Growing a system Banana
• 167. Growing a system
• 168. Growing a system
• 169. Growing a system Bunch
• 170. Growing a system Bunch Bunch
• 171. Growing a system Bunch Bunch Bunch
• 172. Growing a system Bunch Bunch Bunch BunchManager
• 173. Growing a system Bunch Bunch Bunch BunchManager AnyManagers
• 174. compose
• 175. compose
• 176. etc…
• 177. Using composable abstractions means your code can grow without getting more complex Categories and Monoids capture the essence of composition in software!
• 178. Look for Monoids and Categories in your domain where you can You can even bludgeon non- composable things into free monoids and free categories
• 179. VI. Abstraction
• 180. Spanner
• 181. Spanner AbstractSpanner
• 182. Spanner AbstractSpanner AbstractToolThing
• 183. Spanner AbstractSpanner AbstractToolThing GenerallyUsefulThing
• 184. Spanner AbstractSpanner AbstractToolThing GenerallyUsefulThing AbstractGenerallyUsefulThingFactory
• 185. Spanner AbstractSpanner AbstractToolThing GenerallyUsefulThing AbstractGenerallyUsefulThingFactory WhateverFactoryBuilder
• 186. That’s not what abstraction means.
• 187. Code shouldn’t know things that aren’t needed.
• 188. def getNames(users: List[User]): List[Name] = { users.map(_.name) }
• 189. def getNames(users: List[User]): List[Name] = { println(users.length) users.map(_.name) } Over time…
• 190. 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) } }
• 191. “Oh, now we need the roster of names! A simple list won’t do.”
• 192. def getRosterNames(users: Roster[User]): Roster[Name] = { users.map(_.name) }
• 193. 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…
• 194. 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) }
• 195. When code knows too much, soon new things will appear that actually require the other stuff.
• 196. Coupling has increased. The mixed concerns will tangle and snarl.
• 197. Code is rewritten each time for trivially different requirements
• 198. def getNames[F: Functor](users: F[User]): F[Name] = { Functor[F].map(users)(_.name) } getNames(List(alice, bob, carol)) getNames(Roster(alice, bob, carol))
• 199. Not only is the abstract code not weighed down with useless junk, it can’t be! Reusable out of the box!
• 200. Abstraction is about hiding unnecessary information. This a good thing. We actually know more about what the code does, because we have stronger guarantees!
• 201. We’ve seen deep underlying patterns beneath superficially different things A×B A+B
• 202. Just about everything ended up being in a category, or being one.
• 203. There is no better way to understand the patterns underlying software than studying Category Theory.
• 204. 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