Skip to content

Instantly share code, notes, and snippets.

@jamesdabbs

jamesdabbs/categories.md

Created July 2, 2019 15:22
Star
Embed
What would you like to do?
Learn more about clone URLs
Download ZIP
Categories for the Working Programmer - a deckset presentation
Raw
categories.md

[fit] Category Theory

[fit] For the Working Programmer

James Dabbs @jamesdabbs Santa Barbara JavaScript

inline fit

[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

inline fit

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

inline fit

[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 a f : 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 a f : A -> M<B>
  • a way of embedding an A into a M<A>

Commonalities

Each of these examples have the following in common

  • a type-level transformation M
  • a way of chaining an M<A> with a f : A -> M<B>
  • a way of embedding an A into a M<A>

And because of this, each example is composable.

Monads

  • A functor M which transforms a type A into a new type M<A>
  • unit : A -> M<A>
  • bind : M<A> -> (A -> M<B>) -> M<B>

subject to a few natural rules

Monads

  • Maybe - computation with undefined
  • Either - computation with errors
  • List - multi-valued computation
  • Async - asyncronous computation

Monads

  • IO - computations which perform an IO action
  • Reader - computations with access to a read-only context
  • State - 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

[fit] Category Theory

[fit] For the Working Programmer

James Dabbs @jamesdabbs Santa Barbara JavaScript

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment