# Tag Archives: category theory

# The Yoneda Lemma

**Representable Functor** F of C ( a, -):

Video 4.2 Yoneda Lemma

Prove :

**Yoneda Lemma** :

Proof: By “Diagram chasing” below, shows that

**
Left-side**: is indeed a (co-variant) Functor.

**(Higher-order Function**)

**Right-side**: Functor “**F a**“. (**Data Structure)**

Note: When talking about the natural transformations, always mention their component “x”:

Video 5.1 Yoneda Embedding

**Example 1**: F = List functor [x]

**Example 2**: F = C (b, -)

**Note**: check a , b is in co-variant or contra-variant position.

Example 3: F = Id

Right-hand-side: **a** **(data structure)**

Left-hand-side : “**(a -> x)** “is a function called “**handler**” (or “**continuation**“) which takes the argument “a” to provide it as output : “**(a -> x ) -> x**“.

eg. handler to database query, over internet…(technique used in Compiler)

**Co-Yoneda Lemma** : (Contra-variant **a , F**)

**Yoneda Embedding**: Full and Faithful

Note: Instead of proving **a , b** are **isomorphic**, sometimes it is easier to prove the functors **C(a, -) & C(b, -)** are **isomorphic**.[*Proof Trivial: functors preserve composition and *** identity**]

**Application**: **Co-Yoneda Lemma** : (Contra-variant **a , F**)

**Pre-order** Category

3 possibilities: (“1” = singleton)

**Note**: impossible (function must have an image)

**Verify**

Right-Hand Side:

Left-Hand Side:

Yoneda Embedding (Lagatta)

# Haskell in Category Theory

# BM Category Theory II 1.1: Declarative vs Imperative Approach

Excellent lecture using Physics and IT to illustrate the 2 totally different approaches in Programming:

**Imperative**(or Procedural) –**micro**-steps or**Local 微观世界 [eg. C / C++, Java, Python…]****Declarative**(or Functional) –**Macro**-view or**Global 大千世界 [eg. Lisp / Clojure, Scala, F#, Haskell…]**

In **Math**:

- Analysis (Calculus)
- Algebra (Structures: Group, Ring, Field, Vector Space, Category …)

In **Physics**:

- Newton (Laws of Motion), Maxwell (equations)
- Fermat (*) (Light travels in least time), Feynman (Quantum Physics).

In **IT**: Neural Network (AI) uses both 1 & 2.

More examples…

In **Medicine**:

- Western Medicine: germs/ viruses, anatomy, surgery
- Traditional Chinese Medicine (中医): Accupunture, Qi, Yin-Yang.

Note (*): Fermat : My alma mater university in Toulouse (France) named after this 17CE amateur mathematician, who worked in day time as a Chief Judge of Toulouse City, after works spending time in Math and Physcis. He co-invented Analytic Geometry (with Descartes), Probability (with Pascal), also was the “Father of Number Theory” (The Fermat’s ‘Little’ Theorem and The Fermat’s ‘Last’ Theorem). He used Math to prove light travels in straight line (before Newton) due to “**Least Time taken**” (explained here in this BM video).

https://tomcircle.wordpress.com/2013/04/05/lay-cables-at-least-cost/

# BM Category Theory : Motivation and Philosophy

Object-Oriented has 2 weaknesses for Concurrency and Parallel programming :

- Hidden Mutating States;
- Data Sharing.

Category Theory (CT): a higher abstraction of all different Math structures : Set , Logic, Computing math, Algebra… =>

**Our brain works by: 1) Abstraction 2) Composition 3) Identity (to identify)**

What is a Category ?

1) Abstraction:

ObjectsMorphism (Arrow)

2) Composition: Associative

3) Identity

**Notes: **

**Small Category with “Set” as object.****Large Category without Set as object.****Morphism is a Set : “Hom” Set.**

**
Example in Programming**:

- Object : Types Set
- Morphism : Function “Sin” converts degree to R:

Note: We just look at the Category “Types Set” from external Macroview, “forget ” what it contains, we only know the “composition” (Arrows) between the Category “Type Set”, also “forget” what these Arrows (sin,cosin, tgt, etc) actually are, we only study these arrows’ behavior (Associativity).

2.1 : Function of Set, Morphism of Category

**Set: A function is **

**Surjective (greek: epic / epimorphism 满射),****Injective (greek : monic / monomorphism 单射)**

**Category: [Surjective]**

**g 。f = h 。f **

**=> g = h (Right Cancellation )**

2.2 **Monomorphism**

**f 。g = f 。h
=> g = h** (Left cancellation)

NOT Necessary!! Reason ( click here):

In Haskell, 2 foundation Types: Void, Unit

**Void = False
Unit ( ) = True**

Functions : absurd, unit

**absurd :: Void -> a (a = anything)**

unit :: a -> ()

unit :: a -> ()

[to be continued 3.1 ….]

# 代 数拓扑 Algebraic Topology (Part 1/3)

Excellent Advanced Math Lecture Series (Part 1 to 3) by 齊震宇老師

（2012.09.10) Part I:

History: 1900 H. Poincaré invented Topology from Euler Characteristic (V -E + R = 2)

Motivation of Algebraic Topology : Find * Invariants* [1]of various topological spaces (in higher dimension). 求拓扑空间的

**“不变量”**eg.

- Abelian Fundamental Group (so as to manipulate by + -);

- Vector Space (to + – , × ÷ by multiplier Field scalars);

- Ring (to + x) in co-homology
- etc.

then apply algebra (Linear Algebra, Matrices) with computer to compute these invariants (**homology**, **co-homology, etc**).

A topological space can be formed by a “Big Data” Point Set, e.g. genes, tumors, drugs, images, graphics, etc. By finding (co)- / homology – hence the intuitive Chinese term (上) /同调 [2] – is to find “**holes**” in the Big Data in the 10,000 (e.g.) dimensional space the hidden information (co-relationship, patterns, etc).

**Note**: [1] Analogy of an”**Invariant**” in Population: eg. “Age” is an invariant can be added in the “Population Space” as the average age of the citizens.

**Side Reading (Very Clear)** : Invariant and the Fundamental Group Primer

**Note** [2]: **Homology** 同调 = same “tune”.

南朝 刘宋 谢灵运山水诗:

“谁谓古今殊，异代可同调”

同调 = Homology

(希腊 homo = 同, -logy = 知识 / 调)

– “*Reading an ancient text allows us to think “in tune” (or resonant) with the ancient author*.”

**[温习] Category Theory Foundation – 3 important concepts:**

- Categories
- Functors
- Natural Transformation

*[Skip if you are familiar with Category Theory Basics: Video 16:30 mins to 66:00 mins.]*

**[主题] Singular Homology Groups 奇异同调群 (**See excellent writeup in Wikipedia**) (Video 66:20 mins to end)**

- Singular Simplices 奇异 单纯
- Singular Chain Groups 奇异 链 群
- Boundary Operation 边界
- Singular Chain Complex 奇异 单纯复形

**Part 1/3 Video (Whole) **:

# Category Theory in Computing Languages

Is there any connection between category theory and the way computer languages work? by **Thorsten Altenkirch**

Yes, lots.

Just one example: a function with 2 inputs from A and B and results from C would have the type A x B -> C but in functional languages like Haskell we are using A -> (B -> C), i.e. a function that returns a function. This “**currying**” is exactly a the categorical definition of a cartesian closed category as one where **Hom(AxB,C)** is *isomorphic* to **Hom(A,B -> C)** and in this false you can replace Hom(X,Y) with X -> Y.

It is well known that effects in functional programming can be modelled by **monads** which is a concept from category theory. Nowadays a weaker structure called **applicative functors** has become very popular – needless to say also a concept from Category Theory.

Not all languages are functional (yet) but even non-functional languages can be understood using concepts from category theory.

See also:

Free Categories, Free Mono*I*ds, Monads = MonoId+Endofunctor

**Monad Diagram**