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

Advertisements

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