I have found Category Theory has increased my productivity as a programmer more than any other mathematic tool at my disposal. This is my cheat sheet.
Metagraph
- Objects: a, b, c,...
- Arrows: f, g, h,...
- Domain: for each arrow, f, there is an object a = dom f
- Codomain: for each arrow, f, there is an object b = cod f
A Metacategory is a Metagraph plus
- Identity: for each object, a, there is an arrow f: a -> a
- Composition: arrows, <f, g>, where dom g = cod f, admit an arrow h: dom f - > cod g
- Composition is associatve
- Composition obeys left and right unit laws
A Category is an interpretation of a Metacategory within Set Theory.
A Functor, T: C - > B, is a morphism of categories.
- Object function: mapping objects c in C to objects Tc in B
- Arrow function: mapping arrows f in C to arrows Tf in B where the unit and composition are preserved
- T is Covariant if for each arrow f: a -> b in C, Tf: Ta -> Tb in B
- T is Contravariant if for each arrow f: a -> b in C, Tf: Tb -> Ta (arrows are reversed).
- T is an Endofunctor if B = C
A Natural Transformation, t: S -*> T, is a morphism of Functors, T: C -> B.
- Each object c in C yields an arrow, tc: Sc -> Tc, in B
- Each arrow f: a -> b in C holds tb(Sf(Sc)) = tb(Sb) = Tb
A Monad in a Category, C, is an endofunctor, T, with two Natural Transformations; e: Id(C) -*> T, m: T(T) -*> T.
- m(Tm) = m(mT)
- m(Te) = m(eT) = Id(T)
A Monic is an arrow m: a -> b in a Category, C, that is left cancellable.
Given parallel arrows f, g: d -> a, m(f) = m(g) implies f = g
An Epi is an arrow h: a -> b in a Category, C, that is right cancellable.
- Given parallel arrows f, g: b -> c, f(h) = g(h) implies f = g.
An Idempotent is an arrow, f: b -> b, where f(f) = f.
An Initial object, a, of a Category, C, yields for each object, c, in C exactly one arrow f: a -> c.
A Terminal object, a, of a Category, C, yields for each object, c, in C exactly one arrow f: c -> a.
A Monoid is a Category with a single object.
A Groupoid is a Category, C, where for each arrow, f, in C there is an inverse of f.
A Dual Category, D, of a Category, C, is C with all arrows reversed
- An arrow, f: a -> b, in C yields an arrow, g: b -> a, in D.