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]

不過我不確定我們能賣出多少。