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

2.2 Monad & Adjunction

https://youtu.be/lqq9IFSPp7Q

Refs:

1. Download BM’s book “Category Theory for Programmers” :

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 
(,) :: * -> * ->  *  

[* all haskell types]

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 and Concurrent Haskell: 

Read Free Online Book:

http://chimera.labs.oreilly.com/books/1230000000929/index.html

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}}

Parallel and Concurrent Haskell: http://www.youtube.com/playlist?list=PLbgaMIhjbmEm_51-HWv9BQUXcmHYtl4sw

<b>Read Free Online Book:</b>
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’

https://youtu.be/N6sOMGYsvFA

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)

Parallel and Concurrent Haskell: http://www.youtube.com/playlist?list=PLbgaMIhjbmEm_51-HWv9BQUXcmHYtl4sw

<b>Read Free Online Book:</b>
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>

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

This limitation will change when more companies adopt Haskell (eg. Facebook uses Haskell in AI screening fake news, etc)

Excellent eBook (for beginners)

http://learnyouahaskell.com/chapters