Haskell/理解單子/列表

單子

序言：IO，一個應用函子
 理解單子
 也許
 列表
 do 語法
 IO
狀態
 替代和單子Plus
單子轉換器

列表是 Haskell 的基礎部分，在我們進入本章之前，我們已經廣泛地使用過它們。新穎的見解是，列表型別也是一個單子！

作為單子，列表用於模擬可能返回任意數量結果的非確定性計算。它與 Maybe 如何表示可能返回零或一個值的計算有某種相似之處；但對於列表，我們可以返回零個、一個或多個值（值的個數反映在列表的長度中）。

列表的`Monad` 例項

列表的 return 函式簡單地將一個值注入到列表中

return x = [x]

換句話說，這裡的 return 建立一個包含一個元素的列表，即它接收的單個引數。列表 return 的型別是 return :: a -> [a]，或者等效地，return :: a -> [] a。後一種寫法更清楚地表明我們正在用列表型別建構函式 [] 替換 return 簽名中的泛型型別建構函式（我們在理解單子中稱之為 M）（它不同於空列表，但很容易混淆！）。

繫結運算子沒有那麼簡單。我們將從考慮它的型別開始，對於列表的情況，它應該是

[a] -> (a -> [b]) -> [b]

這正是我們所期望的：它從列表中提取值，以將它們傳遞給一個產生新列表的函式。

這裡的實際過程涉及首先對給定列表進行 map，以獲得一個列表列表，即型別 [[b]]（當然，你可能使用的許多函式不會返回列表；但如上型別簽名所示，列表的單子繫結僅適用於返回列表的函式）。為了返回到一個常規列表，我們然後連線列表列表的元素，以獲得型別為 [b] 的最終結果。因此，我們可以定義 (>>=) 的列表版本

xs >>= f = concat (map f xs)

繫結運算子是理解不同單子如何工作的關鍵，因為它的定義指定了在使用單子時使用的鏈式策略。在列表單子的情況下，該策略允許我們模擬非確定性：a -> [b] 函式可以被視為一種方法，從型別為 a 的輸入中，生成型別為 b 的任意數量的可能輸出，而不特別確定任何一個。從這個角度來看，(>>=) 對多個輸入執行此操作，並將所有輸出可能性組合在一個結果列表中。

兔子入侵

將熟悉的列表處理函式合併到單子程式碼中很容易。考慮以下示例：兔子平均每窩產六隻幼崽，其中一半是母的。從一隻母兔開始，我們可以模擬每一代的母幼崽數量（即兔子長大後併產下自己的幼崽後，新的幼崽數量）

Prelude> let generation = replicate 3
Prelude> ["bunny"] >>= generation
["bunny","bunny","bunny"]
Prelude> ["bunny"] >>= generation >>= generation
["bunny","bunny","bunny","bunny","bunny","bunny","bunny","bunny","bunny"]

在這個愚蠢的例子中，所有元素都是相等的，但相同的整體邏輯可以用來模擬放射性衰變、化學反應或任何透過反覆乘法產生一系列元素的現象。

練習
預測 `["bunny", "rabbit"] >>= generation` 的結果應該是什麼。實現 `themselvesTimes :: [Int] -> [Int]`，它接受引數列表中的每個數字 $n$ 並生成 $n$ 個它的副本，放在結果列表中。

棋盤遊戲示例

假設我們正在模擬一個回合制棋盤遊戲，並想找到遊戲所有可能的進展方式。我們需要一個函式來計算下一個回合的所有選項，給定當前棋盤狀態

nextConfigs :: Board -> [Board]
nextConfigs bd = undefined -- details not important

為了找出兩個回合後的所有可能性，我們再次將我們的函式應用於新棋盤狀態列表中的每個元素。我們的函式接收一個棋盤狀態，並返回一個可能的新的狀態列表。因此，我們可以使用單子繫結將函式對映到列表中的每個元素

nextConfigs bd >>= nextConfigs

以同樣的方式，我們可以將結果再次繫結到函式（無限地）以生成下一回合的可能性。根據遊戲的特定規則，我們可能會到達沒有可能的下一回合的棋盤狀態；在這些情況下，我們的函式將返回空列表。

順便說一下，我們可以將幾個回合轉換成一個 do 程式碼塊（就像我們在理解單子中為祖父母示例所做的那樣）

threeTurns :: Board -> [Board]
threeTurns bd = do
  bd1 <- nextConfigs bd  -- bd1 refers to a board configuration after 1 turn
  bd2 <- nextConfigs bd1
  nextConfigs bd2

如果上面的程式碼看起來太神奇，請記住 do 語法只是 (>>=) 操作的語法糖。在每個左箭頭右邊，都有一個函式，它的引數計算結果為一個列表；箭頭左邊的變數代表列表元素。在左箭頭賦值行之後，可能會有後面的行將分配的變數作為函式的引數呼叫。這個後面的函式將對來自左箭頭行函式的列表中的每個元素執行。這個逐元素的過程對應於 (>>=) 定義中的 `map`。一個結果列表列表（原始列表中的每個元素一個）將被展平成一個單個列表（(>>=) 定義中的 `concat`）。

列表推導式

列表單子的工作方式與列表推導式非常相似。讓我們稍微修改一下我們剛剛為 threeTurns 編寫的 do 程式碼塊，使其以 return 結束...

threeTurns bd = do
  bd1 <- nextConfigs bd
  bd2 <- nextConfigs bd1
  bd3 <- nextConfigs bd2
  return bd3

這與以下列表推導式完全一致

threeTurns bd = [ bd3 | bd1 <- nextConfigs bd, bd2 <- nextConfigs bd1, bd3 <- nextConfigs bd2 ]

（在列表推導式中，使用從一個列表中獲取的元素來定義後續列表是完全合法的，就像我們在這裡所做的那樣。）

這種相似並非巧合：列表推導式在幕後是根據 concatMap 定義的，它是一個來自 Prelude 的函式，被定義為 concatMap f xs = concat (map f xs)。這正是列表單子繫結定義的再次出現！概括列表單子的本質：列表單子的繫結是連線和對映的組合，因此組合函式 concatMap 實際上與列表的 >>= 相同（除了不同的語法順序）。

為了使列表單子和列表推導式之間的對應關係完整，我們需要一種方法來複制列表推導式可以執行的過濾操作。我們將在稍後的替代和單子Plus 章中解釋如何實現這一點。

練習

正如在理解單子中所討論的，所有 Monad 也都有 Applicative 的例項。特別是，該例項的 (<*>) 可以定義為

fs <*> xs = concatMap (\f -> map f xs) fs