July 31, 2020 7 min to read

CIS 194 12 Monads 單子

Source: 12-monads

▌Monads 單子

CIS 194 第 12 週 2013 年 4 月 8 日

建議閱讀：

• The Typeclassopedia
• LYAH Chapter 12: A Fistful of Monads
• LYAH Chapter 9: Input and Output
• RWH Chapter 7: I/O
• RWH Chapter 14: Monads
• RWH Chapter 15: Programming with monads

▌Motivation 動機

在過去的幾周中，我們看到了 Applicative 類如何使我們能夠慣用地處理在某種“特殊上下文”中進行的計算-例如，考慮到 Maybe 可能出現的故障，[] 出現了多個可能的輸出， 像在家庭作業中一樣，使用 ((->) e) 諮詢某種環境，或者使用“組合器”方法構造解析器

但是，到目前為止，我們只看到了具有固定結構的計算，例如將數據構造函數應用於固定的參數集。 如果我們不預先知道計算的結構怎麼辦？也就是說，我們希望能夠根據一些中間結果來決定要做什麼？

作為示例，請從作業中回顧 Parser 類型，並假設我們已經為其實現了 Functor 和 Applicative 實例：

newtype Parser a = Parser { runParser :: String -> Maybe (a, String) }
instance Functor Parser where
  ...

instance Applicative Parser where
  ...

回想一下，Parser a 類型的值表示一個解析器，該解析器可以將 String 作為輸入，並可能產生類型 a 的值以及字符串的其餘未解析部分。 例如，整數的解析器，輸入為字符串

"143xkkj"

可能會產生輸出

Just (143, "xkkj")

如您在作業中所見，我們現在可以編寫類似

data Foo = Bar Int Int Char

parseFoo :: Parser Foo
parseFoo = Bar <$> parseInt <*> parseInt <*> parseChar

假設我們有函數 parseInt :: Parser Int 和 parseChar :: Parser Char。 Applicative 實例自動處理可能的失敗（如果解析任何組件失敗，則解析整個 Foo 都會失敗）並依次遍歷 String 輸入的未使用部分到每個組件。

但是，假設我們正在嘗試解析包含數字序列的文件，如下所示：

4 78 19 3 44 3 1 7 5 2 3 2

要注意的是，文件中的第一個數字告訴我們下一個“組”數字的長度。 組之後的下一個數字是下一組的長度，依此類推。 因此，以上示例可以分為以下幾類：

78 19 3 44   -- first group
1 7 5        -- second group
3 2          -- third group

這是一個有些人為的示例，但實際上，許多“真實世界”文件格式都遵循類似的原理，即您讀取某種標頭，然後告訴您隨後幾個塊的長度，或在哪裡可以找到內容。 文件等

我們想為此類型的文件格式編寫一個解析器

parseFile :: Parser [[Int]]

不幸的是，僅使用 Applicative 接口是不可能的。問題在於，Applicative 無法讓我們根據先前的結果來決定下一步該怎麼做：在看到結果之前，我們必須預先決定要運行的解析操作

但是事實證明，解析器類型可以支持這種模式，該模式被抽像到 Monad 類型類中

▌Monad 單子

Monad 類型類被定義為如下：

class Monad m where
  return :: a -> m a

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

  (>>)  :: m a -> m b -> m b
  m1 >> m2 = m1 >>= \_ -> m2

這看起來應該很熟悉！ 我們以前在 IO 上下文中已經看到了這些方法，但實際上它們根本不是特定於 IO 的。 事實證明，與 IO 的單子接口非常有用

return 也看起來很熟悉，因為它與 pure 具有相同的類型。 實際上，每個 Monad 都應該是 Applicative，且 pure = return。 我們兩者都有的原因是 Appilative 是 Monad 已經存在了一段時間之後才發明的

(>>) 只是 (>>=) 的專用版本（如果某些實例想要提供更有效的實現，則它包含在 Monad 類中，但默認情況下就可以了） 因此，要了解它，我們首先需要了解 (>>=)

實際上有第四個方法，稱為 fail，但是將其放在 Monad 類中是一個錯誤，並且您永遠不要使用它，因此我不會告訴您（如果您有興趣，可以在 Typeclassopedia 中閱讀它）

(>>=) （發音為 “綁定 (bind)” ）是所有操作所在！ 讓我們仔細考慮一下它的類型：

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

(>>=) 有兩個參數。 第一個是類型為 m a 的值。 （順便說一句，此類值有時稱為單子值或計算。也有人建議將它們稱為 Mobits。您不能稱其為 “monads”，因為那是一種錯誤：類型構造函數 m 是 a 在任何情況下，想法都是 m a 類型的 Mobit 表示計算，該計算會導致 a 類型的值（或多個值，或者沒有值），並且還可能具有某種“效果”：

• c1 :: Maybe a 是可能失敗的計算，但如果成功，則會導致 a
• c2 :: [a] 是導致（多個）as 的計算
• c3 :: Parser a 是一個隱式消耗 String 的一部分並且（可能）產生 a 的計算
• c4 :: IO a 是可能具有某些 I/O 效果的計算，然後產生 a

等等。(>>=) 的第二個參數呢？ 它是類型 (a -> m b) 的函數。 也就是說，它是一個函數，它將根據第一個計算的結果 選擇 要運行的下一個計算。 這正是體現 Monad 封裝計算能力的潛力，該計算可以根據先前的計算結果選擇下一步要做的事情

因此，所有 (>>=) 真正要做的就是將兩個位加在一起以產生一個更大的位，然後先運行一個，然後再運行另一個，返回第二個的結果。 最重要的轉折在於，我們要根據第一個輸出的輸出來決定哪個運行第二個移動

現在 (>>) 的默認實現應該有意義：

(>>)  :: m a -> m b -> m b
m1 >> m2 = m1 >>= \_ -> m2

m1 >> m2 簡單地先做 m1 然後再做 m2，而忽略 m1 的結果

▌Examples 例子

首先為 Maybe 編寫 Monad 實例：

instance Monad Maybe where
  return  = Just
  Nothing >>= _ = Nothing
  Just x  >>= k = k x

return 當然是 Just。如果 (>>=) 的第一個參數是 Nothing，則整個計算失敗；否則，如果是 Just x，我們將應用第二個參數 x 來決定下一步要做什麼

順便說一句，通常在第二個參數 (>>=) 中使用字母 k，因為 k 代表 “continuation”。 我希望我在開玩笑

一些例子：

check :: Int -> Maybe Int
check n | n < 10    = Just n
        | otherwise = Nothing

halve :: Int -> Maybe Int
halve n | even n    = Just $ n `div` 2
        | otherwise = Nothing

ex01 = return 7 >>= check >>= halve
ex02 = return 12 >>= check >>= halve
ex03 = return 12 >>= halve >>= check

列表構造函數 [] 的 Monad 實例怎麼樣？

instance Monad [] where
  return x = [x]
  xs >>= k = concat (map k xs)

一個簡單的例子：

addOneOrTwo :: Int -> [Int]
addOneOrTwo x = [x+1, x+2]

ex04 = [10,20,30] >>= addOneOrTwo

▌Monad combinators / Monad 組合器

關於 Monad 類的一件好事是，僅使用 return 和 (>>=)，我們可以構建許多不錯的通用組合器，以使用monad進行編程。 讓我們來看幾個

首先，sequence 獲取一元數值列表，並產生一個用於收集結果的單數值。這意味著什麼取決於特定的 monad。例如，在這種情況下，Maybe 僅當所有單個計算都完成時，整個計算才成功；在這種情況下，IO 意味著按順序運行所有計算；在這種情況下，這意味 Parser 在輸入的順序部分上運行所有解析器（並且只有在它們全部都成功時才成功）。

sequence :: Monad m => [m a] -> m [a]
sequence [] = return []
sequence (ma:mas) =
  ma >>= \a ->
  sequence mas >>= \as ->
  return (a:as)

使用 sequence，我們還可以編寫其他組合器，例如

replicateM :: Monad m => Int -> m a -> m [a]
replicateM n m = sequence (replicate n m)

現在我們終於可以編寫我們要編寫的解析器了：它很簡單

parseFile :: Parser [[Int]]
parseFile = many parseLine

parseLine :: Parser [Int]
parseLine = parseInt >>= \i -> replicateM i parseInt

（many 也稱為 zeroOrMore 在作業中）