monads.tex

\section{Monads}
上一节您已经了解了一些Monad的基本概念。Monad是一个类型(内部类型)的包装类型，使得内部类型具有某种结构，从而您可以通过某种方式对内部类型进行组合运算。这其实就是Monad的全部奥义。

为了做到这一点，您只能间接访问Monad中包装的内部类型。比方说，$Maybe$类型其实就是个Monad。它为内部类型添加了一个结构，可能没有返回值，或者返回一个可以求得$3$的计算，亦即$Just\ 3$，而不是直接返回$3$。继而，你可能得到一个计算，它根本不会求得某个值，也就是$Nothing$。

现在你可能希望用某个计算的结果去创建另一个计算，这是Monad最重要的特性之一 -- 它允许您从简单的计算单元构造出复杂计算，并且中间不去要对这些计算求值。

边注：为了强调Monad并无特殊之处，也不是什么怪异魔法，我暂时先避免使用Haskell那些讨人喜欢的语法糖，我将自己实现一些Monad，简单直白的使用它们。

技术上来讲，如果您发现你的某个数据类型是Monad，你可以将它实现成$Monad$类型类(type class)的一个实例。下面是$Monad$类的部分重要代码(该类还有两个成员函数，我们暂时还不需要它们)：

\begin{lstlisting}
class Monad m where
  return :: a -> m a
  (>>=)  :: m a -> (a -> m b) -> m b
\end{lstlisting}


$return$函数，正如它的类型暗示的那样，它接受一个内部类型的值，给出一可以运算得出该值的计算。$(>>=)$函数(通常用其中缀记法$>>=$)更有趣： $c >>= f$是个计算，它把计算$c$的结果丢给$f$。你可以把该成员函数看做用于将中间值($c$的运算结果)传入到更大的计算（$f$的运算结果)。我们很快便会看清楚它究竟看起来是啥样。从现在开始，我将$c$称为源计算，$f$称为消费者函数。

$(>>=)$函数常被称为“绑定子(bingding operator)”或者“绑定函数(bind function)”，因为它将一个计算结果绑定到另一个更大的计算。函数$f$，也就是$(>>=)$的第二个参数，我将在下文中称之为``Monadic Function''。该函数返回一个计算。

函数$(>>=)$的威力在于，传给消费者函数的源计算的结果完全是未指明的。在$Maybe$ Monad中，它可能不会有返回值，这种情况下消费者函数永远不会被调用到。

\subsection{Maybe Monad}

从一个实例出发来理解会更简单一点。暂时想象$Maybe$ Monad并不存在，让我们来定义它：

\begin{lstlisting}
data Maybe a = Just a | Nothing   deriving (Eq, Show)
\end{lstlisting}

你会很快发现，$Maybe$类型其实是一个内部类型的包装。$Maybe$类型的$return$函数很容易实现：在$Maybe$ Monad中， $Just\ x$是个计算，对它求值会得到$x$。

更有趣的是，比方说，你需要在某个计算中使用一个$Maybe$计算(源计算)的结果，将它绑定到变量$x$，假如源计算含有一个结果，那该结果就是$x$，假如没有结果，则整个计算没有结果。该想法是通过绑定子函数$(>>=)$实现的。

\begin{lstlisting}
instance Monad Maybe where
  return x = Just x

  Nothing >>= f = Nothing
  Just x  >>= f = f x
\end{lstlisting}

将计算$Nothing$传递给消费者函数$f$以为着立即返回$Nothing$(因为无结果可用)而无需调用$f$；若是传递进来的是$Just\ x$，则意味着将$x$传递给$f$并返回该结果。

现在让我们重新看看整型值精确四次方根函数$i4throot$。它首先计算传入参数的精确平方根，假如有值，则对其再算一次精确平方根。这听起来是不是很熟悉？当然应该如此，现在我们可以开发利用一下$Maybe$ Monad的属性(你绝对应该试一试)：

\begin{lstlisting}
i4throot :: Integer -> Maybe Integer
i4throot x = isqrt x >>= isqrt
\end{lstlisting}

\subsection{List Monad}

和$Maybe$类型类似，列表类型也是个包装类型。它为内部类型添加了一些逻辑结构，可以返回多个结果。将其计算结果传递给一个Monad函数会发生什么情况？

要回答这个问题，先问问自己：首先，什么是列表？它代表任意多个值，因而也代表了非确定性(non-determinism)。换言之，计算$[2,3,7]$仅仅是一个，它的运算结果是$2$， $3$ 和 $7$。

好了，现在想象一下你在某个计算中需要用到列表计算的结果，于是你想把列表计算的结果绑定到变量$x$。假如$x$中没有结果，则整个计算也没有结果，就像$Maybe$一样。假如列表中有一个结果，则它被绑定到$x$。假如列表中有两个结果呢？如果$x$对应多个值，则消费者函数也会魔术般被调用多次，每次传入$x$绑定的一个值。最终结果则是所有这些单个结果的集合。

\begin{lstlisting}
[10,20,40] >>= \x -> [x+1, x+2]
\end{lstlisting}

求值这个计算将会得到结果$[11,12,21,22,41,42]$，因为你把计算$[10,20,40]$的结果绑定到$x$，其中$x$包含三个结果，于是计算$[x+1, x+2]$将会执行三次，$x$的值分别是$10$，$20$和$40$。三次计算结果将会被合并到最终一个大的运算结果。

$return$函数在这里还是很容易实现，在列表Monad中，$[x]$是个求值为$x$的计算。看一看如何实例化列表类型的Monad：

\begin{lstlisting}
instance Monad [] where
  return x = [x]
  xs >>= f = concat . map f $ xs
\end{lstlisting}

$(>>=)$函数还是很有趣：它首先把消费者函数$f$映射到源列表中的所有值，也就是用$xs$中的所有值调用了一遍$f$。因为$f$的每次调用本身都会返回一个列表，映射得到的结果是个列表的列表。第二步，它连结列表中的所有成员列表形成一个大列表。下面的代码再次阐明了这一切。

\begin{lstlisting}
multiples :: Num a => a -> [a]
multiples x = [x, 2*x, 3*x]

testMultiples :: Num a => [a]
testMultiples = [2,7,23] >>= multiples
\end{lstlisting}

$testMultiples$ 的结果是 $[2,4,6,7,14,21,23,46,69]$。它首先从源列表中取各个值，然后将它们传入消费者函数$multiples$，得到三个列表作为结果：$[2,4,6]$， $[7,14,21]$ 和 $[23,46,69]$。换句话说，它将函数$multiples$映射于源列表。最终，连结三个列表得到一个包含所有结果的列表。

\subsection{Identity Monad}

$Identity$ Monad实际中比较少用，为了接下来描述$State$和$IO$ Monad，这里先稍微介绍一下。当然，这也是为了Monad理论的完整性。你也可能在Monad转换器(Monad Transformer)中看到对$Identity$ Monad的使用，这些我稍后再讲。

$Identity$ Monad包装的计算只是简单的返回一个值而已，并不像$Maybe$或者列表Monad那样假如额外逻辑结构。将一个$identity$计算的结果绑定到消费者函数仅仅意味着原样传入源计算的结果。

\begin{lstlisting}
data Identity a = Identity a

instance Monad Identity where
  return = Identity
  Identity x >>= f = f x
\end{lstlisting}

$Identity 5$是一个计算，其值为$5$。因为$return\ x$需要返回一个求值为$x$的计算，所以很自然，$return\ x$只需直接简单地返回$Identity x$。将$x$传递给计算$Identity\ x$后再传给消费者函数$f$也仅仅意味着直接将结果$x$传递给$f$。