{{ message }}

Instantly share code, notes, and snippets.

# jamesdabbs/categories.md

Created Jul 2, 2019
Categories for the Working Programmer - a deckset presentation

# [fit] For the Working Programmer

James Dabbs @jamesdabbs Santa Barbara JavaScript # 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

# 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] 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?

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)
``````

# 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
generateResetToken : User         -> ResetToken
deliverResetToken  : ResetToken   -> Email
``````

# Composition

``````prompt             : String       -> EmailAddress
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>
generateResetToken : User         -> Maybe<ResetToken>
deliverResetToken  : ResetToken   -> Maybe<Email>

prompt("Email").
chain(findUser).
map(generateResetToken).
chain(deliverResetToken)
``````

# Composition - Async

``````prompt             : String       -> Async<EmailAddress>
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.

• 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

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

• `IO` - computations which perform an `IO` action
• `Reader` - computations with access to a read-only context
• `State` - computations with access to mutable state

# 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

• 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)