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 撰写，试图通过提供非平凡的示例来更广泛、更直观地理解单子