[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 - 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