跳轉到內容

Haskell/Alternative 和 MonadPlus

Edit links
來自華夏公益教科書
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（如果不存在任何 Just x）。

還應該提到，msum（可從 `Data.Foldable` 和 `Control.Monad` 中獲得）只是專門針對 MonadPlus 的 asum。

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、y 和 z 的組合），其中 x^2 + y^2 == z^2 為 False。讓我們看一下上面 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

請記住，guard 在其引數為 False 時返回空列表。對映跨空列表會生成空列表，無論您傳遞什麼函式。因此，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 的組合代表樹中的一條路徑。應用完所有函式後，從底部開始將每個分支的結果連線在一起。任何謂詞不成立的路徑都會評估為空列表，因此對這種連線沒有影響。

練習

[編輯 | 編輯原始碼]
練習
  1. 證明 Maybe 和列表的 Alternative 么半群定律。
  2. 我們可以增強並行解析示例中的解析器，使其能夠以以下方式處理任何字元
    -- | 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]）。
  3. 使用 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 表示的某些非確定性么半群，關鍵定律是左零和左分配，而么半群定律在這種情況下會導致困難，應該放寬或完全放棄。

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


取自 "https://wikibook.tw/w/index.php?title=Haskell/Alternative_and_MonadPlus&oldid=4342264"
華夏公益教科書