Haskell/理解单子/状态

如果您之前使用过任何其他语言进行编程，您可能编写了一些“保持状态”的函数。对于那些不熟悉这个概念的人来说，状态是指一个或多个变量，它们是执行某些计算所需的，但不是相关函数的参数。像C++这样的面向对象语言广泛使用状态变量（以类和对象内部的成员变量形式）。另一方面，像C这样的过程式语言通常使用在当前作用域之外声明的全局变量或函数中的静态变量来跟踪状态。

然而，在Haskell中，这些技术并不容易应用。这样做将需要可变变量，这意味着函数将具有隐藏的依赖关系，这与Haskell的函数纯度相矛盾。幸运的是，通常可以用函数式纯净的方式跟踪状态。我们通过将状态信息从一个函数传递到下一个函数来做到这一点，从而使隐藏的依赖关系变得显式。

State类型旨在简化将状态通过函数传递的过程。在本章中，我们将看到它如何帮助我们解决一些涉及状态的典型问题：模拟状态机和生成伪随机数。

状态机

我们将模拟一个简单的基于硬币式旋转门的有限状态机。我们的模型将得到增强，以便在任何状态下，它将为每个输入创建一个输出（除了状态转换之外）。

旋转门示例

旋转门的有限状态模型在此状态转换图中显示

旋转门有两个状态：锁定和解锁。（它从锁定状态开始）。有两种类型的输入：硬币（对应于有人将硬币投入投币口）和推（对应于有人推动手柄）。每个输入都会导致一个输出（谢谢、打开或嘘）并转换到一个（新的，或者可能是相同的）状态。如果有人在旋转门锁定时投入硬币，他们会得到感谢（是的，它会说话！），并且旋转门会解锁。如果他们添加更多硬币，他们会得到更多的感谢，但不会得到任何好处（旋转门只是保持解锁状态，不记得已经添加了多少额外的硬币）。如果有人在旋转门解锁时推动手柄，手柄会打开让他们通过，然后锁起来以防止其他人通过。如果有人在旋转门锁定时推动手柄，它会礼貌地对他们嘘，但不会让他们通过，并且保持锁定状态。

Haskell中的基本模型

我们将用以下方式表示状态和输出

data TurnstileState = Locked | Unlocked
  deriving (Eq, Show)

data TurnstileOutput = Thank | Open | Tut
  deriving (Eq, Show)

但是输入呢？我们可以将它们建模为函数。这是第一个尝试

coin, push :: TurnstileState -> TurnstileOutput

coin _ = Thank

push Unlocked = Open
push Locked   = Tut

这些函数正确地返回了任何状态下每个输入的输出，但没有给出任何关于新状态的指示。（在命令式程序中，这些“函数”也可能更新一个变量以指示新状态，但这在Haskell中不可行，我们认为也不理想）。答案很简单明了：将新状态与输出一起返回

coin, push :: TurnstileState -> (TurnstileOutput, TurnstileState)

coin _ = (Thank, Unlocked)

push Locked   = (Tut , Locked)
push Unlocked = (Open, Locked)

排序步骤

我们如何使用它？一种方法是列出由一系列输入产生的输出集

monday :: TurnstileState -> ([TurnstileOutput], TurnstileState)
monday s0 =
  let (a1, s1) = coin s0
      (a2, s2) = push s1
      (a3, s3) = push s2
      (a4, s4) = coin s3
      (a5, s5) = push s4
  in ([a1, a2, a3, a4, a5], s5)

GHCi> monday Locked
([Thank,Open,Tut,Thank,Open],Locked)

请注意，与coin和push类似，此monday函数采用初始状态作为参数，并返回最终状态以及输出列表。

练习

实现函数regularPerson, distractedPerson, hastyPerson :: TurnstileState -> ([TurnstileOutput], TurnstileState)。给定一个TurnstileState，每个函数都应该返回不同类型的人的输出（和更新状态）。一个regularPerson总是先投入硬币，然后推动手柄。一个distractedPerson总是先投入硬币，然后漫无目的地走开，没有通过。一个hastyPerson先推动手柄，没有投入硬币。如果手柄打开了（例如，他们跟随一个distractedPerson），他们就通过。如果手柄没有打开（例如，他们跟随一个regularPerson），他们会先投入硬币，然后推动手柄才能通过。 使用这些函数实现tuesday :: TurnstileState -> ([TurnstileOutput], TurnstileState)，返回以下访问者序列的输出：regularPerson、hastyPerson、distractedPerson、hastyPerson。 实现luckyPair :: Bool -> TurnstileState -> (Bool, TurnstileState)，表示两个人连续尝试使用旋转门。第一个是regularPerson或distractedPerson（取决于Bool参数）。第二个人会直接推动手柄，不会投入硬币，如果他们没有通过就会放弃。Bool结果应该指示第二个人是否通过。

从这些示例中可以看出

• 状态（某些固定类型）始终从一步传递到下一步，并且（通常）包含在函数的输入和输出中：将状态作为函数的输入和输出，使我们能够将它们链接在一起作为更大函数中的步骤，就像这些较小函数内的步骤链接在一起一样；
• 步骤的（非状态）输出可能用于决定后续步骤，也可能不使用：hastyPerson使用第一次push的输出来决定他们是否需要投入硬币，但regularPerson总是执行相同的两个步骤，无论它们的输出如何；
• 步骤的（非状态）输出可能用于函数的最终（非状态）返回值，也可能不使用：regularPerson的返回值使用了每个步骤的输出，但luckyPair的返回值不依赖于第一个步骤的输出；
• 除了初始状态之外，函数还可以接收参数：luckyPair接收一个Bool类型的参数；
• 不同函数的（非状态）返回值类型可以不同：coin返回TurnstileOutput，monday返回[TurnstileOutput]，而luckyPair返回Bool。

但是，所有这些代码都很繁琐、编写起来很枯燥且容易出错。理想情况下，如果我们能够自动提取元组的第二个元素（即新的状态）并将其传递到下一步，同时允许函数使用（非状态）值来做出有关后续步骤的决定，或者将其包含在（非状态）结果中，那将是最好的。这就是State登场的地方。

介绍State

Haskell 类型State描述了函数，这些函数会消耗状态并同时生成一个结果和一个更新后的状态，并将它们以元组的形式返回。

状态函数被一个数据类型定义所包裹，该定义附带一个runState访问器，这样就不需要模式匹配。对于我们目前的目的，State类型可以定义为

newtype State s a = State { runState :: s -> (a, s) }

这里，s是状态的类型，而a是生成的結果的类型。将类型命名为State可以说有点用词不当，因为被包裹的值本身并不是状态，而是一个状态处理器。

newtype

注意，我们使用newtype关键字而不是通常的data来定义数据类型。newtype只能用于只有一个构造函数和一个字段的类型。它确保编译器会消除单个字段的简单包裹和解包。因此，简单的包装类型（例如State）通常使用newtype定义。在这种情况下，使用type定义别名是否足够？其实并不够，因为type不允许我们为新的数据类型定义实例，而这正是我们要做的……

State构造函数去哪里了？

在实际应用中，State类型由transformers中的Control.Monad.Trans.State提供（也由mtl中的Control.Monad.State重新导出）。当你使用它时，你会很快发现没有State构造函数可用。transformers包以不同的方式实现State类型。这些差异不会影响我们如何使用或理解State，只是与我们上面提到的State构造函数不同，Control.Monad.Trans.State导出一个state函数，

state :: (s -> (a, s)) -> State s a

它执行相同的任务。至于为什么实际实现不是我们上面提到的显而易见的实现，我们将在后面的章节中说明。

注意

在下面所有代码中，State是一个（参数化的）类型（我们将为它创建Monad等实例），而state是一个函数，它接收一个参数（类型为s -> (a, s)）并返回一个类型为State s a的值。如果你正在按照本教程（我建议这样做）创建自己的State版本，请在newtype声明之后添加以下代码

state :: (s -> (a, s)) -> State s a
state = State

这将确保下面的代码无论你使用的是自己的State实现还是提供的State实现都是有效的。

实例化 Monad

到目前为止，我们所做的只是包裹一个函数类型并为其命名。然而，还有一个组成部分：对于每个类型s，State s都可以被创建为一个Monad实例，这将为我们提供非常方便的使用方式。

要定义一个Monad实例，还需要为Functor和Applicative定义实例。正如我们之前所解释的，这些超类实例可以从我们即将详细定义的Monad实例中推导出来。

import Control.Monad  -- you will need to put this towards the top of the file

instance Functor (State s) where
  fmap = liftM

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

在后面的章节中，我们将更详细地讨论State也作为Functor和Applicative的含义。你将有机会根据它们的特性显式地重新实现上述内容，而不仅仅是依赖于Monad实例。

现在让我们定义这个实例。

instance Monad (State s) where

注意，实例是State s，而不是仅仅是State本身；State不能被创建为Monad的实例，因为它接收两个类型参数，而不是一个。这意味着实际上有很多不同的State monad，每个可能的类型都有一个——State String、State Int、State SomeLargeDataStructure等等。但是，我们只需要编写return和(>>=)的一个实现；这些方法将能够处理s的所有选择。

return函数的实现如下

return :: a -> State s a
return x = State ( \ s -> (x, s) )

将一个值（x）传递给return会生成一个函数，该函数接收一个状态（s）并返回它不变，以及我们要返回的值。作为最后一步，函数被state函数包裹起来。

练习
尝试在查看下面的解决方案之前编写绑定方法。

至于绑定，它可以像这样定义

(>>=) :: State s a -> (a -> State s b) -> State s b
p >>= k = q where
    p' = runState p        -- p' :: s -> (a, s)
    k' = runState . k      -- k' :: a -> s -> (b, s)
    q' s0 = (y, s2) where  -- q' :: s -> (b, s)
        (x, s1) = p' s0    -- (x, s1) :: (a, s)
        (y, s2) = k' x s1  -- (y, s2) :: (b, s)
    q = state q'

我们在上面以一种相当冗长的方式编写了定义，以便更容易地找到相关的步骤。一个更简洁的写法是

p >>= k = state $ \ s0 ->
   let (x, s1) = runState p s0  -- Running the first processor on s0.
   in runState (k x) s1         -- Running the second processor on s1.

(>>=)接收一个状态处理器（p）和一个函数（k），该函数用于从第一个处理器的结果创建另一个处理器。这两个处理器被组合成一个函数，该函数接收初始状态（s）并返回第二个结果和第三个状态（即第二个处理器的输出）。总的来说，(>>=)在这里允许我们依次运行两个状态处理器，同时允许第一个阶段的结果影响第二个阶段的行为。

绑定如何从状态处理器（pA）和一个处理器生成函数（f）创建新的状态处理器（pAB）的示意图。s1、s2和s3是状态。v1和v2是值。pA、pB和pAB是状态处理器。State/runState的包裹和解包是隐式的。

实现中有一个细节，即如何使用runState来撤销State的包裹，以便我们可以访问将应用于状态的函数。例如，runState p的类型是s -> (a, s)。

理解绑定运算符

理解绑定运算符>>=的另一种方法是再次考虑使用类型为(a, s) -> (b, s) 的函数来模拟类型为a -> b的状态函数的显式但繁琐的方式，或者换句话说：a -> s -> (b,s) = a -> (s -> (b,s))。这些函数类将状态从一个函数传递到另一个函数。注意，最后一个签名已经暗示了绑定操作中的右手边的类型，其中抽象类型是S b = (s -> (b, s))。

现在我们已经看到了类型如何暗示monadic签名，让我们考虑一个更具体的问题：给定两个函数f :: s -> (a, s)和g :: a -> s -> (b, s)，我们如何将它们链接起来以生成一个传递中间状态的新函数？

这个问题不需要考虑monad：一种选择是简单地使用函数组合。如果我们把它显式地写成一个lambda表达式，这将有助于我们的阐述

compose :: (s -> (a,s)) ->         {- first function -}
           (a -> (s -> (b,s))) ->  {- second function,  note type is similar to  (a,s) -> (b,s) -}
           s -> (b,s)              {- composed function -}
compose f g = \s0 -> let (a1, s1) = f s0 in (g a1) s1 
{-This lambda expression threads both intermediate results produced by f into those required by g -}

现在，如果除了链接输入函数之外，我们还发现签名为s -> (a,s)的函数都被一个抽象数据类型Wrapped a包裹，因此我们需要调用一些其他提供的函数wrap :: (s -> (a,s)) -> Wrapped a，以及unwrap :: Wrapped a -> (s -> (a,s))来获取内部函数，那么代码会略微改变

{- what happens if the type  s -> (a,s) is wrapped and this new type is  called Wrapped a -}
composeWrapped :: Wrapped a -> (a -> Wrapped b) -> Wrapped b
composeWrapped wrappedf g = wrap (\s0 -> let (a1,s1) = (unwrap wrappedf) s0 in (unwrap (g a1)) s1)

{- or, reusing compose -}
composeWrapped wrappedf g = wrap (compose (unwrap wrappedf) (fmap unwrap g))

这段代码是上面展示的(>>=)的实现，其中wrap = state和unwrap = runState，因此我们现在可以看到上面给出的绑定定义是如何为这种特殊类型的状态函数实现标准函数组合的。

本解释尚未涉及最初的函数Wrapped a和a -> Wrapped b最初来自哪里，但它们解释了你一旦拥有它们就可以用它们做什么。

使用State的旋转门

现在我们来看看State类型如何帮助解决旋转门的例子。首先，通过比较coin :: TurnstileState -> (TurnstileOutput, TurnstileState)的类型和newtype State s a = State { runState :: s -> (a, s) }，我们可以看到，通过用TurnstileState替换s，用TurnstileOutput替换a，我们可以定义

coinS, pushS :: State TurnstileState TurnstileOutput
coinS = State coin
pushS = State push

注意

我在这些名称的末尾添加了S，只是为了区分它们与本页上不是基于State单子的那些名称。这不是你通常会做的事情。

然后，我们可以使用runState提取底层函数并将其应用于状态，例如

GHCi> :t runState coinS
runState coinS :: TurnstileState -> (TurnstileOutput, TurnstileState)
GHCi> runState coinS Locked
(Thank,Unlocked)

注意

这里，runState和函数的部分应用之间有一个有趣的比较。

我们通常认为，例如，take :: Int -> [a] -> [a]是一个有两个参数的函数。但我们也看到了（简要地，这里）我们可以只将其应用于一个参数，以获得一个具有一个剩余参数的函数，例如take 2 :: [a] -> [a]。然后我们可以做例如map (take 2) ["every", "good", "boy"]来得到["ev", "go", "bo"]。事实上，Haskell总是逐个地应用参数，这样take 2 "every"首先应用2来得到一个新函数，然后将"every"应用于它。它可以写成(take 2) "every"。

runState被定义为一个接受单个参数的函数。它返回一个接受单个参数的函数，然后我们可以将初始状态值应用于该函数。所以runState coinS Locked意味着(runState coinS) Locked。但是，就像(take 2) "every"一样，括号是不需要的。

就参数的应用而言，take和runState是相似的：它们接受一个参数并返回一个接受另一个参数的函数。它们之间的最大区别在于它们的定义。当定义take时，它声明两个参数并在函数定义中使用它们。然而，runState（隐式地）被定义为单个参数的函数。它返回的函数是单独定义的（由State的用户定义），State的类型要求它是一个参数的函数。这些实现中的每一个都只直接引用它们自己的参数。

使用旋转门State单子

现在还不算太令人兴奋，但现在coinS和pushS是单子的（它们是函数——虽然是零参数的函数——但返回的是Monad实例），我们可以用它们做单子化的事情，包括使用do符号

mondayS :: State TurnstileState [TurnstileOutput]
mondayS = do
  a1 <- coinS
  a2 <- pushS
  a3 <- pushS
  a4 <- coinS
  a5 <- pushS
  return [a1, a2, a3, a4, a5]

GHCi> :t runState mondayS
runState mondayS :: TurnstileState -> ([TurnstileOutput], TurnstileState)
GHCi> runState mondayS Locked
([Thank,Open,Tut,Thank,Open],Locked)

注意，我们不再编写所有代码来将每个步骤的输出状态传递到下一个步骤中：State单子正在为我们做这件事。许多繁琐且容易出错的工作都被消除了。怎么做到的？请记住，do只是(>>=)操作符的语法糖，所以上面的代码等价于

mondayS =
  coinS >>= (\ a1 ->
    pushS >>= (\ a2 ->
      pushS >>= (\ a3 ->
        coinS >>= (\ a4 ->
          pushS >>= (\ a5 ->
            return [a1, a2, a3, a4, a5] )))))

这使用了我们上面为State定义的(>>=)操作符，从它的State包装器中解开每个状态处理函数，将来自它的输出状态作为参数应用到下一步，并将结果包装回State包装器中。(>>=)操作符的序列，以及return，将所有步骤组合成一个单一的组合状态处理函数，并将其包装在State包装器中，我们可以使用runState访问和运行它。

单子有时被描述为在上下文中提供一个值。一个IO单子可以在我们要求它时从现实世界中提供值。一个Maybe单子可以在存在的情况下提供值，否则就不提供。State单子呢？它可以在我们执行状态处理程序的一步时提供一个值。（而且单子“自动”确保状态更改从一步传递到另一步，而无需我们担心它）。

在这个例子中，仍然有一些繁琐的工作要做，即从每一步获取输出列表并将其组合成一个列表。我们可以做得更好吗？当然可以

mondayS :: State TurnstileState [TurnstileOutput]
mondayS = sequence [coinS, pushS, pushS, coinS, pushS]

我们在关于IO 单子的部分中遇到了sequence。它创建一个单一的动作（在本例中是一个状态处理函数），它在执行时依次运行每个动作（在本例中是状态处理步骤），执行它们并将结果组合成一个列表。

练习
使用sequence实现函数regularPersonS, distractedPersonS, hastyPersonS :: State TurnstileState [TurnstileOutput]。你仍然需要使用do符号来实现第三个函数。[2] 实现luckyPairS :: Bool -> State TurnstileState Bool

evalState和execState

我们已经看到了runState如何访问状态处理函数，以便我们可以执行例如runState mondayS Locked。（我们还在(>>=)的定义中使用了它）。

其他以类似方式使用的函数是evalState和execState。给定一个State a b和一个初始状态，函数evalState将只返回状态处理的结果值，而execState将只返回新的状态。

evalState :: State s a -> s -> a
evalState p s = fst (runState p s)

execState :: State s a -> s -> s
execState p s = snd (runState p s)

好吧，它们没什么特别的。但它们也不是一无是处，它们允许我们执行例如

GHCi> evalState mondayS Locked
[Thank,Open,Tut,Thank,Open]

如果我们只想看到输出序列，而不关心最终状态。

设置状态

如果我们有一个旋转门的工程师，他想用这样的代码测试锁定机制呢

testTurnstile :: State TurnstileState Bool
testTurnstile = do
  --somehow set state to Locked
  check1 <- pushS
  --somehow set state to Unlocked
  check2 <- pushS
  --somehow set state to Locked again
  return (check1 == Tut && check2 == Open)

这个方便的函数可以帮助我们

put :: s -> State s ()
put newState = state $ \_ -> ((), newState)

put是一个单子函数，可以与(>>=)操作符绑定，或者与其他操作一起按顺序放在do结构中。它接受一个状态参数（我们要引入的那个状态），并生成一个状态处理程序，该程序忽略它接收的任何状态，并将我们引入的新状态作为下一个状态返回。由于我们不关心该处理程序的结果（我们只想替换状态），因此元组的第一个元素将是()，即通用占位符值。^[3]

让我们看看它如何帮助工程师

testTurnstile :: State TurnstileState Bool
testTurnstile = do
  put Locked
  check1 <- pushS
  put Unlocked
  check2 <- pushS
  put Locked
  return (check1 == Tut && check2 == Open)

GHCi> runState testTurnstile Locked
(True,Locked)
HHCi> runState testTurnstile Unlocked
(True,Locked)

访问状态

在上面的pushS的定义中，我们使用了现有的代码push。如果我们想在没有这种预先存在的函数的情况下编写它呢？显然我们可以这样做

pushS = state $ \s -> case s of
  Locked   -> (Tut , Locked)
  Unlocked -> (Open, Locked)

但是我们可以用do结构写出来吗？可以，使用这个

get :: State s s
get = state $ \s -> (s, s)

get也是单子函数，它创建一个状态处理程序，该程序将它接收到的状态s作为结果和下一个状态返回。这意味着状态将保持不变，并且将创建它的副本供我们使用。

我们可以这样使用get

pushS = do
  s <- get
  put Locked
  case s of
    Locked   -> return Tut
    Unlocked -> return Open

练习
使用do结构和get或put重写coinS。 扩展testTurnstile，使其在插入硬币后也检查状态是否设置为Unlocked，无论之前的状态如何。为了保险起见，让testTurnstile在测试完成后将旋转门恢复到原始状态。 除了put和get之外，还有 modify :: (s -> s) -> State s () 它使用一个函数修改当前状态，以及 gets :: (s -> a) -> State s a 它生成状态的修改副本，同时保持状态本身不变。为它们编写实现。

单子控制结构

上面的mondayS的第二个版本展示了使用单子的另一个好处，除了隐藏状态线程和使用do符号以及类似功能的能力之外：我们还能够使用sequence等很棒的函数。（你需要import Control.Monad，或者执行GHCi> :m Control.Monad以确保所有这些都在作用域内）。

首先，这里有replicateM

GHCi> evalState (replicateM 6 pushS) Unlocked
[Open,Tut,Tut,Tut,Tut,Tut]

这非常直白。

在我们查看更多内容之前，我们需要一个稍微不同（可以说是更好的）的旋转门有限状态机的实现，使用一个输入类型和一个单一的处理函数

data TurnstileInput = Coin | Push
  deriving (Eq, Show)
  
turnS :: TurnstileInput -> State TurnstileState TurnstileOutput
turnS = state . turn where
  turn Coin _        = (Thank, Unlocked)
  turn Push Unlocked = (Open,  Locked)
  turn Push Locked   = (Tut,   Locked)

GHCi> runState (turnS Coin) Locked
(Thank,Unlocked)

现在我们可以使用mapM，像这样

GHCi> evalState (mapM turnS [Coin, Push, Push, Coin, Push]) Locked
[Thank,Open,Tut,Thank,Open]

这很好地说明了有限状态机是如何转换器的：它将有序的输入序列转换为有序的输出序列，并在转换过程中保持状态。

现在我们来看filterM

getsThroughS :: TurnstileInput -> State TurnstileState Bool
getsThroughS input = do
  output <- turnS input
  return $ output == Open

GHCi> evalState (filterM getsThroughS [Push, Coin, Coin, Push, Push, Coin, Push]) Locked
[Push,Push]

我们可以看到两个人通过了（不出所料，当他们推了手臂时）。如果我们交换前两个输入的顺序，更多人会通过

GHCi> evalState (filterM getsThroughS [Coin, Push, Coin, Push, Push, Coin, Push]) Locked
[Push,Push,Push]

这里有一个不同的方法来使用foldM计算开启次数

countOpens :: [TurnstileInput] -> State TurnstileState Int
countOpens = foldM incIfOpens 0 where
  incIfOpens :: Int -> TurnstileInput -> State TurnstileState Int
  incIfOpens n i = do
    g <- getsThroughS i
    if g then return (n+1) else return n

GHCi> evalState (countOpens [Coin, Push, Coin, Push, Push, Coin, Push]) Locked
3

注意sequence、mapM和filterM总是执行输入列表中的所有动作，但foldM可能会跳过一些动作。

练习

修改regularPersonS、distractedPersonS和hastyPersonS以使用turnS和mapM。 使用sequence或mapM实现tuesdayS。 实现saveCoinsS :: [TurnstileInput] -> State TurnstileState Int，它可能处理所有给定的输入，但如果上一个输入产生了Thanks，则会跳过Coin输入。它返回被跳过的Coin输入的数量。例如evalState (saveCoinsS [Push, Coin, Coin, Coin, Push, Push, Coin, Push]) Locked应该返回2。 实现 sequenceUntil :: (a -> Bool) -> [State s a] -> State s [a]。它处理每个输入，直到其中一个生成的值与谓词匹配，然后不再处理。例如，evalState (sequenceUntil (== Open) [coinS, coinS, coinS, pushS, pushS, coinS]) Locked 应该给出 [Thank,Thank,Thank,Open]。 修改 sequenceUntil 使其适用于任何 Monad 实例。

伪随机数

假设我们在编写一个游戏，在游戏的某些阶段需要随机元素。在现实世界游戏中，这通常是通过骰子或类似方式获得的。对于计算机程序，我们需要一些东西来模拟这样的对象，大多数编程语言都提供了一些“随机数”的概念，可以用于此目的。

生成真正的随机数 很困难。计算机程序几乎总是使用伪随机数 代替。它们是“伪”的，因为它们实际上不是随机的，并且它们是预先知道的。实际上，它们是由算法（伪随机数生成器）生成的，这些算法接受初始状态（通常称为种子）并从中生成一系列看起来是随机的数字。每次请求伪随机数时，都需要更新某个地方的状态，以便生成器可以准备好下次产生新的、不同的随机数。如果知道初始种子和生成算法，则可以完全复制伪随机数序列。

Haskell 全局伪随机数生成器

在大多数编程语言中生成伪随机数非常简单：库中存在某个函数提供伪随机值（并且还更新内部可变状态，以便下次生成不同的值，尽管一些实现可能产生真正的随机值）。Haskell 在 random 包的 System.Random 模块中也有类似的函数

GHCi> :m System.Random
GHCi> :t randomIO
randomIO :: Random a => IO a

什么是 Random？它是可以由 System.Random 模块函数生成伪随机值的类型类。Int、Integer、Bool 等都是 Random 的实例。你可以通过指定结果类型来“请求”其中任何一个

GHCi> randomIO :: IO Int
-1557093684
GHCi> randomIO :: IO Int
1342278538
GHCi> randomIO :: IO Bool
True

更有趣的是，randomIO 是一个 IO 动作。它不可能是其他东西，因为它使用可变状态，而可变状态是我们 Haskell 程序无法触及的。由于这种隐藏的依赖关系，它返回的伪随机值每次都可能不同。

但是，我们在这里学习 State 单子，所以让我们看一下接受并返回随机数生成器状态的显式表示的函数。

带有显式状态的 Haskell 伪随机数生成器

以下是 System.Random 模块中一个稍微不同的函数

GHCi> :t random
random :: (Random a, RandomGen g) => g -> (a, g)

现在没有 IO，我们应该将 g -> (a, g) 模式识别为我们可以放在 State 包装器中的东西。

什么是 RandomGen？它是 System.Random 模块中定义的另一个类。该模块还提供了一个单一实例 StdGen。有几种方法可以创建此类型的值。我们将首先使用的是 mkStdGen :: Int -> StdGen，它从给定的种子创建一个 StdGen 值

GHCi> mkStdGen 666
667 1
GHCi> mkStdGen 666
667 1

请注意，给定相同的种子，你将获得相同的 StdGen。什么是 StdGen？文档称其为“标准伪随机数生成器”，但也许最好将其称为标准伪随机数生成器的状态。我们可以在这里看到

GHCi> let s = mkStdGen 666
GHCi> s
667 1
GHCi> random s :: (Int, StdGen)
(6438947685955577547,392509921 2103410263)

第一个函数（mkStdGen 666）根据给定的 666 种子返回初始状态。第二个函数（random s）接受初始 StdGen 状态并返回一对：一个随机值（我们请求了一个 Int）和一个新的 StdGen 状态。状态如何在内部表示？System.Random 模块以某种方式执行此操作，我们并不关心它是如何执行的。（我们可以看到 StdGen 实现 show，它显示两个有趣的数字。如果我们真的想看看它是如何工作的，我们可以去看源代码，但总有一天，某个聪明人可能会改变它）。random 如何计算新状态？我们也不关心；我们只需要高兴它确实可以做到。

示例：掷骰子

randomR (1,6)

我们将构建一个掷骰子示例。为此，我们将使用一个稍微不同的函数

GHCi> let s = mkStdGen 666
GHCi> randomR (1,6) s
(6,26689338 40692)

randomR 接受一个范围（在本例中为 1 到 6），并返回该范围内的伪随机数（我们很幸运：我们得到了 6！）。

假设我们想要一个掷两个骰子并返回表示每次掷骰结果的一对的函数。这是一种方法

import System.Random --put this towards the top of the file

rollPair :: StdGen -> ((Int, Int), StdGen)
rollPair s0 =
  let (r1, s1) = randomR (1,6) s0
      (r2, s2) = randomR (1,6) s1
  in ((r1, r2), s2)

GHCi> rollPair (mkStdGen 666)
((6,1),647839921 1655838864)

这是否让我们想起我们在 旋转门示例 中第一次尝试的冗长且容易出错的方法？不确定它是否冗长？尝试第一道练习

练习
使用 randomR (1,6) 实现 rollSix :: StdGen -> ([Int], StdGen)，它返回一个列表，表示六次连续掷骰的结果。 实现 rollN :: Int -> StdGen -> ([Int], StdGen)。这有点棘手！但可以使用 iterate 和 take，例如。 我们即将定义 rollDieS :: State StdGen Int。为什么你不先尝试一下，并思考它是什么以及它如何提供帮助。

使用 State 掷骰子

所以，使用 State 的一种更好的方法

rollDieS :: State StdGen Int
rollDieS = state $ randomR (1,6)

GHCi> runState rollDieS (mkStdGen 666)
(6,26689338 40692)

这与 coinS 和 pushS 的原始版本非常相似：已经有一个形式为 s -> (a, s) 的函数，我们只是将其包装在 State 包装器中。现在我们拥有了单子力量！我们可以编写

rollPairS :: State StdGen (Int, Int)
rollPairS = do
  r1 <- rollDieS
  r2 <- rollDieS
  return (r1, r2)

GHCi> runState rollPairS (mkStdGen 666)
((6,1),647839921 1655838864)

并且我们避免了将状态从一个步骤传递到下一个步骤的所有繁琐工作。

练习
使用 do 符号和 rollDieS 实现与 rollSix 行为相同的 rollSixS :: State StdGen [Int]。 使用 replicateM 实现 rollNS :: Int -> State StdGen [Int] 实现 luckyDoubleS :: State StdGen Int。它进行第一次掷骰。如果它是 6，它会再次掷骰并返回两次掷骰的总和，否则它只会返回第一次掷骰的结果。

State 也是一个 Functor 和 Applicative

以下是另一个掷骰函数

rollDieDoubledS :: State StdGen Int
rollDieDoubledS = do
  r <- rollDieS
  return (r * 2)

它的行为应该很清楚。但这对于这样一个简单的函数来说似乎有点冗长。我们能做得更好吗？

正如我们在 之前提到的（并在 上面 看到的那样），State（以及所有其他单子）也是 Functor 和 Applicative 的实例。在 序言中，我们做了

    ...
    let mx = readMaybe s :: Maybe Double
    case fmap (2*) mx of
    ...

这利用了 Maybe 是一个 Functor 的事实。fmap (2*) mx 将 Just x 转换为 Just (2*x)（或 Nothing 转换为 Nothing）。如果我们将 x 视为包装在上下文中的值，我们可以看到 fmap 保留了相同的上下文（它仍然是 Just，或者仍然是 Nothing），但对包装的值应用了转换。我们可以对 State 函子做同样的事情

rollDieDoubledS = fmap (*2) rollDieS

State 的含义不同于 Maybe 的含义（它是状态处理步骤的输出，而不是可能存在的值），但我们对包装的值应用了相同的转换。现在，当我们从 rollDieDoubledS 中解开值时，我们将获得两倍于从 rollDieS 中解开值时获得的值。

假设我们还想 rollTwoSummedS :: State StdGen Int？在序言部分中做了 sz <- (++) <$> getLine <*> getLine，我们也可以做类似的事情

rollTwoSummedS :: State StdGen Int
rollTwoSummedS = (+) <$> rollDieS <*> rollDieS

这段代码依赖于State 也是一个 Applicative，但并不依赖于它是一个 Monad。它将确保每个 rollDieS 操作按顺序执行，并在它们之间正确地链接状态。然后它将组合作为状态处理函数包装在 State 包装器中。组合函数将返回两次连续投掷的总和（并且，虽然不明显，但确保状态被添加为输入参数和输出值）。

Control.Applicative 模块提供了一个名为 liftA2 的函数

liftA2 f u v = f <$> u <*> v

使用它，可以将 rollTwoSummedS 定义为

import Control.Applicative --this needs to be at the top of your file

rollTwoSummedS = liftA2 (+) rollDieS rollDieS

练习

使用 (<$>) 和 (<*>) 或 liftA2 重写 rollPairS。 实现 happyDoubleS :: State StdGen Int，它投掷两个骰子并返回第一个和第二个的总和，但如果第一个是六，则将总数加倍。使用 do 语法进行编码。 使用 (<$>) 和 (<*>) 或 liftA2 重写 happyDoubleS。 你能只使用 (<$>) 和 (<*>)（或 liftA2）重新编码 luckyDoubleS 吗？为什么不能？你能使用 (<$>)（或 fmap）让它更短一点吗？ 使用 fmap 和/或 (<$>) 修改 Monadic 控制结构 练习中的 tuesdayS、saveCoinS 和 sequenceUntil。 在 上一节 中，我们通过延迟 Monad 实例来定义 Functor 和 Applicative 的 State 实例。现在尝试根据它们的行为明确地编写它们，而不使用 Monad 实例。

关于 Functor、Applicative 和 Monad 之间的关系 以及如何选择使用哪一个，将在后面详细介绍。

不同类型的伪随机值

我们看到 randomIO :: Random a => IO a 可以返回一个与 Int 不同的类型的值。它的无 IO 等效项 random :: (Random a, RandomGen g) => g -> (a, g) 也可以。

由于 State StdGen 对它产生的伪随机值的类型是“不可知的”，因此我们可以编写一个类似的“不可知”函数，它提供一个未指定类型的伪随机值（只要它是 Random 的实例）。

getRandomS :: Random a => State StdGen a
getRandomS = state random

与 rollDieS 相比，此函数在其签名中未指定 Int 类型，并使用 random 而不是 randomR；否则，它完全相同。getRandomS 可用于 Random 的任何实例

GHCi> evalState getRandomS (mkStdGen 0) :: Bool
True
GHCi> evalState getRandomS (mkStdGen 0) :: Char
'\64685'
GHCi> evalState getRandomS (mkStdGen 0) :: Double
0.9872770354820595
GHCi> evalState getRandomS (mkStdGen 0) :: Integer
2092838931

实际上，一次性创建所有这些变得非常容易

someTypes :: State StdGen (Int, Float, Char)
someTypes = liftA3 (,,) getRandomS getRandomS getRandomS

allTypes :: State StdGen (Int, Float, Char, Integer, Double, Bool, Int)
allTypes = (,,,,,,) <$> getRandomS
                    <*> getRandomS
                    <*> getRandomS
                    <*> getRandomS
                    <*> getRandomS
                    <*> getRandomS
                    <*> getRandomS

要编写 allTypes，没有 liftA7， 因此我们使用普通的 (<*>) 代替。使用它，我们可以将元组构造函数应用于 State StdGen 单子上下文中七个随机值中的每一个。

allTypes 为 Random 的所有默认实例提供伪随机值；最后插入一个额外的 Int 以证明生成器并不相同，因为两个 Int 将不同。

GHCi> evalState allTypes (mkStdGen 0)
GHCi>(2092838931,9.953678e-4,'\825586',-868192881,0.4188001483955421,False,316817438)

(可能) 不要 put 或 get

在 旋转门示例 中，我们使用 put 来 设置状态，并使用 get 来 访问它。我们可以在此处执行相同的操作吗？当然可以，但可能没有必要。

在该示例中，我们必须编写函数（例如 pushS），这些函数使用当前状态来确定输出和新状态，或者（例如 testTurnstile）将所需状态设置为处理序列的一部分。在我们的随机数示例中，StdGen 状态的所有生成、检查和更新都在 System.Random 模块中内部完成，而我们无需知道如何操作。

现在，在我们的 第一个 rollPair 实现 中，我们了解了 StdGen 状态：我们将其作为参数，将其贯穿各个步骤，然后返回最终状态。如果我们确实想使用该值（也许我们想使用 trace 将其放入调试消息中），那么我们确实有这个机会。并且，使用我们的 State 单子，我们仍然可以。以下显示了一种用法

rollDieS :: State StdGen Int
rollDieS = do s0 <- get
              let (value, s1) = randomR (1,6) s0
              put s1
              return value

这确实详细说明了 State 单子为我们采取的所有步骤，但这将是一个相当奇怪的实现，因为单子的全部意义是让我们不必详细说明这些步骤。

练习
编写 randomElt :: [a] -> State StdGen a，使用 put 和 get 访问 StdGen 状态。它可以假设列表非空，并且应该返回其中一个随机元素。 在不使用 put 或 get 的情况下重写 randomElt。

更好的随机数

除了我们最初使用 randomIO 之外，上面所有示例都使用 mkStdGen，并且都使用相同的种子值 666。这会让游戏变得非常无聊，每次掷出的骰子完全相同。（尽管这可能有用，例如，在测试程序时。）我们如何获得更好的随机数？像这样

getRandomPair :: IO (Int, Int)
getRandomPair = do
  s <- newStdGen
  return $ evalState rollPairS s

newStdGen（实际上）被定义为 newStdGen :: IO StdGen。它是一个 IO 操作，它从 randomIO 使用的相同全局随机状态中生成一个新的随机状态。它还会更新该全局状态，因此 newStdGen 的进一步使用会给出不同的值。

那么，我们不是又回到了起点，又依赖于 IO 了吗？不，我们没有。我们获得了 State 单子全部的功能，可以构建骰子滚动步骤的链，我们可以将这些步骤组合成越来越大的状态转换函数。我们可以在没有 IO 的情况下执行所有操作。在旋转门示例中，我们根本不需要 IO（尽管如果我们想将代码放入某种应用程序中，我们可能会需要它），并且对于随机数的某些用途，每次使用相同的数字可能是有益的。我们只需要 IO 来获得“真正随机”的数字，并且我们可能只需要在程序中使用 newStdGen 一次。很可能它会与其他 IO 操作一起使用，例如

main :: IO ()
main = do
  s <- newStdGen
  let (r1, r2) = evalState rollPairS s
  putStrLn $ "You rolled twice and got " ++ show r1 ++ " and " ++ show r2 ++ "."

处理组合状态

假设我们想创建一个随机的旋转门，每个访客都会收到一个随机的旋转门输入：他们要么插入一枚硬币（但不允许通过）；要么他们可以推动手臂（如果它打开，就可以通过，否则会被送走）。

这是一段有用的代码

randomInputS :: State StdGen TurnstileInput
randomInputS = do
  b <- getRandomS
  return $ if b then Coin else Push

这允许我们生成随机的 turnstileInput 值。但是，我们的随机旋转门机器需要跟踪随机数生成器的状态和旋转门的状态。我们想编写一个像这样的函数

randomTurnS :: State (StdGen, TurnstileState) TurnstileOutput

此函数需要调用 randomInputS（它在 State StdGen 单子中）和 turnS（它在 State TurnstileState 单子中）。

练习
使用 get 和 put 访问和设置组合状态，并使用 runState 调用 randomInputS 和 turnS 来实现 randomTurnS。

randomTurnS 中的大部分代码都用于管理状态：访问组合状态、解包子组件、将它们转发到各个 State 单子、重新组合它们并将组合状态放回。在这种情况下，状态管理代码还不错，但在更复杂的函数中很容易变得很麻烦。而且这是我们希望 State 单子为我们隐藏的东西。

状态处理子组件

理想情况下，我们希望有一些实用程序函数（s），这些函数允许我们在 State (StdGen, TurnstileState) 单子函数中调用 State StdGen 单子函数（或 State TurnstileState 单子函数）。这些函数（s）应该为我们处理状态管理，确保更新组合状态的正确子组件。

这是一个适用于任何以对表示的组合状态的函数，它对对的 fst 执行状态更新

processingFst :: State a o -> State (a,b) o
processingFst m = do
  (s1,s2) <- get
  let (o,s1') = runState m s1
  put (s1',s2)
  return o

注意类型

GHCi> :t processingFst randomInputS
processingFst randomInputS :: State (StdGen, b) TurnstileInput

processingFst 将 State 单子（在本例中，状态类型为 StdGen）“转换”为另一个 State 单子（在本例中，状态类型为 (StdGen, b)，其中 b 可以是任何类型，即使是 TurstileState）。

练习
实现 processingSnd。 修改 randomTurnS 以使用 processingFst 和 processingSnd。

注意 randomTurnS 如何不再直接参与状态管理的细节，并且它的业务逻辑更加明显。

通用子组件处理

我们可以看到 processingFst 和 processingSnd 非常相似。它们都提取组合状态的子组件，在该子组件上运行 runState，然后使用子组件的新值更新组合状态。

让我们将它们组合成一个单一的泛型子组件处理函数。为此，我们可以传入单独的参数，一个类型为 (cmb -> sub)（从组合状态值中提取子组件的函数），另一个类型为 (cmb -> sub -> cmb)（一个函数，给定一个组合值和一个子组件的新值，返回具有更新子组件的修订组合值）。但是，将这两个函数一起打包成一个类型更简洁，我们将称之为 Lens

data Lens cmb sub = Lens
  { view :: cmb -> sub,
    set  :: cmb -> sub -> cmb
  }

我们可以提供指向一对中 fst 和 snd 元素的特定透镜

fstL :: Lens (a,b) a
fstL = Lens fst (\(_,y) x -> (x,y))

sndL :: Lens (a,b) b
sndL = Lens snd (\(x,_) y -> (x,y))

所以现在

GHCi> view fstL ("fred", 5)
"fred"
GHCi> set fstL ("fred", 5) "sue"
("sue",5)

注意

更复杂、更强大的透镜在后面描述，但它们也更难理解工作原理。我们简单的透镜目前足够了，但你可能想以后更新随机检票口代码以使用“正确的透镜”。

我们现在可以使用我们的通用函数替换 processingFst 和 processingSnd。

练习
实现 processing，它接受一个 Lens cmb sub 参数，并将 State sub “转换”为 State cmb。 使用 processing 函数（以及 fstL 和 sndL）重写 randomTurnS。

我们最终的随机检票口代码更简洁，三个独立的逻辑函数被隔离

• 状态管理（现在在一个单独的 processing 实用函数中，可以在其他地方重用）；
• 子组件访问和更新（使用 Lens，也可以在其他地方重用）；和
• 检票口的“业务逻辑”，现在非常明显。

在我们第一个实现中，所有这三个都混在一起。

让我们试一试

GHCi> g <- newStdGen
GHCi> evalState (replicateM 10 randomTurnS) (g, Locked)
[Thank,Open,Tut,Thank,Thank,Open,Tut,Tut,Tut,Thank]

不过我不确定我们能卖出多少。