A презентация

Содержание

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

Слайд 1Category Theory for beginners
Melbourne Scala User Group Feb 2015
@KenScambler
A
B
C

Слайд 2Abstract maths… for us?
Dizzyingly abstract branch of maths
“Abstract nonsense”?
Programming = maths
Programming

= abstraction
Really useful to programming!


Слайд 3The plan
Basic Category Theory concepts
New vocabulary (helpful for further reading)
How it

relates to programming
Category Theory as seen by maths versus FP

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


Слайд 5I. Categories

Слайд 6Category





Objects

Слайд 7Category
Objects
Arrows or morphisms





Слайд 8Category
Objects
Arrows
Domain





f
dom(f)

Слайд 9Category
Objects
Arrows
Domain/Codomain





f
cod(f)
dom(f)

Слайд 10Category
Objects
Arrows
Domain/Codomain





dom(g)
cod(g)
g

Слайд 11Category
Objects
Arrows
Domain/Codomain





Слайд 12Category
Objects
Arrows
Domain/Codomain
Composition





f

Слайд 13Category
Objects
Arrows
Domain/Codomain
Composition





f
g

Слайд 14Category
Objects
Arrows
Domain/Codomain
Composition





f
g
g ∘ f

Слайд 15Category
Objects
Arrows
Domain/Codomain
Composition





f

Слайд 16Category
Objects
Arrows
Domain/Codomain
Composition





f
h

Слайд 17Category
Objects
Arrows
Domain/Codomain
Composition





f
h
h ∘ f

Слайд 18Category
Objects
Arrows
Domain/Codomain
Composition
Identity





Слайд 19Category
Compose
∘ : (B ? C) ? (A ? B) ? (A

? C)

Identity
id : A ? A

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

Слайд 32Examples
Infinite categories
Finite categories
Objects can represent anything
Arrows can represent anything
As long as

we have composition and identity!

Слайд 33Sets & functions
Person
String
Integer
bestFriend
length
name
age
+1

Слайд 34Sets & functions
Infinite arrows from composition
+1∘ length ∘ name
bestFriend ∘ bestFriend
bestFriend

∘ bestFriend ∘ bestFriend
+1∘ age∘ bestFriend






Слайд 35Sets & functions
Objects
Arrows
Composition
Identity

Слайд 36Sets & functions
Objects = sets (or types)
Arrows = functions
Composition = function

composition
Identity = identity function

Слайд 41Class hierarchy
IFruit
IBanana
AbstractBanana
BananaImpl
MockBanana
Tool
Spanner

Слайд 42Class hierarchy
Objects
Arrows
Composition
Identity

Слайд 43Class hierarchy
Objects = classes
Arrows = “extends”
Composition = “extends” is transitive
Identity =

trivial

Слайд 44Class hierarchy Partially ordered sets (posets)
Objects = elements in the set
Arrows

= ordering relation ≤
Composition = ≤ is transitive
Identity = trivial

Слайд 45World Wide Web

www.naaawcats.com
No dogs allowed!


www.robodogs.com
See here for more robots


www.coolrobots.com
BUY NOW!!!!

Слайд 46World Wide Web
Objects = webpages
Arrows = hyperlinks
Composition = Links don’t compose
Identity

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

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

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

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

Слайд 52Category of Garden Hoses
[live code example]

Слайд 53Categories embody the principle of strongly-typed composability

Слайд 54II. Functors

Слайд 55Functors
Functors map between categories
Objects ? objects
Arrows ? arrows
Preserves composition & identity

Слайд 56Functor laws
Composition Law
F(g ∘ f) = F(g) ∘ F(f)

Identity Law
F(idA) =

idF(A)

Слайд 57C
F
D
Category
Category
Functor

Слайд 58C
F
D
Category
Category
Functor
Cat
Category of categories

Слайд 59C
F
D
Category
Category
Functor
Cat
Category of categories
Objects = categories
Arrows

= functors
Composition = functor composition
Identity = Identity functor

Слайд 60C
F
D
A
B
C
g ∘ f
f
g



Слайд 61C
F
D
A
B
C
g ∘ f
f
g


F(A)

Слайд 62C
F
D
A
B
C
g ∘ f
f
g

F(A)
F(B)

Слайд 63C
F
D
A
B
C
g ∘ f
f
g
F(A)
F(B)
F(C)

Слайд 64C
F
D
A
B
C
g ∘ f
f
g
F(A)
F(B)
F(C)
F(f)

Слайд 65C
F
D
A
B
C
g ∘ f
f
g
F(A)
F(B)
F(C)
F(f)
F(g)

Слайд 66C
F
D
A
B
C
g ∘ f
f
g
F(A)
F(B)
F(C)
F(f)
F(g)
F(g ∘ f)

Слайд 67g ∘ f
f
g
F(f)
F(g)
F(g ∘ f)
Composition Law F(g ∘ f) = F(g) ∘

F(f)








Слайд 68g ∘ f
f
g
F(f)
F(g)
F(g ∘ f)
Composition Law F(g ∘ f) = F(g) ∘

F(f)








Слайд 69g ∘ f
f
g
F(f)
F(g)
F(g ∘ f)
Composition Law F(g ∘ f) = F(g) ∘

F(f)








Слайд 70g ∘ f
f
g
F(f)
F(g)
F(g ∘ f)
Composition Law F(g ∘ f) = F(g) ∘

F(f)








Слайд 71g ∘ f
f
g
F(f)
F(g)
F(g ∘ f)
Composition Law F(g ∘ f) = F(g) ∘

F(f)








Слайд 72g ∘ f
f
g
F(f)
F(g)
F(g ∘ f)
Composition Law F(g ∘ f) = F(g) ∘

F(f)








Слайд 73g ∘ f
f
g
F(f)
F(g)
F(g ∘ f)
Composition Law F(g ∘ f) = F(g) ∘

F(f)








Слайд 74g ∘ f
f
g
F(f)
F(g)
F(g ∘ f)
Composition Law F(g ∘ f) = F(g) ∘

F(f)








Слайд 75g ∘ f
f
g
F(f)
F(g)
Composition Law F(g ∘ f) = F(g) ∘ F(f)








F(g) ∘

F(f)

Слайд 76g ∘ f
f
g
F(f)
F(g)
Composition Law F(g ∘ f) = F(g) ∘ F(f)








F(g) ∘

F(f)

F(g ∘ f)

Слайд 77Identity law
F(idA)= idF(A)







A

Слайд 78Identity law
F(idA)= idF(A)







A
idA

Слайд 79Identity law
F(idA)= idF(A)







A
idA
F(idA)

Слайд 80Identity law
F(idA)= idF(A)







A

Слайд 81Identity law
F(idA)= idF(A)






A
F(A)

Слайд 82Identity law
F(idA)= idF(A)






A
F(A)
idF(A)

Слайд 83Identity law
F(idA)= idF(A)






A
F(A)
idF(A)
A
idA
F(idA)

Слайд 84Terminology
homomorphism

Слайд 85Terminology
homomorphism
Same

Слайд 86Terminology
homomorphism
Same
-shape-ism

Слайд 87Terminology
homomorphism
“structure preserving map”

Слайд 88Terminology
homomorphism
Functors are “category homomorphisms”

Слайд 89Functors in code
trait Functor[F[_]] {
def map[A,B](fa: F[A],

f: A => B): F[B]
}

Слайд 90Functors in code
trait Functor[F[_]] {
def map[A,B](fa: F[A],

f: A => B): F[B]
}

Objects to objects

Слайд 91Functors in code
trait Functor[F[_]] {
def map[A,B](fa: F[A],

f: A => B): F[B]
}

Arrows to arrows

Слайд 92Functors in code
trait Functor[F[_]] {
def map[A,B]: (A =>

B) => (F[A] => F[B])
}

Arrows to arrows

Слайд 93Functors laws in code
fa.map(f).map(g)
==
fa.map(g compose f)

Слайд 94Functors laws in code
fa.map(a => a) == fa

Слайд 95Terminology
endomorphism

Слайд 96Terminology
endomorphism
Within

Слайд 97Terminology
endomorphism
Within
-shape-ism

Слайд 98Terminology
endomorphism
“a mapping from something back to itself”

Слайд 99Terminology
endo
“a mapping from something back to itself”

Слайд 100Endofunctors
In Scala, all our functors are
actually endofunctors.
Type
F
Category
Category
Endofunctor
Type

Слайд 101Endofunctors
Luckily, we can represent any functor in our type system as

some F[_]

Type

F

Category

Category

Endofunctor

Type

Слайд 102List Functor
sealed trait List[+A]
case class Cons(head: A, tail: List[A]) extends

List[A]
case object Nil extends List[Nothing]

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

Слайд 104List Functor
potatoList .map(mashEm) .map(boilEm) .map(stickEmInAStew)

Слайд 105List Functor
userList .map(_.name) .map(_.length) .map(_ + 1) .map(_.toString)

Слайд 106Other functors
trait Tree[A]
trait Future[A]
trait Process[A]
trait Command[A]
X => A
(X, A)
trait Option[A]


Слайд 107Functors
Fundamental concept in Category Theory
Super useful
Everywhere
Staple of functional programming
Write code that’s

ignorant of unnecessary context

Слайд 108III. Monoids

Слайд 109Monoids
Some set we’ll call M

Compose
• : M × M ?

M


Identity
id : M

Слайд 110Monoid Laws
Associative Law
(f • g) • h = f

• (g • h )


Identity Laws
f • id = id • f = f

Слайд 111Category Laws
Associative Law
(f ∘ g) ∘ h = f

∘ (g ∘ h )


Identity Laws
f ∘ id = id ∘ f = f

Слайд 112Monoids

Compose
• : M × M ? M


Identity
id : M

Слайд 113Category
Compose
∘ : (B ? C) ? (A ? B) ? (A

? C)

Identity
id : A ? A

Слайд 114Category with 1 object
Compose
∘ : (A ? A) ? (A ?

A) ? (A ? A)

Identity
id : A ? A

Слайд 115Category with 1 object
Compose
∘ : M ? M? M

Identity
id : M

Слайд 116Monoids are categories
Each arrow is an element in the monoid
Only one

object






Слайд 117Monoids are categories



Objects = placeholder singleton
Arrows

= elements of the monoid
Composition = •
Identity = id



Only one object

Each arrow is an element in the monoid

Слайд 118M
H
N
Monoid
Monoid
Monoid homomorphism
(SM, •M, idM)
(SN, •N, idN)

Слайд 119M
H
N
Monoid
Monoid
Monoid homomorphism
(SM, •M, idM)
(SN, •N, idN)
Mon
Category of monoids

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

Слайд 121M
H
N
SM
SN
“structure-preserving map”
Set
Set
function
h
Sets
Where h preserves composition & identity

Слайд 122Example
String length is a monoid homomorphism from (String, +, "") to

(Int, +, 0)

Слайд 123Preserves identity
Preserves composition
"".length == 0

(str1 + str2).length = str1.length + str2.length

Слайд 124Monoids in code
trait Monoid[M] {
def compose(a: M, b: M): M

def id: M
}

Слайд 125Monoids in code
def foldMonoid[M: Monoid]( ms: Seq[M]): M = {

ms.foldLeft(Monoid[M].id) (Monoid[M].compose)
}

Слайд 126Int / 0 / +
import IntAddMonoid._
foldMonoid[Int](Seq( 1,2,3,4,5,6))

? 21


Слайд 127Int / 1 / *
import IntMultMonoid._
foldMonoid[Int](Seq( 1,2,3,4,5,6))

? 720


Слайд 128String / "" / +
foldMonoid[String](Seq( "alea", "iacta", "est"))

? ”aleaiactaest"

Слайд 129Endos / id / ∘
def mash: Potato => Potato
def addOne: Int

=> Int
def flipHorizontal: Shape => Shape
def bestFriend: Person => Person

Слайд 130A=>A / a=>a / compose
foldMonoid[Int => Int](Seq( _ + 12, _

* 2, _ - 3))

? (n: Int) => ((n + 12) * 2) - 3


Слайд 131
Are chairs monoids?

Слайд 132Chair
Composition = You can’t turn two chairs into one
Identity =

Слайд 133Chair stack

Слайд 134Chair stack
Composition = stack them on top Identity = no chairs

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

Слайд 137Monoids embody the principle of weakly-typed composability

Слайд 138IV. Products & sums

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

Слайд 140Algebraic Data Types
Cons(A × List[A])
+ Nil
Some(A)

+ None

OK(A)
+ Error

YellowWiggle
+ BlueWiggle
+ RedWiggle
+ PurpleWiggle

Street × Suburb × Postcode × State

Слайд 141Algebraic Data Types
A × List[A] + 1
A +

1

A + 1

4

Street × Suburb × Postcode × State

Слайд 142Algebraic Data Types
A × List[A] + 1
A +

1

A + 1

4

Street × Suburb × Postcode × State

isomorphic

Слайд 143Terminology
isomorphism

Слайд 144Terminology
isomorphism
Equal

Слайд 145Terminology
isomorphism
Equal
-shape-ism

Слайд 146Terminology
isomorphism
“Sorta kinda the same-ish” but I want to sound really smart
-

Programmers

Слайд 147Terminology
isomorphism
“Sorta kinda the same-ish” but I want to sound really smart
-

Programmers

Слайд 148Terminology
isomorphism
One-to-one mapping between two objects so you can go back-and-forth without

losing information

Слайд 149Isomorphism


object
object
arrows

Слайд 150Isomorphism


Same as identity

Слайд 151Isomorphism


Same as identity

Слайд 152


These 4 Shapes
Wiggles

Set
functions
Set

Слайд 153



These 4 Shapes
Wiggles

Слайд 154



These 4 Shapes
Wiggles

Слайд 155There can be lots of isos between two objects!
If there’s at

least one, we can say they are isomorphic

or A ≅ B

Слайд 156Products
A × B
A
B
first
second
Given the product of A-and-B, we can obtain both

A and B

Слайд 157Sums
A + B
A
B
left
right
Given an A, or a B, we have the

sum A-or-B

Слайд 158Opposite categories
C
Cop
A
B
C
g ∘ f
f
g
A
B
C
fop ∘ gop
fop
gop
Isomorphic!

Слайд 159A
B
C
g ∘ f
f
g
A
B
C
f ∘ g
f
g
Just flip the arrows, and reverse composition!

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

Слайд 161Sums ≅ Products!

Слайд 162Terminology
dual
An object and its equivalent in the opposite category are
to each

other.

Слайд 163Terminology
Co-(thing)
Often we call something’s dual a

Слайд 164Terminology
Coproducts
Sums are also called

Слайд 165V. Composable systems



Слайд 166Growing a system
Banana

Слайд 167Growing a system

Слайд 168Growing a system

Слайд 169Growing a system
Bunch

Слайд 170Growing a system
Bunch
Bunch

Слайд 171Growing a system
Bunch
Bunch
Bunch

Слайд 172Growing a system
Bunch
Bunch
Bunch
BunchManager

Слайд 173Growing a system
Bunch
Bunch
Bunch
BunchManager
AnyManagers

Слайд 181Using composable abstractions means your code can grow without getting more

complex

Categories and Monoids capture the essence of composition in software!

Слайд 182Look for Monoids and Categories in your domain where you can
You

can even bludgeon non-composable things into free monoids and free categories

Слайд 183VI. Abstraction

Слайд 185Spanner
AbstractSpanner

Слайд 186Spanner
AbstractSpanner
AbstractToolThing

Слайд 187Spanner
AbstractSpanner
AbstractToolThing
GenerallyUsefulThing

Слайд 188Spanner
AbstractSpanner
AbstractToolThing
GenerallyUsefulThing
AbstractGenerallyUsefulThingFactory

Слайд 189Spanner
AbstractSpanner
AbstractToolThing
GenerallyUsefulThing
AbstractGenerallyUsefulThingFactory
WhateverFactoryBuilder

Слайд 191That’s not what abstraction means.

Слайд 192Code shouldn’t know things that aren’t needed.

Слайд 193def getNames(users: List[User]):

List[Name] = { users.map(_.name) }

Слайд 194def getNames(users: List[User]):

List[Name] = { println(users.length) users.map(_.name) }

Over time…

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

Слайд 196“Oh, now we need the roster of names! A simple list

won’t do.”

Слайд 197def getRosterNames(users: Roster[User]):

Roster[Name] = { users.map(_.name) }

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

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

Слайд 200When code knows too much, soon new things will appear that

actually require the other stuff.

Слайд 201Coupling has increased. The mixed concerns will tangle and snarl.

Слайд 202Code is rewritten each time for trivially different requirements

Слайд 203def getNames[F: Functor](users: F[User]):

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

Слайд 204Not only is the abstract code not weighed down with useless

junk, it can’t be!

Reusable out of the box!

Слайд 205
Abstraction is about hiding unnecessary information. This a good thing.
We actually

know more about what the code does, because we have stronger guarantees!

Слайд 206We’ve seen deep underlying patterns beneath superficially different things
A×B
A+B

Слайд 207Just about everything ended up being in a category, or being

one.

Слайд 208There is no better way to understand the patterns underlying software

than studying Category Theory.

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

Похожие презентации

Networking и использование для этого профессиональных соцсетей 184
Научно-методическое обеспечение качества, доступности и эффективности дошкольного образования 262
Закордонна практика 182
Праведник народов мира Кецко Антон Митрофанович, пресвитер Минской церкви ЕХБ с января 1942 по июнь 1944 285
Джеймс Кук 300
Аттестационная работа. Эссе. Проектно-исследовательская деятельность 217

Обратная связь

Если не удалось найти и скачать презентацию, Вы можете заказать его на нашем сайте. Мы постараемся найти нужный Вам материал и отправим по электронной почте. Не стесняйтесь обращаться к нам, если у вас возникли вопросы или пожелания:

Email: Нажмите что бы посмотреть 

Что такое ThePresentation.ru?

Это сайт презентаций, докладов, проектов, шаблонов в формате PowerPoint. Мы помогаем школьникам, студентам, учителям, преподавателям хранить и обмениваться учебными материалами с другими пользователями.

Для правообладателей

Яндекс.Метрика