Category theory, composition & functional programming презентация

Introduction
/63

THIS IS NOT A LECTURE
/63

Lets inquire and discover together!
/63

What is programming?
/63

OOP point of view
Class diagram
/63

OOP point of view
Sequence diagram
/63

FP point of view
/63

FP point of view
/63

What is similar between those POVs?
/63

Composition
/63

Programming is Composition
/63

Is there any science which is focused on composition?
/63

Yes, it is Category Theory
/63

Why to study CT?
/63

Source: http://rs.io/why-category-theory-matters/
/63

Why to study CT?
Extremely general and wide-applicable
Gives the new way (not set-theoretic) to look at the foundations of mathematics and programming
Connect different fields and shows their similarities
/63

Why to study CT?
programming
/63

Why to study CT for software engineer?
Growing complexity of software systems and multicore\distributed systems revolution
CT is a source of extremely useful programming ideas
Gives you a great theoretic foundation for programming
CT is the kind of math that is particularly well suited for the minds of programmers
/63

What is a Category?
/63

/63

Category is:
Objects
Arrows between objects
Composition rule:
( . ) :: (a → b) → (b → c) → (a → c)
g . f = \x → g (f x)
/63

Associativity of composition
What?
/63

Associativity of composition
What?
/63

Order of the operations doesn’t matter
Associativity of composition
Why?
/63

Identity Arrow
What?
/63

Identity Arrow
What?
/63

Identity Arrow
What?
/63

It is neutral element (‘zero’) for the composition (id x = х).
It gives us a possibility to define the notion of sameness - isomorphism:
Identity Arrow
Why?
/63

Examples
/63

Category 3
/63

Category 1
/63

Category 0
/63

Integer Category
Objects: singleton (set with only one element in it)
Arrows: all possible integers
Composition: + - integer addition
Identity: 0 - zero.
/63

String Category
Objects: singleton
Arrows: all possible strings
Composition: ++ - string concatenation
Identity: «» - empty string
/63

Monoids
Set-theoretic approach
Set M
Binary operation •: M × M → M
For all a, b and c in M:
(a • b) • c = a • (b • c)
Exists e in M that for all a in M:
e • a = a • e = a.
/63

Examples:
Monoids
Category-theoretic approach
/63

Monoids
Category-theoretic approach
/63

Set Category
Objects: all sets.
Arrows: functions between sets.
Identity: id function between sets.
Composition:
( . ) :: (A → B) → (B → C) → (A → C)
/63

Hask Category
Objects: types in Haskell
Arrows: functions between them (everything is pure!)
Identity: id function: id x = x.
Composition:
( . ) :: (a → b) → (b → c) → (a → c)
/63

/63

Functions
/63

Functions in categories: Functors
/63

Functors: preserving composition
/63

Functors: preserving identities
/63

Functors: in brief
Maps objects to objects
Maps arrows to arrows
Preserve composition and identities
/63

Example
/63

/63

Why is that useful?
/63

/63

41/50
51/63

52/63

Wait, but what if you’ll need
one more container type ?
53/63

54/63

55/63

How to rescue the situation?
56/63

57/63

Conclusions and some further thoughts
CT and programming are tightly connected through composition CT – source of useful patterns for programming: Functors, Monoids, Monads, Lenses, F-algebras, Zippers and more.
CT helps to understand FP better
CT – is in some sense – Science about thinking: the proof is the extremely wide applicability of CT – from logic to biology, from physics and CS to ecology.
/63

Acknowledgements
/63

Acknowledgements
/63

Acknowledgements
Richard Feynman
Jiddu Krishnamurti
/63

Q&A
/63