单子 (函数式编程)

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

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

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

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

data Maybe T = Just T | Nothing

 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)
     end if

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

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

 eta :: T -> Maybe T
 eta(x)  =  Just x

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

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

• 类型构造子 M，建造一个单子类型M T[lower-alpha 2]
• 类型转换子，经常叫做unit或return，将一个对象x嵌入到单子中：
  unit(x) :: T -> M T[lower-alpha 3]
• 组合子，典型的叫做bind（约束变量的那个bind），并表示为中缀算子>>=，去包装一个单体变量，接着把它插入到一个单体函数/表达式之中，结果为一个新的单体值：
  (mx >>= f) :: (M T, T -> M U) -> M U[lower-alpha 4]

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

• unit是bind的左单位元：
  unit(a) >>= λx -> f(x) ↔ f(a)
• unit也是bind的右单位元:
  ma >>= λx -> unit(x) ↔ ma
• bind本质上符合结合律：[lower-alpha 5]
  ma >>= λx -> (f(x) >>= λy -> g(y)) ↔ (ma >>= λx -> f(x)) >>= λy -> g(y)[1]

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

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

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

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

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

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

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

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

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

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

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

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

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

例子：List单子

复数多值平方和立方方根函数可以复合起来产生六次方根函数。支配输入和输出类型的结构和复合不同行动的结构，二者一起是list单子[19]。

弹丸符号•指示bind算子，z是复数，方括号指示数组，而:=含义是定义为:

(f•g)(z) := append(map(f,g(z)))

lift(f) = f° := unit•f = f•unit

sqrt°(z) == append(map(unit,sqrt(z)))= append(map(sqrt,unit(z)))

sxrt(z) = (cbrt°•sqrt°)(z) == append(map(cbrt°,sqrt°(z)))

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

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

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

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

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

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

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 }

• 类型类
• 函子
• 应用式函子

維基教科書中的相關電子：理解单子

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.