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