Haskell/高階單子

單子作為計算

就 Haskell 中單子的用法而言，我們在 理解單子 中的介紹性討論歸結為：每個單子都表示一種 不同型別的計算。在這裡，以及本章的其餘部分，“計算”僅僅是一個函式呼叫：我們正在計算此函式的結果。稍後，我們將給出一些例子來解釋我們的意思，但首先，讓我們回顧一下基本單子運算子的作用

>>=

>>= 運算子用於 對兩個單子計算進行排序。這意味著它將它們組合在一起，以便當組合計算執行時，第一個計算將執行，並且其輸出將被饋送到第二個計算，然後第二個計算將使用（或依賴於）該值執行。

return

在計算方面，return x 只是一個計算，當執行時，它將按原樣生成結果 x，但以其自身（計算）的特定方式。當我們檢視下面的狀態時，後一句短語的含義將變得更加清晰。

那麼計算類比在實踐中是如何工作的呢？讓我們看一些例子。

Maybe 單子

Maybe 單子中的計算（即導致包裝在 Maybe 中的型別的函式呼叫）表示 可能失敗的計算。最簡單的例子是使用查詢表。查詢表是一個將 鍵 關聯到 值 的表。透過知道鍵並使用查詢表，您可以 查詢 值。例如，您可能在電話簿應用程式中有一個將聯絡人姓名作為鍵、電話號碼作為值的查詢表。在 Haskell 中實現查詢表的一種方法是使用成對列表：[(a, b)]。這裡 a 是鍵的型別，b 是值的型別。以下是電話簿查詢表可能的樣子

phonebook :: [(String, String)]
phonebook = [ ("Bob",   "01788 665242"),
              ("Fred",  "01624 556442"),
              ("Alice", "01889 985333"),
              ("Jane",  "01732 187565") ]

您對查詢表最常做的事情可能是查詢值！但是，此計算可能會失敗。如果我們嘗試在我們的電話簿中查詢“Bob”、“Fred”、“Alice”或“Jane”中的一個，一切都會很好，但是如果我們要查詢“Zoe”呢？Zoe 不在我們的電話簿中，因此查詢失敗了。因此，從表中查詢值的 Haskell 函式是一個 Maybe 計算

lookup :: Eq a => a  -- a key
       -> [(a, b)]   -- the lookup table to use
       -> Maybe b    -- the result of the lookup

讓我們探索一些來自 lookup 的結果

Prelude> lookup "Bob" phonebook
Just "01788 665242"
Prelude> lookup "Jane" phonebook
Just "01732 187565"
Prelude> lookup "Zoe" phonebook
Nothing

現在讓我們擴充套件它，以使用單子介面的全部功能。假設，我們現在正在為政府工作，一旦我們從聯絡人那裡獲得了電話號碼，我們想在大型的政府規模查詢表中查詢此電話號碼，以找出其汽車的註冊號。當然，這將是另一個 Maybe 計算。但是，如果他們不在我們的電話簿中，我們當然無法在政府資料庫中查詢他們的註冊號！因此，我們需要一個函式，它將從第一個計算中獲取結果，並將其放入第二個查詢中，但前提是我們第一次沒有獲得 Nothing。如果我們確實從第一個計算中獲得了 Nothing，或者如果我們從第二個計算中獲得了 Nothing，我們的最終結果應該為 Nothing。

comb :: Maybe a -> (a -> Maybe b) -> Maybe b
comb Nothing  _ = Nothing
comb (Just x) f = f x

細心的讀者可能已經猜到了我們要往哪裡走了。沒錯，comb 只是 >>=，但僅限於 Maybe 計算。因此，我們可以將我們的計算連結在一起

getRegistrationNumber :: String       -- their name
                      -> Maybe String -- their registration number
getRegistrationNumber name = 
  lookup name phonebook >>= 
    (\number -> lookup number governmentalDatabase)

如果我們隨後想在第三次查詢中使用來自政府資料庫查詢的結果（例如，我們想查詢他們的註冊號以檢視他們是否欠任何汽車稅），那麼我們可以擴充套件我們的 getRegistrationNumber 函式

getTaxOwed :: String       -- their name
           -> Maybe Double -- the amount of tax they owe
getTaxOwed name = 
  lookup name phonebook >>= 
    (\number -> lookup number governmentalDatabase) >>= 
      (\registration -> lookup registration taxDatabase)

或者，使用 do 塊樣式

getTaxOwed name = do
  number       <- lookup name phonebook
  registration <- lookup number governmentalDatabase
  lookup registration taxDatabase

讓我們在這裡停下來，思考一下如果我們得到 Nothing 會發生什麼。嘗試使用 >>= 將一個計算中的 Nothing 與另一個函式組合將導致 Nothing 被繼續傳遞，並且第二個函式被忽略（如果您不確定，請參閱我們上面對 comb 的定義）。也就是說，在大型計算中的 任何階段 的 Nothing 都會導致總體結果為 Nothing，而不管其他函式如何！因此，我們說 Maybe 單子的結構 傳播失敗。

需要注意的重要一點是，我們絕不侷限於查詢！還有許多許多函式的結果可能會失敗，因此可以使用 Maybe。您可能自己編寫過一兩個。任何 Maybe 中的計算都可以透過這種方式組合。

總結

Maybe 單子的重要特徵是

1. 它表示可能失敗的計算。
2. 它傳播失敗。

列表單子

列表單子中的計算（即以型別 [a] 結尾的計算）表示 具有零個或多個有效答案的計算。例如，假設我們正在模擬井字遊戲（在世界某些地區稱為井字遊戲）。一個有趣（儘管有點牽強）的問題可能是找到遊戲可能進行的所有方式：在給定某個棋盤配置（即正在進行的遊戲）的情況下，找到 3 輪後棋盤可能的狀態。

以下是列表單子的例項宣告

instance Monad [] where
  return a = [a]
  xs >>= f = concat (map f xs)

由於單子只有在我們將其連結在一起時才真正有用，因此讓我們更詳細地介紹一下我們的示例。問題可以歸結為以下步驟

1. 找到下一輪可能的棋盤配置列表。
2. 對這些配置中的每一個重複計算：用下一輪 C 的可能配置列表替換每個配置，將其稱為 C。
3. 我們現在將有一個列表的列表（每個子列表表示先前配置之後的輪次），因此為了能夠重複此過程，我們需要將此列表的列表摺疊成單個列表。

此結構應該類似於上面的單子例項宣告。以下是它可能的樣子，不使用列表單子

getNextConfigs :: Board -> [Board]
getNextConfigs = undefined -- details not important

tick :: [Board] -> [Board]
tick bds = concatMap getNextConfigs bds

find3rdConfig :: Board -> [Board]
find3rdConfig bd = tick $ tick $ tick [bd]

(concatMap 是一個方便的函式，當您需要連線對映的結果時可以使用：concatMap f xs = concat (map f xs)。)或者，我們可以使用列表單子定義它

find3rdConfig :: Board -> [Board]
find3rdConfig bd0 = do
  bd1 <- getNextConfigs bd0
  bd2 <- getNextConfigs bd1
  bd3 <- getNextConfigs bd2
  return bd3

列表推導式

需要注意的一件有趣的事情是列表推導式和列表單子有多麼相似。例如，查詢 畢達哥拉斯三元組 的經典函式

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

這可以直接轉換為列表單子

import Control.Monad (guard)

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

這裡唯一非平凡的元素是 guard。這將在下一個模組 加法單子 中解釋。

狀態單子

當把 State 單子看作一種計算而不是容器時，它實際上更有意義。State 中的計算表示依賴於並修改某些內部狀態的計算。例如，假設您正在編寫一個程式來模擬三體問題。內部狀態將是所有三個天體的位移、質量和速度。然後，一個函式（例如，獲取特定天體的加速度）需要將此狀態作為其計算的一部分進行引用。

State 中計算的另一個重要方面是它們可以修改內部狀態。同樣，在三體問題中，您可以編寫一個函式，該函式在給定特定天體的加速度的情況下，更新其位置。

State 單子與 Maybe 和列表單子有很大不同，因為它不表示計算的結果，而是表示計算本身的特定屬性。

我們的做法是將依賴於某些內部狀態的計算建模為以狀態引數作為輸入的函式。例如，如果您有一個函式f :: String -> Int -> Bool，並且我們想要修改它使其依賴於型別為s的某些內部狀態，那麼該函式變為f :: String -> Int -> s -> Bool。為了允許函式更改內部狀態，該函式返回一個（返回值，新狀態）對。因此，我們的函式變為f :: String -> Int -> s -> (Bool, s)

很明顯，這種方法有點笨拙。但是，型別並不是最糟糕的：如果我們想依次執行兩個有狀態的計算，分別稱為f和g，並將f的結果傳遞給g會發生什麼？第二個需要傳遞第一個計算執行後產生的新狀態，因此我們最終會“傳遞狀態”

fThenG :: (s -> (a, s)) -> (a -> s -> (b, s)) -> s -> (b, s)
fThenG f g s =
  let (v,  s' ) = f s    -- run f with our initial state s.
      (v', s'') = g v s' -- run g with the new state s' and the result of f, v.
  in (v', s'')           -- return the latest state and the result of g

所有這些“管道”可以透過使用 State 單子很好地隱藏起來。型別構造器State接受兩個型別引數：其環境（內部狀態）的型別及其輸出的型別。（即使新狀態在結果對中最後出現，狀態型別也必須在型別引數中首先出現，因為“真實”單子繫結到某種特定型別的狀態，但允許結果型別變化。）所以State s a表示一個有狀態的計算，它依賴於並可以修改型別為s的某些內部狀態，並且結果型別為a。它是如何定義的呢？很簡單，作為一個接收某個狀態並返回一個（值，新狀態）對的函式。

newtype State s a = State (s -> (a, s))

上面fThenG的示例實際上是 State 單子的>>=的定義，您可能還記得第一篇關於單子的章節。

return 的含義

我們之前提到過return x是“什麼也不做”並只返回x的計算。這個想法只在具有副作用的單子（如 State）中才開始真正具有意義。也就是說，State 中的計算有機會透過修改內部狀態來改變後續計算的結果。IO 的情況類似（因為，當然，IO 只是 State 的一個特例）。

return x不會這樣做。由return生成的計算通常不會有任何副作用。單子定律return x >>= f == f x基本上保證了這一點，對於“副作用”這個術語的大多數用法。

進一步閱讀

• Haskell 單子函式之旅 由 Henk-Jan van Tuyl 撰寫
• 關於單子的所有內容 由 Jeff Newbern 撰寫，很好地解釋了單子作為計算的概念，並使用了很好的示例。它還包含一個概述所有主要單子的部分，根據這種計算檢視解釋每個單子，並提供一個完整的示例。
• 單子 由 Eugene Kirpichov 撰寫，試圖透過提供非平凡的示例來更廣泛、更直觀地理解單子