Haskell/Alternative 和 MonadPlus

Alternative 和 MonadPlus (解答)

單子

序言：IO，一個應用函子
 理解單子
 Maybe
List
do 符號
 IO
State
Alternative 和 MonadPlus
單子轉換器

在我們的學習中，我們看到 Maybe 和列表都可以表示結果數量不同的計算。我們使用 Maybe 來表示計算可能會以某種方式失敗（也就是說，它可能會有零個結果或一個結果），而我們使用列表來表示可能有多個可能結果的計算（範圍從零到任意多個結果）。在這兩種情況下，一個有用的操作是將多個計算的所有可能結果合併成一個計算。例如，對於列表，這將相當於連線可能結果的列表。Alternative 類以通用方式捕獲此合併。

定義

注意

Alternative 類及其方法可以在 Control.Applicative 模組中找到。

Alternative 是 Applicative 的一個子類，其例項必須至少定義以下兩個方法

class Applicative f => Alternative f where
  empty :: f a
  (<|>) :: f a -> f a -> f a

empty 是一個具有零個結果的應用計算，而 (<|>) 是一個將兩個計算組合起來的二元函式。

以下是 Maybe 和列表的兩個例項定義

instance Alternative Maybe where
  empty               = Nothing
  -- Note that this could have been written more compactly.
  Nothing <|> Nothing = Nothing -- 0 results + 0 results = 0 results
  Just x  <|> Nothing = Just x  -- 1 result  + 0 results = 1 result
  Nothing <|> Just x  = Just x  -- 0 results + 1 result  = 1 result
  Just x  <|> Just y  = Just x  -- 1 result  + 1 result  = 1 result:
                                -- Maybe can only hold up to one result,
                                -- so we discard the second one.

instance Alternative [] where
  empty = []
  (<|>) = (++) -- length xs + length ys = length (xs ++ ys)

示例：並行解析

傳統的輸入解析涉及一次消費一個字元的輸入的函式。也就是說，解析函式接收一個輸入字串，如果字元滿足某些條件，就會從字串的開頭擷取（即“消費”）字元。例如，你可以編寫一個函式來消費一個大寫字母。如果字串開頭的字元不滿足給定條件，則解析器已失敗。例如，在下面的示例中，我們消費輸入中的一個數字並返回已解析的數字。失敗的可能性透過使用 Maybe 來表示。

digit i (c:_)
  | i > 9 || i < 0 = Nothing
  | otherwise      =
    if [c] == show i then Just i else Nothing

守衛確保我們正在檢查的 Int 是一個單一位數。否則，我們只是檢查我們的字串的第一個字元是否與我們正在檢查的數字匹配。如果透過，我們返回用 Just 包裹的數字。否則我們返回 Nothing。

現在，(<|>) 可以用來並行執行兩個解析器。也就是說，如果第一個解析器成功，我們就使用它的結果，否則我們就使用第二個解析器的結果。如果兩者都失敗，則組合的解析器返回 Nothing。我們可以使用 digit 和 (<|>) 來例如解析二進位制數字字串

binChar :: String -> Maybe Int
binChar s = digit 0 s <|> digit 1 s

解析器庫通常以這種方式使用 Alternative。兩個例子是 Text.ParserCombinators.ReadP 中的 (+++) 和 Text.ParserCombinators.Parsec.Prim 中的 (<|>)。這種使用模式可以用選擇來描述。例如，如果我們想給 binChar 一個可以成功解析的字串，我們有兩個選擇：要麼以 '0' 開始字串，要麼以 '1' 開始字串。

MonadPlus

MonadPlus 類與 Alternative 密切相關

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

它的定義與 Alternative 相同，除了方法名稱不同，Applicative 約束被改為 Monad。不出所料，對於既有 Alternative 又有 MonadPlus 例項的型別，mzero 和 mplus 應該分別等效於 empty 和 (<|>)。

人們可能會合理地懷疑為什麼存在看似多餘的 MonadPlus 類。部分原因是歷史原因：就像 Monad 在 Haskell 中比 Applicative 早出現很久一樣，MonadPlus 也比 Alternative 早得多。除了這種偶然之外，還有一些額外的期望（這些期望不適用於 Alternative）關於 MonadPlus 方法應該如何與 Monad 相互作用，因此表明某物是 MonadPlus 是一個比表明它既是 Alternative 又是 Monad 更強的斷言。在本章的後面，我們將對這個問題做一些額外的考慮。

Alternative 和 MonadPlus 法則

就像大多數通用類一樣，Alternative 和 MonadPlus 預計會遵循一些法則。然而，對於法則的完整集合應該是什麼，並沒有達成普遍共識。最常採用的法則，也是為 Alternative 提供直覺最關鍵的法則，說明 empty 和 (<|>) 構成一個么半群。這意味著

-- empty is a neutral element
empty <|> u  =  u
u <|> empty  =  u
-- (<|>) is associative
u <|> (v <|> w)  =  (u <|> v) <|> w

關於“構成一個么半群”沒有什麼花哨的地方：在上面，“中性元素”和“結合律”就像整數的加法被認為是結合律的，並且具有零作為其中性元素一樣。事實上，這個類比是 MonadPlus 方法名稱 mzero 和 mplus 的來源。

至於 MonadPlus，至少通常會有么半群法則，它們與上面提到的法則完全對應...

mzero `mplus` m  =  m
m `mplus` mzero  =  m
m `mplus` (n `mplus` o)  =  (m `mplus` n) `mplus` o

... 以及另外兩個法則，由 Control.Monad 文件引用

mzero >>= f  =  mzero -- left zero
m >> mzero   =  mzero -- right zero

如果 mzero 被解釋為失敗的計算，這些法則表明，在單子計算鏈中的失敗會導致整個鏈的失敗。

我們將在本章末尾討論一些關於 Alternative 和 MonadPlus 的其他法則建議。

有用函式

除了 (<|>) 和 empty 之外，基礎庫中還有另外兩個與 Alternative 相關的通用函式。

asum

使用 Alternative 時，一個常見的任務是取一個備選值的列表，例如 [Maybe a] 或 [[a]]，並使用 (<|>) 將其摺疊起來。來自 Data.Foldable 的函式 asum 實現了這個作用

asum :: (Alternative f, Foldable t) => t (f a) -> f a
asum = foldr (<|>) empty

在某種意義上，asum 概括了特定於列表的 concat 操作。事實上，當列表是正在使用的 Alternative 時，這兩者是等效的。對於 Maybe，asum 會找到列表中的第一個 Just x，如果沒有就返回 Nothing。

還應該提到的是，msum 可用於 `Data.Foldable` 和 `Control.Monad`，只是 asum 專門用於 MonadPlus。

msum :: (MonadPlus m, Foldable t) => t (m a) -> m a

guard

當討論列表單子時，我們注意到它與列表推導非常相似，但我們沒有討論如何映象列表推導過濾。Control.Monad 中的 guard 函式允許我們做到這一點。

考慮以下推導，它檢索所有畢達哥拉斯三元組（即作為直角三角形邊長的三個整數）。首先，我們將檢查暴力方法。我們將使用布林條件進行過濾；即畢達哥拉斯定理

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

將上面的推導轉換為列表單子 do-block 是

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

guard 函式可以為所有 Alternative 定義如下

guard :: Alternative m => Bool -> m ()
guard True  = pure ()
guard _ = empty

如果 guard 的謂詞為 False，它將減少 do-block 為 empty。給定左零律...

mzero >>= f = mzero
-- Or, equivalently:
empty >>= f = empty

... >>= 操作左側的 empty 將再次產生 empty。由於 do-block 被分解為許多透過 (>>=) 連線的表示式，任何位置的 empty 將導致整個 do-block 變成 empty。

讓我們詳細檢查 guard 在 pythags 中的作用。首先，以下是 guard 為列表單子定義的

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

基本上，guard 封鎖一條路徑。在 pythags 中，我們想要封鎖所有 x^2 + y^2 == z^2 為 False 的路徑（或 x、y 和 z 的組合）。讓我們看看上面 do-block 的展開以瞭解它的工作原理

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

將 >>= 和 return 替換為它們在列表單子中的定義（並使用一些 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 會返回空列表。對映到空列表會生成空列表，無論你傳遞什麼函式。因此，在 gd 中對 guard 的呼叫產生的空列表將導致 gd 生成空列表，而 \_ -> ret x y z 在其他情況下會新增結果，但實際上並沒有被呼叫。

為了理解這為什麼重要，請將列表計算視為一棵樹。使用我們的畢達哥拉斯三元組演算法，我們需要從頂部開始為 z 的每一個選擇建立一個分支，然後從這些分支中的每一個分支開始為 x 的每一個值建立一個分支，然後從這些分支中的每一個分支開始為 y 的每一個值建立一個分支。因此，樹看起來像這樣

   start
   |_________________________...
   |    |         |
z  1    2         3
   |    |____     |____________
   |    |    |    |       |    |
x  1    1    2    1       2    3
   |    |_   |    |___    |_   |
   |    | |  |    | | |   | |  |
y  1    1 2  2    1 2 3   2 3  3

z、x 和 y 的每一個組合表示樹中的一條路徑。一旦所有函式都應用完成，每個分支的結果將從底部開始連線在一起。任何謂詞不成立的路徑都會評估為空列表，因此對這種連線沒有影響。

練習

證明 Maybe 和列表的 Alternative 單子定律。

我們可以增強來自並行解析示例的解析器，使其能夠以以下方式處理任何字元

-- | Consume a given character in the input, and return 
--   the character we just consumed, paired with rest of 
--   the string. We use a do-block  so that if the
--   pattern match fails at any point, 'fail' of the
--   Maybe monad (i.e. Nothing) is returned.
char :: Char -> String -> Maybe (Char, String)
char c s = do
  c' : s' <- return s
  guard (c == c')
  return (c, s')

然後就可以編寫一個 hexChar 函式來解析任何有效的十六進位制字元（0-9 或 a-f）。嘗試編寫此函式（提示：map digit [0..9] :: [String -> Maybe Int]）。

使用 guard 和 Applicative 組合器（pure、(<*>)、(*>) 等）從Maybe 單子章節實現 safeLog。不要使用 Monad 組合器（return、(>>=)、(>>) 等）。

與單子的關係

在討論上面的 Alternative 定律時，我們提到了單子的數學概念。事實上，Haskell 中已經有一個 Monoid 類（在Data.Monoid 中定義）。單子的完整介紹將在後面的章節中給出。但是現在，只需要說 Monoid 的最小定義實現了兩種方法；即中性元素（或“零”）和關聯二元運算（或“加”）。

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

例如，列表形成一個簡單的單子

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

看起來很熟悉，不是嗎？儘管與 Alternative 和 MonadPlus 有驚人的相似之處，但有一個關鍵的區別。請注意例項宣告中使用的是 [a] 而不是 []。單子不一定是任何東西的“包裝器”，或者引數多型的。例如，整數在加法下形成一個單子，其中 0 作為中性元素。Alternative 是一個獨立的型別類，因為它捕獲了一種特定型別的單子，具有獨特的屬性 - 例如，一個二元運算(<|>) :: Alternative f => f a -> f a -> f a，它本質上與 Applicative 上下文相關聯。

其他建議的定律

注意

將此視為獎勵部分。雖然瞭解這些定律的不同版本是件好事，但總的來說，這個問題不值得為此而失眠。

除了上面幾節中提到的普遍假定的定律之外，還有一些其他定律從某些角度來看是有意義的，但並不適用於 Alternative 和 MonadPlus 的所有現有例項。特別是目前的 MonadPlus 可能被視為幾個假設類的交集，這些類將具有其他定律。

以下兩個附加定律通常被建議用於 Alternative。雖然它們確實適用於 Maybe 和列表，但核心庫中存在反例。還要注意，對於也是 MonadPlus 的 Alternative，前面提到的 mzero 定律並不是這些定律的結果。

(f <|> g) <*> a = (f <*> a) <|> (g <*> a) -- right distributivity (of <*>)
empty <*> a = empty -- right absorption (for <*>)

至於 MonadPlus，一個常見的建議是左分配定律，它適用於列表，但不適用於 Maybe

(m `mplus` n) >>= k  =  (m >>= k) `mplus` (n >>= k) -- left distribution

相反，左捕獲定律適用於 Maybe，但不適用於列表

return x `mplus` m = return x -- left catch

通常假定任何 MonadPlus 例項都會滿足左分配或左捕獲。為什麼不能兩者都滿足呢？假設它們都滿足。那麼對於任何 x, y :: m a，

x `mplus` y
= -- monad identity
(return x >>= id) `mplus` (return y >>= id)
= -- left distribution
(return x `mplus` return y) >>= id
= -- left catch
return x >>= id
= -- monad identity
x

這立即排除了除最瑣碎的 MonadPlus 實現之外的所有實現。更糟糕的是，這意味著對於任何 x，mzero `mplus` x = mzero。然後新增單子標識定律 mzero `mplus` x = x 意味著該單子只有一個值，因此與瑣碎的單子 Data.Proxy.Proxy 同構。

最後，值得注意的是，即使關於單子定律也存在分歧。有時針對它們提出的一個案例是，對於某些通常用 MonadPlus 表示的非確定性單子，關鍵定律是左零和左分配，而在這些情況下，單子定律會導致困難，應該完全放鬆或放棄。

一些完全可選的進一步閱讀，供好奇的讀者參考