## Programming subset of Category Theory Cheatsheet

functor: given `Producer[A]` with output `A`, allows post-processing values with `A => B` to get `Producer[B]`
contravariant functor: given `Consumer[A]` with input `A`, allows pre-processing values with `B => A` to get `Consumer[B]`
profunctor: given `Pipe[A, B]` with input `A` and output `B`, allow pre-processing input values with `C => A`, and post-processing output values with `B => D` to get `Pipe[C, D]`
applicative: gives `map2`, `map3` ... `mapN`. where `map2: (F[A], F[B]), (A, B => C) => F[C]` ... `mapN: (F[A] .. F[N]), (A .. N => Z) => F[Z]`
monad: gives `flatten: F[F[A]] => F[A]`. If you `map`, then `flatten`, you can chain operations: `flatten(maybeReadFile.map(maybeParseAsInteger)) = Maybe[Integer]`
monoid: gives `plus` and `zero`
alternative: gives `orElse: F[A], F[A] => F[A]`
category: function-like entity with `compose` and `identity`
arrow: category with `fork`/`join`
comonad: given `Cursor[A]` with output `A`, allows post-processing values under nested cursors with `Cursor[A] => B` to get `Cursor[B]`. i.e.

``````List(1,1,2).extend(sumOfList) = List(4, 3, 2)
// list's cursor = head + tail
// sumOfList(List(1,1,2)) = 4
// sumOfList(List(1,2))   = 3
// sumOfList(List(2))     = 2
sumOfList: List[Int] => Int

AST(nodes...).extend(typecheckNodeAndChildren) = AST(typednodes...) // the type of each node depends on the types of child nodes
// ast's cursor = node + children
typecheckNodeAndChildren: AST[Node] => TypedNode
``````

algebra: interface + laws

free X: data that only represents the operations of an algebraic structure X, but doesn't do anything.
free monoid: colloq. list
yoneda: colloq. free functor built from a functor
coyoneda: colloq. free functor convertible into a functor
day convolution: representation of `map2`

tensor: binder of multiple arguments. default tensor is tuple: `(A, B) => C`

on monoids: `applicative`, `alternative`, `monad` and `category` are all specialized monoids with different tensors
intuition:

• monoid tensor is `tuple`

`````` plus: (A, A) => A
// if i can combine tuples of A then i can combine a tupleN of A!
// i can squish any List[A] into one A!
``````
• monad tensor is `compose`. `compose F G = F[G[_]]`

`````` plus: F compose F => F  // flatten: F[F[_]] => F[_]
// if i can combine composes of F then i can combine a composeN of F!
// i can flatten any F[F[F[F[F[F[F... into one F!
``````
• alternative tensor is `higherTuple`. `higherTuple F G = (F[_], G[_])`

`````` plus: F higherTuple F => F  // orElse: F[_], F[_] => F[_]
// if i can combine higherTuples of F then i can combine a higherTupleN of F!
// i can choose from any paths (F orElse F orElse F orElse...) one successful F!
``````
• applicative tensor is `map2` (day convolution). `map2 F G = (F[A], G[B], (A, B) => C)`

`````` plus: F map2 F => F  // map2: (F[A], F[B], (A, B) => C) => F[C]
// if i can combine map2s of F then i can combine a mapN of F!
// i can zip any (F[A], F[B] ... F[N]) with an (A ... N => Z) to get one F[Z]!
``````

f-algebra: `F[A] => A`, fold-like function
f-coalgebra: `A => F[A]`, unfold-like function
recursion: `fold`-like function calling itself with some context while `reducing` a context.
corecursion: `unfold`-like function calling itself with some context while `building up` a context

cata: `fold`
ana: `unfold`
hylo: `unfold` then `fold`
meta: `fold` then `unfold`
prepro: `map` then `fold`
postpro: `unfold` then `map`
para: `fold` with cursor
zygohistoprepro: dumb meme
elgot algebra: `unfold` then `fold` where `unfold` part can short-circuit
elgot coalgebra: `unfold` then `fold` with cursor, where cursor tail is mapped by elgot coalgebra

benefits of FP:
Most programming tasks are reduced to variants of `plus`.

or even:
Most programming tasks can be summarized as "do a bunch of stuff".
FP separates the `bunch` and the `do` parts.
Use any of the available `plus`es to bunch your program together, then write an interpreter for it and just `do` it.
And since we can have multiple interpreters, we also gain the ability to "do a bunch of different stuff"

Get A Weekly Email With Trending Projects For These Topics
No Spam. Unsubscribe easily at any time.
Functional Programming (10,979
Free Software (8,370
Tensor (2,379