Haskell/MonadPlus

我們已經學習過, Maybe 和列表都表示了一個計算能夠擁有的結果數量. 換句話說, 我們使用 Maybe 來表示計算或許會失敗的情況 (即0種或1種結果), 我們使用列表來表示計算能夠返回0個或任意多個結果的情況.

或許有時我們會需要將兩個這些類型的計算所表示的所有結果合併起來. 比如說, 我們能夠將兩個列表 (++) 起來以"合併"兩個列表所表示的計算結果.

定義

MonadPlus 類型類定義了兩個函數. mzero 是表示沒有結果的值; mplus 則是一個將兩個計算合併的二元函數.

class Monad m => MonadPlus m where
  mzero :: m a
  mplus :: m a -> m a -> m a

以下是 Maybe 和列表的 instance:

instance MonadPlus [] where
  mzero = []
  mplus = (++)
 
instance MonadPlus Maybe where
  mzero                   = Nothing
  Nothing `mplus` Nothing = Nothing -- 0 个结果 + 0 个结果 = 0 个结果
  Just x  `mplus` Nothing = Just x  -- 1 个结果  + 0 个结果 = 1 个结果
  Nothing `mplus` Just x  = Just x  -- 0 个结果 + 1 个结果  = 1 个结果
  Just x  `mplus` Just y  = Just x  -- 1 个结果  + 1 个结果  = 2 个结果,
                                    -- 但是 Maybe 最多只能表示1个结果,
                                    -- 因此我们丢弃掉第二个.

另外, 在 Control.Monad.Error 模塊中, (Either e) 也定義了 MonadPlus 的 instance:

instance (Error e) => MonadPlus (Either e) where
  mzero            = Left noMsg
  Left _  `mplus` n = n
  Right x `mplus` _ = Right x

和 Maybe 一樣, (Either e) 表示了可能會失敗的計算. 但和 Maybe 不一樣的是, (Either e) 允許這個失敗的計算包含一條信息 (通常是一個字符串). 一般來說, Left s 表示一個信息為 s 的失敗的計算, Right x 則表示結果為 x 的成功的計算.

例子: 並行解析

傳統的輸入解析一般會使用一次"消耗"一個字符的一系列函數. 換句話說, 一個解析函數接收一個輸入字符串, 從頭部削去 (也就是所謂的"消耗") 一個滿足特定條件的字符. 比如說, 一個消耗一個大寫字符的函數. 但是如果這個頭部的字符不滿足這個特定的條件, 本次解析就失敗了; 因此在這樣的函數中使用 Maybe 或許是個好主意.

我們將使用 mplus 來並行運行兩個解析器. 換句話說, 如果第一個解析器成功我們就返回它的結果, 否則如果第二個成功我們就返回第二個的結果. 若兩個都失敗了, 我們返回, Nothing.

下例中, 我們消耗一個特定的數字字符並返回它所代表的數字.

digit :: Int -> String -> Maybe Int
digit i s | i > 9 || i < 0 = Nothing
          | otherwise      = do
  let (c:_) = s
  if [c] == show i then Just i else Nothing

我們的 guard 保證了我們所檢查的 Int只有一位. 然後, 我們檢查字符串的首位是否匹配我們所想要的數字. 如果匹配的話, 我們返回一個包裹在 Just 中的數字. do 代碼塊保證了失敗的任何模式匹配都將返回 Nothing.

我們使用 digit 和 mplus 函數來解析一個由二進位位組成的字符串:

binChar :: String -> Maybe Int
binChar s = digit 0 s `mplus` digit 1 s

解析器庫一般都以類似的方式使用 MonadPlus. 好奇的話, 你可以看看 Text.ParserCombinators.ReadP 中 (+++) 函數的實現, 或者 Text.ParserCombinators.Parsec.Prim 中的 (<|>).

MonadPlus 法則

MonadPlus 的 instance 必須滿足一些法則, 就如同 Monad 的 instance 需要滿足三條 Monad 法則一樣. 不幸的是, 人們對 MonadPlus 法則並沒有達成一致的意見. 最通常的意見是, mzero 和 mplus 需要形成一個么半群 (monoid). 換句話說:

-- mzero 是一个无具体意义的"中立"值
mzero `mplus` m  =  m
m `mplus` mzero  =  m
-- mplus 满足结合律
-- (但并不是所有的 instance 都满足这条定律, 因为这和一些无尽的值构造相悖)
m `mplus` (n `mplus` o)  =  (m `mplus` n) `mplus` o

"形成一個么半群" 並沒有什麼特別之處: 在上例中, "中立值" 和 "結合律" 可以比作整數加法的交換律和整數0. 事實上, 這也是為什麼這兩個函數叫做 mzero (m零) 和 mplus (m加).

Control.Monad 的 Haddock 文檔 額外規定了以下法則:

mzero >>= f  =  mzero
m >> mzero   =  mzero

HaskellWiki 則給出了具有爭議的另一條:

(m `mplus` n) >>= k  =  (m >>= k) `mplus` (n >>= k)

甚至還有更多的法則. 有時例如 IO 的 Monad 也會有 MonadPlus 的 instance. 參見 All About Monads 以及 Haskell Wiki.

實用函數

除了基礎的 mplus 和 mzero, 還有兩個應用了 MonadPlus 的通用函數:

msum

處理 MonadPlus 的常見操作: 將一個列表中的 MonadPlus 值, 例如 [Maybe a] 或 [[a]], 用 mplus 進行 fold. msum 函數正是為此而生:

msum :: MonadPlus m => [m a] -> m a
msum = foldr mplus mzero

某種意義上, msum 是只能用在列表上的函數 concat 的推廣. 事實上, 當應用在列表上時這兩個函數完全相同. 對於 Maybe, msum 返回其中的第一個 Just x,若其不存在則返回 Nothing.

guard

我們注意到, 列表 monad 和列表解析之間的驚人相似, 但我們或許不是很清楚列表解析中的過濾是如何實現的. guard 就是實現的方式.

我們來看看這個計算所有勾股數 (也就是能形成直角三角形三邊長的三個數) 的列表解析. 首先我們檢查暴力的方法. 我們用一個布爾條件來過濾那些非勾股數的組合:

pythags = [ (x, y, z) | z <- [1..], x <- [1..z], y <- [x..z], x^2 + y^2 == z^2 ]

將如上的列表解析寫成列表 monad 的形式:

pythags = do
  z <- [1..]
  x <- [1..z]
  y <- [x..z]
  guard (x^2 + y^2 == z^2)
  return (x, y, z)

guard 函數的定義:

guard :: MonadPlus m => Bool -> m ()
guard True  = return ()
guard _ = mzero

具體地, 當它獲得一個 False 作為參數時, guard 會將整個 do 代碼塊的運算結果化為 mzero. 因為由於 MonadPlus 法則第一條, mzero 位於 (>>=) 左側的運算將總是得回 mzero. do 代碼塊實際上是一系列用 (>>=) 串聯起來的表達式的語法糖, 因此在任何位置出現的 mzero 都將使它的最終結果變為 mzero.

我們將擴展上面的 pythags 函數以展示 guard 在列表 monad 中的應用. 首先, 這是將 guard 特化到列表 monad 後的實現:

guard :: Bool -> [()]
guard True  = [()]
guard _ = []

簡單地說, guard 堵住了 一條運算路徑. 在 pythags 中, 我們希望能夠堵住所有 x^2 + y^2 == z^2 為 False 的路徑 (或者說, x, y 和 z 的組合). 讓我們在展開 do 代碼塊後的代碼:

pythags =
  [1..] >>= \z ->
  [1..z] >>= \x ->
  [x..z] >>= \y ->
  guard (x^2 + y^2 == z^2) >>= \_ ->
  return (x, y, z)

將 (>>=) 和 return 替換成它們在列表 monad 中的特化 (並使用 let 綁定來增加可讀性), 我們得到如下等價代碼:

pythags =
 let ret x y z = [(x, y, z)]
     gd  z x y = concatMap (\_ -> ret x y z) (guard $ x^2 + y^2 == z^2)
     doY z x   = concatMap (gd  z x) [x..z]
     doX z     = concatMap (doY z  ) [1..z]
     doZ       = concatMap (doX    ) [1..]
 in doZ

我們注意到當它的參數為 False 時, guard 返回一個空列表. 而無論我們使用什麼函數, 對一個空列表 map 總是返回一個空列表. 因此在 gd 的 let 綁定中對於 guard 的調用中返回的空列表將使 gd 返回一個空列表, 因此 ret 也是一個空列表.

為了更好地理解, 我們可以將列表 monad 中的計算想像成一棵樹. 用我們的算法, 我們需要從頂部開始為每一個 x 的選取創建一個分支, 然後再在這些分支地下為所有 y 的選擇創建分支, z 也是同樣. 因此這棵"計算樹"會長這樣:

   start
   |____________________________________________ ...
   |                     |                    |
x  1                     2                    3
   |_______________ ...  |_______________ ... |_______________ ...
   |      |      |       |      |      |      |      |      |
y  1      2      3       2      3      4      3      4      5
   |___...|___...|___... |___...|___...|___...|___...|___...|___...
   | | |  | | |  | | |   | | |  | | |  | | |  | | |  | | |  | | |
z  1 2 3  2 3 4  3 4 5   2 3 4  3 4 5  4 5 6  3 4 5  4 5 6  5 6 7

每一個 x, y 和 z 的組合都代表了樹中的一條路徑. 當所有計算完成以後, 每一個分支被從下至上合併起來. 任何不滿足條件的路徑此時被轉化成空列表, 因此對合併過程沒有影響.

練習
證明 Maybe 和列表確實滿足 MonadPlus 法則. 我們能夠修改上面的解析器, 使其接收任意字符: -- | 消耗输入中的一个指定字符, 返回一个二元组, 其中包含了这个字符以及余下的字符串. 我们用 一个 do 代码块使得任意位置失败的模式匹配 都将返回 Maybe 的"失败状态" (也就是 Nothing) char :: Char -> String -> Maybe (Char, String) char c s = do let (c':s') = s if c == c' then Just (c, s') else Nothing 此時我們能夠實現一個 hexChar 函數, 其接收任何合法的十六進位數字符 (0-9 或 a-f). 試著實現這個函數 (提示: map digit [0..9] :: [String -> Maybe Int]).

和 Monoid 的關係

當我們討論 MonadPlus 法則時, 我們提到了數學上的么半群 (Monoid). 事實上 Haskell 中存在著一個 Monoid 類型類, 詳細教程請參見Haskell趣學指南中的章節:

class Monoid m where 
  mempty  :: m
  mappend :: m -> m -> m

列表是一個簡單的 monoid:

instance Monoid [a] where
  mempty  = []
  mappend = (++)

看起來是不是很熟悉呢? 儘管和 MonadPlus 有些相似, 它們有一點關鍵而微妙的區別. 注意在 instance 聲明中我們使用了 [a] 而不是 []. Monoid 並不一定是其他類型的"容器", 或者說不一定是多態的. 比如說, 整數加法構成了一個 Monoid, 其中"中立值" (mempty) 為0.

確實, MonadPlus 的 instance 看起來和 Monoid 類似, 因為兩者都有"零"和"加"的概念. 事實上, 我們能夠讓 MonadPlus 成為 Monoid 的子類 (如果值得這番功夫的話):

 instance MonadPlus m => Monoid (m a) where
   mempty  = mzero
   mappend = mplus

註解 由於 instance 聲明中自由變量 a 的存在, 上述代碼在 Haskell 98 中並不合法. 除非你開啟 GHC 的 語言擴展 FlexibleInstances: 如果你使用的是 GHCi, 使用參數 -XFlexibleInstances 啟動它或者在交互提示符下輸入 :set -XFlexibleInstances. 如果你編譯後再運行程序的話, 在源文件第一行加上 {-# LANGUAGE FlexibleInstances #-}.

我們重申一下, Monoid 和 MonadPlus 工作與不同的"層次". 正如之前所說, Monoid 並不一定是其他類型的"容器", 或者說不一定是多態的. 更加正式地, Monoid 的 kind 為 *, 但 MonadPlus 的 instance 的 kind 為 * -> *. (後者本身也是 Monad).

---

MonadPlus

習題解答

Monads

理解 Monad  >> 高級 Monad  >> Monad 進階  >> MonadPlus  >> Monadic parser combinators  >> Monad transformers  >> Monad 實務

Haskell

Haskell基礎 >> 初級Haskell >> Haskell進階 >> Monads 高級Haskell >> 類型的樂趣 >> 理論提升 >> Haskell性能 庫參考 >> 普通實務 >> 特殊任務