Ch14 Monads.tex

\documentclass[./main.tex]{subfiles}

\begin{document}

\subsection*{简介}

在第七章 I/O 中，我们讨论了\acode{IO}单子，然而当时只局限于如何它与外界进行交互，并没有讨论什么是单子。

...

\subsection*{重构早期代码}

\subsubsection*{Maybe 链}

回忆一下第十章的\acode{PNM.hs}代码中的\acode{parseP5}函数：

\begin{lstlisting}[language=Haskell]
  -- header
  matchHeader :: L.ByteString -> L.ByteString -> Maybe L.ByteString
  matchHeader prefix str
    | prefix `L8.isPrefixOf` str = Just (L8.dropWhile isSpace (L.drop (L.length prefix) str))
    | otherwise = Nothing

  -- nat = natural number
  getNat :: L.ByteString -> Maybe (Int, L.ByteString)
  getNat s = case L8.readInt s of
    Nothing -> Nothing
    Just (num, rest)
      | num <= 0 -> Nothing
      | otherwise -> Just (fromIntegral num, rest)

  getBytes :: Int -> L.ByteString -> Maybe (L.ByteString, L.ByteString)
  getBytes n str =
    let count = fromIntegral n
        both@(prefix, _) = L.splitAt count str
     in if L.length prefix < count
          then Nothing
          else Just both

  -- parse function
  parseP5 :: L.ByteString -> Maybe (Greymap, L.ByteString)
  parseP5 s =
    case matchHeader (L8.pack "PS") s of
      Nothing -> Nothing
      Just s1 ->
        case getNat s1 of
          Nothing -> Nothing
          Just (width, s2) ->
            case getNat (L8.dropWhile isSpace s2) of
              Nothing -> Nothing
              Just (height, s3) ->
                case getNat (L8.dropWhile isSpace s3) of
                  Nothing -> Nothing
                  Just (maxGrey, s4)
                    | maxGrey > 255 -> Nothing
                    | otherwise ->
                        case getBytes 1 s4 of
                          Nothing -> Nothing
                          Just (_, s5) ->
                            case getBytes (width * height) s5 of
                              Nothing -> Nothing
                              Just (bitmap, s6) ->
                                Just (Greymap width height maxGrey bitmap, s6)
\end{lstlisting}

接着又使用了\acode{(>>?)}函数来减少模式匹配：

\begin{lstlisting}[language=Haskell]
  (>>?) :: Maybe a -> (a -> Maybe b) -> Maybe b
  Nothing >>? _ = Nothing
  Just v >>? f = f v
\end{lstlisting}

...

\subsubsection*{隐式状态}

简化后的代码如下：

\begin{lstlisting}[language=Haskell]
  parseP5_take2 :: L.ByteString -> Maybe (Greymap, L.ByteString)
  parseP5_take2 s =
    matchHeader (L8.pack "P5") s
      >>? \s ->
        skipSpace ((), s)
          >>? (getNat . snd)
          >>? skipSpace
          >>? \(width, s) ->
            getNat s
              >>? skipSpace
              >>? \(height, s) ->
                getNat s
                  >>? \(maxGrey, s) ->
                    getBytes 1 s
                      >>? (getBytes (width * height) . snd)
                      >>? \(bitmap, s) -> Just (Greymap width height maxGrey bitmap, s)
\end{lstlisting}

我们仍然遇到了重复的行为模式：消费一些字符串，返回一个结果，接着将剩下的字符串传入下一个函数进行消费。然而这套模式有隐藏的风险：如果希望将其余部分的信息在链中传递，
那么就需要将链中的每个元素都进行修改，将每个二元元组改为三元元组！

我们解决这个问题的方法是将管理当前字符串的责任从链中的单个函数移动到将函数进行串联的函数中：

\begin{lstlisting}[language=Haskell]
  (==>) :: Parse a -> (a -> Parse b) -> Parse b
  firstParser ==> secondParser = Parse chainedParser
    where
      chainedParser initState =
        case runParse firstParser initState of
          Left errMessage ->
            Left errMessage
          Right (firstResult, newState) ->
            runParse (secondParser firstResult) newState
\end{lstlisting}

我们同样将解析状态的细节隐藏进\acode{ParseState}类型中。即使\acode{getState}与\acode{putState}函数都不会检查解析状态，因此对\acode{ParseState}的任何修改
都不会影响现有的代码。

\subsection*{寻找共有模式}

...

\subsection*{单子 typeclass}

我们可以在 Haskell 的 typeclass 中捕获链接和注入的概念，同时又希望它们具有类型。标准的 Prelude 已经定义了这样的一个 typeclass，即\acode{Monad}。

\begin{lstlisting}[language=Haskell]
  class Monad m where
    -- chain
    (>>=)  :: m a -> (a -> m b) -> m b
    -- inject
    return :: a -> m a
\end{lstlisting}

注：新的 Haskell 版本中 Monad 还需要先实现\acode{Applicative}实例，而\acode{Applicative}又需要先实现\acode{Functor}实例。

这里的\acode{>>=}是链接函数，而\acode{return}则是注入函数。

...

\subsection*{行话时间}

\begin{itemize}
  \item "Monadic" 即为“与单子有关”。一个 monadic \textit{类型}就是\acode{Monad} typeclass 的一个实例；一个 monadic \textit{值}拥有一个 monadic 类型。
  \item 当我们说一个类型“是一个单子”，这实际上在简述它是\acode{Monad} typeclass 的一个实例。作为\acode{Monad}的一个实例则拥有必要的 monadic 的类型构造函数，
        注入函数，以及链接函数。
  \item 同样的，引用“\acode{Foo}单子”意味着正在谈论名为\acode{Foo}的类型，且它是\acode{Monad}的一个实例。
  \item “动作 action”则是一个 monadic 值的别称。这个词的这种用法可能起源于用于 I/O 单子的引入，其中像\acode{print "foo"}这样的单子值可能具有可观察到的副作用。
        具有 monadic 返回类型的函数也可以称为操作，尽管这种情况不太常见。
\end{itemize}

\subsection*{使用一个新的单子：展示你的成果！}

在介绍单子时，我们展示了一些已经具备 monadic 形态的预定义代码。现在让我们定义其接口。

纯 Haskell 代码编写很简单，但是它不能执行 I/O。有时我们希望在记录一些决策时，不必将 log 信息写入文件中。现在来开发一个这样的库。

回忆在之前将 glob 模式转为正则表达式的小节中所开发的\acode{globToRegex}函数。我们将修改它，使其保存它所翻译的每个特殊模式序列的记录。

作为开始，首先将返回类型通过\acode{Logger}类型构造函数进行包装。

\begin{lstlisting}[language=Haskell]
  globToRegex :: String -> Logger String
\end{lstlisting}

\subsubsection*{隐藏信息}

\begin{lstlisting}[language=Haskell]
  module Logger
    ( Logger,
      Log,
      runLogger,
      record,
    )
  where
\end{lstlisting}

像这样隐藏细节有两个好处：它为我们实现单子提供了相当大的灵活性，更重要的是，它为用户提供了一个简单的界面。

我们的\acode{Logger}类型存粹是一个\textit{类型}构造函数。没有导出用户创建这种类型的值所需的值构造函数，用户仅仅可以使用 \acode{Logger} 来编写类型签名。

\acode{Log} 类型即字符串列表的同义词，将若干签名变得更有可读性。使用列表字符串是为了实现起来更加的方便。

\begin{lstlisting}[language=Haskell]
  type Log = [String]
\end{lstlisting}

相较于提供用户一个值构造函数，更好的是提供一个\acode{runLogger}函数，用于记录操作。它将同时返回操作的结果，以及计算时的日志。

\begin{lstlisting}[language=Haskell]
  runLogger :: Logger a -> (a, Log)
\end{lstlisting}

\subsubsection*{控制退出}

\acode{Monad} typeclass 不提供任何方法让值脱离它们的 monadic 束缚。可以使用\acode{return}将值注入进一个单子中，可以使用\acode{(>>=)}将值从单子中提取出来，
而位于其右侧的函数将会得到解包的值，该函数再将其结果重新进行包装。

多数单子拥有一个或多个类似\acode{runLogger}的函数。最典型的就是\acode{IO}，通常只会在退出程序时才退出。

一个单子执行函数会将代码运行在单子内部并展开其结果。这样的函数通常是提供给值从其一元包装器中转义的唯一方法。因此单子的作者可以完全控制单子内发生的任何事物。

\subsubsection*{留痕}

当在一个\acode{Logger}中操作时，用户代码调用\acode{record}来记录事物。

\begin{lstlisting}[language=Haskell]
  record :: String -> Logger ()
\end{lstlisting}

由于记录发生在单子的管道中，所以操作的结果不提供任何信息。

通常来说，一个单子会提供一个或多个像\acode{record}一样的帮助函数。它们是访问该单子的特殊行为的方法。

模块中也为\acode{Logger}类型提供了\acode{Monad}实例。它们是客户端模块为了能使用这个单子所需的全部定义。

\subsubsection*{使用 Logger 单子}

下面是将 glob-to-regexp 在\acode{Logger}单子中转换的方法：

\begin{lstlisting}[language=Haskell]
  globToRegex :: String -> Logger String
  globToRegex cs =
    globToRegex' cs >>= \ds -> return $ '^' : ds
\end{lstlisting}

注意\acode{(>>=)}的类型：它从左侧的\acode{Logger}包裹中中提取值，然后将解包的值传递给右侧的函数。在其右侧的函数则需要使用\acode{Logger}包装其结果。这也正是
\acode{return}所做的：获取一个纯值，包裹该值进入一个单子类型的构造函数中。

\begin{lstlisting}[language=Haskell]
  ghci> :type (>>=)
  (>>=) :: (Monad m) => m a -> (a -> m b) -> m b
  ghci> :type (globToRegex "" >>=)
  (globToRegex "" >>=) :: (String -> Logger b) -> Logger b
\end{lstlisting}

即使编写一个不做任何事情的函数也要调用\acode{return}将结果包装成正确的类型。

\begin{lstlisting}[language=Haskell]
  globToRegex' :: String -> Logger String
  globToRegex' "" = return "$"
\end{lstlisting}

当调用\acode{record}来存储一个日志，需要用\acode{(>>)}而不是\acode{(>>=)}来进行串联。

\begin{lstlisting}[language=Haskell]
  globToRegex' ('?' : cs) =
  record "any"
    >> globToRegex' cs
    >>= \ds -> return ('.' : ds)
\end{lstlisting}

记住它是\acode{(>>=)}的一种变体，它会忽略左侧的结果。我们知道\acode{record}的结果总是\acode{()}，因此无需捕获该结果。

我们可以使用\acode{do}符号来整洁一下代码：

\begin{lstlisting}[language=Haskell]
  globToRegex'' ('*' : cs) = do
    record "kleene star"
    ds <- globToRegex'' cs
    return $ ".*" ++ ds
\end{lstlisting}

解析字符类主要遵循以上这种模式：

\begin{lstlisting}[language=Haskell]
  globToRegex' ('[' : '!' : c : cs) =
    record "character class, negative"
      >> charClass cs
      >>= \ds -> return $ "[^" ++ c : ds
  globToRegex' ('[' : c : cs) =
    record "character class"
      >> charClass cs
      >>= \ds -> return $ "[" ++ c : ds
  globToRegex' ('[' : _) =
    fail "unterminated character class"
\end{lstlisting}

\subsection*{混合纯代码与单子代码}

根据目前所见到的代码，单子看起来有一个很大的缺点：使用普通的纯函数处理被包装后的值时，会变得很棘手。以下是这个浅显问题的一个简单说明。假设有一个简单的代码运行在
\acode{Logger}单子中并返回一个字符串。

\begin{lstlisting}[language=Haskell]
  ghci> let m = return "foo" :: Logger String
\end{lstlisting}

如果希望得知该字符串的长度，我们无法直接调用\acode{length}：因为字符串被封装了，类型并不匹配。

迄今为止我们所能做的就是类似这样：

\begin{lstlisting}[language=Haskell]
  ghci> :type   m >>= \s -> return (length s)
  m >>= \s -> return (length s) :: Logger Int
\end{lstlisting}

通过\acode{(>>=)}解包该字符串，接着用一个小的匿名函数来调用\acode{length}并通过\acode{return}重新进行包装。

由于\acode{Monad} typeclass 已经提供了\acode{(>>=)}与\acode{return}函数用于解包与打包一个值，\acode{liftM}函数则不需要知道任何单子实现的细节。

\begin{lstlisting}[language=Haskell]
  liftM :: (Monad m) => (a -> b) -> m a -> m b
  liftM f m = m >>= \i -> return $ f i
\end{lstlisting}

当我们为一个类型声明\acode{Functor} typeclass 实例时，我们需要编写自己的\acode{fmap}。相反的，\acode{liftM}不需要了解单子的内部，因为它们抽象出来了
\acode{(>>=)}与\acode{return}。我们只需要通过适当的类型约束编写它一次。

\acode{liftM}函数预定义在\acode{Control.Monad}模块中。

为了检测\acode{liftM}是如何提高可读性的，我们来比较连个相同作用的代码。首先是不使用\acode{liftM}的情况：

\begin{lstlisting}[language=Haskell]
  charClass_wordy (']' : cs) =
    globToRegex' cs >>= \ds -> return $ ']' : ds
  charClass_wordy (c : cs) =
    charClass_wordy cs >>= \ds -> return $ c : ds
\end{lstlisting}

然后是使用\acode{liftM}来去除\acode{(>>=)}以及匿名函数：

\begin{lstlisting}[language=Haskell]
  charClass (']' : cs) = (']' :) `liftM` globToRegex' cs
  charClass (c : cs) = (c :) `liftM` globToRegex' cs
\end{lstlisting}

与\acode{fmap}一样，我们经常以中缀形式使用\acode{liftM}。阅读这种表达式的一种简单方法是“将左侧的纯函数应用于右侧一元操作的结果”。

\acode{liftM}太有用了以致于\acode{Control.Monad}定义了若干变体，用于结合更长的操作链。来看一下\acode{globToRegex'}函数的最后一个分句：

\begin{lstlisting}[language=Haskell]
  globToRegex' (c : cs) = liftM2 (++) (escape c) (globToRegex' cs)

  escape :: Char -> Logger String
  escape c
    | c `elem` regexChars = record "escape" >> return ['\\', c]
    | otherwise = return [c]
    where
      regexChars = "\\+()^$.{}]|"
\end{lstlisting}

而上述的\acode{liftM2}函数定义如下：

\begin{lstlisting}[language=Haskell]
  liftM2 :: (Monad m) => (a -> b -> c) -> m a -> m b -> m c
  liftM2 f m1 m2 =
    m1 >>= \a ->
      m2 >>= \b ->
        return (f a b)
\end{lstlisting}

它首先执行第一个操作，接着第二个，再使用纯函数\acode{f}组合它们的结果，并封装该结果。除了\acode{liftM2}，\acode{Control.Monad}中的变体达到了\acode{liftM5}。

\subsection*{消除一些误解}

略。

\subsection*{构建一个 Logger 单子}

\acode{Logger}类型的定义非常简单：

\begin{lstlisting}[language=Haskell]
  newtype Logger a = Logger {execLogger :: (a, Log)}
\end{lstlisting}

它一个二元元组，第一个元素是具体操作的结果，而第二个元素则是该操作中产生的所有日志的列表。

我们将该元组包装进了一个\acode{newtype}中使其变为独立类型。\acode{runLogger}函数则是从包装中提取出该元组。而暴露出来执行一个日志行为的函数，\acode{runLogger}，
则是\acode{execLogger}的一个别名。

\begin{lstlisting}[language=Haskell]
  runLogger = execLogger
\end{lstlisting}

\acode{record}帮助函数则是通过传入的信息，创建了一个单例列表：

\begin{lstlisting}[language=Haskell]
  record s = Logger ((), [s])
\end{lstlisting}

该操作的结果为\acode{()}，这也是为什么在结果位置放置它的缘故。

现在开始\acode{Monad}实例的\acode{return}，它很简单：不记录日志，并将其入参存储值结果位置。

\begin{lstlisting}[language=Haskell]
  instance Functor Logger where
    fmap f (Logger (a, l)) = Logger (f a, l)

  instance Applicative Logger where
    pure a = Logger (a, [])
    (<*>) (Logger (h, w)) (Logger (a, x)) = Logger (h a, w ++ x)

  instance Monad Logger where
    m >>= k =
      let (a, w) = execLogger m
          n = k a
          (b, x) = execLogger n
      in Logger (b, w ++ x)
\end{lstlisting}

注：现代版本 Haskell 在实现 Monad 实例之前还需要先实现 Functor 与 Applicative 实例。

\subsubsection*{序列化日志，而不是序列化计算}

我们定义的\acode{(>>=)}确保了左侧的日志信息将会附加到右侧的新的日志信息中。然而，它并没有涉及\acode{a}与\acode{b}的计算：\acode{(>>=)}是惰性的。

正如其它大多数的单子行为一样，严格程度是由单子的实现者所控制的。它不是所有单子都共享的常量。实际上一些单子由多种风格，每一种都会有不同的严格程度。

\subsubsection*{Writer 单子}

我们的\acode{Logger}单子实际上是标准\acode{Writer}单子的特殊版本，可以在\acode{mtl}库的\acode{Control.Monad.Writer}模块中找到。关于\acode{Writer}的例子
将会在下一章中讲到。

\subsection*{Maybe 单子}

\acode{Maybe}类型是最简单的\acode{Monad}实例。它代表着计算可能不会返回一个结果。

当我们将一系列返回\acode{Maybe}的计算通过\acode{(>>=)}或\acode{>>}串联起时，它们任意一个返回\acode{Nothing}时，后续的计算都不再进行。

注意，尽管链条并不是完全短路的。链路中的每个\acode{(>>=)}或\acode{(>>)}仍然会匹配左侧的\acode{Nothing}，并生产一个\acode{Nothing}在右侧，直至最后。容易
遗忘的点：当链路中的一个计算失败时，剩下的链路以及\acode{Nothing}值的消费在运行时是廉价的，但并不是全免。

\subsubsection*{执行 Maybe 单子}

执行\acode{Maybe}单子的函数名为\acode{maybe}。（记住“执行”一个单子包括对单子求值并返回一个去掉单子类型包装的结果。）

\begin{lstlisting}[language=Haskell]
  maybe :: b -> (a -> b) -> Maybe a -> b
  maybe n _ Nothing  = n
  maybe _ f (Just x) = f x
\end{lstlisting}

它第一个参数是当结果为\acode{Nothing}时，给定的返回；第二个参数则是当结果为\acode{Just}时，应用到解包值上的函数。

\subsubsection*{Maybe 作为优秀的 API 设计}

下面是一个\acode{Maybe}作为单子使用的例子。给定一个用户名，希望通过移动电话运营商找到账单地址。

\begin{lstlisting}[language=Haskell]
  import Data.Map qualified as M

  type PersonName = String

  type PhoneNumber = String

  type BillingAddress = String

  data MobileCarrier
    = Honest_Bobs_Phone_Network
    | Morrisas_Marvelous_Mobiles
    | Petes_Plutocratic_Phones
    deriving (Eq, Ord)

  findCarrierBillingAddress ::
    PersonName ->
    M.Map PersonName PhoneNumber ->
    M.Map PhoneNumber MobileCarrier ->
    M.Map MobileCarrier BillingAddress ->
    Maybe BillingAddress
\end{lstlisting}

我们的第一个版本是可怕的梯形代码，带着一堆\acode{case}表达式：

\begin{lstlisting}[language=Haskell]
  variation1 :: (Ord k1, Ord k2, Ord k3) => k1 -> M.Map k1 k2 -> M.Map k2 k3 -> M.Map k3 a -> Maybe a
  variation1 person phoneMap carrierMap addressMap =
    case M.lookup person phoneMap of
      Nothing -> Nothing
      Just number ->
        case M.lookup number carrierMap of
          Nothing -> Nothing
          Just carrier -> M.lookup carrier addressMap
\end{lstlisting}

\acode{Data.Map}模块的\acode{lookup}函数拥有一个 monadic 返回类型

\begin{lstlisting}[language=Haskell]
  ghci> :module +Data.Map
  ghci> :type Data.Map.lookup
  Data.Map.lookup :: (Ord k, Monad m) => k -> Map k a -> m a
\end{lstlisting}

换言之，如果给定的键在 map 中，\acode{lookup}通过\acode{return}将值注入至单子；反之，调用\acode{fail}。这是很有意思的 API 设计，尽管我们会认为这是一个糟糕的
选择。

\begin{itemize}
  \item 正面来看，成功与失败的行为是根据调用\acode{lookup}所产生的单子自动定值的。更妙的的是，\acode{lookup}本身并不需要知道或关系这些行为。
  \item 反面来看，问题在于错误的单子中使用\acode{file}会抛出令人厌恶的异常。
\end{itemize}

使用\acode{do}简化：

\begin{lstlisting}[language=Haskell]
  variation2 :: (Ord k1, Ord k2, Ord k3) => k1 -> M.Map k1 k2 -> M.Map k2 k3 -> M.Map k3 b -> Maybe b
  variation2 person phoneMap carrierMap addressMap = do
    number <- M.lookup person phoneMap
    carrier <- M.lookup number carrierMap
    M.lookup carrier addressMap
\end{lstlisting}

如果这些 lookup 中任意一个失败了，那么\acode{(>>=)}以及\acode{(>>)}的定义意味着函数的整个结果将会变为\acode{Nothing}，正如第一次尝试中显式的使用\acode{case}
那样。

通过\acode{flip}还可以将函数体变为一行：

\begin{lstlisting}[language=Haskell]
  variation3 :: Ord a => a -> M.Map a a -> M.Map a a -> M.Map a b -> Maybe b
  variation3 person phoneMap carrierMap addressMap =
    lookup phoneMap person >>= lookup carrierMap >>= lookup addressMap
    where
      lookup = flip M.lookup
\end{lstlisting}

\subsection*{列表单子}

虽然\acode{Maybe}类型即可以表示没有值，也可以表示一个值，但在很多情况下，我们希望返回一些事先不知道的结果。显然列表非常适合这个目的。列表的类型表明我们可以将它用作
单子，因为他的类型构造函数有一个自由变量。当然，我们可以使用列表作为单子。

略。

如果将\acode{(>>=)}应用至列表，我们会发现其类型为\acode{[a] -> (a -> [b]) -> [b]}。这看起来就跟\acode{map}类似：

\begin{lstlisting}[language=Haskell]
  ghci> :type (>>=)
  (>>=) :: (Monad m) => m a -> (a -> m b) -> m b
  ghci> :type map
  map :: (a -> b) -> [a] -> [b]
\end{lstlisting}

看上去并不匹配，不过可以使用\acode{flip}：

\begin{lstlisting}[language=Haskell]
  ghci> :type (>>=)
  (>>=) :: (Monad m) => m a -> (a -> m b) -> m b
  ghci> :type flip map
  flip map :: [a] -> (a -> b) -> [b]
\end{lstlisting}

仍有一个问题：\acode{flip map}的第二个参数的类型是\acode{a -> b}，而\acode{(>>=)}对于列表的第二个参数是\acode{a -> [a]}。我们该怎么做呢？

函数\acode{flip map}可以返回任何\acode{b}类型作为其结果。如果在签名中将\acode{b}替换为\acode{[b]}，那么类型签名就变为\acode{a -> (a -> [a]) -> [[b]]}。
换言之，如果我们 map 一个函数返回列表的列表，我们则会得到列表的列表作为返回。

\begin{lstlisting}[language=Haskell]
  ghci> flip map [1,2,3] (\a -> [a,a+100])
  [[1,101],[2,102],[3,103]]
\end{lstlisting}

有趣的是，我们并没有真正改变类型签名。\acode{(>>=)}的类型是\acode{[a] -> (a -> [b]) -> [b]}，而当映射函数返回列表时，\acode{flip map}的类型为
\acode{[a] -> (a -> [b]) -> [[b]]}。这里仍有一个类型不匹配；我们仅仅将一项从类型签名的中间移到了末尾。不过这并没有白费功夫：现在需要一个接受\acode{[[b]]}并
返回\acode{[b]}的函数，这里推荐\acode{concat}：

\begin{lstlisting}[language=Haskell]
  ghci> :type concat
  concat :: [[a]] -> [a]
\end{lstlisting}

该类型建议我们翻转参数给到\acode{map}，接着\acode{concat}结果得到一个非嵌套的列表。

\begin{lstlisting}[language=Haskell]
  ghci> :type \xs f -> concat (map f xs)
  \xs f -> concat (map f xs) :: [a] -> (a -> [a1]) -> [a1]
\end{lstlisting}

这正是列表的\acode{(>>=)}的定义：

\begin{lstlisting}[language=Haskell]
  instance Monad [] where
    return x = [x]
    xs >>= f = concat (map f xs)
\end{lstlisting}

注：以上是旧版的定义。略。

\subsubsection*{理解列表单子}

列表单子类似于我们熟悉的 Haskell 工具：列表表达式。我们可以通过两个列表的笛卡尔积来说明它们的相似性。首先是写一个列表表达式：

\begin{lstlisting}[language=Haskell]
  comprehensive xs ys = [(x, y) | x <- xs, y <- ys]
\end{lstlisting}

这一次，我们将对一元代码使用花括号表示法。这将突出一元代码在结构上与列表表达式的相似之处：

\begin{lstlisting}[language=Haskell]
  monadic xs ys = do x <- xs; y <- ys; return (x, y)
\end{lstlisting}

注：原本的\acode{monadic xs ys = do { x <- xs; y <- ys; return (x, y)}}会被 HLS 简化成上述代码。

这里的唯一真正的区别是，我们构造的值出现在一系列表达式的末尾，而不是像列表表达式那样出现在开头。两者的结果是完全一致的：

\begin{lstlisting}[language=Haskell]
  ghci> comprehensive [1,2] "bar"
  [(1,'b'),(1,'a'),(1,'r'),(2,'b'),(2,'a'),(2,'r')]
  ghci> comprehensive [1,2] "bar" == monadic [1,2] "bar"
  True
\end{lstlisting}

刚开始的时候很容易对列表单子感到困惑，让我们再次看一下单子笛卡尔乘积代码。这次将重新排列函数：

\begin{lstlisting}[language=Haskell]
  blockyDo :: Monad m => m a -> m b -> m (a, b)
  blockyDo xs ys = do
    x <- xs
    y <- ys
    return (x, y)
\end{lstlisting}

对于列表\acode{xs}中的每个元素，函数的其余部分求值一次，每次都将\acode{x}绑定到列表中的不同的值上。然后对于列表\acode{ys}中的每个元素，函数的剩余部分求值一次，
每次都将\acode{y}绑定到列表中的不同值。

这里我们真正拥有的是一个双重嵌套循环！这突出了一个关于单子的重要事实：除非知道一个单子代码块将在那个单子中执行，否则无法预测它的行为。

现在让嵌套的循环更加明显一些：

\begin{lstlisting}[language=Haskell]
  blockyPlain :: (Monad m) => m a -> m b -> m (a, b)
  blockyPlain xs ys =
    xs
      >>= \x ->
        ys
          >>= \y -> return (x, y)

  blockyPlain_reloaded :: [a] -> [b] -> [(a, b)]
  blockyPlain_reloaded xs ys =
    concatMap (\x -> concatMap (\y -> return (x, y)) ys) xs
\end{lstlisting}

注：这里与文中不同之处在于使用了\acode{concatMap}而不是\acode{concat (map (...}。

\subsubsection*{令列表单子生效}

下面是一个简单的暴力约束求解。给定一个整数，它会找到所有正整数对，这些正整数相乘后会得到该值（这就是要解决的约束）。

\begin{lstlisting}[language=Haskell]
  guarded :: Bool -> [a] -> [a]
  guarded True xs = xs
  guarded False _ = []

  multiplyTo :: Int -> [(Int, Int)]
  multiplyTo n = do
    x <- [1 .. n]
    y <- [x .. n]
    guarded (x * y == n) $ return (x, y)
\end{lstlisting}

测试：

\begin{lstlisting}[language=Haskell]
  ghci> multiplyTo 8
  [(1,8),(2,4)]
  ghci> multiplyTo 100
  [(1,100),(2,50),(4,25),(5,20),(10,10)]
  ghci> multiplyTo 891
  [(1,891),(3,297),(9,99),(11,81),(27,33)]
\end{lstlisting}

\subsection*{do 代码块的脱糖}

略。

\subsubsection*{单子作为可编程的分号}

略。

\subsubsection*{为何选择无糖？}

略。

\subsection*{State 单子}

我们早在第十章节中就发现了\acode{Parse}是一个单子。它有着两个独立的角度：一个是当解析失败时，提供带有细节的错误信息（通过\acode{Either}类型达成）；另一个就是
它携带着隐式状态，该例子中为\acode{ByteString}。

这种读写状态的需求在 Haskell 程序中很常见，因此标准库提供了一个名为\acode{State}的单子，其位于\acode{Control.Monad.State}模块中。

当我们的\acode{Parse}类型携带一个\acode{ByteString}作为它的状态片段时，\acode{state}单子可以携带任何类型的状态。我们将状态的未知类型称为\acode{s}。

给定一个状态值，我们检查它，然后产生一个结果和一个新的状态值。假设结果可以是任何类型\acode{a}。捕获这个想法的类型签名是\acode{s -> (a, s)}；获取一个状态
\acode{s}，对其做某些操作，然后返回结果\acode{a}，以及一个新的状态\acode{s}。

\subsubsection*{状态单子}

我们先来开发一个\acode{State}单子

\begin{lstlisting}[language=Haskell]
  type SimpleState s a = s -> (a, s)
\end{lstlisting}

我们的单子是一个函数，用于转换一个状态，并返回一个值。正因如此，状态单子有时候会被称为状态转换单子。

这是一个类型别名，而不是一个新类型，所以这里有点作弊，不过这可以简化很多之后的描述。

早在本章开头，我们提到了一个单子有一个单类型入参的类型构造函数，而这里则是带两个参数的类型。这里的关键是要理解我们可以部分应用类型，正如部分应用普通函数那样。接下来是
一个简单的示例：

\begin{lstlisting}[language=Haskell]
  type StringState a = SimpleState String a
\end{lstlisting}

这里将变量\acode{s}绑定至\acode{String}。\acode{StringState}类型仍有一个类型参数\acode{a}。现在有了一个适合单子的类型构造函数，换言之，单子的类型构造函数是
\acode{SimpleState s}，而不仅仅只是\acode{SimpleState}。

接下来是单子所需的\acode{return}函数：

\begin{lstlisting}[language=Haskell]
  returnSt :: a -> SimpleState s a
  returnSt a = \s -> (a, s)
\end{lstlisting}

它所做的就是获取结果和当前状态，并将它们“元组化”。到目前为止，我们可能已经习惯了这样的想法，即带有多个参数的 Haskell 函数知识一个单参数的函数链，不过以防万一，这里
有一种更熟悉的编写\acode{returnSt}的方法，它使这个函数更明显且简单：

\begin{lstlisting}[language=Haskell]
  returnAlt :: a -> SimpleState s a
  returnAlt a s = (a, s)
\end{lstlisting}

单子最后一块定义就是\acode{(>>=)}，这里使用了标准库中\acode{State}定义中的实际变量名：

\begin{lstlisting}[language=Haskell]
  bindSt :: SimpleState s a -> (a -> SimpleState s b) -> SimpleState s b
  bindSt m k = \s -> let (a, s') = m s in k a s'
\end{lstlisting}

这些单字母变量名对可读性并没有什么好处，所以让我们看看是否可以替换一些更有意义的名称。

\begin{lstlisting}[language=Haskell]
  -- m == step
  -- k == makeStep
  -- s == oldState
  bindAlt step makeStep oldState =
    let (result, newState) = step oldState
     in makeStep result newState
\end{lstlisting}

为了理解这个定义，记住\acode{step}是一个类型为\acode{s -> (a, s)}的函数。当需要计算它时，将会得到一个元组，我们需要使用它返回一个新的\acode{s -> (a, s)}类型的
函数。这恐怕比从\acode{bindAlt}类型中去掉\acode{SimpleState}类型别名，以及测试类型的入参与返回值，要来的更简单。

\begin{lstlisting}[language=Haskell]
  bindAlt :: (s -> (a, s)) -> (a -> s -> (b, s)) -> (s -> (b, s))
\end{lstlisting}

\subsubsection*{读取与修改状态}

状态单子的\acode{(>>=)}与\acode{return}定义很简单：移动状态，但并不触碰该状态。

\begin{lstlisting}[language=Haskell]
  getSt :: SimpleState s s
  getSt = \s -> (s, s)

  putSt :: s -> SimpleState s ()
  putSt s = const ((), s)
\end{lstlisting}

注：原文的\acode{putSt s = \_ -> ((), s)}现改为\acode{putSt s = const ((), s)}。

\subsubsection*{真正的状态单子可用吗？}

我们在前一节中使用的唯一简化技巧是为\acode{SimpleState}使用类型别名而不是类型定义。如果引入了一个线类型的包装器，那么额外的包装和解包将使代码变得更难理解。

为了定义一个\acode{Monad}实例，我们需要提供合适的类型构造函数，以及\acode{(>>=)}与\acode{return}的定义。这就是\textit{真实的}\acode{State}定义。

\begin{lstlisting}[language=Haskell]
  newtype State s a = State
    { runState :: s -> (a, s)
    }
\end{lstlisting}

这里所做的是包装\acode{s -> (a, s)}类型进一个\acode{State}构造函数中。使用 Haskell 的 record 语义来进行类型定义，自动获得一个\acode{runState}函数用来从其
构造函数中解包一个\acode{State}值。\acode{runState}的类型是\acode{State s a -> s -> (a, s)}。

\acode{return}的定义与\acode{SimpleState}几乎相同，除了需要通过\acode{State}构造函数来进行包装。

\begin{lstlisting}[language=Haskell]
  returnState :: a -> State s a
  returnState a = State (a,)
\end{lstlisting}

注：原文为\acode{returnState a = State \$ \s -> (a, s)}，这里进行了简化。

\acode{(>>=)}的定义有点复杂，因为它需要使用\acode{runState}来移除\acode{State}包装器。

\begin{lstlisting}[language=Haskell]
  bindState :: State s a -> (a -> State s b) -> State s b
  bindState m k = State $ \s ->
    let (a, s') = runState m s
     in runState (k a) s'
\end{lstlisting}

该函数与早前定义的\acode{bindSt}仅在多了包装和解包动作上有所不同。

读与修改状态也是同理，添加包装：

\begin{lstlisting}[language=Haskell]
  get :: State s s
  get = State $ \s -> (s, s)

  put :: s -> State s ()
  put s = State $ const ((), s)
\end{lstlisting}

注：原文为\acode{put s = State \$ \_ -> ((), s)}。

\subsubsection*{使用状态单子：生成随机值}

我们已经使用过状态单子的前身\acode{Parse}用于解析二进制数据。这个例子中，是将要操作的状态类型直接连接到\acode{Parse}类型中。

\acode{State}单子，相反，接受任意状态类型作为参数，\acode{State ByteString}。

如果拥有命令式语言的背景，那么状态单子可能会比其它单子更易接受。因为命令式语言都是关于携带一些隐式状态，读取一部分，并通过赋值修改其它部分，而这正是状态单子的作用。

Haskell 生成随机值的标准库名为\acode{System.Random}。它允许任何类型的随机值生成，不仅仅是数值。该模块包含了若干方便的函数于\acode{IO}单子中。例如，等同于
C 的 \acode{rand} 函数：

\begin{lstlisting}[language=Haskell]
  import System.Random

  rand :: IO Int
  rand = getStdRandom $ randomR (0, maxBound)
\end{lstlisting}

（\acode{randomR}函数接受一个闭合的区间作为随机值的范围）

\acode{System.Random}模块提供一个 typeclass，\acode{RandomGen}，其供我们定义随机的\acode{Int}源。\acode{StdGen}类型则是标准\acode{RandomGen}的实例。
它生成伪随机值。如果我们拥有真正随机数据的外部来源，便可以将其作为\acode{RandomGen}的实例，并获得真正随机的值，而不仅仅是伪随机值。

另一个 typeclass，\acode{Random}，则指示如何生成特定类型的随机值。模块定义了所有常用类型的\acode{Random}实例。

顺带一提，上面\acode{rand}的定义读取并修改了一个内置的全局随机生成器，该生成器位于\acode{IO}单子中。

\subsubsection*{尝试纯粹性}

到目前为止，我们一直强调尽可能避免使用\acode{IO}单子，如果只是为了生成一些随机值而使用它，那就很可惜。实际上\acode{System.Random}包含了纯随机数生成函数。

纯函数的缺点是，我们必须获得或创建一个随机生成器，在调用它时，它返回一个新的随机数生成器：记住，在纯函数中我们不能修改现有生成器的状态。

如果我们忘记不可变性，并且在函数中重用相同的生成器，那么则会得到完全相同的“随机”数：

\begin{lstlisting}[language=Haskell]
  twoBadRandoms :: (RandomGen g) => g -> (Int, Int)
  twoBadRandoms gen = (fst $ random gen, fst $ random gen)
\end{lstlisting}

\acode{random}函数使用了一个隐式范围而不是\acode{randomR}里用户提供的范围。\acode{getStdGen}函数从\acode{IO}单子中获取当前的全局标准数值生成器。

不幸的是，正确的传递和使用生成器的连续版本并不会产生令人满意的数。

\begin{lstlisting}[language=Haskell]
  twoGoodRandoms :: (RandomGen g) => g -> ((Int, Int), g)
  twoGoodRandoms gen =
    let (a, gen') = random gen
        (b, gen'') = random gen'
     in ((a, b), gen'')
\end{lstlisting}

现在我们了解了状态单子，但是它看起来是隐藏生成器的一个很好的候选。状态单子允许我们规整的管理可变状态，同时保证我们的代码不会有其它意想不到的副作用，比如修改文件或建立
网络连接。这使得我们更容易推断代码的行为。

\subsubsection*{状态单子中的随机值}

下面是一个状态单子，携带一个\acode{StdGen}作为它的状态：

\begin{lstlisting}[language=Haskell]
  type RandomState a = State StdGen a
\end{lstlisting}

生成一个随机值现在只需要获取当前的生成器，使用它，然后修改状态，用新的生成器替换它。

\begin{lstlisting}[language=Haskell]
  getRandom :: (Random a) => RandomState a
  getRandom =
    get >>= \gen ->
      let (val, gen') = random gen
       in put gen' >> return val
\end{lstlisting}

我们现在可以使用之前看到的一些一元机制来编写一个更简洁的函数，用于给出一对随机数：

\begin{lstlisting}[language=Haskell]
  getTwoRandoms :: (Random a) => RandomState (a, a)
  getTwoRandoms = liftM2 (,) getRandom getRandom
\end{lstlisting}

\subsubsection*{运行状态单子}

正如之前提到的那样，每个单子都有其特化的计算函数。本例的状态单子，有若干种选择：

\begin{itemize}
  \item \acode{runState} 同时返回结果和最终状态；
  \item \acode{evalState} 仅返回结果，丢弃最终状态；
  \item \acode{execState} 丢弃结果，仅返回最终状态。
\end{itemize}

\acode{evalState}与\acode{execState}函数仅仅是\acode{runState}以及\acode{fst}与\acode{snd}的组合。因此最需要记住的是\acode{runState}函数。

以下是如何实现\acode{getTwoRandoms}函数的完整用例：

\begin{lstlisting}[language=Haskell]
  runTwoRandoms :: IO (Int, Int)
  runTwoRandoms = do
    oldState <- getStdGen
    let (result, newState) = runState getTwoRandoms oldState
    setStdGen newState
    return result
\end{lstlisting}

\acode{runState}的调用遵循一个标准模式：传递它至一个包含在状态单子中的函数，以及一个初始状态；它返回函数的结果以及最终状态。

围绕\acode{runState}调用的代码仅仅获取当前全局\acode{StdGen}值，然后替换它，以便后续对\acode{runTwoRandoms}或其他随机生成函数的调用可以获得更新的状态。

\subsubsection*{更多特性}

很难想象编写只有一个状态值要传递的代码。当我们想要一次跟踪多个状态片段时，通常的技巧是在一个数据类型中维护它们。这里有一个例子：跟踪我们分发的随机数的数量：

\begin{lstlisting}[language=Haskell]
  data CountedRandom = CountedRandom
    { crGen :: StdGen,
      crCount :: Int
    }

  type CRState = State CountedRandom

  getCountedRandom :: (Random a) => CRState a
  getCountedRandom = do
    st <- get
    let (val, gen') = random (crGen st)
    put CountedRandom {crGen = gen', crCount = crCount st + 1}
    return val
\end{lstlisting}

该例子碰巧消耗了状态的两个元素，并构造了一个全新的状态。更普遍的场景是，可能只读取或修改状态的一部分。该函数获取到目前为止生成的随机值数量。

\begin{lstlisting}[language=Haskell]
  getCount :: CRState Int
  getCount = gets crCount
\end{lstlisting}

注：原文为\acode{getCount = crCount `liftM` get}，这里用\acode{gets crCount}进行简化。

如果我们希望更新部分状态，那么代码可能就没那么显而易见了。

\begin{lstlisting}[language=Haskell]
  putCount :: Int -> CRState ()
  putCount a = do
    st <- get
    put st {crCount = a}
\end{lstlisting}

还存在一个名为\acode{modify}的函数，其组合了\acode{get}与\acode{put}步骤。它将状态转换函数作为参数，但它并不令人满意：我们仍然无法摆脱笨拙的记录更新语法：

\begin{lstlisting}[language=Haskell]
  putCountModify :: Int -> CRState ()
  putCountModify a = modify $ \st -> st {crCount = a}
\end{lstlisting}

\subsection*{单子与函子}

略（原文 Haskell 版本过旧，已不适合现在的学习）。

\end{document}