[fit] Category Theory
[fit] For the Working Programmer
James Dabbs @jamesdabbs Santa Barbara JavaScript
[fit] Design
[fit] Patterns
Design Patterns
- Prepackaged solutions to problems
Design Patterns
- Prepackaged solutions to shapes of problems
Design Patterns
- Prepackaged solutions to shapes of problems
- Shared language for solutions - presenter, strategy, visitor
Design Patterns
Elements of Reusable Object-Oriented Software
Gang of Four
Favor object composition over class inheritance -- Gang of Four
[fit] Composition
Composition
- Building up large, complex systems by assembling smaller, simpler ones
Goal
- To better understand how things can be composed
- To learn a shared language for describing patterns of composition
[fit] Category
[fit] Theory
- Algebra
- Algebra - what can we do with
+
and*
?
- Algebra - what can we do with
+
and*
? - Geometry
- Algebra - what can we do with
+
and*
? - Geometry - what can we do with angles and distances?
- Algebra - what can we do with
+
and*
? - Geometry - what can we do with angles and distances?
- Category theory
- Algebra - what can we do with
+
and*
? - Geometry - what can we do with angles and distances?
- Category theory - what can we do with functions and composition?
Categories
A category is
Categories
A category is
- a collection of objects
Categories
A category is
- a collection of objects
- a collection of functions between those objects
Categories
A category is
- a collection of objects
- a collection of functions between those objects
- a means of composing those functions
subject to a few natural rules
Categories - Rules
Composition must have an identity id
.
Categories - Rules
Composition must have an identity id
. So
compose(f, id) = f = compose(id, f)
for any function f
Categories - Rules
Composition must be associative.
Categories - Rules
Composition must be associative. So
compose(f, compose(g, h)) = compose(compose(f, g), h)
for any functions f
, g
, h
.
Categories - Rules
"Composition is associative" is a fancy way of saying, "we can write compose(f, g, h)
and not worry about the order"
Categories - Examples
Objects: sets Functions: functions between sets Composition:
compose(f, g) = f ∘ g
Categories - Examples
Objects: JavaScript types Functions: JavaScript functions Composition:
compose(f, g) = x => f(g(x))
Categories - Examples
Since composition is associative, we can write
compose = (...fs) => x => fs.reduceRight((v, f) => f(v), x)
to compose arbitrarily many functions together in order.
Categories - Examples
Objects: JavaScript types
Functions: f : A -> [B]
Categories - Examples
f : A -> [B]
g : B -> [C]
Composition: ?
Categories - Examples
f : A -> [B]
g : B -> [C]
Composition:
compose(f, g) = a => f(a).flatMap(g)
[fit] Composition
Composition
compose = (...fs) => x => fs.reduceRight((v, f) => f(v), x)
pipe = (...fs) => x => fs.reduce((v, f) => f(v), x)
Composition
get = key => obj => obj[key]
uppercase = str => str.toUpperCase()
take = length => str => str.slice(0, length)
reverse = str => str.split('').reverse().join('')
Composition
pipe(
get('name'),
uppercase,
take(6),
reverse
)({ name: 'James Dabbs' })
Composition
const pipeline = pipe(
get('name'),
uppercase,
take(6),
reverse
)
pipeline({ name: 'James Dabbs' })
Composition
get('name') : Object -> String
uppercase : String -> String
take(6) : String -> String
reverse : String -> String
Composition
get('name') : Object -> String
take(6) : String -> String
Composition
get('name') : Object -> String
take(6) : String -> String
get : String -> Object -> String
take : Integer -> String -> String
Composition
const pipeline = pipe(
get('name'),
uppercase,
take(6),
reverse
)
pipeline({ name: 'James Dabbs' })
Composition
// controller : Request -> JSON
const controller = pipe(
validate,
perform,
present
)
Composition
// controller : Request -> JSON
const controller = pipe(
validate, // pure, but may fail validation
perform, // queries db
present // pure
)
Composition
const sendPasswordReset = pipe(
promptFor,
findUser,
generateResetToken,
deliverResetToken
)("Email")
Composition
prompt : String -> EmailAddress
findUser : EmailAddress -> User
generateResetToken : User -> ResetToken
deliverResetToken : ResetToken -> Email
[fit] Live
Composition
prompt : String -> EmailAddress
findUser : EmailAddress -> User
generateResetToken : User -> ResetToken
deliverResetToken : ResetToken -> Email
Composition - Either
prompt : String -> Either<string, EmailAddress>
findUser : EmailAddress -> Either<string, User>
generateResetToken : User -> Either<string, ResetToken>
deliverResetToken : ResetToken -> Either<string, Email>
Composition - Either
prompt : String -> Either<string, EmailAddress>
findUser : EmailAddress -> Either<string, User>
generateResetToken : User -> Either<string, ResetToken>
deliverResetToken : ResetToken -> Either<string, Email>
prompt("Email").
chain(findUser).
map(generateResetToken).
chain(deliverResetToken)
Composition - Either
type Either<A, B> = Left<A> | Right<B>
right(value).chain(f) = right(f(value))
left(error).chain(f) = left(error)
Composition - Maybe
prompt : String -> EmailAddress | undefined
findUser : EmailAddress -> User | undefined
generateResetToken : User -> ResetToken | undefined
deliverResetToken : ResetToken -> Email | undefined
Composition - Maybe
type Maybe<A> = Some<A> | None<A>
some(a).chain(f) = some(f(a))
none().chain(f) = none()
Composition - Maybe
prompt : String -> Maybe<EmailAddress>
findUser : EmailAddress -> Maybe<User>
generateResetToken : User -> Maybe<ResetToken>
deliverResetToken : ResetToken -> Maybe<Email>
prompt("Email").
chain(findUser).
map(generateResetToken).
chain(deliverResetToken)
Composition - Async
prompt : String -> Async<EmailAddress>
findUser : EmailAddress -> Async<User>
generateResetToken : User -> Async<ResetToken>
deliverResetToken : ResetToken -> Async<Email>
Composition - Async
type Async<A> = Promise<A>
Composition - Async
type Async<A> = Promise<A>
async(a).chain(f) = a.then(f)
Commonalities
Each of these examples have the following in common
Commonalities
Each of these examples have the following in common
- a type-level transformation
M
Commonalities
Each of these examples have the following in common
- a type-level transformation
M
- a way of chaining an
M<A>
with af : A -> M<B>
Commonalities
Each of these examples have the following in common
- a type-level transformation
M
- a way of chaining an
M<A>
with af : A -> M<B>
- a way of embedding an
A
into aM<A>
Commonalities
Each of these examples have the following in common
- a type-level transformation
M
- a way of chaining an
M<A>
with af : A -> M<B>
- a way of embedding an
A
into aM<A>
And because of this, each example is composable.
Monads
- A functor
M
which transforms a typeA
into a new typeM<A>
unit : A -> M<A>
bind : M<A> -> (A -> M<B>) -> M<B>
subject to a few natural rules
Monads
Maybe
- computation withundefined
Either
- computation with errorsList
- multi-valued computationAsync
- asyncronous computation
Monads
IO
- computations which perform anIO
actionReader
- computations with access to a read-only contextState
- computations with access to mutable state
[fit] A monad is
[fit] a way of extending functions
[fit] composably
State
type State<S, A> = S -> (A, S)
State
type State<S, A> = S -> (A, S)
f : A -> State<S, B> = A -> S -> (B, S)
g : B -> State<S, C> = B -> S -> (C, S)
State
type State<S, A> = S -> (A, S)
f : A -> State<S, B> = A -> S -> (B, S)
g : B -> State<S, C> = B -> S -> (C, S)
Need
compose(f, g) : A -> S -> (C, S)
Takeaways
Takeaways
- Shared language is crucial for shared understanding
Takeaways
- Shared language is crucial for shared understanding
- Category theory is the lingua franca of composition
Takeaways
- Shared language is crucial for shared understanding
- Category theory is the lingua franca of composition
- You could have invented a monad
Takeaways
- Shared language is crucial for shared understanding
- Category theory is the lingua franca of composition
- You could have invented a monad (maybe)
Takeaways
- Shared language is crucial for shared understanding
- Category theory is the lingua franca of composition
- You could have invented a monad (maybe)
- Learn you a Haskell
References
- https://blog.ploeh.dk/2017/10/04/from-design-patterns-to-category-theory/
- https://jrsinclair.com/articles/2019/elegant-error-handling-with-the-js-either-monad/
- https://medium.com/@luijar/kliesli-compositions-in-javascript-7e1a7218f0c4
- https://bartoszmilewski.com/2014/10/28/category-theory-for-programmers-the-preface/
- https://www.freecodecamp.org/news/pipe-and-compose-in-javascript-5b04004ac937/
- http://learnyouahaskell.com/
[fit] Category Theory
[fit] For the Working Programmer
James Dabbs @jamesdabbs Santa Barbara JavaScript