BM Category Theory II 8: F-Algebra, Lambek’s Lemma , Catamorphism, Coalgebra, Anamorphism

[Continued from previous BM Category Theory …]

\boxed { \text {type Algebra f a = f a} \to \text {a} }

Intuition: [Artificial Intelligence] You teach the computer like to a Primary 6 kid, that Algebra is a type of expression (f) which, after evaluation,  returns a value.

If a = i (initial) [or u (terminal)],
\boxed { \text {(f i} \to \text {i )} \implies \text {f = Fix-point} }

Intuition: Fix-point because, the Initial “i”, after evaluating the expression f, returns itself “i”.

Lambek’s Lemma 
\boxed { \text {Initial Algebra is an Isomorphism} }

Note: Endo-functor is a functor (equivalent to function in Set Theory) within the same Category (Endo = Self = 自)

Video 8.1 F-Algebras & Lambek’s Lemma 

Video 8.2 Catamorphism & Anamorphism 

foldr ~ catamorphism (浅层变质) of a Fix-point endo-functor on a List.

Examples: Fibonacci, Sum_List

Remark: Cool Math! the more  advanced concept it is, the more closer to Nature (eg.Geology, Biology) : Catamorphism 浅层(风化)变质, or “thin-layer change in nature” (in Functional Programming languages: foldr or map) eg : add1 to a list (1 5 3 8…) 
= (2 6 4 9 …)

\boxed { \text {type Coalgebra f a = a} \to \text {f a} }

Intuition: Reverse of Algebra, given a value, Coalgebra returns an expression (f).

Anamorphism (合成变质) ~ unfoldr

Example: Prime numbers

Remark: Anamorphism (合成变质) or “synthesised change in nature“: eg. Start from a  “seed” prime number “2” generates  all other infinite prime numbers (3 5 7 9 11 13 17 …)

Note: In Haskell, no difference between Initial and Terminal Fix-points. However, since Fix-point is not unique, in Category Theory there is the Least Fix-point (Initial) and Greatest Fix-point (Terminal).


Reading “Understanding F-Algebra ” by BM:

Catamorphism (下态) :

Anamorphism :

F-Algebra & F-coalgebra:

BM 5&6 : Category Adjunctions 伴随函子

Adjunction is the “weakening of Equality” in Category Theory.

Equivalence of 2 Categories if:

5.2  Adjunction definition: (L, R, \epsilon, \eta ) such that the 2 triangle identities below ( red and blue) exist.

6.1 Prove: Let C any category, D a Set.

\boxed {\text {C(L 1, -)} \simeq \text {R}}

{\text {Right Adjoint R in Set category is }} {\text {ALWAYS Representable}}

1 = Singleton in Set D

From an element in the singleton Set always ‘picks’ (via the function) an image element from the other Set, hence :
\boxed {\text{Set (1, R c) } \simeq \text{Rc }}

Examples : Product & Exponential are Right Adjoints 

Note: Adjoint is a more powerful concept to understand than the universal construction of Product and Exponential.


\boxed  {\text {Every Adjunction gives a Monad}}


\boxed {\text {Left Adjoint: L } \dashv \text { R }}

R \circ \ L = m = \text { Monad}

L \circ \ C = \text { Co-Monad}

With Product (Left Adjoint) and Exponential (Right Adjoint) => \text {State Monad}

Category Theory II 2: Limits, Higher order functors

1.2 Introduction to Limit 

Analogy : Product to Cones (Limit)

2.1 Five categories used to define Limit:

  1. Index category (I)
  2. Category C: Functors (constant ,  D)
  3. Cones (Lim D)
  4. Functor Category [I, C ]:objects are (constant, D ), morphisms are natural transormations
  5. Set category of Hom-Set Cones [I,C] to Hom-Set C (c , Lim D )

2.2 Naturality

3.1 Examples: Equalizer

CoLimit = duality of Limit (inverted cone = co-Cone)

Functor Continuity = preserve Limit

BM Category Theory 8 : Function objects (Exponentials), Curry / unCurry


[Revision] Product (or Sum = co-Product) is a Bifunctor

  • takes 2 objects to produce 3rd object;
  • takes 2 morphisms to produce 3rd morphism. 

Functions are “morphisms between Category objects”  = a Hom-Set, which itself is an object : ‘a -> b’.

Using the same method of Universal Construction of Product objects in category :  

  1. Define a Pattern ,
  2. Ranking which object is better, 
  3. Pick the best object up to an UNIQUE Isomorphism.

we can similarly construct the Function Objects ‘a => b‘ (in Haskell as ‘a -> b’) :

Intuitively, the above diagram is interpreted as: 

  • evalthe Function object(a=>b) x ato return result b
  • g is up to Unique isomorphism (hSAME as ‘eval: \boxed {g = eval \circ (h \text { x } id )}

Curry / Non-curry : Associative (yellow brackets below are optional).

\boxed {z \to (a \to b ) \iff z \to a \to b }

\boxed { (f a ) \: b \iff f a \: b }

Note: function (f a) returns as a new  function which applies on argument b. Equivalently, also read as “f takes 2 arguments a, b”.


f :: Bool -> Int

Bool = {0, 1}
{ f = (Int \text { x }  Int) = Int^{2} = Int ^ {Bool}}

The number of possibilities of applying f from a to b is \boxed {b^{a}} , hence we call:  
\boxed {\text {Function object f as EXPONENTIAL}}

8.2  Algebraic Data Types