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:

F# Monad:

View story at Medium.com

Advertisements

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
  3. Law of Associativity:
    x + (y + z) = (x + y) + z
  4. 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…

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 }