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: