# Category Theory III for Programmers (Part 1 & 2)

The most interesting “Category Theory” （范畴论) for Programmers course III by Dr. Bartosz Milewski , a follow-up of last year’s course II.

Prerequisites:

1. Fundamental of Category Theory: Functor, Natural Transformation, etc. (Course II Series)
2. (Nice to have) : Basic Haskell Functional Programming Language. (Quick Haskell Tutorial)

1.1: Overview Part 1

Category Theory (CT) = Summary of ALL Mathematics

Functional Programming = Application of CT

Philosophical Background:

• Math originated 3,000 years ago in Geometry by Greek Euclid with Axioms and deductive （演译） Proof-driven Logic.
• Geometry = Geo (Earth) + Metry (Measurement).
• Math evolved from 2-dimensional Euclidean Geometry through 17 CE French Descartes’s Cartesian Geometry using the 13CE Arabic invention “Algebra” in Equations of n dimensions: $(x_1, x_2,..., x_n)$, $(y_1, y_2,..., y_n)$
• Use of Algebra: 1) Evaluation of algebraic equations (in CT: “Functor”) ; 2) Manipulation. eg. Substitution (in CT : “Monad” ), Container (in CT: “Endo-Functor” ), Algebraic Operations (in CT: “Pure, Return, Binding” ).
• Lawvere Theories: unified all definitions of Monoids (from Set to CT)
• Free Monoid = “List” (in Programming). Eg. Concatenation of Lists = new List (Composition, Associative Law) ; Empty List (Unit Law).
• Advance of Math in 21CE comes back to Geometry in new Math branches like Algebraic Geometry, Algebraic Topology, etc.

Note: The only 2 existing human Languages invented were derived from forms & shapes (images) of the mother Earth & Nature:

1. Ancient Greek Geometry (3000 years) ;
2. Ancient Chinese Pictogram Characters (象形汉字, 3000 years 商朝. 甲骨文 ) .

https://youtu.be/F5uEpKwHqdk

1.1: Overview Part 2

Keypoints: (just a ‘helicopter’ view of the whole course syllabus)

• Calculus: infinite Product, infinite Sum (co-Product), End, co-End.
• Kan-extensions
• Geometry in “Abstract” aka Topology: “Topos”
• Enriched Category : (2-category) Analogy : complex number makes Trigonometry easy; same does Enriched Category.
• Groupoid => “HTT” : Homotopic Type Theory

https://youtu.be/CfoaY2Ybf8M

2.1 String Diagrams (Part 1) Composing Natural Transformations (Vertical & Horizontal): $\alpha \; \beta$ (assumed naturality) https://youtu.be/eOdBTqY3-Og  https://youtu.be/lqq9IFSPp7Q

Refs:

https://github.com/hmemcpy/milewski-ctfp-pdf

# ​Parallel and Concurrent Haskell (3)

3.1 Algebraic Data Types: Product Type, Sum Type

Projection by Pattern Match:

fst :: (a , b )  -> a
fst  (x, _) = x

snd (_,y) = y

:t  ( , ) data constructor

( , ) :: a -> b -> (a,b) type constructor

Kind
:k (,) type constructor
(,) :: * -> * ->  *

Laziness

3.2 Sum Type

data Either a b = Left a | Right b
Left :: a -> Either a b
Right :: b -> Either a b

safeSqrt :: Either String Double -> Either String Double

safeSqrt (Left str) = Left str
safeSqrt (Right x) =
if x <0
then Left “Error”
else Right (sqrt x)

safeSqrt  sx =
case sx of
Left str -> Left str
Right str ->if x < 0
then Left “Error”
else Right (sqrt x)

data Bool = True | False
case x < 0 of
True -> …
False -> …

(<) :: Ord a => a -> a -> Bool

Note: Ord = Order

a + 0 = a

data X a = X a | Y Void

a + 0

a * 1 = a

type Y a = (a , () )

a * 0 = 0
type Z a = (a, Void) ~ Void

Note: (a, Void) is an impossible pair of 2 elements, because Void has no element, so (a, Void) is equivalent to Void.

2 = 1 + 1
2 = Bool
Bool = True | False

# Parallel & Concurrent Haskell (2)

Continued from : (Part 1)

2.2 Data Structure

Function (+) ::  D -> D -> D
inc  x  = 1 + x ~ (+) ::  1 + x

Section (Partial appl) : inc  = (+ 1)

Type ~ Set {values} : Integer Set / Boolean Set {0,1} / Empty Set “Void” { } / …

Type of Singleton (1 element) : Unit ( )

Declare a new Type : data

data () = ()
1st () = Type of Unit
2nd () = constructor of Unit

Haskell convention : Type name = constructor name

(To avoid having too many nsmes)

Define cares Ian product of Types (Sets):

data Product a b = P a b

Product : Type constructor
P : Data constructor (function with 2 args of types a, b)
P :: a -> b -> Product a b

Data Immutable : remember how it was constructed.

(+) :: Num a => a -> a -> a

sqDist ‘ ‘ (P x y ) = x^2 + y^2
sqDist ‘ ‘ :: Num a =-> Product a a -> a

Built-in for “pair”:

data ( , ) a b =( , ) a b

eg.
( , ) 1 2 gives (1, 2)

All data (Types) are formed by only 2 methods : Product or Sum. $\boxed {\text {Algebraic Data : by Product, Sum}}$

http://chimera.labs.oreilly.com/books/1230000000929/index.html
<a href=”https://tomcircle.files.wordpress.com/2017/07/20170712_200456.png”><img src=”https://tomcircle.files.wordpress.com/2017/07/20170712_200456.png&#8221; alt=”” class=”wp-image-13955 alignnone size-full” width=”1064″ height=”1262″></a>

# Parallel and Concurrent Haskell (1)

2016

1-1: Introduction

Everything in Haskell is PURE (function), including side effects (print, I/O such as open files, update data, …)

“Pure”: f (x) = a, regardless of ‘x’ value may change, always returns the result ‘a’

2.1 Function

f a b = function f, arg a & b

sqDist (x, y ) = x^2 + y^2
main = print $sqDist (3, 4) dist pt = sqrt$ sqDist pt

dist = sqrt . sqDist

Note: pronounce “.” as “AFTER

id  :: a -> a [Signature] # Polymorphic
id  x = x [Implementation]

flop :: (a, b) -> (b, a)
flop p = = (snd p,fst p)

flop’ (x,y) = (y,x)

Example:
print \$ flop (5, “Hello!”)

Currying
sqDist :: Double ->Double -> Double
Equivalent to: sqDist 1 arg but return a function (Double -> Double)
sqDist :: Double -> (Double -> Double)

sqDist x y = x^2 + y^2

Equiv: sqDist (x,y) # but difficult to partial application.

Partial Application (pass fewer args)
sqDist 0 = Double -> Double

sqdistfromzero
:: Double -> Double
sqdistfromzero = sqDist 0

2.2 Functions

Function (+) ::  D -> D -> D
inc  x  = 1 + x ~ (+) ::  1 + x

Section (Partial appl) : inc  = (+ 1)

To be continued … (Part 2)

http://chimera.labs.oreilly.com/books/1230000000929/index.html
<a href=”https://tomcircle.files.wordpress.com/2017/07/20170712_200456.png”><img src=”https://tomcircle.files.wordpress.com/2017/07/20170712_200456.png&#8221; alt=”” class=”wp-image-13955 alignnone size-full” width=”1064″ height=”1262″></a>

# Functional Programming for the Object Oriented – Øystein Kolsrud

• Imperative
• Object- Oriented
• Functional Programming

Part 2: Example – The 8 Queens Problem

Note: A simpler Haskell coding here.

Morphism: 态射 (Mapping : 映射)

Functor (F): 函子 $F :: C \to D$

Covariant: 协变 $C \to D$

Contravariant: 逆变 $C^{Op} \to D$

Type: 类型 Facebook rewrote the SPAM rule-based AI engine (“Sigma“)  with Haskell functional programming to filter 1 million requests / second.     # A Category Language : Haskell

Haskell is the purest Functional Language which is based on Category Theory. It is so different from the Imperative (aka prodecural, like C) or Object-Oriented “O-O” (C++, Java, Python…) or Scripting (Javascript,  PhP, …) languages, it also stands out among its family of Functional Programming “FP” (Lisp, Scala, …).

Still a language more academic than commercial (it doesn’t support JVM and Android, unlike Scala which is both O-O and FP, also on JVM), Haskell is the language to learn together with the Advanced Math “Category Theory“.

One FP developer says:

“My heart (Love)  is with Haskell, my brain (practical) with Scala.” 