Monad_Haskell Notes 10

I. From Functor to Monad

From a type perspective, Functor to Applicative to Monad is a progressive process from general to special (Monad is a special Applicative, Applicative is a special Functor)

Functor

Can map ordinary functions over values with context

fmap :: (Functor f) => (a -> b) -> f a -> f b

Used to solve the simplest scenario in context-related calculations: How to apply a function without context to a value with context?

(+1) ->? Just 1

fmap appears:

> fmap (+1) (Just 1)
Just 2

Applicative

Enhancement above Functor, can map functions in context over values with context

(<*>) :: (Applicative f) => f (a -> b) -> f a -> f b
pure :: (Applicative f) => a -> f a

Applicative can be understood as computation context, Applicative values are computations, for example:

Maybe a represents computations that might fail, [a] represents computations with many results (non-deterministic computation), and IO a represents computations with side-effects.

P.S. For more information about computation context, see [Functor and Applicative_Haskell Notes 7](/articles/functor 与 applicative-haskell 笔记 7/#articleHeader4)

Used to solve another scenario in context-related calculations: How to apply a function with context to a value with context?

Just (+1) ->? Just 1

<*> appears:

> Just (+1) <*> (Just 1)
Just 2

Monad

Enhancement above Applicative, can apply a function that takes ordinary values and outputs values with context, to a value with context

(>>=) :: (Monad m) => m a -> (a -> m b) -> m b

If you have a value with context m a, how can you throw it into a function that only accepts ordinary values a, and return a value with context? That is, how do you apply a function of type a -> m b to m a?

Used to solve the last scenario in context-related calculations: How to apply a function that takes ordinary values and outputs values with context, to a value with context?

\x -> Just (x + 1) ->? Just 1

>>= appears:

> Just 1 >>= \x -> Just (x + 1)
Just 2

Relationship Between the Three

From interface behavior perspective, these three things are all about values and functions with context (i.e., context-related calculations). So, consider, how many combination situations are there?

When function input and output types are consistent
- Function in context + Value in context: Applicative
- Function in context + Ordinary value: Wrap with pure then call
- Ordinary function + Value in context: Functor
- Ordinary function + Ordinary value: Function call
When function input and output types are inconsistent
- Function takes ordinary value, outputs value in context + Value in context: Monad
- Function takes ordinary value, outputs value in context + Ordinary value: Call directly
- Function takes value in context, outputs ordinary value + Value in context: Call directly
- Function takes value in context, outputs ordinary value + Ordinary value: Wrap with pure then call

So, for this scenario (applying functions that may or may not be in context to values that may or may not be in context), having Functor, Applicative and Monad is already enough to handle all situations

II. Monad typeclass

class Applicative m => Monad m where
  (>>=)       :: forall a b. m a -> (a -> m b) -> m b
  (>>)        :: forall a b. m a -> m b -> m b
  m >> k = m >>= \_ -> k
  return      :: a -> m a
  return      = pure
  fail        :: String -> m a
  fail s      = errorWithoutStackTrace s

Actually, Monad instances only require implementing the >>= function (called bind). In other words, Monad is just Applicative functor that supports >>= operation

return is an alias for pure, so it still accepts an ordinary value and puts it into a minimal context (wraps ordinary value into a Monad)

(>>) :: m a -> m b -> m b defines default implementation, applies function \_ -> m b to m a through >>=, used for ignoring previous calculation results (in chain operations)

P.S. In chain operations, replacing >> with >>= \_ -> makes it easy to understand

P.S. The forall in type declarations above refers to ∀ (quantifier in discrete mathematics, universal quantifier ∀ means "for all", existential quantifier ∃ means "exists"). So forall a b. m a -> (a -> m b) -> m b means, for any type variables a and b, the type of >>= function is m a -> (a -> m b) -> m b. Can omit forall a b., because by default all lowercase type parameters are arbitrary:

In Haskell, any introduction of a lowercase type parameter implicitly begins with a forall keyword

III. Maybe Monad

Maybe's Monad implementation is quite intuitive:

instance  Monad Maybe  where
  (Just x) >>= k      = k x
  Nothing  >>= _      = Nothing
  fail _              = Nothing

>>= applies function k to value inside Just, and returns result, if Nothing, directly returns Nothing. For example:

> Just 3 >>= \x -> return (x + 1)
Just 4
> Nothing >>= \x -> return (x + 1)
Nothing

P.S. Note the function we provide \x -> return (x + 1), return's value is demonstrated, requires function type to be a -> m b, so wrapping result with return is very convenient, and semantics is also appropriate

This characteristic is very suitable for handling a series of operations that might fail scenarios, like JS's:

const err = error => NaN;
new Promise((resolve, reject) => {
  resolve(1)
})
.then(v => v + 1, err)
.then(v => {throw v}, err)
.then(v => v * 2, err)
.then(console.log.bind(this), err)

A series of operations, intermediate steps might fail (throw v), after failure get result representing error (in above example is NaN), if no failure then can get correct result

Describe using Maybe's Monad characteristics:

> return 1 >>= \x -> return (x + 1) >>= \_ -> (fail "NaN" :: Maybe a) >>= \x -> return (x * 2)
Nothing

1:1 perfect restoration, calmly handle a series of operations that might fail using Maybe Monad

IV. do Notation

Used do statement block in I/O scenarios (called do-notation), can combine a series of I/O Actions, for example:

> do line <- getLine; char <- getChar; return (line ++ [char])
hoho
!"hoho!"

String together 3 I/O Actions, and returned the last I/O Action. Actually, do notation is not only for I/O scenarios, also applicable to any Monad

Regarding syntax, do notation requires each line must be a monadic value, why?

Because do notation is just syntactic sugar for >>=, for example:

foo = do
  x <- Just 3
  y <- Just "!"
  Just (show x ++ y)

Analogy to ordinary calculations without context:

let x = 3; y = "!" in show x ++ y

Not hard to discover do notation's clean and concise advantage, actually is:

foo' = Just 3   >>= (\x ->
  Just "!" >>= (\y ->
  Just (show x ++ y)))

Without do notation, would need to manually write a bunch of lambda nesting:

Just 3 >>= (\x -> Just "!" >>= (\y -> Just (show x ++ y)))

So <-'s function is:

Like using >>= to bring monadic value to lambda

Have >>=, then what about >>, how to use?

maybeNothing :: Maybe Int
maybeNothing = do
  start <- return 0
  first <- return ((+1) start)
  Nothing
  second <- return ((+2) first)
  return ((+3) second)

When we write a line of operation in do notation, but don't use <- to bind values, actually it's using >>, it ignores the calculation result. We just want them ordered, not their results, and it's much prettier than writing _ <- Nothing.

Finally, there's fail, when errors occur in do notation will automatically call fail function:

fail        :: String -> m a
fail s      = errorWithoutStackTrace s

By default will error, cause program to crash, specific Monad instances have their own implementations, like Maybe:

fail _              = Nothing

Ignores error message, and returns Nothing. Try it out:

> do (x:xs) <- Just ""; y <- Just "abc"; return y;
Nothing

Pattern matching fails in do statement block, directly returns fail, significance lies in:

This way pattern matching failure is only limited within our monad's context, not entire program failure

V. List Monad

instance Monad []  where
  xs >>= f             = [y | x <- xs, y <- f x]
  (>>) = (*>)
  fail _              = []

List's context refers to an uncertain environment (non-determinism), i.e., exists multiple results, for example [1, 2] has two results (1,2), [1, 2] >>= \x -> [x..x + 2] has 6 results (1,2,3,2,3,4)

P.S. How to understand "multiple results"?

When first learning C language there was a confusion, can functions have multiple return? Then how to return multiple values?

Can return an array (or struct, linked list, etc.), organize multiple values together (put into a data structure), return as a package

If a function returns an array, uncertain how many results it returns, this is the so-called uncertain environment

From List's Monad implementation perspective, >>= is a mapping operation, nothing much to say

>> looks a bit interesting, equivalent to *> defined on Applicative:

class Functor f => Applicative f where
  (*>) :: f a -> f b -> f b
  a1 *> a2 = (id <$ a1) <*> a2

class  Functor f  where
  (<$)        :: a -> f b -> f a
  (<$)        =  fmap . const

const                   :: a -> b -> a
const x _               =  x

Function is discard values in first parameter, only retain structural meaning (List length information), for example:

> [1, 2] >> [3, 4, 5]
[3,4,5,3,4,5]

Equivalent to:

> ((fmap . const) id $ [1, 2]) <*> [3, 4, 5]
[3,4,5,3,4,5]
-- Or
> [id, id] <*> [3, 4, 5]
[3,4,5,3,4,5]

List Comprehension and do Notation

An interesting example:

> [1,2] >>= \n -> ['a','b'] >>= \ch -> return (n,ch)
[(1,'a'),(1,'b'),(2,'a'),(2,'b')]

The n at the end looks unscientific (looking at infixl 1 >>= seems can't access), actually can access n, because of lambda expression's greedy matching characteristic, equivalent to:

[1,2] >>= \n -> (['a','b'] >>= \ch -> return (n,ch))
-- Full version with parentheses
([1, 2] >>= (\n -> (['a','b'] >>= (\ch -> return (n,ch)))))

Function body without boundaries matches to rightmost end, related discussion see Haskell Precedence: Lambda and operator

P.S. Additionally, if uncertain about expression's binding method (don't know how to add parentheses), there's a magical method, see How to automatically parenthesize arbitrary haskell expressions?

Rewrite with do notation:

listOfTuples = do
  n <- [1,2]
  ch <- ['a','b']
  return (n,ch)

Formally very similar to List Comprehension:

[ (n,ch) | n <- [1,2], ch <- ['a','b'] ]

Actually, List Comprehension and do notation are both syntactic sugar, will eventually convert to >>= for calculation

VI. Monad laws

Similarly, Monad also needs to follow some rules:

Left identity: return a >>= f ≡ f a
Right identity: m >>= return ≡ m
Associativity: (m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)

Identity properties don't look very obvious, can use Kleisli composition to convert to more standard form:

-- | Left-to-right Kleisli composition of monads.
(>=>)       :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)
f >=> g     = \x -> f x >>= g

(Excerpted from Control.Monad)

From type declaration perspective, >=> is equivalent to composition operation between Monad functions (monadic function), these functions take ordinary values, output monadic values. Analogy to ordinary function composition:

(.)    :: (b -> c) -> (a -> b) -> a -> c
(.) f g = \x -> f (g x)

>=> composes Moand m => a -> m b functions from left to right, . composes a -> b functions from right to left

P.S. So, is there right-to-left Monad function composition? Yes, it's <=<

Describe Monad laws using Kleisli composition (>=>):

Left identity: return >=> f ≡ f
Right identity: f >=> return ≡ f
Associativity: (f >=> g) >=> h ≡ f >=> (g >=> h)

Satisfies these 3 rules, so is standard Monoid, Moand m => a -> m b function set and >=> operation defined on it forms monoid, identity element is return

P.S. Monad laws described using >=>, greater significance lies in these 3 rules are necessary laws for forming mathematical category, from then on has mathematical significance of category, see Category theory for details

MonadPlus

Things that simultaneously satisfy Monad and Monoid have dedicated name, called MonadPlus:

class (Alternative m, Monad m) => MonadPlus m where
  mzero :: m a
  mzero = empty
  mplus :: m a -> m a -> m a
  mplus = (<|>)

In List scenario, mzero is [], mplus is ++:

instance Alternative [] where
  empty = []
  (<|>) = (++)

What's the use of this?

For example, if want to filter list elements, List Comprehension is simplest:

> [ x | x <- [1..50], '7' `elem` show x ]
[7,17,27,37,47]

Can also handle with >>=:

> [1..50] >>= \x -> if ('7' `elem` show x) then [x] else []
[7,17,27,37,47]

Conditional expression looks somewhat bloated, with MonadPlus can change to more concise and powerful expression:

> [1..50] >>= \x -> guard ('7' `elem` show x) >> return x
[7,17,27,37,47]

Among them guard function is as follows:

guard           :: (Alternative f) => Bool -> f ()
guard True      =  pure ()
guard False     =  empty

Takes boolean value, outputs value with context (True corresponds to () in default context, False corresponds to mzero)

After guard processing, then use >> to restore non-identity values to original values (return x), while identity element after >> operation is still identity element ([]), gets filtered out

Corresponding do notation is as follows:

sevensOnly = do
  x <- [1..50]
  guard ('7' `elem` show x)
  return x

Compare List Comprehension form:

[ x | x <- [1..50], '7' `elem` show x ]

Very similar, both are concise expressions with almost no extra punctuation

Function in do Notation

Converting Monad laws to do notation description, can get another set of equivalent transformation rules:

-- Left identity
do { x′ <- return x;
    f x′
  }
≡
do { f x }

--  Right identity
do { x <- m;
    return x
  }
≡
do { m }

-- Associativity
do { y <- do { x <- m;
              f x
            }
    g y
  }
≡
do { x <- m;
    do { y <- f x;
          g y
        }
  }
≡
do { x <- m;
    y <- f x;
    g y
  }

These rules have 2 functions:

Can be used to simplify code

  skip_and_get = do
    unused <- getLine
    line <- getLine
    return line

  -- Using Right identity, remove extra return
  skip_and_get = do
    unused <- getLine
    getLine

Can avoid do block nesting

  main = do
    answer <- skip_and_get
    putStrLn answer

  -- Expand
  main = do
    answer <- do
      unused <- getLine
      getLine
    putStrLn answer

  -- Use associativity to undo do block nesting
  main = do
    unused <- getLine
    answer <- getLine
    putStrLn answer

VII. Monad and Applicative

Back to initial scenario, we already know Monad can syntactically simplify context-related calculations, can apply a -> m b to m a

Since Monad is built on Applicative foundation, then, compared with Applicative, where is Monad's core advantage, why does it exist?

Because applicative functor doesn't allow flexible interaction between applicative values

This, how to understand?

Look at another Maybe Applicative example:

> Just (+1) <*> (Just (+2) <*> (Just (+3) <*> Just 0))
Just 6

Applicative operations where intermediate links don't fail, can normally get results. What if intermediate links fail?

-- Intermediate failure
> Just (+1) <*> (Nothing <*> (Just (+3) <*> Just 0))
Nothing

Also meets expectations, pure Applicative operations seem to already meet needs. Look carefully at how we just expressed intermediate link failure: Nothing <*> some thing. This Nothing is like a hard-coded bomb, is a pure static scenario

Then if want dynamic explosion, what to do?

-- Insufficient flexibility
> Just (+1) <*> (Just (\x -> if (x > 1) then Nothing else return (x + 2)) <*> (Just (+3) <*> Just 0))
<interactive>:85:1: error:
? Non type-variable argument in the constraint: Num (Maybe a)
  (Use FlexibleContexts to permit this)
? When checking the inferred type
    it :: forall a. (Ord a, Num (Maybe a), Num a) => Maybe (Maybe a)

Error reason is attempting to dynamically control explosion, but got a Maybe (Maybe a):

> Just (\x -> if (x > 1) then Nothing else return (x + 2)) <*> (Just (+3) <*> Just 0)
Just Nothing

Reason for this awkward situation is Applicative's <*> just mechanically takes function from left context, applies to value in right context. Taking function from Maybe only has two results: either can't take anything from Nothing, immediately explode; or take an f from Just f, operation gets Just (f x), if previous step (x) didn't explode then can't explode anymore

So, from application scenario perspective, Monad is a computation context control, handles some general scenarios, such as error handling, I/O, computations with uncertain result counts, etc., its existence significance is: more flexible than Applicative, allows adding control at each calculation step, like Linux pipes