Haskell/理解單子

關於單子，甚至關於 "單子" 這個詞本身，都存在著某種神秘感。雖然我們這組章節的目標之一就是揭開圍繞它們的神秘面紗，但要理解這種神秘感是怎樣產生的並不難。單子在 Haskell 中非常有用，但這個概念起初往往很難理解。由於單子有如此多的應用，人們經常從特定的角度來解釋它們，這可能會阻礙你全方位理解它們。

從歷史上看，單子被引入 Haskell 用於執行輸入和輸出 - 也就是我們在 簡單的輸入和輸出 章和 這部分的序章 中討論的那種 I/O 操作。對於像讀取和寫入檔案這樣的操作，預定的執行順序至關重要，而單子操作自然適合於這種順序執行。但是，單子絕不侷限於輸入和輸出。它們可以用來提供各種各樣的功能，例如異常、狀態、非確定性、延續、協程等等。事實上，由於單子的多功能性，這些構造並不需要作為語言內置於 Haskell 中；相反，它們是由標準庫定義的。

在 序章 中，我們從一個例子開始，並用它逐步介紹了一些新的概念。在這裡，我們將以相反的方式進行，從單子的定義開始，並以此建立起與我們已經瞭解的知識之間的聯絡。

定義

一個單子 由三部分組成

• 一個 型別構造器 m；
• 一個函式 return；
• 一個運算子 (>>=)，讀作 "繫結"。

該函式和運算子是 Monad 型別類的成員，其型別分別為

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

並且需要滿足後面將解釋的 三個定律。

舉一個具體的例子，考慮 Maybe 單子。型別構造器為 m = Maybe，而 return 和 (>>=) 的定義如下

return :: a -> Maybe a
return x  = Just x

(>>=)  :: Maybe a -> (a -> Maybe b) -> Maybe b
m >>= g = case m of
             Nothing -> Nothing
             Just x  -> g x

Maybe 是單子，return 透過用 Just 包裹一個值來將其引入單子。至於 (>>=)，它接受一個 m :: Maybe a 值和一個 g :: a -> Maybe b 函式。如果 m 是 Nothing，則無需執行任何操作，結果為 Nothing。否則，在 Just x 的情況下，g 應用於 x（包裹在 Just 中的底層值），從而得到一個 Maybe b 結果。注意，該結果可能為 Nothing 也可能不為 Nothing，具體取決於 g 對 x 的處理。總而言之，如果 m 中存在一個型別為 a 的底層值，我們將其應用於 g，這將把底層值重新引入 Maybe 單子。

理解 return 和 (>>=) 如何工作的關鍵第一步是跟蹤哪些值和引數是單子的，哪些不是。就像在許多其他情況下一樣，型別簽名是我們的指導。

動機：Maybe

為了瞭解 (>>=) 和 Maybe 單子的用處，請考慮以下示例：想象一個家庭資料庫，它提供了兩個函式

father :: Person -> Maybe Person
mother :: Person -> Maybe Person

這些函式用來查詢某人的父親或母親的名字。如果我們的資料庫缺少一些相關資訊，Maybe 允許我們返回一個 Nothing 值來表示查詢失敗，而不是導致程式崩潰。

讓我們將我們的函式組合起來，以查詢不同的祖父母。例如，以下函式用來查詢外祖父（母親的父親）

maternalGrandfather :: Person -> Maybe Person
maternalGrandfather p =
    case mother p of
        Nothing -> Nothing
        Just mom -> father mom

或者，考慮一個函式來檢查兩位外祖父是否都在資料庫中

bothGrandfathers :: Person -> Maybe (Person, Person)
bothGrandfathers p =
    case father p of
        Nothing -> Nothing
        Just dad ->
            case father dad of
                Nothing -> Nothing
                Just gf1 ->                          -- found first grandfather
                    case mother p of
                        Nothing -> Nothing
                        Just mom ->
                            case father mom of
                                Nothing -> Nothing
                                Just gf2 ->          -- found second grandfather
                                    Just (gf1, gf2)

真是太麻煩了！每個查詢都可能因為返回 Nothing 而失敗，如果這種情況發生，整個函式也會因為返回 Nothing 而失敗。

顯然，必須有一種更好的方法來編寫這段程式碼，而不是一遍又一遍地重複 Nothing 的情況！確實，這就是 Maybe 單子所要做的。例如，用於檢索外祖父的函式與 (>>=) 運算子具有完全相同的結構，因此我們可以將其改寫為

maternalGrandfather p = mother p >>= father

藉助 lambda 表示式和 return，我們也可以改寫兩個外祖父的函式

bothGrandfathers p =
   father p >>=
       (\dad -> father dad >>=
           (\gf1 -> mother p >>=   -- gf1 is only used in the final return
               (\mom -> father mom >>=
                   (\gf2 -> return (gf1,gf2) ))))

雖然這些巢狀的 lambda 表示式可能看起來很令人困惑，但這裡需要注意的是，(>>=) 使我們擺脫了列出所有 Nothing 的麻煩，將注意力重新轉移到程式碼的有趣部分。

更準確地說：father p 的結果是一個單子值（在本例中，根據 p 的父親是否在資料庫中，結果要麼是 Just dad，要麼是 Nothing）。由於 father 函式接受一個普通（非單子）值，因此 (>>=) 將 p 的 dad 作為一個非單子 值傳遞給它。father dad 的結果再次成為單子，這個過程持續進行。

因此，(>>=) 幫助我們將非單子值傳遞給函式，而無需真正離開單子。在 Maybe 單子中，單子方面是指關於是否能找到值的不確定性。

型別類

在 Haskell 中，Monad 型別類用來實現單子。它由 Control.Monad 模組提供，幷包含在 Prelude 中。該類具有以下成員方法

class Applicative m => Monad m where
    return :: a -> m a
    (>>=)  :: m a -> (a -> m b) -> m b

    (>>)   :: m a -> m b -> m b
    fail   :: String -> m a

除了 return 和 bind 之外，還有兩個額外的成員方法，(>>) 和 fail。它們都有預設實現，因此在編寫例項時不需要提供它們。

運算子 (>>)，讀作 "然後"，只是一種方便的工具，其預設實現為

m >> n = m >>= \_ -> n

當第二個操作不涉及第一個操作的結果時，(>>) 用於對兩個單子操作進行排序，這在 IO 等單子中是一種常見的情況。

printSomethingTwice :: String -> IO ()
printSomethingTwice str = putStrLn str >> putStrLn str

函式 fail 用於處理 do 符號 中的模式匹配失敗。它是一個不幸的技術必需品，與單子本身沒有直接關係。建議不要在程式碼中直接呼叫 fail。

Monad 和 Applicative

需要注意的是，Applicative 是 Monad 的超類。 這有幾個值得強調的後果。首先，每個 Monad 也是一個 Functor 和 Applicative，因此 fmap、pure、(<*>) 都可以與單子一起使用。其次，實際編寫 Monad 例項也需要提供 Functor 和 Applicative 例項。我們將在本章後面討論如何做到這一點。第三，如果你已經學習了 序章，那麼 return 和 (>>=) 的型別和作用應該看起來很熟悉...

(*>) :: Applicative f => f a -> f b -> f b
(>>) :: Monad m => m a -> m b -> m b

pure :: Applicative f => a -> f a
return :: Monad m => a -> m a

(*>) 和 (>>) 型別的唯一區別在於約束從 Applicative 變成了 Monad。實際上，這是這兩種方法的唯一區別：如果你在處理 Monad，你總是可以替換 (*>) 和 (>>)，反之亦然。pure/return 也一樣——事實上，如果 Applicative 例項中存在 pure 的獨立定義，甚至不需要實現 return，因為 return = pure 是 return 的預設定義。

計算的概念

我們已經看到 (>>=) 和 return 如何方便地用於移除使用 Maybe 時出現的樣板程式碼。然而，這還不足以證明為什麼 monad 如此重要。我們下一步將以一種截然不同的風格重寫兩位祖父函式：使用 do 語法，並帶有 顯式花括號和分號。根據你對其他程式語言的經驗，你可能會發現這很有啟發性

bothGrandfathers p = do {
    dad <- father p;
    gf1 <- father dad;
    mom <- mother p;
    gf2 <- father mom;
    return (gf1, gf2);
  }

如果你覺得這看起來像一個指令式程式設計語言的程式碼片段，那是因為它是。特別是，這種命令式語言支援 *異常* ：father 和 mother 是可能無法產生結果的函式，而是會引發異常；當這種情況發生時，整個 do 塊將 *失敗*，即以異常終止（意味著在此評估為 Nothing）。

換句話說，表示式 father p 的型別是 Maybe Person，它被解釋為命令式 *語言* 中的語句，該語句返回一個 Person 作為結果，或者失敗。

對於所有 monad 來說都是如此：型別 M a 的值被解釋為命令式語言 M 中的 *語句*，該語句返回型別 a 的值作為其結果；這種語言的語義由 monad M 決定。^[3]

在這種解釋下， *then* 運算子 (>>) 只是分號的實現，而 (>>=) 則是分號和先前計算步驟結果的賦值（繫結）。就像 let 表示式可以寫成函式應用一樣，

   let x = foo in (x + 3)        corresponds to      foo  &  (\x -> id (x + 3))      -- v & f = f v 

賦值和分號可以用繫結運算子編寫

   x <- foo; return (x + 3)      corresponds to      foo >>= (\x -> return (x + 3))

在函式的情況下，& 和 id 是微不足道的；在 monad 的情況下，>>= 和 return 則是實質性的。

& 運算子組合了兩個純粹的 *計算*，foo 和 id (x + 3)，同時為變數 x 建立一個新繫結來儲存 foo 的 *值*，使 x 可用於第二個計算步驟，id (x + 3)。

繫結運算子 >>= 組合了兩個 *計算* 步驟，foo 和 return (x + 3)，以 monad M 特定的方式，同時為變數 x 建立一個新繫結來儲存 foo 的 *結果*，使 x 可用於下一個計算步驟，return (x + 3)。在 Maybe 的特定情況下，如果 foo 無法產生結果，則會跳過第二步，整個組合計算也會立即失敗。

函式 return 將一個普通值 a 提升到 M a，也就是命令式語言 M 中的語句，當執行/執行時，該語句將在沒有任何特定於 M 的額外效果的情況下產生值 a。這由 Monad Laws 保證，foo >>= return === foo 和 return x >>= k === k x；見下文。

注意

(>>=) 以及因此 Monad 位於 do 塊中的左箭頭背後的這一事實解釋了為什麼我們無法在 序言 中解釋它們，當時我們只瞭解 Functor 和 Applicative。Applicative 足以提供 do 塊的一些功能，但不是全部。

命令式語言的不同語義對應於不同的 monad。下表展示了每個 Haskell 程式設計師都應該知道的經典選擇。如果你對 monad 的概念仍然不清楚，學習以下章節中的每個示例不僅會讓你獲得一個全面的工具箱，還能幫助你理解它們背後的共同抽象。

Monad	命令式語義	華夏公益教科書章節
Maybe	異常（匿名）	Haskell/Understanding monads/Maybe
錯誤	異常（帶錯誤描述）	Haskell/Understanding monads/Error
IO	輸入/輸出	Haskell/Understanding monads/IO
[] （列表）	非確定性	Haskell/Understanding monads/List
Reader	環境	Haskell/Understanding monads/Reader
Writer	記錄器	Haskell/Understanding monads/Writer
State	全域性狀態	Haskell/Understanding monads/State

此外，這些不同的語義不需要孤立地發生。正如我們將在接下來的幾章中看到，可以透過使用 monad 變換器 將多個 monad 的語義組合成單個 monad 來混合和匹配它們。

Monad Laws

在 Haskell 中，Monad 型別類 (以及因此所有繫結 (>>=) 和 return 的實現) 的每個例項都必須遵循以下三條定律

m >>= return     =  m                        -- right unit
return x >>= f   =  f x                      -- left unit

(m >>= f) >>= g  =  m >>= (\x -> f x >>= g)  -- associativity

Return 作為中性元素

return 的行為由左單位律和右單位律指定。它們指出 return 不執行任何計算，它只是收集值。例如，

maternalGrandfather p = do
        mom <- mother p
        gf  <- father mom
        return gf

與

maternalGrandfather p = do
        mom  <- mother p
        father mom

完全相同，這是由於右單位律。

繫結的結合律

結合律確保 (就像分號一樣) 繫結運算子 (>>=) 只關心計算的順序，而不關心它們的巢狀；例如，我們可以這樣寫 bothGrandfathers (與我們最早沒有 do 的版本相比)

bothGrandfathers p =
   (father p >>= father) >>=
       (\gf1 -> (mother p >>= father) >>=
           (\gf2 -> return (gf1,gf2) ))

*then* 運算子 (>>) 的結合律是一個特例

(m >> n) >> o  =  m >> (n >> o)

Monadic 組合

透過將定律重鑄為

(f >=> g) >=> h  =  f >=> (g >=> h)

更容易理解繫結的結合律，其中 (>=>) 是 *monad 組合運算子*，它是函式組合運算子 (.) 的近似模擬，只是引數反轉了。它被定義為

(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c
f >=> g = \x -> f x >>= g

還有 (<=<)，它是 (>=>) 的反轉版本。當使用它時，組合的順序與 (.) 相匹配，因此在 (f <=< g) 中 g 首先出現。^[4]

Monad 和範疇論

Monad 最初來自數學中稱為範疇論的一個分支。幸運的是，要理解和使用 Haskell 中的 monad，完全不需要理解範疇論。範疇論中對 monad 的定義實際上使用了略微不同的表示。翻譯成 Haskell，這種表示給出了 monad 的一個替代但等效的定義，這可以讓我們對 Monad 類有一些額外的見解。^[5]

到目前為止，我們已經用 (>>=) 和 return 來定義 monad。相反，替代定義將 monad 視為具有兩個附加組合器的函子

fmap   :: (a -> b) -> M a -> M b  -- functor

return :: a -> M a
join   :: M (M a) -> M a

出於本文討論的目的，我們將使用在 有關函子類的章節 中討論的函子作為容器的隱喻。根據它，函子 M 可以被認為是容器，因此 M a "包含" 型別為 a 的值，並具有相應的對映函式，即 fmap，它允許將函式應用於容器內部的值。

在這種解釋下，這些函式的行為如下

• fmap 將給定函式應用於容器中的每個元素
• return 將元素打包到容器中，
• join 獲取容器的容器並將它扁平化為單個容器。

使用這些函式，繫結組合器可以定義如下

m >>= g = join (fmap g m)

同樣，我們可以給出 fmap 和 join 的定義，它們用 (>>=) 和 return 表示

fmap f x = x >>= (return . f)
join x   = x >>= id

liftM 及其朋友

之前，我們指出每個 Monad 都是一個 Applicative，因此也是一個 Functor。其中一個結果是 return 和 (>>) 分別是 pure 和 (*>) 的 monad 版本。然而，這並非全部。首先，Control.Monad 定義了 liftM，它是一個具有奇怪熟悉的型別簽名的函式...

liftM :: (Monad m) => (a1 -> r) -> m a1 -> m r

正如你可能猜到的那樣，liftM 只是用 (>>=) 和 return 實現的 fmap，就像我們在上一節中做的那樣。因此，liftM 和 fmap 是可以互換的。

另一個帶有奇特型別的 Control.Monad 函式是 ap

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

類似於其他情況，ap 是 (<*>) 的一個僅限於單子的版本。

在 Control.Monad 和其他基本庫模組中，還有很多其他 Applicative 函式具有專門針對 Monad 的版本。它們的存在主要是因為歷史原因：在 Haskell 中引入 Monad 和 Applicative 之間經過了幾年，Applicative 成為 Monad 的超類更是花了幾年的時間，因此使用專門的變體成為可選的。雖然原則上如今幾乎不需要使用僅限於單子的版本，但實際上你會在其他人的程式碼中經常看到 return 和 (>>) - 現在，它們的使用已經很成熟，這得益於超過二十年的 Haskell 實踐，而 Applicative 還沒有成為 Monad 的超類。

注意

鑑於 Applicative 是 Monad 的超類，實現 Monad 最明顯的方法是從編寫 Functor 例項開始，然後沿著類層次結構向下移動。

instance Functor Foo where
    fmap = -- etc.

instance Applicative Foo where
    pure = -- etc.
    (<*>) = -- etc.

instance Monad Foo where
    (>>=) = -- etc.

在閱讀接下來的幾章時，你可能想要編寫 Monad 的例項並嘗試它們，無論是為了執行書中的示例還是為了進行你可能想到的其他實驗。然而，以上面所示的方式編寫例項需要實現 pure 和 (<*>)，這在本書的此時此刻並不是一個舒適的任務，因為我們還沒有介紹 Applicative 法則（我們只會在 應用性函子章節 中介紹）。幸運的是，有一個變通方法：只實現 (>>=) 和 return，從而提供一個自包含的 Monad 例項，然後使用 liftM、ap 和 return 來填補其他例項。

instance Monad Foo where
    return = -- etc.
    (>>=) = -- etc.

instance Applicative Foo where
    pure = return
    (<*>) = ap

instance Functor Foo where
    fmap = liftM

關於單子的這一系列初始章節中的示例和練習不需要編寫 Applicative 例項，因此你可以使用這種變通方法，直到我們詳細討論 Applicative。