README.md

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: colloq. free monad
cofree: colloq. free comonad
free monoid: colloq. list
yoneda: colloq. free functor built from a functor
coyoneda: colloq. free functor convertible into a functor
codensity: colloq. continuations-based free monad
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 pluses 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"