Ch11 Functors, Applicative Functors and Monoids.tex

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

\begin{document}

由纯粹性，高阶函数，参数化代数数据类型，以及 typeclasses 所构成的 Haskell，相比于其他语言，允许我们实现更高等级的多态。
我们无需考虑类型是如何属于一个类型阶级系统的，而是由合理的 typeclasses 如何连接它们的。

Typesclasses 是开放的，这就意味着我们可以定义自己的数据类型。

\subsection*{函子 Functors 复习}

回忆：Functors 可以用于映射至比如列表，\acode{Maybe}，树，等等。在 Haskell 中它们被 \acode{Functor} typeclass
所描述，其仅有一个名为 \acode{fmap} 的 typeclass 方法，该方法的类型是\acode{fmap :: (a -> b) -> f a -> f b}。
它表示：给我一个接受一个\acode{a}并返回一个\acode{b}的函数，以及给我一个（或多个）\acode{a}的容器，那么我将给你一个
（或多个）\acode{b}的容器。有点像是将函数应用至容器中的元素。

如果一个类型构造函数是\acode{Functor}的实例，那么它的 kind 就必须是\acode{* -> *}，这代表它必须刚好接受一个类型作为
类型参数。像是\acode{Maybe}是 Functor 的实例，它接受一个类型参数，如\acode{Maybe Int}或\acode{Maybe String}。
如果一个类型构造函数接受两个参数，比如\acode{Either}，我们不能这样\acode{instance Functor Either where}，不过
可以这样\acode{instance Functor (Either a) where}，那么\acode{fmap}作为\acode{Either a}的类型前面就可以这样
\acode{fmap :: (b -> c) -> Either a b -> Either a c}。

现在看看\acode{IO}是怎么样的一个\acode{Functor}实例。当我们\acode{fmap}一个函数在一个 I/O action 上，我们希望
拿回的 I/O action 是已经被映射过的：

\begin{lstlisting}[language=Haskell]
  instance Functor IO where
    fmap f action = do
        result <- action
        return (f result)
\end{lstlisting}

对一个 I/O action 映射的结果仍然是一个 I/O action，因此需要用\textit{do}语法来把两个 I/O action 粘合成一个。

\begin{lstlisting}[language=Haskell]
  main = do
    line <- getLine
    let line' = reverse line
    putStrLn $ "You said " ++ line' ++ " backwards!"
    putStrLn $ "Yes, you really said " ++ line' ++ " backwards!"
\end{lstlisting}

用\acode{fmap}改写：

\begin{lstlisting}[language=Haskell]
  main = do
    line <- fmap reverse getLine
    putStrLn $ "You said " ++ line ++ " backwards!"
    putStrLn $ "Yes, you really said " ++ line ++ " backwards!"
\end{lstlisting}

如果将\acode{fmap}应用至\acode{IO}，其类型便为\acode{fmap :: (a -> b) -> IO a -> IO b}。

如果将一个 I/O action 绑定到一个名称上时，仅仅想要应用一个函数，那么可以考虑使用\acode{fmap}，因为这看起来更简洁。如果
想要应用多个函数，那么可以声明自己的函数，将其变为 lambda 或者使用函数组合：

\begin{lstlisting}[language=Haskell]
  import Data.Char
  import Data.List

  main = do
    line <- fmap (intersperse '-' . reverse . map toUpper) getLine
    putStrLn line
\end{lstlisting}

\begin{lstlisting}[language=Bash]
  $ runhaskell fmappingIO.hs
  hello there
  E-R-E-H-T- -O-L-L-E-H
\end{lstlisting}

\acode{intersperse '-' . reverse . map toUpper}这个函数接受一个字符串，映射\acode{toUpper}后的返回值再应用
\acode{reverse}，最后应用\acode{intersperes '-'}。

另一个我们已经接触过的\acode{Functor}实例就是\acode{(->) r}。函数类型\acode{r -> a}可以被重写为\acode{(->) r a}，
就像是\acode{2 + 3}可以表达为\acode{(+) 2 3}。从另一个角度来看\acode{(->) r a}，它其实就是一个接受两个类型参数的
构造函数，例如\acode{Either}。但是记住\acode{Functor}只能接受一个参数类型，这也是为什么\acode{(->)}不是
\acode{Functor}的一个实例，但是\acode{(->) r}则是。在\acode{Control.Monad.Instances}有更多的细节：

\begin{lstlisting}[language=Haskell]
  instance Functor ((->) r) where
    fmap f g = (\x -> f (g x))
\end{lstlisting}

首先来看看\acode{fmap}的类型\acode{fmap :: (a -> b) -> f a -> f b}。我们把所有的\acode{f}替换成\acode{(->) r}，
那么就是\acode{fmap :: (a -> b) -> ((->) r a) -> ((->) r b)}，然后将\acode{(->) r a}与\acode{(->) r b}换成
\acode{r -> a}与\acode{r -> b}，则得到\acode{fmap :: (a -> b) -> (r -> a) -> (r -> b)}。

将一个函数映射至另一个函数可以生产出一个函数，就像是映射一个函数在\acode{Maybe}上生产出一个\acode{Maybe}，映射一个函数在
一个列表上能生成出一个列表。那么上述的类型实例说的是什么呢？它接受一个\acode{a}至\acode{b}的函数，以及一个\acode{r}至
\acode{a}的函数，返回一个\acode{r}至\acode{b}的函数。这就是一个函数组合！另一种实例的写法：

\begin{lstlisting}[language=Haskell]
  instance Functor ((->) r) where
    fmap = (.)
\end{lstlisting}

很明显就是将\acode{fmap}当函数组合在用。在 GHCI 中使用\acode{:m + Control.Monad.Instances}加载模块，测试：

\begin{lstlisting}[language=Haskell]
  ghci> :t fmap (*3) (+100)
  fmap (*3) (+100) :: (Num a) => a -> a
  ghci> fmap (*3) (+100) 1
  303
  ghci> (*3) `fmap` (+100) $ 1
  303
  ghci> (*3) . (+100) $ 1
  303
  ghci> fmap (show . (*3)) (*100) 1
  "300"
\end{lstlisting}

\acode{fmap}等同于函数组合这件事儿对我们而言并不是很实用，但是这至少是一个有趣的观点。Functors 其实比较像是 computation，
函数被映射到另一个计算会经由那个函数映射过后的计算。

在看一下\acode{fmap}的类型\acode{fmap :: (a -> b) -> f a -> f b}，那么为了简洁不写\acode{(Functor f) =>}部分。
在学柯里化的时候提到过 Haskell 的函数实际上只接受一个参数，即\acode{a -> b -> c}，如果调用时少写一个参数，那么返回的函数
就需要接受剩下的参数。所以\acode{a -> b -> c}可以写成\acode{a -> (b -> c)}，这样柯里化更加明显。

同样的如果写成\acode{fmap :: (a -> b) -> (f a -> f b)}，我们可以认为\acode{fmap}不是一个接受函数与函子并返回一个函子的
函数，而是一个接受函数并返回一个新函数的函数，而这个返回的新函数接受一个函子作为参数，并返回一个函子。接受一个\acode{a -> b}
函数并返回一个\acode{f a -> f b}函数，这被称为\textit{提升 lifting}一个函数。我们用 GHCI 的\acode{:t}命令检查：

\begin{lstlisting}[language=Haskell]
  ghci> :t fmap (*2)
  fmap (*2) :: (Num a, Functor f) => f a -> f a
  ghci> :t fmap (replicate 3)
  fmap (replicate 3) :: (Functor f) => f a -> f [a]
\end{lstlisting}

表达式\acode{fmap (*2)}是一个接受基于数值的函子\acode{f}并返回一个数值函子的函数。函子可以是一个列表一个\acode{Maybe}，
一个\acode{Either String}，等等。表达式\acode{fmap (replicate 3)}则接受任意类型的函子并返回一个该类型列表函子。

\begin{anote}
  当我们说\textit{一个基于数值的函子 a functor over numbers}时，你可以认为是\textit{一个拥有数值的函子 a functor that
    has numbers in it}。前者的描述更加精准，后者则更容易理解。
\end{anote}

当使用部分应用绑定至一个名称时，比如说\acode{fmap (++"!")}，在 GHCI 更加的显而易见。

\begin{lstlisting}[language=Haskell]
  ghci> :t fmap (++"!")
  fmap (++"!") :: Functor f => f [Char] -> f [Char]
\end{lstlisting}

可以把\acode{fmap}想像成一个函数，接受另一个函数与一个函子，然后将接受的函数对函子中每个元素做映射；也可以想象成是一个函数，
接受一个函数并将其提升 lift 到可以在函子上操作。这两种想法都是正确的，且在 Haskell 中是等价的。

接下来我们开始学习\textbf{函子定律 functor laws}。为了让某物成为一个函子，它必须满足某些条件。所有的函子都要求具有某些性质，
它们必须是能被映射的，对它们调用\acode{fmap}应该要用一个函数映射至每一个元素，且没有额外的操作。这些行为都被函子定律所描述。
对于\acode{Functor}的实例而言，总共有两条定律该被遵守。不过它们不会在 Haskell 中自动被检查，需要用户自己确认这些条件。

\textbf{函子第一定律是如果将\acode{id}函数映射至该函子，得到的函子必须是原来的函子}。用代码表示即\acodegrn{fmap id = id}，
换言之如果\acode{fmap id}至一个函子，返回的结果跟直接\acode{id}至该函子是一样的。\acode{id}是一个 identity 函数，
可以写作是\acode{\\x -> x}。

\begin{lstlisting}[language=Haskell]
  ghci> fmap id (Just 3)
  Just 3
  ghci> id (Just 3)
  Just 3
  ghci> fmap id [1..5]
  [1,2,3,4,5]
  ghci> id [1..5]
  [1,2,3,4,5]
  ghci> fmap id []
  []
  ghci> fmap id Nothing
  Nothing
\end{lstlisting}

看一下\acode{Maybe}的\acode{fmap}的实现，可以知道第一定律是如何遵守的：

\begin{lstlisting}[language=Haskell]
  instance Functor Maybe where
    fmap f (Just x) = Just (f x)
    fmap f Nothing = Nothing
\end{lstlisting}

\textbf{函子第二定律是将两个函数合成并将结果映射至一个函子的结果，与现将第一个函数映射函子再将第二个函子映射至该函子的结果是一样的}。
即\acodegrn{fmap (f . g) = fmap f . fmap g}，或者另一种写法，对于任何一个函子\acode{F}，满足\acodegrn{fmap (f . g) F =
  fmap f (fmap g F)}。

\subsection*{高级函子 Applicative functors}

本节开始学习高级函子，在 Haskell 中由 \acode{Applicative} typeclass 描述，可在\acode{Control.Applicative}模块中找到。

函数在 Haskell 中默认是柯里化的，这就意味着一个函数看起来接受若干参数实际上是接受一个参数并返回一个函数再接受一个参数，以此类推。
如果一个函数的类型是\acode{a -> b -> c}，那么通常会说它接受两个参数并返回一个\acode{c}。这就是为什么可以将\acode{f x y}
表达为\acode{(f x) y}。这个机制允许我们部分应用函数，仅需调用少一些的参数，返回的函数可以被传递至另一个函数。

迄今为止我们映射函数至函子，所映射的函数都是仅一个参数的。但是当映射一个接受两个参数的函数像是\acode{*}至一个函子，该怎么办呢？
首先让我们来观测几个实际的例子。如果有\acode{Just 3}，我们做\acode{fmap (*) (Just 3)}，会得到什么？从\acode{Maybe}实现
\acode{Functor}的实例中我们知道如果是一个\acode{Just something}值，会将函数应用至\acode{Just}中的\acode{something}。
因此\acode{fmap (*) (Just 3)}的结果是\acode{Just ((*) 3)}，即\acode{Just (* 3)}。有意思！我们得到了一个包裹在
\acode{Just}中的函数！

\begin{lstlisting}[language=Haskell]
  ghci> :t fmap (++) (Just "hey")
  fmap (++) (Just "hey") :: Maybe ([Char] -> [Char])
  ghci> :t fmap compare (Just 'a')
  fmap compare (Just 'a') :: Maybe (Char -> Ordering)
  ghci> :t fmap compare "A LIST OF CHARS"
  fmap compare "A LIST OF CHARS" :: [Char -> Ordering]
  ghci> :t fmap (\x y z -> x + y / z) [3,4,5,6]
  fmap (\x y z -> x + y / z) [3,4,5,6] :: (Fractional a) => [a -> a -> a]
\end{lstlisting}

如果映射\acode{compare}，其类型是\acode{(Ord a) => a -> a -> Ordering}至一个字符列表，得到\acode{Char -> Ordering}的
列表，因为函数\acode{compare}是部分应用在列表中的每个字符上的。不是\acode{(Ord a) => a -> Ordering}函数的列表，因为第一个
\acode{a}被应用的是一个\acode{Char}，因此第二个\acode{a}就必须是\acode{Char}类型了。

我们见识到了如何映射“多参数”函数至函子，得到的是一个包含了该函数的函子。那现在我们能对这个包含了函数的函子做什么呢？我们能用一个
消费这些函数的函数来映射至这个函子，这些函子中的函数都会被当做参数传给消费函数。

\begin{lstlisting}[language=Haskell]
  ghci> let a = fmap (*) [1,2,3,4]
  ghci> :t a
  a :: [Integer -> Integer]
  ghci> fmap (\f -> f 9) a
  [9,18,27,36]
\end{lstlisting}

但如果一个函子值是\acode{Just (3 *)}，一个函子值是\acode{Just 5}，我们希望从\acode{Just (3 *)}取出函数并映射至\acode{Just 5}
呢？普通的函子是没法做的，因为他们仅支持映射普通函数至已存在的函子。即使当我们映射\acode{\\f -> f 9}至一个包含了函数的函子上，我们
也只是映射了一个普通函数。也就是说我们没法用\acode{fmap}将一个包在函子里的函数映射至一个函子。我们可以用模式匹配将\acode{Just}中的
函数抽出来再映射至\acode{Just 5}，不过我们希望有一个通用方法，对于任何函子都有效。

现在来看看\acode{Applicative}这个 typeclass，可以在\acode{Control.Applicative}中找到它，其定义了两个函数\acode{pure}以及
\acode{<*>}。没有任何的默认实现，因此如果希望某物成为高级函子，那么我们需要定义这两个函数。其定义如下：

\begin{lstlisting}[language=Haskell]
  class (Functor f) => Applicative f where
    pure :: a -> f a
    (<*>) :: f (a -> b) -> f a -> f b
\end{lstlisting}

这简单的三行告诉了我们很多东西！首先是第一行，定义\acode{Applicative}类，并引入了类约束，即\acode{Applicative} typeclass 的
构造函数中的类型首先必须的是一个\acode{Functor}，因为这样才能使用\acode{fmap}。

第一个定义的方法是\acode{pure}。其类型声明是\acode{pure :: a -> f a}。\acode{f}在这里就是高级函子的实例。其接受一个任意类型，
返回一个包含了该任意类型的高级函子。

一个更好理解\acode{pure}的方式就是它接受一个值，将该值放入某些默认（或纯）context 中 -- 这个最小的 context 仍然包含了这个值。

\acode{<*>}函数非常有趣，其类型声明是\acode{f (a -> b) -> f a -> f b}，这跟\acode{fmap :: (a -> b) -> f a -> f b}很像。
也就是一个增强版的\acode{fmap}。\acode{fmap}接受一个函数和函子，并将函数应用至函子内的值，而\acode{<*>}接受一个包含了函数的函子，
以及另一个函子，并类似于提取第一个函子中的函数应用至第二个函子中。

下面是\acode{Maybe}实现\acode{Applicative}的实例：

\begin{lstlisting}[language=Haskell]
  instance Applicative Maybe where
    pure = Just
    Nothing <*> _ = Nothing
    (Just f) <*> something = fmap f something
\end{lstlisting}

首先是\acode{pure}，这里的\acode{pure = Just}是因为\acode{Just}的值构造函数是普通函数，等同于\acode{pure x = Just x}。

其次是\acode{<*>}，我们不能从\acode{Nothing}中提取函数，因此其返回值就是\acode{Nothing}；如果是一个包含函数的\acode{Just}，
那么将该函数映射至第二个参数，这里第二个参数也有可能是\acode{Nothing}，不过\acode{fmap}任何函数至\acode{Nothing}也都会返回
\acode{Nothin}，因此无需多虑。

测试一下：

\begin{lstlisting}[language=Haskell]
  ghci> Just (+3) <*> Just 9
  Just 12
  ghci> pure (+3) <*> Just 10
  Just 13
  ghci> pure (+3) <*> Just 9
  Just 12
  ghci> Just (++"hahah") <*> Nothing
  Nothing
  ghci> Nothing <*> Just "woot"
  Nothing
\end{lstlisting}

普通的函子能将函数映射至函子本身，但是可能没法拿到结果；而高级函子则可以让你用单一一个函数操作好几个函子。比如：

\begin{lstlisting}[language=Haskell]
  ghci> pure (+) <*> Just 3 <*> Just 5
  Just 8
  ghci> pure (+) <*> Just 3 <*> Nothing
  Nothing
  ghci> pure (+) <*> Nothing <*> Just 5
  Nothing
\end{lstlisting}

这里发生了什么？让我们一步一步来看。\acode{<*>}是左关联的，意味着\acode{pure (+) <*> Just 3 <*> Just 5}等同于
\acode{(pure (+) <*> Just 3) <*> Just 5}。首先\acode{+}函数被放进了一个函子中，这个例子中就是\acode{Maybe}包含了该
函数，因此\acode{pure (+)}即是\acode{Just (+)}。其次\acode{Just (+) <*> Just 3}发生了，其结果为\acode{Just (3+)}，
这是因为部分应用，仅将\acode{3}应用至\acode{+}函数返回的是一个接受一个参数的函数。最后\acode{Just (3+) <*> Just 5}被
运算，结果就是\acode{Just 8}。

这很棒吧！用 applicative 风格来使用高级函子，如\acode{pure f <*> x <*> y <*> ...}就让我们可以哪一个接受多个参数的函数，
而且这些参数不一定是包在函子内的。这样套用多个在函子 context 的值，该函数可以消费任意多的参数，毕竟\acode{<*>}只是在做
部分应用而已。

如果考虑到\acode{pure f <*> x}等同于\acode{fmap f x}的话，这样的用法就更方便了。这是一条 applicative 定律，之后会进行
详细讲解。如果我们将一个函数置入默认 context 中，接着提取并应用至另一个一个高级函子中的值，那么这就跟映射一个函数至高级函子
一样。与其\acode{pure f <*> x <*> y <*> ...}，可以写作\acode{fmap f x <*> y <*> ...}。这就是为什么
\acode{Control.Applicative}导出了一个名为\acode{<\$>}的函数，它实际上就是一个中置版本的\acode{fmap}，其定义如下：

\begin{lstlisting}[language=Haskell]
  (<$>) :: (Functor f) => (a -> b) -> f a -> f b
  f <$> x = fmap f x
\end{lstlisting}

\begin{anote}
  快速提示：类型变量跟参数的名字还有值绑定的名称不冲突。\acode{f}在函数的类型声明中是类型变量，说明\acode{f}应该要满足
  \acode{Functor} typeclass 的条件。而在函数本体中的\acode{f}则表示一个函数，我们将它映射至\acode{x}。我们同样用
  \acode{f}来表示它们并代表它们是相同的东西。
\end{anote}

通过使用\acode{<\$>}，applicative 风格的好处就很显著了。如果将\acode{f}应用至三个高级函子，就可以这样
\acode{f <\$> x <*> y <*> z}。如果参数不是高级函子而是普通值，则是\acode{f x y z}。

让我们再看看它是如何工作的。我们有一个值\acode{Just "johntra"}以及一个值\acode{Just "volta"}，我们想要合并他们成为
一个在\acode{Maybe}函子内部的\acode{String}。我们可以这么做：

\begin{lstlisting}[language=Haskell]
  ghci> (++) <$> Just "johntra" <*> Just "volta"
  Just "johntravolta"
\end{lstlisting}

在正式讲解发生了什么之前，先比较一下：

\begin{lstlisting}[language=Haskell]
  ghci> (++) "johntra" "volta"
  "johntravolta"
\end{lstlisting}

可以将一个普通的函数应用在高级函子上真棒。只用写一些\acode{<\$>}以及\acode{<*>}就可以把函数变为 applicative 风格，操作
这些 applicatives 并返回一个 applicative。太酷了！

无论如何，当运算\acode{(++) <\$> Just "johntra" <*> Just "volta"}时，首先\acode{(++)}其类型是\acode{(++) :: [a]
-> [a] -> [a]}，映射至\acode{Just "johntra"}，返回值为\acode{Just ("johntra"++)}，类型为\acode{Maybe ([Char] ->
[Char])}。注意\acode{(++)}的第一个参数被吃掉了，即\acode{a}转换为\acode{Char}。接着是\acode{Just ("johntra"++)
  <*> Just "volta"}，从\acode{Just}提取出的函数并映射至\acode{Just "volta"}，得到\acode{Just "johntravolta"}。
这里只要任意一个值是\acode{Nothing}，那么得到的结果也是\acode{Nothing}。

列表（实际上说的是列表构造函数，\acode{[]}）也是高级函子。惊喜吧！下面是\acode{[]}如何作为\acode{Applicative}实例的：

\begin{lstlisting}[language=Haskell]
  instance Applicative [] where
    pure x = [x]
    fs <*> xs = [f x | f <- fs, x <- xs]
\end{lstlisting}

之前我们说\acode{pure}接受一个值并将其放入一个默认 context 中，或者说，一个最小 context 仍然包含该值。这里的最小 context
就是空列表，\acode{[]}，不过空列表并不包含一个值，所以我们没法将其当做\acode{pure}。这也是为什么\acode{pure}实际上是接受
一个值，然后返回一个带有单元素的列表。同样的，\acode{Maybe}的最小 context 是\acode{Nothing}，但它其实表示的是没有值，
所以\acode{pure}其实是被实现成了\acode{Just}。

\begin{lstlisting}[language=Haskell]
  ghci> pure "Hey" :: [String]
  ["Hey"]
  ghci> pure "Hey" :: Maybe String
  Just "Hey"
\end{lstlisting}

那么\acode{<*>}呢？如果我们假定\acode{<*>}的类型是限制在列表上的话，我们会得到\acode{(<*>) :: [a -> b]-> [a]  -> [b]}。
这是用列表表达式来实现的。\acode{<*>}必须以某种方式从左侧参数中提取函数并映射至右侧参数上。不过这里左侧列表可以是没有函数，
一个函数，或者多个函数；右侧列表也可以存储若干值。这就是为什么我们使用列表表达式从两方列表中取值。我们要将左侧列表中所有可能的函数
映射至右侧列表中所有可能的值。

\begin{lstlisting}[language=Haskell]
  ghci> [(*0),(+100),(^2)] <*> [1,2,3]
  [0,0,0,101,102,103,1,4,9]
\end{lstlisting}

左侧列表包含三个函数，而右侧列表有三个值，那么结果就是有九个元素的列表。左边列表的每个函数都应用在右侧列表的每个值。如果列表中的
函数接受两个参数，那么也可以应用到两个列表上：

\begin{lstlisting}[language=Haskell]
  ghci> [(+),(*)] <*> [1,2] <*> [3,4]
  [4,5,5,6,3,4,6,8]
\end{lstlisting}

这是因为\acode{<*>}是左关联的，即\acode{[(+),(*)] <*> [1,2]}会先运行，得到\acode{[(1+),(2+),(1*),(2*)]}，又因为左侧
列表中的每个函数都会应用至右边列表中的每个值，即\acode{[(1+),(2+),(1*),(2*)] <*> [3,4]}，最终结果如上所述。

列表的 applicative 风格是非常有趣的：

\begin{lstlisting}[language=Haskell]
  ghci> (++) <$> ["ha","heh","hmm"] <*> ["?","!","."]
  ["ha?","ha!","ha.","heh?","heh!","heh.","hmm?","hmm!","hmm."]
\end{lstlisting}

你可以认为列表是一个非确定性 non-deterministic 的计算。对于像\acode{100}或\acode{"what"}则是确定性 deterministic 计算，
即只有一个结果；而\acode{[1,2,3]}则可以看作是没有确定究竟是哪一种结果，也就是说它代表的是所有可能的结果。在运行
\acode{(+) <\$> [1,2,3] <*> [4,5,6]}时，可以视为两个非确定性的计算通过\acode{+}进行运算，只不过会产生另一个非确定性的计算，
而结果更加不确定。

Applicative 风格对于列表而言是一个取代列表表达式的好方法。第二章里计算\acode{[2,5,10]}与\acode{[8,10,11]}相乘的结果，需要：

\begin{lstlisting}[language=Haskell]
  ghci> [ x*y | x <- [2,5,10], y <- [8,10,11]]
  [16,20,22,40,50,55,80,100,110]
\end{lstlisting}

通过 applicative 风格改写：

\begin{lstlisting}[language=Haskell]
  ghci> (*) <$> [2,5,10] <*> [8,10,11]
  [16,20,22,40,50,55,80,100,110]
\end{lstlisting}

如果我们希望将两个列表中的所有乘积大于 50 的数找出来，仅需：

\begin{lstlisting}[language=Haskell]
  ghci> filter (>50) $ (*) <$> [2,5,10] <*> [8,10,11]
  [55,80,100,110]
\end{lstlisting}

可以看到列表的运算中，\acode{pure f <*> xs}等同于\acode{fmap f xs}。\acode{pure f}就是\acode{[f]}，以及
\acode{[f] <*> xs}将应用左侧列表中的每个函数至右侧列表中的每个值，但左边其实只有一个函数，所以看上去就像是 mapping。

另一个我们已经遇到的\acode{Applicative}实例就是\acode{IO}，其实现：

\begin{lstlisting}[language=Haskell]
  instance Applicative IO where
    pure = return
    a <*> b = do
        f <- a
        x <- b
        return (f x)
\end{lstlisting}

\acode{pure}将值放入最小 context 内，这里即\acode{return}，意味着一个 I/O action 不做任何事情，返回其包含的值，
但实际上并没有做任何 I/O 操作比如打印至终端或者文件读取。

而\acode{<*>}被限制在\acode{IO}上的话，它的类型就是\acode{<*> :: IO (a -> b) -> IO a -> IO b}，即接受一个生产
函数的 I/O action，以及另一个 I/O action，由它们创建一个新的 I/O action，也就是把第二个参数传给第一个参数，得到的
返回值放进新的 I/O action 中。注意\textit{do}语法就是将若干 I/O action 粘合成一个，这正是我们现在所做的。

通过\acode{Maybe}已经\acode{[]}，我们可以认为\acode{<*>}就是从其左参数中提取一个函数，再将该函数应用至右参数上。
而对于\acode{IO}，仍然是提取，不过带上了\textit{序列 sequencing}这个概念，因为接受两个 I/O actions 顺序执行，或者
说是粘合成为一个 I/O action。从第一个 I/O action 中取值，但要取出 I/O action 的结果，因此它必须先被执行。

例如：

\begin{lstlisting}[language=Haskell]
  myAction :: IO String
  myAction = do
      a <- getLine
      b <- getLine
      return $ a ++ b
\end{lstlisting}

这个 I/O action 提示用户输入两行在返回合并的两行。达到这个目的就是将两个\acode{getLine} I/O actions 粘合在一起后
使用\acode{return}。而使用 applicative 可以这样写：

\begin{lstlisting}[language=Haskell]
  myAction :: IO String
  myAction = (++) <$> getLine <*> getLine
\end{lstlisting}

表达式\acode{(++) <\$> getLine <*> getLine}的类型是\acode{IO String}，意味着该表达式跟别的 I/O action 完全
一样，因此可以这么做：

\begin{lstlisting}[language=Haskell]
  main = do
    a <- (++) <$> getLine <*> getLine
    putStrLn $ "The two lines concatenated turn out to be: " ++ a
\end{lstlisting}

另一个\acode{Applicative}实例就是\acode{(->) r}：

\begin{lstlisting}[language=Haskell]
  instance Applicative ((->) r) where
    pure x = (\_ -> x)
    f <*> g = \x -> f x (g x)
\end{lstlisting}

\acode{pure}接受值，创建一个忽视入参且将该值作为返回的函数，即\acode{pure :: a -> (r -> a)}。

\begin{lstlisting}[language=Haskell]
  ghci> (pure 3) "blah"
  3
\end{lstlisting}

因为有柯里化，函数应用时左关联的，所以可以省略括号：

\begin{lstlisting}[language=Haskell]
  ghci> pure 3 "blah"
  3
\end{lstlisting}

而\acode{<*>}的实现则有点神秘，让我们看看作为高级函子如何使用该函数：

\begin{lstlisting}[language=Haskell]
  ghci> :t (+) <$> (+3) <*> (*100)
  (+) <$> (+3) <*> (*100) :: (Num a) => a -> a
  ghci> (+) <$> (+3) <*> (*100) $ 5
  508
\end{lstlisting}

两个高级函子输入\acode{<*>}返回一个高级函子，所以如果输入两个函数，则得到一个新的函数。这里发生了什么？当使用
\acode{(+) <\$> (+3) <*> (*100)}时，我们在创造一个函数，该函数会将\acode{(+3)}以及\acode{(*100)}的结果，
应用\acode{+}，再进行返回，即\acode{5}给到\acode{(+3)}以及\acode{(*100)}，得到\acode{8}与\acode{500}后，
将\acode{+}应用至\acode{8}与\acode{500}，得\acode{508}。再比如：

\begin{lstlisting}[language=Haskell]
  ghci> (\x y z -> [x,y,z]) <$> (+3) <*> (*2) <*> (/2) $ 5
  [8.0,10.0,2.5]
\end{lstlisting}

这里也一样。创建一个将会调用\acode{\\x y z -> [x,y,z]}函数的函数，输入的参数是\acode{(+3)}，\acode{(*2)}，
以及\acode{(/2)}。\acode{5}则被分别输入进这三个函数中，接着调用\acode{\\x y z -> [x,y,z]}得到结果。

我们可以认为函数作为盒子包含着它们最终的结果，因此\acode{k <\$> f <*> g}创建了一个将最终会对\acode{f}与
\acode{g}的结果而调用\acode{k}的函数。

另一个我们还没遇到过的\acode{Applicative}实例就是\acode{ZipList}，它位于\acode{Control.Applicative}模块中。

实际上列表要作为一个高级函子可以有很多种方式。已经介绍过的一种就是应用\acode{<*>}，左参是若干函数，右参则是若干值，
结果这是函数应用于所有值后的所有组合。例如\acode{[(+3),(*2)] <*> [1,2]}，\acode{(+3)}会先应用至\acode{1}与
\acode{2}，接着再是\acode{(*2)}应用至\acode{1}与\acode{2}，最终得\acode{[4,5,2,4]}。

而\acode{[(+3),(*2)] <*> [1,2]}理论上也可以将左参第一个函数应用至右参第一个值，再将左参第二个函数应用至右参的
第二个值，以此类推。

由于一个类型不能对同个 typeclass 定义两个实例，因此才有\acode{ZipList a}，它只有一个构造函数\acode{ZipList}，
一个字段，它的类型是列表：

\begin{lstlisting}[language=Haskell]
  instance Applicative ZipList where
    pure x = ZipList (repeat x)
    ZipList fs <*> ZipList xs = ZipList (zipWith (\f x -> f x) fs xs)
\end{lstlisting}

\acode{<*>}就是上面说的顺序应用，这是通过\acode{zipWith (\\f x -> f x) fs xs}实现的。又因为\acode{zipWith}
的原理，返回的列表长度由输入的列表中最短的那个决定。

\acode{pure}在这里同样有趣。它接受一个值，将其置入一个无限循环该值的列表中，例如\acode{pure "haha"}在这里返回
\acode{ZipList (["haha", "haha", "haha" ...)}。这里可能会令人迷惑，之前我们说过\acode{pure}是把一个值放入
最小的 context 中，而无限长的列表不可能会是一个最小的 context。然而这对 zip 列表来说很合理，因为它必须在列表的
每个位置都有值。这也遵守了\acode{pure f <*> xs}必须要等价于\acode{fmap f xs}的特性。

那么 zip 列表是如何用 applicative 风格运作的呢？\acode{ZipList a}类型并没有\acode{Show}实例，因此我们需要使用
\acodered{getZipList}函数从一个 zip 列表中提取出一个原始列表。

\begin{lstlisting}[language=Haskell]
  ghci> getZipList $ (+) <$> ZipList [1,2,3] <*> ZipList [100,100,100]
  [101,102,103]
  ghci> getZipList $ (+) <$> ZipList [1,2,3] <*> ZipList [100,100..]
  [101,102,103]
  ghci> getZipList $ max <$> ZipList [1,2,3,4,5,3] <*> ZipList [5,3,1,2]
  [5,3,3,4]
  ghci> getZipList $ (,,) <$> ZipList "dog" <*> ZipList "cat" <*> ZipList "rat"
  [('d','c','r'),('o','a','a'),('g','t','t')]
\end{lstlisting}

\begin{anote}
  \acode{(,,)}函数等同于\acode{\\x y z -> (x,y,z)}。同样的\acode{(,)}函数等同于\acode{\\x y -> (x,y)}。
\end{anote}

除了\acode{zipWith}，标准库还提供了\acode{zipWith3}，\acode{zipWith4}，一直到 7。

\acode{Control.Applicative}定义了一个名为\acode{liftA2}的函数，其定义如下：

\begin{lstlisting}[language=Haskell]
  liftA2 :: (Applicative f) => (a -> b -> c) -> f a -> f b -> f c
  liftA2 f a b = f <$> a <*> b
\end{lstlisting}

没什么特别的，它就是将一个函数应用在两个高级函子上，并没有用我们才熟悉的 applicative 风格。提及它是因为为什么高级函子
要比普通的函子强。如果只是普通的函子，我们只能将一个函数映射在一个函子上，而对于高级函子而言，可以将一个函数映射在若干
高级函子上。另一件有趣的事情就是\acode{liftA2}的类型，其接受一个普通的二元函数，将其提升为可运作在两个函子上的函数。

这里有个有趣的概念：我们可以将两个高级函子合成为一个高级函子，而新的这个高级函子则将两个函子装在列表中。例如我们有
\acode{Just 3}与\acode{Just 4}，假设后者是一个单例列表：

\begin{lstlisting}[language=Haskell]
  ghci> fmap (\x -> [x]) (Just 4)
  Just [4]
\end{lstlisting}

那么我们有\acode{Just 3}与\acode{Just [4]}，我们如何得到\acode{Just [3, 4]}呢？很简单：

\begin{lstlisting}[language=Haskell]
  ghci> liftA2 (:) (Just 3) (Just [4])
  Just [3,4]
  ghci> (:) <$> Just 3 <*> Just [4]
  Just [3,4]
\end{lstlisting}

\acode{:}是一个函数，它接受一个元素与一个列表，返回一个新的列表，而接受的元素位于新列表的头部。现在有了
\acode{Just [3,4]}，那么再将它跟\acode{Just 2}绑定在一起就能变为\acode{Just [2,3,4]}了。我们可以将任意数量的
高级函子绑在一起成为一个新的高级函子，其中包含了装有结果的列表。让我们尝试着实现一个函数，接受一个列表的高级函子，并
返回一个高级函子，其中包含了结果的列表：

\begin{lstlisting}[language=Haskell]
  sequenceA' :: (Applicative f) => [f a] -> f [a]
  sequenceA' [] = pure []
  sequenceA' (x : xs) = (:) <$> x <*> sequenceA' xs
\end{lstlisting}

哈，递归！首先将一个列表的高级函子转换成一个装有列表的高级函子。以此我们可以推测出边界调节。如果将一个空的列表变成一个
装有列表的高级函子，只需要将该空列表放进一个默认的 context。现在看一下如何递归。如果我们有一个有头尾的列表（这里的
\acode{x}是一个高级函子，而\acode{xs}是一个列表的高级函子），只需再次对尾部调用\acode{sequenceA'}，即得到一个
装有列表的高级函子。接着将高级函子\acode{x}中的值添加至装有高级函子的列表头部即可，就这么简单！

例如\acode{sequenceA' [Just 1, Just 2]}则是\acode{(:) <\$> Just 1 <*> sequenceA [Just 2]}，等同于
\acode{(:) <\$> Just 1 <*> ((:) <\$> sequenceA' [])}，这里的\acode{sequenceA' []}就是\acode{Just []}，
那么表达式现在就是\acode{(:) <\$> Just 1 <*> ((:) <\$> Just 2 <*> Just [])}，即\acode{(:) <\$> Just 1
  <*> Just [2]}，得\acode{Just [1,2]}！

另外就是通过 fold 来实现\acode{sequenceA'}了：

\begin{lstlisting}[language=Haskell]
  sequenceA' :: (Applicative f) => [f a] -> f [a]
  sequenceA' = foldr (\x -> (<*>) ((:) <$> x)) (pure [])
\end{lstlisting}

测试：

\begin{lstlisting}[language=Haskell]
  ghci> sequenceA' [Just 3, Just 2, Just 1]
  Just [3,2,1]
  ghci> sequenceA' [Just 3, Nothing, Just 1]
  Nothing
  ghci> sequenceA' [(+3),(+2),(+1)] 3
  [6,5,4]
  ghci> sequenceA' [[1,2,3],[4,5,6]]
  [[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]
  ghci> sequenceA' [[1,2,3],[4,5,6],[3,4,4],[]]
  []
\end{lstlisting}

太酷了。当应用在\acode{Maybe}上时，\acode{sequenceA'}创造一个新的\acode{Maybe}，其中包含了一个装有所有结果的列表。
如果其中一个值是\acode{Nothing}，那整个结果就会是\acode{Nothing}。

当应用在函数时\acode{sequenceA'}接受一堆函数的列表，并返回一个返回为列表的函数。

执行\acode{(+) <\$> (+3) <*> (*2)}将创建一个接受单一参数的函数，将\acode{(+3)}与\acode{(*2)}应用至该单一参数，
最后调用\acode{+}将两者相加。同理，\acode{sequenceA' [(+3),(*2)]}则创建一个接受单一参数的函数，将列表中的每个函数
都应用至该单一参数，最后用\acode{:}将它们装进一个列表中。

当我们有一个列表的函数时，想将相同的参数都输入给这些函数时，\acode{sequenceA'}就非常好用。例如，有一个数值，我们不知道
其是否满足一系列的判断，那么就可以这样：

\begin{lstlisting}[language=Haskell]
  ghci> map (\f -> f 7) [(>4),(<10),odd]
  [True,True,True]
  ghci> and $ map (\f -> f 7) [(>4),(<10),odd]
  True
\end{lstlisting}

下面代码展示了在列表表达式中使用\acode{sequenceA'}：

\begin{lstlisting}[language=Haskell]
  ghci> sequenceA [[1,2,3],[4,5,6]]
  [[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]
  ghci> [[x,y] | x <- [1,2,3], y <- [4,5,6]]
  [[1,4],[1,5],[1,6],[2,4],[2,5],[2,6],[3,4],[3,5],[3,6]]
  ghci> sequenceA [[1,2],[3,4]]
  [[1,3],[1,4],[2,3],[2,4]]
  ghci> [[x,y] | x <- [1,2], y <- [3,4]]
  [[1,3],[1,4],[2,3],[2,4]]
  ghci> sequenceA [[1,2],[3,4],[5,6]]
  [[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]
  ghci> [[x,y,z] | x <- [1,2], y <- [3,4], z <- [5,6]]
  [[1,3,5],[1,3,6],[1,4,5],[1,4,6],[2,3,5],[2,3,6],[2,4,5],[2,4,6]]
\end{lstlisting}

可能会有点难以理解，让我们首先来看\acode{sequenceA [[1,2],[3,4]]}，根据定义\acode{sequenceA (x : xs) =
  (:) <\$> x <*> sequenceA xs}以及边界条件\acode{sequenceA [] = pure []}来进行拆解：

\begin{enumerate}
  \item 首先是\acode{sequenceA [[1,2],[3,4]]}；
  \item 计算得\acode{(:) <\$> [1,2] <*> sequenceA [[3,4]]}；
  \item 接着计算内部的\acode{sequenceA}，得\acode{(:) <\$> [1,2] <*> ((:) <\$> [3,4] <*> sequenceA [])}；
  \item 这里碰到了边界条件，即\acode{(:) <\$> [1,2] <*> ((:) <\$> [3,4] <*> [[]])}
  \item 首先计算\acode{(:) <\$> [3,4] <*> [[]]}部分，将左列表中每个元素应用\acode{:}（即\acode{3}与\acode{4}）
        以及右列表的每个元素（即\acode{[]}），得到\acode{3:[], 4:[]}，即\acode{[3],[4]}。代入上条表达式即
        \acode{(:) <\$> [1,2] <*> [[3],[4]]}；
  \item 接下来同理，\acode{:}应用在左列表的每个元素（\acode{1}与\acode{2}）以及右列表的每个元素（\acode{[3]}与
        \acode{[4]}），得\acode{[1:[3],1:[4],2:[3],2:[4]]}，即\acode{[[1,3],[1,4],[2,3],[2,4]]}。
\end{enumerate}

计算\acode{(+) <\$> [1,2] <*> [4,5,6]}会得到一个非确定性的结果\acode{x + y}，其中\acode{x}代表\acode{[1,2]}中的
每个值，而\acode{y}代表\acode{[4,5,6]}中的每个值。我们用列表表示每一种可能的情况。同样的在计算\acode{sequence
    [[1,2],[3,4],[5,6],[7,8]]}时，它的结构会是非确定性的\acode{[x,y,z,w]}，其中\acode{x}代表\acode{[1,2]}中的
每个值，而\acode{y}代表\acode{[3,4]}中的每个值，以此类推。我们使用列表来代表非确定性的计算，每个元素都是一个可能的情况，
这也是为什么这里使用了列表的列表。

处理 I/O actions 时，\acode{sequenceA}的效果与\acode{sequence}一样！

\begin{lstlisting}[language=Haskell]
  ghci> sequenceA [getLine, getLine, getLine]
  heyh
  ho
  woo
  ["heyh","ho","woo]
\end{lstlisting}

与普通函子一样，高级函子也有一些定理。最重要的定理我们已经提到了，即满足\acode{pure f <*> x = fmap f x}，其他的还有：

\begin{enumerate}
  \item \acodegrn{pure id <*> v = v}
  \item \acodegrn{pure (.) <*> u <*> v <*> w = u <*> (v <*> w)}
  \item \acodegrn{pure f <*> pure x = pure (f x)}
  \item \acodegrn{u <*> pure y = pure (\$ y) <*> u}
\end{enumerate}

总结一下，高级函子不仅有趣还非常的实用，它允许我们结合不同种类的计算，例如 I/O 计算，非确定性结果的计算，有可能失败的计算等等。
使用\acode{<\$>}与\acode{<*>}，可以将普通的函数来运作在任意数量的高级函子上。

\subsection*{newtype 关键字}

目前为止我们知道了如何使用\acode{data}关键字来定义属于自己的代数数据类型，我们也学习了如何用\acode{type}来定义类型同义词。
本节我们将会学习如何使用\acode{newtype}从一个现有的类型定义出新的类型，并说明为什么这么做。

上一节中，我们见识到了多种方式使得列表类型成为高级函子。一种方式是用\acode{<*>}从左列表中获取每个函数并应用至右列表中的每个
元素，返回所有可能的组合：

\begin{lstlisting}[language=Haskell]
  ghci> [(+1),(*100),(*5)] <*> [1,2,3]
  [2,3,4,100,200,300,5,10,15]
\end{lstlisting}

另一种方式是左右列表的顺序应用，最终就像是将两个列表 zip 起来。而列表已经实现了\acode{Applicative}实例，因此我们的做法是
引入\acode{ZipList a}类型，其包含一个值构造函数，\acode{ZipList}：

\begin{lstlisting}[language=Haskell]
  ghci> getZipList $ ZipList [(+1),(*100),(*5)] <*> ZipList [1,2,3]
  [2,200,15]
\end{lstlisting}

那么这个\textit{newtype}关键字有关系吗？我们可能会将\acode{ZipList a}类型这样定义：

\begin{lstlisting}[language=Haskell]
  data ZipList a = ZipList [a]
\end{lstlisting}

这样一个类型仅有一个值构造函数，且该构造函数只有一个字段，即列表的某值。同样我们可能会使用 record 语法，这样就可以自动获得
一个从\acode{ZipList}中提取列表的函数出来：

\begin{lstlisting}[language=Haskell]
  data ZipList a = ZipList { getZipList :: [a] }
\end{lstlisting}

这看起来不错，实际上也能很好的工作。使用\textit{data}关键字包装改类型成为另一个类型，然后将新的这个类型成为 typeclass 的
实例，这样便是第二种做法。

Haskell 中的\textit{newtype}实际上就是用作于此。在实际的库中，\acode{ZipList a}的定义如下：

\begin{lstlisting}[language=Haskell]
  newtype ZipList a = ZipList { getZipList :: [a] }
\end{lstlisting}

没有使用\textit{data}关键字，而是使用了\acode{newtype}。为什么这么做呢？首先\textit{newtype}更快，如果使用的是
\textit{data}关键字来包装一个类型，那么程序运行时进包与出包都会带来性能损失。但是使用\textit{newtype}时，Haskell 知道
你使用的是现有类型包装后的新类型（正如其名），因为你想要的是同样的内核，而又不同的类型。

那么为什么不总是使用\textit{newtype}而还有\textit{data}呢？因为\textit{data}可以有若干值构造函数，而每个构造函数又
可以拥有零个或多个字段：

\begin{lstlisting}[language=Haskell]
  data Profession = Fighter | Archer | Accountant

  data Race = Human | Elf | Orc | Goblin

  data PlayerCharacter = PlayerCharacter Race Profession
\end{lstlisting}

而\textit{newtype}就被限制在了一个字段的构造函数。

就像是\textit{data}那样，对于\textit{newtype}我们也可以使用\textit{deriving}关键字。

\begin{lstlisting}[language=Haskell]
  newtype CharList = CharList { getCharList :: [Char] } deriving (Eq, Show)
\end{lstlisting}

\begin{lstlisting}[language=Haskell]
  ghci> CharList "this will be shown!"
  CharList {getCharList = "this will be shown!"}
  ghci> CharList "benny" == CharList "benny"
  True
  ghci> CharList "benny" == CharList "oisters"
  False
\end{lstlisting}

这个特定的\textit{newtype}，值构造函数的类型是：

\begin{lstlisting}[language=Haskell]
  CharList :: [Char] -> CharList
\end{lstlisting}

相反的，被生成出来的\acode{getCharList}函数其类型为：

\begin{lstlisting}[language=Haskell]
  getCharList :: CharList -> [Char]
\end{lstlisting}

它接受一个\acode{CharList}值并转换为一个\acode{[Char]}值。可以把这个想象成包装和解包，也可以认为将值从一个类型转换为
另一个类型。

\subsubsection*{使用 newtype 来实现 typeclass 实例}

很多时候会想要将我们的类型属于某个 typeclass，但是类型变量并没有符合我们想要的。把\acode{Maybe}定义成\acode{Functor}
很容易，因为\acode{Functor}的 typeclass 定义：

\begin{lstlisting}[language=Haskell]
  class Functor f where
    fmap :: (a -> b) -> f a -> f b
\end{lstlisting}

我们开始：

\begin{lstlisting}[language=Haskell]
  instance Functor Maybe where
\end{lstlisting}

接着实现\acode{fmap}。所有的类型参数被填上，由于\acode{Maybe}取代了\acode{Functor}中\acode{f}的位置，所以如果我们
看看\acode{fmap}应用在\acode{Maybe}上时是什么样子时，它会是这样：

\begin{lstlisting}[language=Haskell]
  fmap :: (a -> b) -> Maybe a -> Maybe b
\end{lstlisting}

现在想让元组成为\acode{Functor}的一个实例时，用\acode{fmap}应用在这个元组，则会应用到该元组的第一个元素。例如
\acode{fmap (+3) (1,1)}会得到\acode{4,1}。对于\acode{Maybe}，只需要\acode{instance Functor Maybe where}，
这是因为对于\textbf{}{只消费一个参数}的类型构造函数很容易定义成\acode{Functor}的实例，但是对于\acode{(a,b)}这样的
有若干个参数类型的就没办法。我们可以使用\acode{newtype}来重新定义元组，使得第二个类型参数代表了元组中的第一个元素部分。

\begin{lstlisting}[language=Haskell]
  newtype Pair b a = Pair { getPair :: (a,b)}
\end{lstlisting}

接着定义\acode{Functor}的实例，函数被映射到元组的第一个部分：

\begin{lstlisting}[language=Haskell]
  instance Functor (Pair c) where
    fmap f (Pair (x,y)) = Pair (f x, y)
\end{lstlisting}

如你所见，可以对 \textit{newtype} 进行模式匹配，接着将函数\acode{f}应用至元组的第一部分，再使用\acode{Pair}值构造函数
将元组转回\acode{Pair b a}。\acode{fmap}的类型则会是：

\begin{lstlisting}[language=Haskell]
  fmap :: (a -> b) -> Pair c a -> Pair c b
\end{lstlisting}

我们说\acode{instance Functor (Pair c) where}以及\acode{Pair c}取代了\acode{Functor} typeclass \acode{f}的
位置：

\begin{lstlisting}[language=Haskell]
  class Functor f where
    fmap :: (a -> b) -> f a -> f b
\end{lstlisting}

现在如果转换一个元组为\acode{Pair b a}，则可以使用\acode{fmap}，同时函数将映射到第一部分：

\begin{lstlisting}[language=Haskell]
  ghci> getPair $ fmap (*100) (Pair (2,3))
  (200,3)
  ghci> getPair $ fmap reverse (Pair ("london calling", 3))
  ("gnillac nodnol",3)
\end{lstlisting}

\subsubsection*{newtype 的惰性}

我们提到过\textit{newtype}通常比\textit{data}要快，而\textit{newtype}唯一能做的事情就是将现有的类型转换成一个新的
类型，也就是说 Haskell 将通过\textit{newtype}所定义类型视为原始类型。这也意味着\textit{newtype}不仅更快，它还是惰性的。

之前提到过 Haskell 默认是惰性的，意味着计算只有要在打印函数的结果时才会发生，或者说只有当真正需要结果的时候才会进行计算。
在 Haskell 中\acode{undefined}代表会造成错误的计算，如果试着计算它，也就是将其打印至终端，Haskell 会抛出异常：

\begin{lstlisting}[language=Haskell]
  ghci> undefined
  *** Exception: Prelude.undefined
\end{lstlisting}

而我们构建一个列表，其中包含一些\acode{undefined}的值，且第一个不为\acode{undefined}时使用\acode{head}，那一切都会被
顺利的计算，因为 Haskell 不需要列表中其他元素来得出结果：

\begin{lstlisting}[language=Haskell]
  ghci> head [3,4,5,undefined,2,undefined]
  3
\end{lstlisting}

考虑以下类型：

\begin{lstlisting}[language=Haskell]
  data CoolBool = CoolBool { getCoolBool :: Bool }
\end{lstlisting}

这是一个使用\acode{data}关键字定义的代数数据类型，其包含一个值构造函数且只有一个类型为\acode{Bool}的字段。编写一个函数用于
模式匹配\acode{CoolBool}并返回\acode{"hello"}，无论里面的\acode{Bool}是否为真：

\begin{lstlisting}[language=Haskell]
  helloMe :: CoolBool -> String
  helloMe (CoolBool _) = "hello"
\end{lstlisting}

将其应用至\acode{undefined}：

\begin{lstlisting}[language=Haskell]
  ghci> helloMe undefined
  "*** Exception: Prelude.undefined
\end{lstlisting}

这里为什么又要抛出异常呢？通过\textit{data}关键字所定义的类型可以拥有若干值构造函数，为了检查给与的函数是否匹配
\acode{CoolBool _}模式，在构造值的时候 Haskell 必须计算值才知道值构造函数是否被使用。当计算\acode{undefined}值时，立刻
抛出异常。

不使用\acode{data}来定义\acode{CoolBool}而是\acode{newtype}时：

\begin{lstlisting}[language=Haskell]
  newtype CoolBool = CoolBool {getCoolBool :: Bool}
\end{lstlisting}

\begin{lstlisting}[language=Haskell]
  ghci> helloMe undefined
  "hello"
\end{lstlisting}

能正常工作！这是为什么呢？正如之前所说的，使用\textit{newtype}时 Haskell 内部可以将新的类型用旧的类型来表示。无需再套一层
包装，只需要注意它们是不同的类型即可。又因为 Haskell 知道通过\textit{newtype}关键字所创建的类型仅可以拥有一个构造函数，
它无需计算传入至构造函数的值用于确保\acode{(CoolBool _)}的模式，因为\textit{newtype}类型仅允许值构造函数有一个字段。

\subsubsection*{type vs newtype vs data}

快速复习一下\acode{type}，\acode{data}以及\acode{newtype}。

\acode{type}关键字用于类型同义词，代表给予现有类型另一个名字：

\begin{lstlisting}[language=Haskell]
  type IntList = [Int]
\end{lstlisting}

这样可以允许我们使用\acode{IntList}的名称来代指\acode{[Int]}。两者可交换使用，但并不会因此有一个\acode{IntList}的值
构造函数，因为它们只是两种称呼同一个类型的方式，并不在乎用那个名称：

\begin{lstlisting}[language=Haskell]
  ghci> ([1,2,3] :: IntList) ++ ([1,2,3] :: [Int])
  [1,2,3,1,2,3]
\end{lstlisting}

当我们想让类型签名更加清晰，给予我们跟了解函数的 context 时，则可以定义类型同义词。

\acode{newtype}关键字则是将现有的类型包装成一个新的类型，大部分是为了要让它们可以是特定的 typeclass 的实例。当使用
\acode{newtype}来包装一个现有的类型是，这个类型与原有类型是分开的。

\begin{lstlisting}[language=Haskell]
  newtype CharList = CharList { getCharList :: [Char] }
\end{lstlisting}

我们不能用\acode{++}将\acode{CharList}与\acode{[Char]}拼接在一起，也不能用\acode{++}来将两个\acode{CharList}
拼接在一起，这是因为\acode{++}只能应用在列表上，而\acode{CharList}并不是列表。

当我们在\acode{newtype}声明中使用 record 语法的时候，我们会得到将新的类型转换成旧的类型的函数。

最后使用\acode{data}关键字是为了定义自己的类型，它们可以在代数数据结构中放任意数量的构造函数。

\subsection*{幺半群 Monoids}

Haskell 中的 typeclass 用于表示类型某些公共行为的接口。

\acode{*}是一个函数接受两个数值并使它们相乘。如果某数相乘的是\acode{1}，那么结果还是某数其本身，无论是\acode{1 * x}
还是\acode{x * 1}。同样的，\acode{++}是一个接受两个列表并结合它们的函数。与\acode{*}一样，一个列表在结合空列表
\acode{[]}的情况下并不会改变列表自身。

看起来\acode{*}与\acode{1}以及\acode{++}与\acode{[]}都有共同的属性：

\begin{enumerate}
  \item 函数接受两个参数。
  \item 入参与返回值的类型相同。
  \item 在使用二元函数时，存在一个值不会改变另一个值。
\end{enumerate}

这两个操作还有共性的地方就是：当拥有若干值时，使用二元函数将这些值变为一个，计算顺序并不影响结果：

\begin{lstlisting}[language=Haskell]
  ghci> (3 * 2) * (8 * 5)
  240
  ghci> 3 * (2 * (8 * 5))
  240
  ghci> "la" ++ ("di" ++ "da")
  "ladida"
  ghci> ("la" ++ "di") ++ "da"
  "ladida"
\end{lstlisting}

我们称这个属性为\textit{结合律 associativity}。\acode{*}满足结合律，\acode{++}也是。而\acode{-}不是，例如
\acode{(5 - 3) - 4}以及\acode{5 - (3 - 4)}的结果并不一致。

这些属性就是\textit{幺半群 monoids}！一个幺半群就是有一个遵守结合律的二元函数，以及有一个可以相对那个函数作为
identity 的值。一个相对于一个函数的 identity 意为函数在调用它与另一个值时，结果永远是另一个值。看看幺半群是如何
定义的：

\begin{lstlisting}[language=Haskell]
  class Monoid m where
    mempty :: m
    mappend :: m -> m -> m
    mconcat :: [m] -> m
    mconcat = foldr mappend mempty
\end{lstlisting}

\acode{Monoid} typeclass 定义于\acode{import Data.Monoid}。现在让我们花点时间来熟悉它。

首先可以看到只有具体类型才可以作为\acode{Monoid}的实例，因为\acode{m}并不接受任何类型参数。这与\acode{Functor}
以及\acode{Applicative}不同，后两者的实例需要的是接受一个参数的类型构造函数。

第一个函数\acode{mempty}。其实它并不是一个函数，因为它不接受参数，因此它是一个多态的常数，类似于\acode{Bounded}的
\acode{minBound}，\acode{mempty}代表着特定幺半群的 identity 值。

接下来就是\acode{mappend}，一个接受两个同类型值并返回同类型结果的二元函数。值得注意的是它的名字不太符合它真正的意思，
它的名字隐含了要将两个东西连接在一起。

最后一个函数\acode{mconcat}。它接受一个列表的幺半群值，并将它们用\acode{mappend}简化成单一的值。它有一个默认的
实现，就是从\acode{mempty}作为起始值，然后用\acode{mappend}进行 fold。对于大部分的实例而言默认实现没什么问题，
我们也不会想要实现自己的\acode{mconcat}。当我们定义一个类型属于\acode{Monoid}时，大多数时候实现\acode{mempty}
与\acode{mappend}就够了，而\acode{mconcat}对于某些实例，有可能会有更高效的方式才需要自己去实现。

继续下去之前我们来看一下幺半群的定理。我们提到过必须要有一个值可作为对应二元函数的 identity 值，且该二元函数必须是
满足结合律的。构造一个\acode{Monoid}实例却不遵守这些规则，这样的实例对任何人都没有用，因为使用\acode{Monoid}
typeclass，我们依靠的就是幺半群的定理。不然的话，这么做的意义就没有了。所以我们必须确保它们遵循：

\begin{enumerate}
  \item \acodegrn{mempty `mappend` x = x}
  \item \acodegrn{x `mappend` mempty = x}
  \item \acodegrn{(x `mappend` y) `mappend` z = x `mappend` (y `mappend` z)}
\end{enumerate}

\subsubsection*{列表是幺半群}

列表的幺半群实例非常的简单：

\begin{lstlisting}[language=Haskell]
  instance Monoid [a] where
    mempty = []
    mappend = (++)
\end{lstlisting}

列表是\acode{Monoid} typeclass 的一个实例，无论其内部的元素类型。注意写的时候是\acode{instance Monoid [a]}而
不是\acode{instance Monoid []}，因为\acode{Monoid}需要一个具体类型作为实例。

测试：

\begin{lstlisting}[language=Haskell]
  ghci> [1,2,3] `mappend` [4,5,6]
  [1,2,3,4,5,6]
  ghci> ("one" `mappend` "two") `mappend` "tree"
  "onetwotree"
  ghci> "one" `mappend` ("two" `mappend` "tree")
  "onetwotree"
  ghci> "one" `mappend` "two" `mappend` "tree"
  "onetwotree"
  ghci> "pang" `mappend` mempty
  "pang"
  ghci> mconcat [[1,2],[3,6],[9]]
  [1,2,3,6,9]
  ghci> mempty :: [a]
  []
\end{lstlisting}

注意最后一行，我们需要显式的类型注解，如果仅仅是\acode{mempty}，GHCI 并不会知道使用哪个实例，因此我们需要宣称希望的
是列表实例。

注意幺半群不需要\acode{a `mappend` b}等同于\acode{b `mappend` a}。列表显然不满足：

\begin{lstlisting}[language=Haskell]
  ghci> "one" `mappend` "two"
  "onetwo"
  ghci> "two" `mappend` "one"
  "twoone"
\end{lstlisting}

\subsubsection*{\acode{Product}与\acode{Sum}}

我们已经验证了数值被视为幺半群，只需要二元函数是\acode{*}以及 identity 值是\acode{1}。实际上这并不是唯一的办法将数值
视为幺半群。另一个方法就是\acode{+}以及 identity 值\acode{0}：

\begin{lstlisting}[language=Haskell]
  ghci> 0 + 4
  4
  ghci> 5 + 0
  5
  ghci> (1 + 3) + 5
  9
  ghci> 1 + (3 + 5)
  9
\end{lstlisting}

幺半群定理成立。

\acode{Data.Monoid}模块为此提供了两种类型，即\acode{Product}以及\acode{Sum}。\acode{Product}定义如下：

\begin{lstlisting}[language=Haskell]
  newtype Product a =  Product { getProduct :: a }
    deriving (Eq, Ord, Read, Show, Bounded)
\end{lstlisting}

简单，就是一个\textit{newtype}包装了一个类型参数同时带有一些衍生实例。其\acode{Monoid}实例有点像这样：

\begin{lstlisting}[language=Haskell]
  instance Num a => Monoid (Product a) where
    mempty = Product 1
    Product x `mappend` Product y = Product (x * y)
\end{lstlisting}

\acode{mempty}是一个包装在\acode{Product}构造函数中的\acode{1}。\acode{mappend}模式匹配\acode{Product}构造函数，
将两值相乘后再包装回\acode{Product}。如你所见，还有\acode{Num a}类约束，意味着\acode{Product a}要在所有\acode{a}
都是\acode{Num}实例的情况下才能是\acode{Monoid}的实例。那么作为一个幺半群来使用\acode{Product a}，我们就需要做一下
\textit{newtype}的包装和解包：

\begin{lstlisting}[language=Haskell]
  ghci> getProduct $ Product 3 `mappend` Product 9
  27
  ghci> getProduct $ Product 3 `mappend` mempty
  3
  ghci> getProduct $ Product 3 `mappend` Product 4 `mappend` Product 2
  24
  ghci> getProduct . mconcat . map Product $ [3,4,2]
  24
\end{lstlisting}

这是一个很好的\acode{Monoid} typeclass 的用例，不过没有人真的会这样将两值相乘。稍后我们会说明尽管这样显而易见的定义还是
有它方便的地方。

\acode{Sum}跟\acode{Product}定义的方式相似，也可以：

\begin{lstlisting}[language=Haskell]
  ghci> getSum $ Sum 2 `mappend` Sum 9
  11
  ghci> getSum $ mempty `mappend` Sum 3
  3
  ghci> getSum . mconcat . map Sum $ [1,2,3]
  6
\end{lstlisting}

\subsubsection*{\acode{Any}与\acode{All}}

另一个有两种行为像是幺半群的类型就是\acode{Bool}。第一个方式是\textit{or}函数\acode{||}作为二元函数以及\acode{False}
作为 identity 值。这样如果另一个值是\acode{True}那么返回的就是\acode{True}，如果是\acode{False}则返回\acode{False}。
\acode{Any}这个\textit{newtype}是\acode{Monoid}的一个实例，其定义如下：

\begin{lstlisting}[language=Haskell]
  newtype Any = Any { getAny :: Bool }
    deriving (Eq, Ord, Read, Show, Bounded)
\end{lstlisting}

其实例像是这样：

\begin{lstlisting}[language=Haskell]
  instance Monoid Any where
    mempty = Any False
    Any x `mappend` Any y = Any (x || y)
\end{lstlisting}

示例：

\begin{lstlisting}[language=Haskell]
  ghci> getAny $ Any True `mappend` Any False
  True
  ghci> getAny $ mempty `mappend` Any True
  True
  ghci> getAny . mconcat . map Any $ [False, False, False, True]
  True
  ghci> getAny $ mempty `mappend` mempty
  False
\end{lstlisting}

另一个\acode{Bool}表现为\acode{Monoid}的方式是\acode{&&}作为二元函数以及\acode{True}作为 identity 值。其
\textit{newtype}定义如下：

\begin{lstlisting}[language=Haskell]
  newtype All = All { getAll :: Bool }
    deriving (Eq, Ord, Read, Show, Bounded)
\end{lstlisting}

其实例：

\begin{lstlisting}[language=Haskell]
  instance Monoid All where
    mempty = All True
    All x `mappend` All y = All (x && y)
\end{lstlisting}

示例：

\begin{lstlisting}[language=Haskell]
  ghci> getAll $ mempty `mappend` All True
  True
  ghci> getAll $ mempty `mappend` All False
  False
  ghci> getAll . mconcat . map All $ [True, True, True]
  True
  ghci> getAll . mconcat . map All $ [True, True, False]
  False
\end{lstlisting}

\subsubsection*{\acode{Ordering}幺半群}

还记得\acode{Ordering}类型么？它是比较运算后得到的结果，其包含三个值：\acode{LT}，\acode{EQ}以及\acode{GT}：

\begin{lstlisting}[language=Haskell]
  ghci> 1 `compare` 2
  LT
  ghci> 2 `compare` 2
  EQ
  ghci> 3 `compare` 2
  GT
\end{lstlisting}

对于列表，数值以及布尔值而言，找到幺半群很容易，因为它们都是一些常见的函数以及一些幺半群行为。而对于\acode{Ordering}
而言，我们需要花点力气才能辨别一个幺半群，不过实际上它的\acode{Monoid}实例是非常符合直觉的：

\begin{lstlisting}[language=Haskell]
  instance Monoid Ordering where
    mempty = EQ
    LT `mappend` _ = LT
    EQ `mappend` y = y
    GT `mappend` _ = GT
\end{lstlisting}

这个实例这么运作：当\acode{mappend}两个\acode{Ordering}值时，左值被保留，除非左值是\acode{EQ}那么则会保留右值
作为结果。

例如如果我们逐字母比较单词\acode{"ox"}与\acode{"on"}，首先比较的是两个单词的首字母，看看它们是否相等然后再是第二个
字母，\acode{'x'}在字母表是大于\acode{'n'}的，因此前者比后者大。而\acode{EQ}是 identity 这个直觉，可以在插入
相同字母在两个单词的相同位置时，并不会改变字母表顺序得知。\acode{"oix"}仍然大于\acode{"oin"}。

值得注意的是作为\acode{Monoid}实例的\acode{Ordering}，\acode{x `mappend` y}不等于\acode{y `mappend` x}。
因为第一个参数是保留着的，除非是\acode{EQ}，\acode{LT `mappend` GT}得\acode{LT}，而\acode{GT `mappend` LT}
得\acode{GT}：

\begin{lstlisting}[language=Haskell]
  ghci> LT `mappend` GT
  LT
  ghci> GT `mappend` LT
  GT
  ghci> mempty `mappend` LT
  LT
  ghci> mempty `mappend` GT
  GT
\end{lstlisting}

好了，那么幺半群如何有用的呢？假设你在编写一个函数接受两个字符串，比较它们长度并返回一个\acode{Ordering}。如果两个
字符串的长度相等，那么我们希望按字母进行比较。一种方式：

\begin{lstlisting}[language=Haskell]
  lengthCompare :: String -> String -> Ordering
  lengthCompare x y =
    let a = length x `compare` length y
        b = x `compare` y
     in if a == EQ then b else a
\end{lstlisting}

先比较长度的结果为\acode{a}，再比较字典顺序的结果为\acode{b}，长度一样时，则返回字典顺序。

如果善用\acode{Ordering}是一种幺半群，那么可以简化函数：

\begin{lstlisting}[language=Haskell]
  lengthCompare :: String -> String -> Ordering
  lengthCompare x y = (length x `compare` length y) `mappend` (x `compare` y)
\end{lstlisting}

与原文不一样之处在于无须\acode{import Data.Monoid}。测试：

\begin{lstlisting}[language=Haskell]
  ghci> lengthCompare "zen" "ants"
  LT
  ghci> lengthCompare "zen" "ant"
  GT
\end{lstlisting}

记住在使用\acode{mappend}时，左参总是被保留的，除非是\acode{EQ}，这时右参被保留。这也是为什么我们要将比较重要的顺序
放在左参。如果要延展这个函数，要让它们比较元音的顺序，并把这个设为第二重要的比较条件，可以这样改写：

\begin{lstlisting}[language=Haskell]
  lengthCompare :: String -> String -> Ordering
  lengthCompare x y =
    (length x `compare` length y)
      `mappend` (vowels x `compare` vowels y)
      `mappend` (x `compare` y)
    where
      vowels = length . filter (`elem` "aeiou")
\end{lstlisting}

这里写了一个帮助函数，接受一个字符串并告知有多少个元音拥有筛选，再应用\acode{length}。测试：

\begin{lstlisting}[language=Haskell]
  ghci> lengthCompare "zen" "anna"
  LT
  ghci> lengthCompare "zen" "ana"
  LT
  ghci> lengthCompare "zen" "ann"
  GT
\end{lstlisting}

第一个例子，\acode{"zen"}长度短于\acode{"anna"}返回\acode{LT}。第二个例子，长度一样，但第二个字符串元音多，返回
\acode{LT}。第三个例子，长度相等，元音个数相等，最后经过字典顺序得\acode{"zen"}更大。

\acode{Ordering}的幺半群允许我们用不同方式比较事务，并根据重要度的不同而定义比较的顺序。

\subsubsection*{\acode{Maybe}幺半群}

让我们看看\acode{Maybe a}构造\acode{Monoid}实例的若干方式，以及这些实例的用途。

一种让\acode{Maybe a}视作幺半群的方式是其类型参数\acode{a}是幺半群，接着实现\acode{mappend}将包在\acode{Just}
里的至对应\acode{mappend}，同时让\acode{Nothing}作为 identity。使用\acode{Nothing}作为 identity 这样如果
\acode{mappend}的两个值其中一个是\acode{Nothing}时，保留另一个。以下是实例声明：

\begin{lstlisting}[language=Haskell]
  instance Monoid a => Monoid (Maybe a) where
    mempty = Nothing
    Nothing `mappend` m = m
    m `mappend` Nothing = m
    Just m1 `mappend` Just m2 = Just (m1 `mappend` m2)
\end{lstlisting}

注意这里的类约束，即只有当\acode{a}是\acode{Monoid}时，\acode{Maybe a}才可作为\acode{Monoid}实例。接下来就是
\acode{mappend}任意一方是\acode{Nothing}时，结果则是另一方。如果\acode{mappend}两个\acode{Just}值，那么就
\acode{mappend}两个\acode{Just}的内容，用\acode{Just}包装后再返回值。

\begin{lstlisting}[language=Haskell]
  ghci> Nothing `mappend` Just "andy"
  Just "andy"
  ghci> Just LT `mappend` Nothing
  Just LT
  ghci> Just (Sum 3) `mappend` Just (Sum 4)
  Just (Sum {getSum = 7})
\end{lstlisting}

那么如果\acode{Maybe}的内容并非\acode{Monoid}实例呢？在我们不知道内容是否为幺半群的情况下，是不能\acode{mappend}
两个值的，那么该怎么做？一种方式是丢弃第二个值并保留第一个。为此，\acode{First a}类型出现了，其定义：

\begin{lstlisting}[language=Haskell]
  newtype First a = First { getFirst :: Maybe a }
    deriving (Eq, Ord, Read, Show)
\end{lstlisting}

接受一个\acode{Maybe a}将其用\textit{newtype}包装。\acode{Monoid}实例：

\begin{lstlisting}[language=Haskell]
  instance Monoid (First a) where
    mempty = First Nothing
    First (Just x) `mappend` _ = First (Just x)
    First Nothing `mappend` x = x
\end{lstlisting}

\acode{mempty}是包在\acode{First}中的\acode{Nothing}。如果\acode{mappend}的第一个参数是\acode{Just}，那么
直接忽略第二个参数；如果第一个参数是\acode{Nothing}，则直接返回第二个参数，无论是\acode{Just}或\acode{Nothing}：

\begin{lstlisting}[language=Haskell]
  ghci> getFirst $ First (Just 'a') `mappend` First (Just 'b')
  Just 'a'
  ghci> getFirst $ First Nothing `mappend` First (Just 'b')
  Just 'b'
  ghci> getFirst $ First (Just 'a') `mappend` First Nothing
  Just 'a'
\end{lstlisting}

\acode{First}在我们有用若干\acode{Maybe}值，并想要知道它们中任意一个是否为\acode{Just}时，非常的有用。利用
\acode{mconcat}：

\begin{lstlisting}[language=Haskell]
  ghci> getFirst . mconcat . map First $ [Nothing, Just 9, Just 10]
  Just 9
\end{lstlisting}

如果我们希望\acode{Maybe a}保留的是第二个参数的幺半群实现时，\acode{Data.Monoid}提供了一个\acode{Last a}类型：

\begin{lstlisting}[language=Haskell]
  ghci> getLast . mconcat . map Last $ [Nothing, Just 9, Just 10]
  Just 10
  ghci> getLast $ Last (Just "one") `mappend` Last (Just "two")
  Just "two"
\end{lstlisting}

\subsubsection*{使用幺半群来 fold 数据结构}

幺半群的另一个有趣的使用方式就是让它来帮助我们 fold 一些数据结构。目前为止我们只 fold 过列表，不过列表并不是唯一一种可以
fold 的数据结构。我们几乎可以 fold 任意一种数据结构，例如树。

正因为太多的数据结构可以被 fold，\acodeppl{Foldable} typeclass 就被引入了。很像\acode{Functor}用作于映射，
\acode{Foldable}用于任何可以被 fold 起来的东西！可以在\acode{Data.Foldable}中找到它，又因为与\acode{Prelude}中
多数名称重名的缘故，我们需要：

\begin{lstlisting}[language=Haskell]
  import Foldable qualified as F
\end{lstlisting}

让我们来看看与\acode{Prelude}中的\acode{foldr}，\acode{foldl}，\acode{foldr1}以及\acode{foldl1}有什么区别。

\begin{lstlisting}[language=Haskell]
  ghci> :t foldr
  foldr :: (a -> b -> b) -> b -> [a] -> b
  ghci> :t F.foldr
  F.foldr :: (F.Foldable t) => (a -> b -> b) -> b -> t a -> b
\end{lstlisting}

\acode{foldr}接受一个列表并进行 fold，而\acode{Data.Foldable}中的\acode{foldr}则是接受任意可被 fold 的类型。
它们作用于列表的行为一致：

\begin{lstlisting}[language=Haskell]
  ghci> foldr (*) 1 [1,2,3]
  6
  ghci> F.foldr (*) 1 [1,2,3]
  6
\end{lstlisting}

那么其它类型呢？比如说\acode{Maybe}：

\begin{lstlisting}[language=Haskell]
  ghci> F.foldl (+) 2 (Just 9)
  11
  ghci> F.foldr (||) False (Just True)
  True
\end{lstlisting}

现在来看一下之前章节定义的树结构：

\begin{lstlisting}[language=Haskell]
  data Tree a = Empty | Node a (Tree a) (Tree a) deriving (Show, Read, Eq)
\end{lstlisting}

一棵树要么是一颗空树，要么是一个包含值的节点且还指向另外两棵树。定义它之后我们还将其定义成\acode{Functor}的实例，现在
将它定义成\acode{Foldable}的实例。一种方式是实现\acode{foldr}，另一种比较简单的方式是实现\acode{foldMap}，它也
属于\acode{Foldable} typeclass。\acode{foldMap}的类型如下：

\begin{lstlisting}[language=Haskell]
  foldMap :: (Monoid m, Foldable t) => (a -> m) -> t a -> m
\end{lstlisting}

第一个参数是一个函数，该函数接受一个 foldable 结构包含的类型（这里就是\acode{a}）并返回一个 monoid 值，第二个参数
就是包含类型\acode{a}的 foldable 结构。它将函数映射至 foldable 结构上，因此生产一个包含了 monoid 值的 foldable
结构。接着用\acode{mappend}在这两个 monoids 值上，并返回单个 monoid 值。比较酷的是只要实现了这个函数，那么就可以
让我们的函数成为\acode{Foldable}。所以只要实现某个类型的\acode{foldMap}，就可以得到那个类型的\acode{foldr}与
\acode{foldl}。

接下来就是定义\acode{Tree}成为\acode{Foldable}实例：

\begin{lstlisting}[language=Haskell]
  instance F.Foldable Tree where
    foldMap f Empty = mempty
    foldMap f (Node x l r) =
      F.foldMap f l `mappend` f x `mappend` F.foldMap f r
\end{lstlisting}

我们这样思考：如果提供一个接受树元素并返回一个 monoid 值的函数，我们如何减少我们的树变为单个 monoid 值呢？我们在做
\acode{fmap}树的时候是将函数应用在节点上，接着递归的应用函数在做子树与右子树上。这里我们不仅仅是要映射一个函数，还要
通过使用\acode{mappend}合并值返回一个 monoid 值。首先是考虑空树，它不包含任何值，因此它变为\acode{mempty}。

非空树比较有趣。它包含了两个子树同时还有值。这种情况下使用\acode{foldMap}递归同一个函数\acode{f}在左右子树上。记住，
\acode{foldMap}返回一个 monoid 值。函数\acode{f}也应用在节点的值上。这时就有了三个 monoid 值（两个从子树而来，
一个从节点而来），我们希望将它们合并成为一个值。为此，使用\acode{mappend}，自然而然的从左子树开始，接着是节点，再
然后就是右子树。

注意我们并不一定要提供一个将普通值转成 monoid 的函数。我们只是把它当做 \acode{foldMap} 的参数，要决定的是如何应用
该函数，将多个 monoids 转换成一个 monoid。

考虑下面这棵树：

\begin{lstlisting}[language=Haskell]
  testTree =
    Node
      5
      ( Node
          3
          (Node 1 Empty Empty)
          (Node 6 Empty Empty)
      )
      ( Node
          9
          (Node 8 Empty Empty)
          (Node 10 Empty Empty)
      )
\end{lstlisting}

对其进行 fold：

\begin{lstlisting}[language=Haskell]
  ghci> F.foldl (+) 0 testTree
  42
  ghci> F.foldl (*) 1 testTree
  64800
\end{lstlisting}

\acode{foldMap}不仅对创建新的\acode{Foldable}实例有用；它对简化我们的结构称为单一的 monoid 值也有用。例如我们
想要知道树中有没有\acode{3}，我们可以这么做：

\begin{lstlisting}[language=Haskell]
  ghci> getAny $ F.foldMap (\x -> Any $ x == 3) testTree
  True
\end{lstlisting}

此处的\acode{\x -> Any \$ x == 3}接受一个数值并返回一个 monoid，即一个包在\acode{Any}中的\acode{Bool}。
\acode{foldMap}将这个函数应用至树的每个节点，并把结果用\acode{mappend}简化成单一的 monoid。如果这么做：

\begin{lstlisting}[language=Haskell]
  ghci> getAny $ F.foldMap (\x -> Any $ x > 15) testTree
  False
\end{lstlisting}

我们也能将\acode{foldMap}配合\acode{\\x -> [x]}使用来将树转成列表：

\begin{lstlisting}[language=Haskell]
  ghci> F.foldMap (\x -> [x]) testTree
  [1,3,6,5,8,9,10]
\end{lstlisting}

\end{document}