Table of Contents

1 The defintion of Monoid

  • Monoid is similar to a Group, but it does not have an inverse for each element.
  • Monoid can be formed by \((M, \otimes)\) and satified following laws:
    • If \(\forall m \in M\), then there exists an identity \(I\) such as \(I \otimes m = m \otimes I = m\)
    • If \(\forall m_1, m_2, m_3 \in M\), then \((m_1 \otimes m_2) \otimes m_3 = m_1 \otimes (m_2 \otimes m_3)\)

2 The definition of Category

  • A class of objects
  • A set of morphisms or a set of arrows
  • Category is a set including objects and morphisms/arrow

    • Each object has identity morphism
    • The composition of morphisms are associative

    category_def2.png

  • Example
  • Morphism is NOT function in Category
  • Reddit

     Objects are nature number: 0, 1, 2, 3…
  Morphisms: m → n are \( m \times n \) matrices
  Identity Morphism: 3 → 3 is 3 × 3 matrix
   \[
      \begin{pmatrix}
   1 & 0 & 0 \\
         0 & 1 & 0 \\
         0 & 0 & 1
         \end{pmatrix}
   \]
  Composition: matrix multiplication ∘

  Identity
  M(1, 1) : 1 → 1
  M(2, 2) : 2 → 2

  Morphism:
  M(1, 2) : 1 → 2
  M(2, 3) : 2 → 3

  Composition
     M(1, 2) ∘ M(2, 3) → M (1, 3)

     Associative
  M₁(1, 2) ∘ M₂(2, 3) ∘ M₃(3, 4) = M₄(1, 4)
  M₁(1, 2) ∘ (M₂(2, 3) ∘ M₃(3, 4)) = M₁(1, 2) ∘ M₂₃(2, 4) = M₄(1, 4)
  ⇒ M₁ ∘ M₂ ∘ M₃ ≡ M₁ ∘ (M₂ ∘ M₃)

3 Monad is a Monoid

  1. A monad is a monoid in a category of endofunctor
  2. What does it mean?

    • functors are as elements in category.
      • \(T \in C\)
    • The operation is functor composition
      • \(T \otimes T = T\)
    • Each functor \(T\) has an identity functor \(I\) such that
      • \(I \otimes T = T \otimes I = T\)
    • The operation satisfied Associativity law because monoid satisfied associativity law.
    • \(T \otimes T \otimes T = T \otimes (T \otimes T)\)

4 definition of Monad

\begin{align*} \mu &: T \times T \rightarrow T \quad \text{ where } T \text{ is endofunctor} \\ \mu T &: (T \times T) \times T \rightarrow T^2 \\ T \mu &: T \times (T \times T) \rightarrow T^2 \quad \text{Associativity law in Monoid}\\ \mu T &= T \mu \quad \text{from commutative diagram} \\ \mu ∘ \mu T &= T \quad \mu(T^2) = T \quad \because \mu T = T \\ \mu ∘ T \mu &= T \quad \mu (T^2) = T \quad \because T \mu = T \\ T \mu \mu &= \mu T \mu \\ \eta &: I \rightarrow T \\ \mu_a &: T \times T a \rightarrow T a \quad \text{ where } \mu = \text{ join in Haskell} \\ \eta_a &: I a \rightarrow T a \quad \text{ where } I \text{ identity endofunctor } \\ \end{align*}

5 urls: Monad

f(x) = x² + x³
A = B → B ∘ μ η
C  E   F = f(9) = 4

Matrix \[ A= \begin{bmatrix} \cos(\beta) & -\sin(\beta)\\ \sin(\beta) & \cos(\beta) \end{bmatrix} + B = \begin{bmatrix} \cos \beta & -\sin \beta \\ \sin \beta & \cos \beta \end{bmatrix} \] Matrix multiplication

  1. Matrix addition
    1. matrix division
f::(Monad m)=> m a -> (a -> m b) -> m b

transpose::[[a]] -> [[a]]
transpose [] -> repeat []
transpose (x:cs) = zipWith(:) x $ transpose cs

6 What is Functor

  • The definition of Functor
    • Given a category \(\mathcal{C}\) and \(\mathcal{D}\)
    • Functor map Object in \(\mathcal{C}\) to Object in \(\mathcal{D}\)
      • \(F(a) \in \mathcal{D}\) \(a \in \mathcal{C}\)
      • F(a -> b) -> F(a) -> F(b) where a ∈ \(\mathcal{C}\) b ∈ \(\mathcal{D}\)
    • Functor map morphism/arrow in \(\mathcal{C}\) to morphism/arrow in \(\mathcal{D}\)
    • \( F Id_a = Id_{F a} \)
  • The definition of Functor in Haskell. Functor is the type class with two methods,

    class Functor f where
    fmap::(a -> b) -> f a -> f b
    
    • Other way to think about it is as following:
    • \( F(a \rightarrow b) \rightarrow F(a) \rightarrow F(b) \)
    • \(F\) is a functor and transform a function \(g:a \rightarrow b\) to a new function \(F(a) \rightarrow F(b)\)
    • If \(g\) function is from type Int to type \(String\) and the functor is Maybe, then the new function is from Maybe(Int) → Maybe(String)
    • The instance of Functor has to satisfy following two laws:
    fmap id = id
            fmap (f . g) = (fmap f) . (fmap g)
    
  • What is the difference between Functor and Monad.
    • Monad is the subtype of Functor
  • Vector and matrix forms a category?

7 What is Monad

  1. What is the definition of Monad? Monad is Monoid over the endofunctor

    class Applicative m => Monad m where
      return:: a -> m a
              return = pure
      (>>=)::(Monad m) => m a -> (a -> m b) -> m b
    
  2. When to use Monad?

8 What is Monoid and Monad

  1. Monad definition from "What we talk about when we are talking about Monads" Tomas Petricek Monad Definition in Haskell

    • A monad is an operator M on types, together triple functions:
      • map::(a → b) → (M a → M b)
      • unit:: a → M a
      • join:: M (M a) → M a
    • Satisfying following laws
    • join ∘ join = join ∘ map unit
      • join ∘ unit = id = join ∘ map join
  2. A Monad over its category 𝓒 is a triple (T, 𝜂, 𝜇) where T : \(\mathscr{C}\) → \(\mathscr{C}\) is a functor,

    • Good explanation in Reddit What is Monad
    • 𝜇 : T2 → T and 𝜂 : Id → T are nature transformations such that:
      1. μA ∘ T μA = μA ∘ μTA
        • T μA ⇒ Apply μA inside T

          fmap join [[[1, 2]], [[3]]]
                    
                   μ_A
          
          => [[1, 2], [3]]
          
        • Apply μA inside first then Apply μA from outside = Apply μA from outside first then Apply μA
        • Take the layer from inside first and then take the top layer = take the layer from inside and then take the top layer
      2. μA ∘ ηTA = idTA = μA ∘ T ηA
      3. join = μ
      4. unit = η
    • 1 and 2 are equvalent as following
    1. join ∘ join = join ∘ map join
      • join ∘ join ⇒ peel the layers off from outside.
      • join ∘ join ⇒ T ⊗ T ⊗ T → T

        let s = [[[1], [2]], [[3]]]
                -- join::[[[]]] -> [[]]
                -- join::[[]] -> []
                -- => (join . join)::[[[]]] -> []
        (join . join) s -- [1, 2, 3]
        
        • join ∘ map join ⇒ peel the layers off from inside.
        let s = [[[1], [2]], [[3]]]
                -- join::[[[]]] -> [[]]
                -- join::[[]] -> []
                -- => 
        (join . map join) [[[1], [2]], [[3]]] -- [1, 2, 3]
                -- map(\x -> join x) [[[1] [2]], [[3]]]
                -- map(\x -> join [[1], [2]] => [1, 2] ) –- peel from inside
                -- map(\x -> join [[3]] => [3])
                -- [[1, 2], [3]]
                -- join [[1, 2], [3]] => [1, 2, 3]
        
        1. join ∘ unit = join ∘ map unit

    Reference

  3. What is the difference between Monad and Monoid? There are couple axioms for Monoid
    1. m₁ ⊗ m₂ ∈ M if m₁ and m₂ ∈ M
    2. id ⊗ m = m ⊗ id = m
    3. m1 ⊗ m2 ⊗ m3 = m1 ⊗ (m2 ⊗ m3)
  4. The mathematic definition of Monad
    1. μ :: I → T
    2. η :: T ⊗ T → T
    3. T is the endofunctor which means from a category to itself. (T : C → C)
  5. The domain and co-domain of η are both Functor
    • ⊗ is Functor composition
    • e.g. if T = m a then T ⊗ T = m (m a)
    • e.g. T = [] then T ⊗ T = [[]]
    • In Haskell, type constructor is like a Functor

      class Applicative f => Monad f where
        return :: a -> f a
        join f (f a) -> f a
        fmap f (a -> b) -> (f a -> f b) -- f = (a -> m b)
      
      -- definition in GHC
      class Applicative m => Monad m where
        return :: a -> m a
        (>>=)::m a -> (a -> m b) -> m b
      
              -- f = (a -> m b)
      m >>= f = join $ fmap (a -> m b) m b
      m >>= f = join $ fmap f $ m b
      m >>= f = join $ m (f b)
      m >>= f = join $ m (m b)
      

      Use join and fmap represents (>>=)

      -- f = (a -> m b)                          
      m >>= f = join $ fmap f m b       
      m >>= f = join $ fmap f $ m b              
              m >>= f = join $ m (f b)                   
      m >>= f = join $ m (m b)                   
      
      1. Maybe is Monad
      instance Monad Maybe where
        return Nothing = Nothing
        (>>=) (Just a) f = Just f a
      
        addMaybe::Maybe Int -> Maybe Int -> Maybe Int
        addMaybe Nothing _ = Nothing
        addMaybe _ Nothing = Nothing
        addMaybe (Just a) (Just b) = Just (a + b)
      
        -- other implementation
        addMaybe::Maybe Int -> Maybe Int -> Maybe Int
        addMaybe m1 m2 = do
                a <- m1
                b <- m2
                return (a + b)
      

9 Applicative

  1. How to use Applicative
  2. What is Applicative
  3. What is the difference between Monad and Applicative
class Functor f => Applicative f where
  pure:: a -> f a
 (<*>):: f (a -> b) -> f a -> f b

class Applicative f => Monad f where
  return:: a -> f a
  (>>=)::m a -> (a -> m b) -> m b

Author: aaa

Created: 2023-09-27 Wed 11:44

Validate