Monad_Haskell 筆記 10

一。從 Functor 到 Monad

從類型來看，Functor 到 Applicative 再到 Monad 是從一般到特殊的遞進過程（Monad 是特殊的 Applicative，Applicative 是特殊的 Functor）

Functor

能夠把普通函數 map over 到一個具有 context 的值

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

用來解決 context 相關計算中最簡單的場景：怎樣把一個不具 context 的函數應用到具有 context 的值？

(+1) ->? Just 1

fmap 登場：

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

Applicative

在 Functor 之上的增強，能夠把 context 裡的函數 map over 到一個具有 context 的值

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

Applicative 可以理解為計算語境（computation context），Applicative 值就是計算，比如：

Maybe a 代表可能會失敗的 computation，[a] 代表同時有好多結果的 computation(non-deterministic computation)，而 IO a 代表會有 side-effects 的 computation。

P.S. 關於 computation context 的詳細信息，見 [Functor 與 Applicative_Haskell 筆記 7](/articles/functor 與 applicative-haskell 筆記 7/#articleHeader4)

用來解決 context 相關計算中的另一個場景：怎樣把一個具有 context 的函數應用到具有 context 的值？

Just (+1) ->? Just 1

<*> 登場：

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

Monad

在 Applicative 之上的增強，能夠把一個輸入普通值輸出具有 context 值的函數，應用到一個具有 context 的值

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

如果你有一個具有 context 的值 m a，你能如何把他丟進一個只接受普通值 a 的函數中，並回傳一個具有 context 的值？也就是說，你如何套用一個型態為 a -> m b 的函數至 m a？

用來解決 context 相關計算中的最後一個場景：怎樣把一個輸入普通值輸出具有 context 的值的函數，應用到具有 context 的值？

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

>>= 登場：

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

三者的關聯

從接口行為來看，這三個東西都是圍繞具有 context 的值和函數在搞事情（即，context 相關的計算）。那麼，考慮一下，共有幾種組合情況？

函數輸入輸出類型一致的情況
- context 裡的函數 + context 裡的值：Applicative
- context 裡的函數 + 普通值：用 pure 包一下再調
- 普通函數 + context 裡的值：Functor
- 普通函數 + 普通值：函數調用
函數輸入輸出類型不一致的情況
- 函數輸入普通值，輸出 context 裡的值 + context 裡的值：Monad
- 函數輸入普通值，輸出 context 裡的值 + 普通值：直接調用
- 函數輸入 context 裡的值，輸出普通值 + context 裡的值：直接調用
- 函數輸入 context 裡的值，輸出普通值 + 普通值：用 pure 包一下再調

所以，就這個場景（把是否處於 context 裡的函數應用到是否處於 context 裡的值）而言，擁有 Functor、Applicative 和 Monad 已經足夠應付所有情況了

二。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

實際上，Monad 實例只要求實現 >>= 函數（稱之為 bind）即可。換言之，Monad 就是支持 >>= 操作的 Applicative functor 而已

return 是 pure 的別名，所以仍然是接受一個普通值並把它放進一個最小的 context 中（把普通值包進一個 Monad 裡面）

(>>) :: m a -> m b -> m b 定義了預設實現，把函數 \_ -> m b 通過 >>= 應用到 m a 上，用於（鏈式操作中）忽略前面的計算結果

P.S. 鏈式操作中，把遇到的 >> 換成 >>= \_ -> 就很容易弄明白了

P.S. 上面類型聲明中的 forall 是指 ?（離散數學中的量詞，全稱量詞 ? 表示「任意」，存在量詞 ? 表示「存在」）。所以 forall a b. m a -> (a -> m b) -> m b 是說，對於任意的類型變量 a 和 b，>>= 函數的類型是 m a -> (a -> m b) -> m b。可以省略掉 forall a b.，因為預設所有的小寫字母類型參數都是任意的：

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

三。Maybe Monad

Maybe 的 Monad 實現相當符合直覺：

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

>>= 把函數 k 應用到 Just 裡的值上，並返回結果，Nothing 的話，就直接返回 Nothing。例如：

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

P.S. 注意我們提供的函數 \x -> return (x + 1)，return 的價值體現出來了，要求函數類型是 a -> m b，所以把結果用 return 包起來很方便，並且語義也很恰當

這種特性很適合處理一連串可能出錯的操作的場景，比如 JS 的：

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)

一連串的操作，中間步驟可能出錯（throw v），出錯後得到表示錯誤的結果（上例中是 NaN），沒出錯的話就能得到正確的結果

用 Maybe 的 Monad 特性來描述：

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

1:1 完美還原，利用 Maybe Monad 從容應對一連串可能出錯的操作

四。do 表示法

在 I/O 場景用到過 do 語句塊（稱之為do-notation），可以把一串 I/O Action 組合起來，例如：

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

把 3 個 I/O Action 串起來，並返回了最後一個 I/O Action。實際上，do 表示法不僅能用於 I/O 場景，還適用於任何 Monad

就語法而言，do 表示法要求每一行都必須是一個 monadic value，為什麼呢？

因為do 表示法只是 >>= 的語法糖，例如：

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

類比不涉及 context 的普通計算：

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

不難發現 do 表示法的清爽簡潔優勢，實際上是：

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

如果沒有 do 表示法，就要手動寫一堆 lambda 嵌套：

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

所以 <- 的作用是：

像是使用 >>= 來將 monadic value 帶給 lambda 一樣

>>= 有了，那 >> 呢，怎麼用？

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

當我們在 do 表示法寫了一行運算，但沒用到 <- 來綁定值的話，其實實際上就是用了 >>，他會忽略掉計算的結果。我們只是要讓他們有序，而不是要他們的結果，而且他比寫成 _ <- Nothing 要來得漂亮得多。

最後，還有 fail，do 表示法中發生錯誤時會自動調用 fail 函數：

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

預設會報錯，讓程序掛掉，具體 Monad 實例有自己的實現，比如 Maybe：

fail _              = Nothing

忽略錯誤消息，並返回 Nothing。試玩一下：

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

在 do 語句塊中模式匹配失敗，直接返回 fail，意義在於：

這樣模式匹配的失敗只會限制在我們 monad 的 context 中，而不是整個程序的失敗

五。List Monad

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

List 的 context 指的是一個不確定的環境（non-determinism），即存在多個結果，比如 [1, 2] 有兩個結果（1,2），[1, 2] >>= \x -> [x..x + 2] 就有 6 個結果（1,2,3,2,3,4）

P.S. 怎麼理解「多個結果」？

初學 C 語言時有個困惑，函數能不能有多個 return？那要怎麼返回多個值？

可以返回一個數組（或者結構體、鏈表等都行），把多個值組織到��起（放進一個數據結構），打包返回

如果一個函數返回個數組，就不確定他返回了多少個結果，這就是所謂的不確定的環境

從 List 的 Monad 實現來看，>>= 是個映射操作，沒什麼好說的

>> 看起來有點意思，等價於定義在 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

作用是丟棄第一個參數中的值，僅保留結構含義（List 長度信息），例如：

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

等價於：

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

List Comprehension 與 do 表示法

一個有趣的示例：

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

最後的 n 看著不太科學（看 infixl 1 >>= 好像訪問不到），實際上能訪問到 n，是因為 lambda 表達式的貪婪匹配特性，相當於：

[1,2] >>= \n -> (['a','b'] >>= \ch -> return (n,ch))
-- 加括號完整版
([1, 2] >>= (\n -> (['a','b'] >>= (\ch -> return (n,ch)))))

函數體沒界限就匹配到最右端，相關討論見 Haskell Precedence: Lambda and operator

P.S. 另外，如果不確定表達式的結合方式（不知道怎麼加括號）的話，有神奇的方法，見 How to automatically parenthesize arbitrary haskell expressions?

用 do 表示法重寫：

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

形式上與 List Comprehension 很像：

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

實際上，List Comprehension 和 do 表示法都只是語法糖，最後都會轉換成 >>= 進行計算

六。Monad laws

同樣，Monad 也需要遵循一些規則：

左單位元（Left identity）：return a >>= f ≡ f a
右單位元（Right identity）：m >>= return ≡ m
結合律（Associativity）：(m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)

單位元的性質看起來不很明顯，可以藉助 Kleisli composition 轉換成更標準的形式：

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

（摘自 Control.Monad）

從類型聲明來看，>=> 相當於*Monad 函數之間的組合運算*（monadic function），這些函數輸入普通值，輸出 monadic 值。類比普通函數組合：

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

>=> 從左向右組合 Moand m => a -> m b 的函數，. 從右向左組合 a -> b 的函數

P.S. 那麼，有沒有從右向左的 Monad 函數組合呢？沒錯，就是 <=<

用 Kleisli composition（>=>）來描述 Monad laws：

左單位元：return >=> f ≡ f
右單位元：f >=> return ≡ f
結合律：(f >=> g) >=> h ≡ f >=> (g >=> h)

滿足這 3 條，所以是標準的 Monoid，Moand m => a -> m b 函數集合及定義在其上的 >=> 運算構成幺半群，幺元是 return

P.S. 用 >=> 描述的 Monad laws，更大的意義在於這 3 條是形成數學範疇所必須的規律，從此具有範疇的數學意義，具體見 Category theory

MonadPlus

同時滿足 Monad 和 Monoid 的東西有專用的名字，叫 MonadPlus：

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

在 List 的場景，mzero 就是 []，mplus 是 ++：

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

這有什麼用呢？

比如要對列表元素進行過濾的話，List Comprehension 最簡單：

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

用 >>= 也能搞定：

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

條件表達式看起來有些臃腫，有了 MonadPlus 就可以換成更簡潔有力的表達方式：

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

其中 guard 函數如下：

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

輸入布爾值，輸出具有 context 的值（True 對應放在缺省 context 裡的 ()，False 對應 mzero）

經 guard 處理後，再利用 >> 把非幺元值恢復成原值（return x），而幺元經過 >> 運算後還是幺元（[]），就被濾掉了

對應的 do 表示法如下：

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

對比 List Comprehension 形式：

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

非常相像，都是幾乎沒有多餘標點的簡練表達

在 do 表示法中的作用

把 Monad laws 換成 do 表示法描述的話，就能得到另一組等價轉換規則：

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

這些規則有2 個作用：

能夠用來簡化代碼

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

 -- 利用 Right identity，去掉多餘的 return
 skip_and_get = do
   unused <- getLine
   getLine

能夠避免 do block 嵌套

 main = do
   answer <- skip_and_get
   putStrLn answer

 -- 展開
 main = do
   answer <- do
     unused <- getLine
     getLine
   putStrLn answer

 -- 用結合律解開 do block 嵌套
 main = do
   unused <- getLine
   answer <- getLine
   putStrLn answer

七。Monad 與 Applicative

回到最初的場景，我們已經知道了 Monad 在語法上能夠簡化 context 相關計算，能夠把 a -> m b 應用到 m a 上

既然 Monad 建立在 Applicative 的基礎之上，那麼，與 Applicative 相比，Monad 的核心優勢在哪裡，憑什麼存在？

因為 applicative functor 並不允許 applicative value 之間有彈性的交互

這，怎麼理解？

再看一個 Maybe Applicative 的示例：

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

中間環節都不出錯的 Applicative 運算，能夠正常得到結果。如果中間環節出錯了呢？

-- 中間失敗
> Just (+1) <*> (Nothing <*> (Just (+3) <*> Just 0))
Nothing

也符合預期，純 Applicative 運算似乎已經滿足需要了。仔細看看剛才是如何表達中間環節的失敗的：Nothing <*> some thing。這個 Nothing 就像是硬編碼裝上去的炸彈，是個純靜態場景

那想��動態爆炸的話，怎麼辦？

-- 靈活性不足
> 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)

出錯的原因是試圖動態控制爆炸，卻搞出來一個 Maybe (Maybe a)：

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

之所以會出現這樣尷尬的局面，是因為 Applicative 的 <*> 只是機械地從左側 context 裡取出函數，應用到右側 context 裡的值上。從 Maybe 取函數只有兩種結果：要麼從 Nothing 取不出東西來，立即爆炸；要麼從 Just f 取出個 f，運算得到 Just (f x)，上一步（x）沒炸的話就炸不了了

所以，從應用場景來看，Monad 是一種計算語境控制，應對一些通用場景，比如錯誤處理，I/O，不確定結果數量的計算等等，其存在意義是：比 Applicative 更靈活，允許在每一步計算中添加控制，像 Linux 管道一樣