# 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).

Ref:

Reading “Understanding F-Algebra ” by BM: https://bartoszmilewski.com/2013/06/10/understanding-f-algebras/

Catamorphism (下态) : https://www.zhihu.com/question/52180621/answer/129582557

Anamorphism : https://zhuanlan.zhihu.com/cofree/21354189

F-Algebra & F-coalgebra: http://stackoverflow.com/a/16022059/5822795

# 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.

6.2

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

vice-versa.

$\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

8.1

[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”.

Example:

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

# BM Category Theory 7:  Category of categories

7.1 Product (Sum ) of Categories = Bifunctor

Category of categories : Cat

$TensorProduct \bigotimes 1$

7.2 Monoidal Categories, Profunctor