单子 (函数式编程)

在函数式编程中，单子（monad）是一种抽象，它允许以泛型方式构造程序。支持它的语言可以使用单子来抽象出程序逻辑需要的样板代码。为了达成这个目标，单子提供它们自己的数据类型（每种类型的单子都有特定的类型），它表示一种特殊形式计算，与之在一起的有两个过程，一个过程用来包装单子内“任何”基本类型的值（产生单子值），另一个过程用来函数复合 (计算机科学)那些输出单子值的函数（叫做单子函数）。

单子的概念和术语二者最初都来自范畴论，这里的单子被定义为具有额外结构的函子。开始于1980年代晚期和1990年代早期的研究，确立了单子可以将看似完全不同的计算机科学问题置于一个统一的函数式模型之下。范畴论还提供了叫做单子定律的一些形式要求，任何单子都应当满足它并可以用它来验证单子代码。

通过单子，编程者可以把复杂的函数序列变成简洁的管道，它抽象出了辅助数据管理、控制流或副作用。单子可以简化范围宽广的问题，比如处理潜在未定义值（通过`Maybe`单子），或将值保持在一个灵活而形式正确的列表中（使用`List`单子）。因为单子使得某种计算的语义明确，它们还可以用来实现便捷的语言特征。一些语言比如Haskell，甚至在它们的核心库中为通用单子结构提供预制的定义和常用实例。

## 概述

单子可以通过定义一个类型构造子`m`和两个运算即`unit`和`bind`来建立。C. A. McCann解释说：“对于单子`m`，类型`m a`的值，表示可以在这个单子上下文内访问的类型`a`的值。”

- `unit`（也叫做`return`），接受一个类型`a`的值，把它们包装成使用这个类型构造子建造的类型`m a`的“单子值”。
- bind（典型的表示为`>>=`），接受一个在类型`a`上的函数`f`，并应用`f`于去包装的值`a`，并可把`f`的结果处理成单体值`m a`。在后面的从函子推导章节有可作为替代的等价构造，使用`join`函数替代了`bind`算子。

通过这些元素，编程者可以复合出一个函数调用的序列（管道），在一个表达式中通过一些bind算子把它们链接起来。每个函数调用转变它的输入普通类型值，而bind算子处理返回的单子值，它被填入到序列中下一个步骤。

在每对复合的函数调用之间，bind算子`>>=`可以向单子值`m a`注入在函数`f`内不可访问的额外信息，并沿着管道传递下去。它还可进行细致的执行流控制，比如只在特定条件下调用函数，或以特定次序执行函数调用。

## Maybe单子例子

下面的快捷伪代码例子展示编程者使用单子的动机。未定义的值或运算，是健壮的软件应当准备好做出优雅处理的一个特殊问题。

完成这个目标的第一步是建立一个可选类型，它标记一个值，要么承载某个类型`T`（`T`可以是任何类型）的值，要么没有承载值。新的类型将叫做`Maybe T`，而这个类型的值，可以包含要么类型`T`的值，要么空值`Nothing`。类型`T`的值`x`，若定义并用于`Maybe`上下文，则叫做`Just x`。这么做是通过区分一个变量，是处在承载了有定义的值的情况，还是处在未定义的情况，来避免混淆。

```haskell
data Maybe T = Just T | Nothing
```

`Maybe T`可以被理解为一种“包装”类型，把类型`T`包装成具有内建异常处理的一种新类型，尽管不承载关于异常成因的信息。

在下列的伪代码中，前缀着`m`的变量有针对某种类型`T`的类型`Maybe T`。例如，如果变量`mx`包含一个值，那么它是`Just x`，这里的变量`x`有类型`T`。`λx -> ...`是匿名函数，它的形式参数`x`的类型是推论而来，而`∘`是函数复合算子。

另一个改进是，函数通过`Maybe`类型，能管理简单的检查异常：一旦某个步骤失败，就短路并返回`Nothing`；如果计算成功则，返回正确的值而无需再评论。

加法函数`add`，在做二个`Maybe`值`mx`和`my`的加法之时，就实现了上述改进，它可以如下这样定义：

```haskell
add :: Maybe Number -> Maybe Number -> Maybe Number
add mx my  = ...
    if mx is Nothing then
        ... Nothing
    else if my is Nothing then
        ... Nothing
    else
        ... Just (x + y)
```

书写函数来逐一处理`Maybe`值的各种情况可能相当枯燥，并且随着定义更多函数而变得更甚。将多个步骤链接起来的运算，是减轻这种状况的一种方式，通过使用中缀算子如`mx >>= f`，甚至可以直观的表示出，将每个步骤得出的（可能未定义的）结果，填入下一步骤之中。因为每个结果在技术上被插入到另一个函数之中，这个算子转而接受一个函数作为一个形式参数。由于`add`已经指定了它的输出类型，保持这个算子的灵活性，而接受输出与其输入不同类型的函数应当没有什么伤害：

```haskell
>>= :: Maybe T -> (T -> Maybe U) -> Maybe U
(mx >>= f) = ...
    if mx is (Just x) then
        ... f(x)    -- f返回类型Maybe U的定义值
    else
        ... Nothing -- f不返回值
```

在具有`>>=`可用时，`add`可以被精制为更紧凑的表述：

```haskell
add mx my  = 
    mx >>= λx ->
        (my >>= λy ->
            Just (x + y))
```

这更加简洁，而一点额外的分析就能揭示出它的强大之处。首先，`Just`在`add`中扮演的唯一角色，就是将一个低层值标记（tag）为也是`Maybe`值。为了强调`Just`通过包装低层值而在其上施加作用，它也可以被精制为函数，比如叫做`eta`：

```haskell
eta :: T -> Maybe T
eta x  =  Just x
```

整体情况是这两个函数`>>=`和`eta`被设计用来简化`add`，但是他们明显的不以任何方式依赖于`add`的细节，只是有关于`Maybe`类型。这些函数事实上可以应用于`Maybe`类型的任何值和函数，不管底层的值的类型。例如，下面是来自Kleene三值逻辑的一个简洁的NOT算子，也使用了相同的函数来自动化未定义值：

```haskell
trinot :: Maybe Boolean -> Maybe Boolean
trinot mp  =  mp >>= λp -> (eta ∘ not) p
```

可以看出来`Maybe`类型，和与之一起的`>>=`和`eta`，形成了单子。尽管其他单子会具体化不同的逻辑过程，而且一些单子可能有额外的属性，它们都有三个类似的构件（直接或间接的）服从这个例子的纲要。

## 定义

对函数式编程中的单子的更常用的定义，比如在上面的例子中用到的，实际上基于了Kleisli范畴，而非范畴论的标准定义。两个构造可以证明在数学上是等价的，任何定义都能产生有效的单子。给定任何良好定义的基本类型`T`、`U`，单子构成自三个部分：

- 类型构造子 `M`，建造一个单子类型`M T`Semantically, M is not trivial and represents an endofunctor over the category of all well-typed values: $M: \mathit{Val} \to \mathit{Val}$
- 类型转换子，经常叫做unit或return，将一个对象`x`嵌入到单子中：
- `unit(x) :: T -> M T`While a (parametrically polymorphic) function in programming terms, (often called η in category theory) is mathematically a natural transformation, which maps between functors: $\eta_{A} : \mathrm{id}(\mathit{Val}_{A}) \to M(\mathit{Val}_{A})$
- 组合子，典型的叫做bind（约束变量的那个bind），并表示为中缀算子`>>=`，去包装一个单体变量，接着把它插入到一个单体函数/表达式之中，结果为一个新的单体值：
- `(mx >>= f) :: (M T, T -> M U) -> M U`bind, on the other hand, is not a natural transformation in category theory, but rather an extension $-^{*}$ that lifts a mapping (from values to computations) into a morphism between computations: $\forall f : \mathit{Val}_{A} \to M(\mathit{Val}_{B}), f^{*}: M(\mathit{Val}_{A}) \to M(\mathit{Val}_{B})$

但要完全具备单子资格，这三部分还必须遵守一些定律：

- `unit(a) >>= λx -> f(x) '''&harr;''' f(a)`
- `ma >>= λx -> unit(x) '''&harr;''' ma`
- `ma >>= λx -> (f(x) >>= λy -> g(y)) '''&harr;''' (ma >>= λx -> f(x)) >>= λy -> g(y)`

在代数上，这意味任何单子都引起一个范畴（叫做Kleisli范畴）和在函子（从值到计算）的范畴上的幺半群，具有单子复合作为二元算子和`unit`作为单位元。

单子为有价值的技术提供了机会，超出了只是组织程序逻辑。单子可以为有用的语法特征奠定基础工作，而它们的高级和数学本质能实现重大的抽象。

## 语法糖do表示法

尽管公开的使用`bind`通常就行得通，很多编程者偏好模仿指令式语句的语法（在Haskell中称为“do表示法”，在OCaml中称为“perform表示法”，在F♯中称为“计算表达式”，在Scala中称为“for推导式”）。这只是将单子管道伪装成代码块的语法糖；编译器会悄悄的将这些表达式转换成底层的函数式代码。

将上述的`Maybe`单子例子中的`add`函数伪码转换成Haskell代码来用行动展示这个特征。非单子版本的`add`用Haskell写出来如下这样：

```haskell
add mx my =
    case mx of
    Nothing -> Nothing
    Just x  -> case my of
               Nothing -> Nothing
               Just y  -> Just (x + y)
```

在使用单子的Haskell中，`return`是`unit`的标准名字，加上必须显式处置的lambda表达式，即使多了这些技术，`Maybe`单子使得定义更加清晰：

```haskell
add mx my =
    mx >>= (\x ->
        my >>= (\y ->
            return (x + y)))
```

使用do表示法，可以进一步精炼成非常直观的序列：

```haskell
add mx my = do
    x <- mx
    y <- my
    return (x + y)
```

甚至通用单子定律自身都可以用do表示法来表达：

```haskell
do { x <- return v; f x }            ==  do { f v }
do { x <- m; return x }              ==  do { m }
do { y <- do { x <- m; f x }; g y }  ==  do { x <- m; y <- f x; g y }
```

尽管方便，开发者应当记住这种块风格只是语法上的并可外观上替代为单子(甚至非单子的CPS）表达式。使用`bind`来表达单子管道仍在很多情况下是更加清晰的，一些函数式编程拥戴者提议，由于块风格允许初学者存续来自指令式编程的习惯，应当避免缺省的而只在明显更优越的时候使用它。

## 历史

在编程中术语“单子”（monad）实际上最早可追溯至APL和J编程语言，它们趋向于是纯函数式的。但是，在这些语言中，“monad”仅是只接受一个形式参数的函数的简称（有二个形式参数的函数叫做“dyad”）。

数学家Roger Godement最初在1950年代晚期公式化单子概念（起绰号为“标准构造”），而术语“monad”成为主导要归功于范畴学家桑德斯·麦克兰恩。但是，上述的使用bind定义的形式，最初由数学家Heinrich Kleisli在1965年描述，用来证明任何单子都可以特征化为在两个（协变）函子之间的伴随。

开始于1980年代，单子模式的模糊概念在计算机科学社区中浮出水面。依据编程语言研究者Philip Wadler，计算机科学家John C. Reynolds于1970年代和1980年代早期，在他讨论传递续体风格的价值的时候，预见到了它的一些方面，范畴论作为形式语义学的丰富来源，和在值和计算之间的类型区别。研究性语言Opal，它活跃设计直到1990年，还有效的将I/O基于在单子类型之上，但是这个联系在当时没有实现。

计算机科学家Eugenio Moggi最早明确的将范畴论的单子联系于函数式编程，在1989年于讨论会论文之中，随后在1991年还有更加精制的期刊提交。在早期的工作中，一些计算机科学家使用范畴论推进为lambda演算提供语义。Moggi的关键洞察是真实世界程序不只是从值到另外的值的函数，而是形成在这些值之上计算的变换。在用范畴论术语形式化的时候，这导致的结果是单子作为表示这些计算的结构。

其他一些人以这个想法为基础并进行了推广，包括Philip Wadler和Simon Peyton Jones，二者都参与了Haskell规定。特别是，Haskell直到v1.2一直使用有问题的“惰性流”模型来将I/O调和于惰性求值，然后切换到了更灵活的单子接口。Haskell社区继续将单子应用于函数式编程的很多问题中，使用Haskell工作的研究者最终将单子模式推广成广泛的结构层级，包括应用式函子和箭头 (计算机科学)。

首先，使用单子的编程很大程度上局限于Haskell及其派生者，但是由于函数式编程已经影响了其他编程范型，很多语言结合了单子模式（不这么称呼的话也在精神上）。其公式化现已存在于Scheme、Perl、Python、Racket、Clojure、Scala和F#之中，并已经被考虑用于新的ML标准。

## 用途

单子模式的价值超出了只是压缩代码和提供到数序推理的联系。不管开发者采用的语言或缺省编程范型是什么，遵从单子模式都会带来纯函数式编程的很多利益。通过实化特定种类的计算，单子不仅封装了这个计算模式的冗长细节，而且它以声明式方式来这么做，增进了代码清晰性。因为单子值所显式代表的不只是计算出的值，而是计算出的作用（effect），单子表达式在参照透明性上可以被替代为它们的值，非常像纯表达式能做到的那样，允许了基于重写的很多技术和优化。

典型的，编程者会使用`bind`来把单子函数链接成一个序列，这导致了一些人把单子描述为“可编程的分号”，参照众多指令式语言使用分号来分割语句。但是，需要强调单子实际上不确定计算的次序；甚至在使用它们作为中心特征的语言中，更简单的函数复合可以安排程序内的步骤。单子的一般效用准确的说在于简化程序的结构并通过抽象来增进关注点分离。

单子结构还可以被看作修饰模式的独特的数学和编译时间变种。一些单子可以传载对函数是不可访问的额外数据，而且一些单子甚至具有在执行上的更细致控制，例如只在特定条件下调用一个函数。因为它们让应用程序员实现领域逻辑，而卸载样板代码至预先开发的模块，单子甚至可以当作面向方面编程的工具。

单子的另一个值得注意的用途，是在其他方面都纯函数式的代码中，隔离副作用，比如输入/输出或可变的状态 (计算机科学)。即使纯函数式语言仍可以不使用单子来实现这些“不纯”计算，特别是通过对函数复合和续体传递风格（CPS）的错综复杂混合。但是使用单子，多数这些脚手架可以被抽象出去，本质上通过提取出在CPS代码中每个反复出现的模式并集束到一个独特的单子之中。

如果一个语言缺省的不支持单子，仍有可能实现这个模式，经常没有多少困难。在从范畴论转换成编程术语的时候，单子结构是概念 (泛型编程)并可以在支持限定的多态的等价特征的任何语言中直接定义。一个概念在操作底层数据类型时保持对操作细节不可知的能力是强大的，然而单子的独特特征和严格行为将它们同其他概念区别开来。

## 分析

单子模式的利益之一是将数学上的精确性施加到编程逻辑上。不只是单子定律可以用来检查实例的有效性，而且来自有关结构（比如函子）的特征可以通过子类型来使用。

### 从函子推导

尽管在计算机科学中少见，可以直接使用范畴论，它定义单子为有二个额外自然变换的函子。作为开始，一个结构要求叫做map的高阶函数（“泛函”）从而具备函子资格：

`map φ :: (a -> b) -> ma -> mb`

但是这不总是一个主要问题，尤其是在单子派生自预先存在的函子的时候，单子马上就自动继承`map`。出于历史原因，在Haskell中这个`map`转而叫做`fmap`。

单子的第一个变换实际上同于来自Kleisli三元组的`unit`，但是更密切的服从结构的层级，结果是`unit`特征化一个应用式函子，这是在单子和基本函子之间的中间结构。在应用式的上下文中，`unit`有时被称为`pure`，但是这仍是相同的函数。在这个构造中有不同的地方是定律`unit`必须满足；因为`bind`未定义，这个约束转而依据`map`给出：

`(unit ∘ φ) x ↔ ((map φ) ∘ unit) x`

从应用式函子到单子的最后跳跃来自于第二个变换`join`函数，在范畴论中这个自然变换通常叫做μ，它扁平化单子的嵌套应用：

`join(mma) :: M (M T) -> M T`

作为特征性函数，`join`必须还满足三个单子定律的变体：

`join ∘ (map join) mmma ↔ (join ∘ join) mmma ↔ ma`

`join ∘ (map unit) ma ↔ (join ∘ unit) ma ↔ ma`

`join ∘ (map map φ) mma ↔ ((map φ) ∘ join) mma ↔ mb`

不管开发者是否直接定义单子或Kleisli三元组，底层的结构都是相同的，二者形式可以轻易的相互导出：

`(map φ) ma ↔ ma >>= (unit ∘ φ)`

`join(mma) ↔ mma >>= id`

`ma >>= f ↔ (join ∘ (map f)) ma`

### 例子：List单子

<image>

`List`单子天然的展示了如何手工的从更简单的函子导出单子。在很多语言中，列表结构与很多基本特征一起是预定义的，所以假定`List`类型构造子和`append`算子（用中缀表示法表示为`++`）已经存在于这里了。

将一个平常的值嵌入到列表中在多数语言中也是微不足道的：

`unit(x) = [x]`

自此，通过列表推导式迭代的应用一个函数，看起来就是对`bind`的一个容易的选择，从而将列表转换成完全的单子。这个方式的困难在于`bind`预期一个单子函数，它在这种情况下会输出列表自身；随着更多函数的应用，嵌套的列表的层次会累加，要求不止一个基本推导式。

但是，在整个列表上应用任何“简单”函数的过程，也就是`map`，就直截了当了：

`(map φ) xlist = [ φ(x1), φ(x2), ..., φ(xn) ]`

现在，这两个过程已经将`List`提升为应用式函子。要完全具备单子资格，只需要`join`的一个正确的表示法来扁平化重复的结构，但是对于列表，这意味着去包装一个外部列表来包含着值的那些内部列表：

`join(xlistlist) = join([xlist1, xlist2, ..., xlistn])`` = xlist1 ++ xlist2 ++ ... ++ xlistn`

结果的单子不只是一个列表，而且在应用函数的时候可以自动调整大小和压缩自身。`bind`现在可以从一个公式导出，接着被用来通过单子函数的管道向`List`填入值：

`(xlist >>= f) = join ∘ (map f) xlist`

这种单子列表的一个应用是表示非确定性算法。`List`可以持有一个算法中所有执行路径的结果，接着每一步骤压缩自身来忘记那一步导致了这个结果（有时这是同确定性、穷举算法的重要区别）。另一利益是检查可以嵌入到单子中；特定路径可以透明的在它们第一个失败点上被剪除，而不需要重写管道上的函数。

突出`List`的第二种情况是复合多值函数。例如，一个数的`n`次复数方根将产生`n`个不同复数，但是如果另个`m`方根接受了这些结果，最终复合出的`m•n`的值应当同一于一次`m•n`次方根的输出。`List`完全自动化了这个问题的处置，压缩来自每一步骤的结果成一个平坦的、数学上正确的列表。

## 更多例子

### IO单子（Haskell）

正如提及过的那样，纯粹的代码不应有不可管理的副作用，但是不妨碍程序“显式”的描述和管理各种作用。这个想法是Haskell的IO单子的中心，在这里一个类型`IO a`的对象，可以被看作包含了程序外部的世界的当前状态，并计算类型`a`的一个值。不计算值的计算，也就是过程，有着类型`IO ()`，它“计算”虚设值`()`。在编程者bind一个`IO`值到一个函数的时候，这个函数基于世界的场景（来自用户的输入、文件等）做出决定，接着产生反映新的世界状态（程序输出）的一个单子值。

例如，Haskell有一些函数作用在宽广的文件系统之上，包括有检查一个文件存在的一个函数和删除一个文件的另一函数。二者的类型签名是：

```haskell
doesFileExist :: FilePath -> IO Bool
removeFile :: FilePath -> IO ()
```

第一个函数关注一个给定文件是否真的存在，作为结果输出一个布尔值于`IO`单子之内。第二个函数在另一方面，只关心在文件系统上的起到作用，所以对于`IO`容器它们的输出为空。

`IO`不只限于文件I/O；它甚至允许用户I/O，还有指令式语法糖，可以模仿典型的Hello World程序：

```haskell
main :: IO ()
main = do
    putStrLn "Hello, world!"
    putStrLn "What is your name, user?"
    name <- getLine
    putStrLn ("Nice to meet you, " ++ name ++ "!")
```

不加语法糖，代码可以转写为如下单子管道（在Haskell中`>>`是`bind`的一种变体，用在只有单子作用是紧要的而底层结果可以丢弃的时候）：

```haskell
main :: IO ()
main =
    putStrLn "Hello, world!" >>
    putStrLn "What is your name, user?" >> 
    getLine >>= (\name ->
        putStrLn ("Nice to meet you, " ++ name ++ "!"))
```

### Writer单子（JavaScript）

另一个常见的情况是保存日志文件或以其他方式报告程序的进度。有时，编程者想要记录更特殊的技术数据用于以后的性能分析或调试。Writer单子可以通过生成逐步积累的辅助输出来处理这些任务。

为了展示单子模式不局限于主要的函数式语言，这个例子用JavaScript实现了`Writer`单子。首先，数组（具有嵌套的尾部）允许构造`Writer`类型为链表。底层的输出值将位于这个数组的位置0，而位置1将隐蔽的持有连成一链的一些辅助注释：

```Javascript
const writer = [value, []];
```

定义`unit`是非常简单的：

```Javascript
const unit = value => [value, []];
```

定义输出具有调试注释的`Writer`对象的简单函数只需要`unit`：

```Javascript
const squared = x => [x * x, [`${x} was squared.`]];
const halved = x => [x / 2, [`${x} was halved.`]];
```

真正的单子仍需要`bind`，但是对于`Writer`，这简单的相当于将函数的输出附加至单子的链表：

```Javascript
const bind = (writer, transform) => {
    const [value, log] = writer;
    const [result, updates] = transform(value);
    return [result, log.concat(updates)];
};
```

样例函数现在可以使用`bind`链接起来，但是定义单子复合的一个版本（这里叫做`pipelog`）允许更加简洁的应用这些函数：

```Javascript
const pipelog = (writer, ...transforms) =>
    transforms.reduce(bind, writer);
```

最终结果是在逐步计算和为以后审查而记录之间的清晰的关注分离：

```Javascript
pipelog(unit(4), squared, halved);
// 结果的writer对象 = [8, ['4 was squared.', '16 was halved.']]
```

## 外部链接

HaskellWiki参考：

- " All About Monads " (originally by Jeff Newbern) — A comprehensive discussion of all the common monads and how they work in Haskell; includes the "mechanized assembly line" analogy.
- " Typeclassopedia " (originally by Brent Yorgey) — A detailed exposition of how the leading typeclasses in Haskell, including monads, interrelate.

教程：

- " A Fistful of Monads " (from the online Haskell textbook Learn You a Haskell for Great Good! — A chapter introducing monads from the starting-point of functor and applicative functor typeclasses, including examples.
- " For a Few Monads More " — A second chapter explaining more details and examples, including a `Probability` monad for Markov chains.
- " Functors, Applicatives, And Monads In Pictures (by Aditya Bhargava) — A quick, humorous, and visual tutorial on monads.

个案：

- " UNIX pipes as IO monads " (by Oleg Kiselyov) — A short essay explaining how Unix pipes are effectively monadic.
- Pro Scala: Monadic Design Patterns for the Web (by Gregory Meredith) — An unpublished, full-length manuscript on how to improve many facets of web development in Scala with monads.