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 的組合都代表了樹中的一條路徑. 當所有計算完成以後, 每一個分支被從下至上合併起來. 任何不滿足條件的路徑此時被轉化成空列表, 因此對合併過程沒有影響.
練習 |
---|
|
和 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 聲明中自由變量
|
我們重申一下, 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
|