A Fistful of Monads

Kotlin Monad (and Functor, Applicative)

1. Functor “map” (Kotlin) (fmap or <$> in Haskell)

https://hackernoon.com/kotlin-functors-applicatives-and-monads-in-pictures-part-3-3-832d58d92445

2. Monadsflatmap” (>>= in Haskell)

Haskell Monad:

http://learnyouahaskell.com/a-fistful-of-monads

Do not fear Monoid / Monoidal Category / Monad:

Monad in Haskell

F# Monad:

View at Medium.com

(分享自知乎网)

https://zhuanlan.zhihu.com/p/29542641

Monoid and Monad

Quora: What is the difference between monoid and monad? by Mort Yao https://www.quora.com/What-is-the-difference-between-monoid-and-monad/answer/Mort-Yao?share=41115848&srid=ZyHj

A well-said, perhaps the briefest ever answer is: monad is just a monoid in the category of endofunctors.

monoid is defined as an algebraic structure (generally, a set) M with a binary operation (multiplication) • : M × M → M and an identity element (unit) η : 1 → M, following two axioms:

i. Associativity
∀ a, b, c ∈ M, (a • b) • c = a • (b • c)

ii. Identity
∃ e ∈ M ∀ a ∈ M, e • a = a • e = a

When specifying an endofunctor T : X → X (which is a functor that maps a category to itself) as the set M, the Cartesian product of two sets is just the composition of two endofunctors; what you get from here is a monad, with these two natural transformations:

1. The binary operation is just a functor composition μ : T × T → T
2. The identity element is just an identity endofunctor η : I → T

Satisfied the monoid axioms (i. & ii.), a monad can be seen as a monoid which is an endofunctor together with two natural transformations. 

The name “monad” came from “monoid” and “triad”, which indicated that it is a triple (1 functor + 2 trasformations), monoidic algebraic structure.



In other words, monoid is a more general, abstract term. When applying it to the category of endofunctors, we have a monad.

https://www.quora.com/What-is-the-difference-between-monoid-and-monad/answer/Bartosz-Milewski?share=e4dc6c63&srid=ZyHj

State Monad: Milewski

Don’t fear the Monad

Brian Beckman:

You can understand Monad without too much Category Theory.

Functional Programming = using functions to compose from small functions to very complex software (eg. Nuclear system, driverless car software…).

Advantages of Functional Programming:

  • Strong Types Safety: detect bugs at compile time.
  • Data Protection thru Immutability: Share data safely in Concurrent / Parallel processing.
  • Software ‘Componentisation’ ie Modularity : Each function always returns the same result, ease of software reliability testing.

Each “small” function is a Monoid.
f : a -> a (from input of type ‘a‘ , returns type ‘a’)
g: a -> a

compose h from f & g : (strong TYPING !!)
h = f。g : a -> a

[Note] : Object in Category, usually called Type in Haskell, eg. ‘a’ = Integer)

You already know a Monoid (or Category in general) : eg Clock

  1. Objects: 1 2 3 …12 (hours)
  2. Arrow (Morphism): rule “+”:

    7 + 10 = 17 mod 12 = 5

    • Law of Associativity:
      x + (y + z) = (x + y) + z
    • Identity (or “Unit”): (“12”):
      x + 12 = 12 + x = x

    More general than Monoid is a “Monoidal” Category where: (instead of only single object ‘a’, now more “a b c…”)
    f : a -> b
    g: b -> c
    h = f。g : a -> c

    Function under composition Associative rule and with an Identity => Monoid

    Monad (M): a way to manage the side-effects (I/O, exception , SQL Database, etc) within the Functional Programming way like monoidal categories: ie associative composition, identity.

    Remark: For the last 60 years in Software, there have been 2 camps:

    1. Bottom-Up Design: from hardware foundation, build performance-based languages: Fortran, C, C++, C#, Java…
    2. Top-Down Design: from Mathematics foundation, build functional languages (Lambda-Calculus, Lisp, Algo, Smalltalk, Haskell…).
    3. F# (Microsoft) is the middle-ground between 1 & 2.

    Ref: What is a Monad ?

    Monad = chaining operations with binding “>>=”

    • Possible use: allows to write mini-language, parser…

    《知乎》https://zhuanlan.zhihu.com/p/29542641?from=timeline

    BM Category Theory 10: Monad & Monoid

    10.1 Monad
    Analogy

    Function : compose “.“, Id

    Monad: compose “>>=“, return

    Imperative (with side effects eg. state, I/O, exception ) to Pure function by hiding or embellishment in Pure function but return “embellished” result.

    10. 2 Monoid

    Monoid in category of endo functors = Monad

    Ref Book : 

    What is the significance of monoids in category theory? by Bartosz Milewski 

    BM Category Theory 3 & 4 Monoid, Kleisli Category (Monad), Terminal /Initial Object, Product… Free Monoid 

    [Continued from 1.1 to 2.2]

    3.1 Monoid M (m, m)

    Same meaning in Category as in Set: Only  1 object, Associative, Identity

    Thin / Thick Category:

    • “Thin” with only 1 arrow between 2 objects; 
    • “Thick” with many arrows between 2 objects.

    Arrow : relation between 2 objects. We don’t care what an arrow actually is (may be total / partial order relations like = or \leq , or any relation), just treat arrow abstractly.

    Note: Category Theory’s “Abstract Nonsense” is like Buddhism “空即色, 色即空” (Form = Emptiness).

    Example of Monoid: String Concatenation: identity = Null string.

    Strong Typing: function f calls function g, the type of the output of f must match with the type of the input of g.

    Weak Typing:   no need to match type. eg. Monoid.

    Category induces a Hom-Set: (Set of “Arrows”, aka Homomorphism 同态, which preserves structure after the “Arrow”)

    • C (a, b) : a -> b
    • C (a,a) for Monoid : a -> a

    3.2 Kleisli Category (Monad) 

    Morphism between a, b :
    \boxed{a \to (b, \text {string})}

    In brief, embellish the returned output b with string. 

    In the example of Kleisli Category, using Monoid (single object) with embellishing string => Monad (covered in later videos).

    4.1 Monad (one definition) : Kleisli

    Set and Category SET: 

    • Set has elements and function between sets.
    • Category SET has NO element, only arrows (morphisms)

    Universal Construction: define relations between Objects.

    Set is rich with functions, except 1 case: There is no function from a non-empty set to Void (because a function must have an image in the co-domain, but Void has no element as the Image.)

    Terminal Object : all other objects (each with UNIQUE arrow) point to it. [Denoted as () or Unit]

    \boxed { \forall a, \exists f :: a \to ()}

    \boxed { \forall a, f :: a \to (), g :: a \to () \implies f = g } (Uniqueness of arrow)

    Note: Terminal Object (T.O.) is the largest object. There is no T.O. in Natural numbers.

    Initial Object: reverse of Terminal object. Outgoing arrow from Void.

    absurd :: Void -> a

    Category “Equality”:

    • 2 objects are isomorphic (exists an inverse arrow), but we don’t say they are equal;
    • Arrows can be equal by associativity :  f \circ (g \circ h) = (f \circ g) \circ h

    Terminal Object (Similarly, Initial Object) is unique (up to ONLY ONE Isomorphism). 

    Assume both Ta and Tb are Terminal Objects. Prove Ta = Tb by showing there is only one isomorphism.

    Note1: example of 2 isomorphisms between 2 Objects : (0, 1) and (T, F) => 

    • 1st isomorphism : (1 ~ T), (0 ~ F)
    • 2nd isomorphism: (1 ~ F), (0 ~ T)

    Note2: There are outgoing arrows from T.O. => generalising.

    4.2 Products

    C^{op} : also a Category with all arrows in C reversed.

    Products (Cartesian) of 2 objects (a,b): by Universal Construction.

    p and q are (good) projections of c.
    p’ and q’ are (another) projections of c’.

    c is the product of (a, b) if 
    there is a UNIQUE  isomorphism m,
    \boxed {m :: c' \to c }
    \boxed {p' = p  \circ m}
    \boxed{q' = q  \circ m}

    II 3.2 Free Monoid

    Monoid : with a Set of 2 generators (a, b)

    • Identity: e*a = a*e = a; 
    • Associativity

    Free Monoid = {e, a, b, ab, ba, aab, abb, ….}, notice it is generated by the set {a, b} and thus not a Monoid (noted as Mon).

    We can create a Functor U (aka  Forgetting function) between Monoid and its underlying Set: 

    \boxed { U :: Mon \to Set }

    Minggatu-Catalan Number

    Minggatu-Catalan Number

    image

    First discovered by the Chinese Mathematician Minggatu 明安图 (清 康熙, 1730), later by the French (né Belgian) École Polytechnique mathematician Eugène Charles Catalan (1814 – 1894).

    Proof: Consider ways of making sums with {0, 1, 2, 3, 4…} and +, ( , ).

    0 = (0)
    1 way for 0
    \boxed {C_{0} = 1}

    0+1 =(0+1) :
    1 way for 1 \boxed {C_{1} = 1}

    0 +1 +2 = ((0+(1+2)) = ((0+1)+2):
    2 ways for 2 \boxed {C_{2} = 2}

    0+1+2+3 = (0+(1+(2+3))) = (0+((1+2)+3))= ((0+1)+(2+3)) = ((0+(1+2))+3) = (((0+1)+2)+3) :
    5 ways for 3 \boxed {C_{3} = 5}

    0+1+2+3+…+n = ?
    ? ways for n \boxed {C_{n} = ?}

    Try finding the pattern for C_{4}:

    Let A represents {0, 1, 2, 3, 4}.
    There are 4 cases:

    Case 1:
    (\underbrace{(A)}_{C_{0}} + \underbrace{(A+ A+ A+ A)} _{C_{3}})

    Case 2:
    ( \underbrace{ (A+A ) }_{C_{1}} + \underbrace{ (A+ A+ A) }_{C_{2}} )

    Case 3:
    ( \underbrace{ (A+A+A ) }_{C_{2}} + \underbrace{ ( A+ A) }_{C_{1}})

    Case 4:
    ( \underbrace{ (A+A+A+A) }_{C_{3}} + \underbrace{ (A) }_{C_{0}} )

    C_{4} = C_{0}.C_{3} + C_{1}.C_{2} + C_{2}.C_{1}+ C_{3}.C_{0}

    Generalise:
    C_{n+1} = C_{0}.C_{n-0} + C_{1}.C_{n-1} + C_{2}.C_{n-2} + ...+ C_{k}.C_{n-k} + ...+ C_{n-0}.C_{0}

    Recurrence Sequence of C_{n}:
    \boxed{ \begin{cases} C_{0} =1, \\ C_{n+1} = \displaystyle\sum_{k=0}^{n}C_{k}C_{n-k} , & \text{( } n \geq {0} \text {)} \end{cases} }

    image

    Step 1: Generating Function C(x) :
    Let C(x) =C_{0} + C_{1}x+ C_{2}x^2 + ...+ C_{n}x^n

    \boxed {\displaystyle C(x) = \sum_{n=0}^{\infty} C_{n} x^n }

    C(x)^{2} = (C_{0}C_{0})+ (C_{0}C_ {1} + C_{1}C_{0})x+ (C_{0}C_{2}+ C_{1}C_{1}+ C_{2}C_{0} ) x^2 + ...

    The coefficient for x^{n}: \displaystyle \sum_{k=0}^{n}C_{k}C_{n-k}

    \displaystyle C(x)^2 = \sum_{n=0}^{\infty} \underbrace{ \left (\sum_{k=0}^{n}C_{k}C_{n-k} \right)}_{\text {coeff of }x^{n}} x^n = \sum_{n=0}^{\infty} \underbrace{ C_{n+1}}_{\text {recurrence}} x^n

    \displaystyle x.C(x)^{2} =x. \sum_{n=0}^{\infty} C_{n+1} x^n = \sum_{n=0}^{\infty} C_{n+1} x^{n +1}
    Change (n+1) to n by adjusting initial value from n= 0 to 1:
    \displaystyle x.C(x)^{2} = \sum_{n=1}^{\infty} C_{n} x^n

    Reset the initial value from n=1 to 0:
    \displaystyle x.C(x)^{2} = \sum_{n=0}^{\infty} C_{n} x^n - C_{0}
    We have seen
    C_{0}= 1 and
    \displaystyle C(x) = \sum_{n=0}^{\infty} C_{n} x^n

    \displaystyle x.C(x)^{2} - C(x) +1 = 0
    This is the quadratic equation on C (x):

    C(x)= \frac{1 \pm \sqrt{1-4x} }{2x}

    2x.C(x)= 1 \pm \sqrt{1-4x}

    Case: 2x.C(x)= 1 + \sqrt{1-4x}
    When x \rightarrow 0
    2x.C(x)= 0
    1 + \sqrt{1-4x}= 1+1=2
    Impossible !

    Case: 2x.C(x)= 1 - \sqrt{1-4x}
    When x \rightarrow 0
    2x.C(x)= 0
    1 - \sqrt{1-4x}= 1- 1=0

    Step 2: The closed form for the generating function C(x) :

    \boxed { C(x)= \frac{1 - \sqrt{1-4x} }{2x} }

    Step 3: The closed form for C_{n}

    We expand \sqrt{1-4x} into power series:

    Let \displaystyle \sqrt{1-4x}= K(x)= \sum_{k=0}^{\infty}K_{k}x^{k}

    2xC(x)= 1 - \sqrt{1-4x}
    \displaystyle 2xC(x)= 1 - \sum_{k=0}^{\infty}K_{k}x^{k}

    \displaystyle 2x\sum_{k=0}^ {\infty}C_{k}x^{k} = 1 - \sum_{k=0}^{\infty}K_{k}x^{k}

    Move 2x inside the left sum:
    \displaystyle \sum_{k=0}^ {\infty}2C_{k}x^{k+1} = 1 - \sum_{k=0}^{\infty}K_{k}x^{k}

    Synchronise the indices k,
    \displaystyle \sum_{k=1}^ {\infty}2C_{k-1}x^{k} = 1 - K_{0} - \sum_{k=1}^{\infty}K_{k}x^{k}

    \displaystyle \sum_{k=1}^ {\infty}2C_{k-1}x^{k} + \sum_{k=1}^{\infty}K_{k}x^{k} = 1 - K_{0}

    \displaystyle \sum_{k=1}^ {\infty} (2C_{k-1} + K_{k})x^{k} = 1 - K_{0}

    We compare the coefficient of each term x^{k} :

    x^{0}: 0 = 1- K_{0}
    x^{1}: 2C_{0} + K_{1} = 0
    x^{2}: 2C_{1} + K_{2} = 0

    x^{n}: 2C_{n} + K_{n+1} = 0

    \boxed{ \begin{cases} K_{0} =1, \\ C_{n} = \displaystyle - \frac {K_{n+1}}{2} , & \text{( } n \geq {0} \text {)} \end{cases} }

    We need to express K_{n+1} in term of n only.

    Go back to the definition of K(x):
    \displaystyle K(x)= \sum_{k=0}^{\infty}K_{k}x^{k}

    \displaystyle K(x)= K_{0}+K_{1}x + K_{2}x^{2} + ...+ K_{n}x^{n}+...

    Differentiate:
    \displaystyle K'(x)=1.K_{1}x + 2K_{2}x^{1} + ...+ nK_{n}x^{n-1}+...

    \displaystyle K'(0)= 1K_{1}

    Differentiate 2nd time:
    \displaystyle K''(x)=2.1K_{2} + ...+ n. (n-1)K_{n}x^{n-2}+...

    \displaystyle K''(0)= 2.1K_{2}

    Continue …

    K^{(n)}(x)= n (n-1)(n-2)...2.1K_{n} + ...

    K^{(n)}(0)= n! K_{n}

    \boxed { K_{n} = \frac { K^{(n)}(0)}{n!} = \frac { K^{(n)}(0)}{n^{\underline {n}}} }

    Note: See blog on “Falling Factorial”: x^{\underline {n}}

    Next step, we shall find K^{(n)}(0) in term of n
    Recall
    K(x) = (1-4x)^{\frac {1}{2}}

    K'(x) = -2.(1-4x)^{-\frac {1}{2}}
    K''(x) = -2.2(1-4x)^{-\frac {3}{2}}
    K'''(x) = -2.4.3(1-4x)^{-\frac {5}{2}}
    K''''(x) = -2.6.5.4(1-4x)^{-\frac {7}{2}}

    K^{(n)}(x) = -2.(2n-2)^{\underline {n-1}}(1-4x)^{-\frac {2n-1}{2}}

    K^{(n+1)}(x) = -2.(2n)^{\underline {n}}(1-4x)^{-\frac {2n+1}{2}}

    \boxed { K^{(n+1)}(0) = -2.(2n)^{\underline {n}} }

    Also from above, we have seen:
    \boxed { K_{n} = \frac { K^{(n)}(0)}{n^{\underline {n}}} }

    Change n to (n+1):
    K_{n+1} = \frac { K^{(n+1)}(0)}{(n+1)^{\underline {n+1}}}

    K_{n+1} = \frac { -2.(2n)^{\underline {n}} } {(n+1)^{\underline {n+1}}}
    From step 3 above, we also know:
    C_{n} = - \frac {K_{n+1}} {2}

    C_{n} = \frac { (2n)^{\underline {n}} } {(n+1)^{\underline {n+1}}} = \frac {1}{n+1} \frac { (2n)^{\underline {n}} } {(n)^{\underline {n}}}
    since (n+1)^{\underline {n+1}} = (n+1)!= (n+1).n! = (n+1). (n)^{\underline {n}}
    and
    \frac { (2n)^{\underline {n}}} {(n)^{\underline {n}}} = \binom {2n}{n}  (by definition of Falling Factorial)

    \boxed {\displaystyle C_{n} = \frac {1}{n+1} \binom {2n}{n}  } [QED]

    image

    Ref:

    1. History:
    image

    2. Proof of Minggatu Catalan numbers

    3. Monoid

    4. Kleene Star

    5. Ref:
    Math Girls by Hiroshi Yuki et al.
    http://www.amazon.co.uk/dp/0983951306/ref=cm_sw_r_udp_awd_UKSvtb1AXNWCE