Monads for the Curious Programmer, Part 2 (中英文对照版)

Monads for the Curious Programmer: Part 2

In my previous post I talked about categories, functors, endofunctors, and a little about monads. Why didn’t I just start with a Haskell definition of a monad and skip the math? Because I believe that monads are bigger than that. I don’t want to pigeonhole monads based on some specific language or application. If you know what to look for you’ll find monads everywhere. Some languages support them better, as a single general abstraction, others require you to re-implement them from scratch for every use case. I want you to be able to look at a piece of C++ code and say, “Hey, that looks like a monad.” That’s why I started from category theory, which sits above all programming languages and provides a natural platform to talk about monads.

在我的上一篇博客中，我讲到了范畴，函子，自函子以及一点单子。为什么我不直接从Haskell关于单子的定义直接开讲且跳过数学部分呢？因为我觉得单子的概念要更重要。我不想从一些特定的语言或者应用来限制单子。如果你知道你要找什么，那单子到处都是。一些语言支持的较好，就像一个单一的一般化抽象；而另一些则要求你对每一种情况都从头开始实现。我期望你可以看到一些C++代码就说“嘿，这不就是单子嘛！”。这就是为什么我从要从范畴论开始，范畴论提供了讨论单子的一个自然的平台而居于所有的编程语言之上。

In this installment I will talk about some specific programming challenges that, on the surface, seem to have very little in common. I will show how they can be solved and how from these disparate solutions a pattern emerges that can be recognized as a monad. I’ll talk in some detail about the

Maybe

monad and the

List

monad, since they are simple and illustrate the basic ideas nicely. I will leave the really interesting examples, like the state monad and its variations, to the next installment.

这部分中，我将讨论几个特定的编程问题。这些问题初看起来几乎完全不同。我将向你展示如何解决它们，他们的不同解决方案中孕育一个可以被识别为单子的模式。我会详细讨论Maybe单子以及List单子，因为它们不仅简单而且优雅地展示了基本的思想。我把真正有趣的单子，如状态单子及其变体留待下一部分。

Challenges of Functional Programming

函数式编程的挑战

You know what a function is: called with the same argument it always returns the same result. A lot of useful computations map directly to functions. Still, a lot don’t. We often have to deal with some notions of computations that are not functions. We can describe them in words or implement as procedures with side effects. In non-functional languages such computations are often called “functions” anyway– I’ll enclose such usage with quotation marks. Eugenio Moggi, the guy who introduced monads to computing, listed a few examples:

你已经知道什么是函数：用同样的参数调用，总是返回同样的记过。许多有用的计算可以直接对应到函数，同样也有许多不能。我们常常处理那些不是函数的计算概念。我们可以把它们描述为带副作用的过程。在非函数式编程语言中，这样的计算也被叫做“函数”——我会把这种用法用引号括起来。把单子的概念引入到计算中的Eugenio Moggi列出了一些例子：

• Partial “functions”: For some arguments they never terminate (e.g., go into an infinite loop). These are not really functions in the mathematical sense.
• 不完整“函数”：对于有些参数，它们永不停止（例如进入无穷循环）。数学的意义上这不是真正的函数。
• Nondeterministic “functions”: They don’t return a single result but a choice of results. Non-deterministic parsers are like this. When given an input, they return a set of possible parses. Which of them is right depends on the context. These are not really functions because a function must return a single value.
• 非确定性“函数”：它们不是返回一个值，而是一些值的其中之一。非确定性解析就是这样的。对于给定的输入，它们返回一个可能解析的集合。那一个有效取决于上下文环境。这些不是真正的函数因为函数只能返回一个值。
• “Functions” with side effects: They access and modify some external state and, when called repeatedly, return different results depending on that state.
• 带副作用的“函数”：它们访问和修改一些外部状态。这样重复调用的时候，返回值依赖于这些状态。
• “Functions” that throw exceptions: They are not defined for certain arguments (or states) and they throw exceptions instead of returning a result.
• 抛出异常的“函数”：对于某些参数（或状态），它们未定义。同时抛出一个异常而不是返回一个值。
• Continuations.
• 延续体。
• Interactive input:

  getchar

  is a good example. It’s result depends on what hits the keyboard.
• 交互式输入：getchar就是个例子。其结果取决于键盘上敲什么；
• Interactive output:

  putchar

  is a good example. It’s not a function because it doesn’t return anything (if it returns an error code, it doesn’t depend on the argument). Still, it can’t be just optimized away if we want any output to appear on the screen.
• 交互式输出：putchar就是个例子。它不返回任何东西（它可以返回错误吗，但是这不是决定于输入参数），所有不是函数。另外，如果你想在屏幕上看到任何输出的，这个也绝对不能被优化掉。

The amazing thing is that, using some creative thinking, all these problems can be solved using pure functional methods. I won’t discuss all of them, but I’ll show you a series of progressively more interesting examples.

最令人兴奋的事情是，使用一些创新型的思维，所有这些问题都可用纯函数是的方法解决。我不会全部讨论这些，而是给出一系列渐进而且有趣的例子。

Error Propagation and Exceptions

错误传播和异常

Who doesn’t deal with error propagation? Let’s dissect the problem: You are defining a computation that can return a valid result only for a subset of possible arguments. So what happens when the argument is “wrong”? Well, you can return an error.

谁不会遇到错误的传播问题呢？我们来讨论这个问题。你可以定义一个计算过程，对仅仅有效的的输入参数子集才返回一个有效的值。那么当参数是“错误”的时候怎么办呢？你可以返回一个错误。

In the simplest case you might add one extra bit, success or failure, to your result. Sometimes you can spare a bit in the result type: If the correct result is always a non-negative number, you may return negative one as an error. Or, if the result is a pointer, you might return a null pointer instead. But these are just small hacks introduced for the sake of performance. And, like most hacks, they can lead to dangerous code. Consider this (likely incorrect) code:

简单的情况下，可以在返回值中增加额外的bit来表征成功和失败。有时候可以在返回值中设置一些备用位。如果结果总是非负数字，你可以返回负一作为错误；如果结果是指针，那么你可以返回空指针。但是这不过是小点的蛮干罢了。和大多数的蛮干类似，这也会导致危险的代码，看下面的（看似正确）的例子：

size_t off = fileName.find('.');      

string ext = fileName.substr(off, fileName.length() - off);      

If

fileName

contains no dot, the result is a special value

npos

signifying an error. The problem is that

npos

is of the same type as a non-error result, so it can be passed quietly to

string::substr

causing undefined behavior.

如果fileName不包含点，返回特殊值npos来表征错误/问题在于npos和非错误的返回值是一样类型的。因此可以毫不声响地传给string::subst，最后导致为定义的行为。

A more general and safer solution is to change– extend– the type of the result to include an error bit. You can do it for any type of result. In Haskell, you just define a type constructor called

Maybe

:

一个更通用，更安全的方案是去改变——扩展——返回值的类型来包含错误位。对任何的错误都可以这样做。在Haskell中，定义一个叫做Maybe的类型构造器：

data Maybe a = Nothing | Just a      

It takes an arbitrary type

a

and defines a new type that adds the special value

Nothing

to the set of possible values of

a

. In C++ that would be equivalent to a template:

它接受任意类型a然后通过把a的可能取值的集合加一个特殊值Nothing来定义一个新的类型。C++中，它等价于如下模板：

template<class T>      

struct Maybe {      

    T just; // valid if 'nothing' is false      

    bool nothing;      

};      

(This is just an example. I’m not arguing that

Maybe

would be very useful in C++ which has other mechanisms for error propagation.)

（这仅仅用作例子，我并不是争辩说Maybe在C++中非常有用，C++有处理错误传播的其他机制。）

So here we have a way to turn a computation that’s not defined for all values into a function that’s defined over the whole domain, but which returns a new richer type.

所以现在我们有了一种方法，可以把并不是对所有的值都有定义的函数转换成一个在所有的域上都有定义的函数，不过返回一个新的更丰富的类型。

The next question is, do these new things– functions returning

Maybe

– compose? What should the caller do with the result of such a function when it’s part of a larger computation? One thing is for sure, this result cannot be passed directly to an unsuspecting function–the error cannot be easily ignored– which is good. If we replace

find

by a new function

safe_find

that returns a

Maybe<size_t>

, the client won’t call

substr

with it. The types wouldn’t match. Instead, the result of

safe_find

must be unpacked and (much more likely than before) tested.

接下来的问题是，这个返回Maybe的新东西可以组合吗？当调用者本身是更大的计算的一部分的时候如何这样的函数的返回值呢？可以确定的一件事是，返回值不能直接传递给一个对此一无所知的函数，否则错误很容易被忽略。这对我们来说是好事。如果我们用返回Maybe<size_t>的safe_find来替换find的话，因为类型不匹配，客户代码就不能调用substr了。以此，我们需要解包safe_find的返回值并且做测试判断（和先前很类似）。

Maybe<size_t> off = safe_find(fileName, '.');      

string ext;      

if (!off.nothing)      

    ext = fileName.substr(off.just, fileName.length() - off.just);      

Notice what happened here: By changing the return type of a function we broke the natural way functions compose– the result of one becoming the input of the next. On the other hand, we have come up with a new way of composing such functions. Let me chain a few of such compositions for better effect:

注意这儿的情况：由于改变了函数的返回类型，我们也破坏了原先组合函数的自然方法——把一个函数的输出作为另一函数的输入。但是与此同时，我们也得到了另一种新的组合这样函数的方式。我们把这样的组合串起来使其效果明显。

Maybe<Foo> foo = f(x);      

if (!foo.nothing) {      

    Maybe<Bar> bar = g(foo.just);      

    if (!bar.nothing) {      

        Maybe baz = h(bar.just);      

        if (!baz.nothing) {      

            ...      

        }      

    }      

}      

I have highlighted the elements of the “glue,” which is used to compose our new, more error-conscious functions. Notice how this boilerplate glue gets in the way of code clarity. Ideally, we would like to write something like this:

我把“胶水”代码高亮显示，这些代码用来组合我们这些包含错误处理的新函数。注意那些样板代码是如何直观地把事情搞定的。理想情况下，我们最好可以写如下的代码

DO      

{      

    auto y = f(x);      

    auto v = g(y);      

    auto z = h(v);      

    return z;      

}      

where

DO

would magically provide the glue that’s implicit in the chaining of

f

,

g

, and

h

.

这里DO会魔术般地把f，g和h隐式地串联起来。

It’s not easy to do this– abstract the glue away– in C++. I’m not even going to try. But in Haskell it’s a different story. Let’s start with the almost direct translation of the C++ code into Haskell:

在C++中把这些胶水代码抽象出去不大容易，我甚至不想去尝试。不过在Haskell中情况就不同了。我们先从最把C++代码直接翻译成Haskell代码开始：

compose n =      

    let m = f n in      

    case m of      

    Nothing -> Nothing      

    Just n1 ->      

        let m1 = g n1 in      

        case m1 of      

        Nothing -> Nothing      

        Just n2 ->      

            let n3 = h n2 in      

            n3      

The if statements are replaced by Haskell’s pattern matching (

case x of

). The

m

s are the

Maybe

s and the

n

s art their contents (if they aren’t

Nothing

s).

If语句被Haskell的模式匹配（case x of）所取代。ms表示一些Maybe而ns表示其内容（如果内容不是Nothing）。

Notice the characteristic cascading style of this code– the nested conditionals or pattern matches. Let’s analyze one level of such a cascade. We start with a

Maybe

value (one returned by

f n

). We unpack it and examine the contents. If the result is not an error (

Just n1

), we continue with the rest of the body of

compose

. I have highlighted the “rest of the body” in blue (the “glue” is still in red).

注意这些代码非常明显的层叠式风格，无论是嵌套的条件判断还是模式匹配。我们分析一层这样的层叠。从一个Maybe值开始（由f n所返回），我们首先解包，然后处理其内容。如果不是错误（Just n1）则继续compose函数的后面部分。我们后面的这部分用蓝色高亮显示（胶水代码依旧使用红色）。

What’s also important is that, if the result is an error (the

Nothing

branch of the pattern match) the whole “rest of the body” is skipped. In order to abstract the glue, we have to abstract the “rest of the body” as well. Such an abstraction is called a continuation. Let’s write this continuation as a lambda (lambdas in Haskell are written using the backslash, which is nothing but the Greek letter λ missing one leg):

另一个重要点在于，如果结果是错误（模式匹配的Nothing分支），整个“后面部分”都直接挑过。要想抽象这些辅助代码，我们先得抽象“后面部分”。这样的抽象称为“延续体”。现在把这个延续体写为lambda运算（Haskell中lambda使用反斜线开始，也就是少了一条腿的希腊字母λ）：

/ n1 ->      

    let m1 = g n1 in      

    case m1 of      

    Nothing -> Nothing      

    Just n2 ->      

        let n3 = h n2 in      

        n3      

And here’s the trick: We can abstract the glue as a (higher-order) function that takes a

Maybe

value and a continuation. Let’s call this new function

bind

and rewrite

compose

with its help:

技巧性在于，我们可以把辅助的胶水代码抽象为一个带有Maybe值的（高阶）函数。现在把这个函数叫做bind，然后使用它重写compose：

compose n =      

    let m = f n in      

    -- the first argument is m, the second is the whole continuation      

    bind m (/n1 ->      

                let m1 = g n1 in      

                case m1 of      

                Nothing -> Nothing      

                Just n2 ->      

                    let n3 = h n2 in      

                    n3)      

Here’s how

bind

is implemented:

下面的bind的实现：

bind m f =      

    case m of      

    Nothing -> Nothing  -- bypass the continuation      

    Just n -> f n       -- pass n to the continuation      

or, more compactly,

或者更精简的形式，

bind Nothing cont  = Nothing      

bind (Just n) cont = cont n      

Figure 1 illustrates the complete code transformation. The result of

f n

, which is a

Maybe

, is passed to

bind

, represented by a blue box. Inside

bind

the

Maybe

is unpacked. If its value is

Nothing

, nothing happens. If its value is

Just n1

, the rest of the code, the continuation, is called with the argument

n1

. The continuation itself is rewritten using

bind

, and so on. The final continuation calls

return

, which I will explain shortly.

图1展示了完整的代码转换。f n的调用结果是Maybe，然后传给bind，bind用蓝色的框表示。在bind内部，Maybe首先解包。如果是Nothing，一切早就；如果是Just n1，就会用参数n1调用余下部分代码，也就是延续体。最后一个延续体调用return，这个稍后解释。

Fig 1. Composition of functions that return Maybe results

图1 返回Maybe结果的函数组合

The position of

bind

, the blue box in Figure 1, between its

Maybe

argument and the continuation suggests that infix notation might be more appropriate. Indeed, in Haskell

bind

is represented by the infix operator,

>>=

:

Bind的位置，图一中蓝色的框，处于其参数Maybe和延续体之间，这暗示着中缀表示法可能更合适。事实上，Haskell中bind就是用中缀操作符>>=来表达的：

Nothing  >>= cont = Nothing      

(Just x) >>= cont = cont x      

(The left-hand side of the equal sign is the operator between its two arguments [actually, patterns], and the right-hand side is the body of the function.) We can express the type signature of the bind function as:

（等号左边的是其两个参数『亦即模式』的操作符，等号右边的是函数体）我们可以把bind函数的类型签名表示为：

(>>=) :: Maybe a -> (a -> Maybe b) -> Maybe b      

It takes a

Maybe a

and a function from

a

to

Maybe b

(that’s our continuation). It returns a

Maybe b

. When dealing with higher order functions I find type signatures extremely useful; so much so that I often use them as comments in my C++ meta-code.

它带两个参数，Maybe a和从a到Maybe b的映射的函数（延续体），返回Maybe b。处理高阶函数的时候，我发现类型签名极其有用，以至于我常常把它们用作C++元代码的注释。

The complete rewrite of

compose

using

>>=

looks like this:

使用>>=完全重写compose后是这个样子

compose1 n =      

    f n >>= /n1 ->      

        g n1 >>= /n2 ->      

            h n2 >>= /n3 ->      

                return n3      

Now is the time to explain the mysterious

return

at the end of the function. No, it’s not the keyword for returning a result from a function. It’s a function that takes an argument of type

a

and turns it into a

Maybe a

:

显示可以解释函数末尾那个神秘的return了。这不是一个从函数中返回值的关键字。它是一个函数，以类型a为参数，把它转换为Maybe a：

return n = Just n      

We need

return

because the result of

compose

is a

Maybe

. If any of the functions returns

Nothing

,

compose

returns

Nothing

(it’s part of the definition of

>>=

). Only when all functions succeed do we call

return

with the correct result,

n3

. It turns

n3

into

Just n3

, thus announcing the success of the computation and encapsulating the final result.

Return之所以必要是因为compose的结果是Maybe类型。如果其中任何一个返回Nothing，compose就返回Nothing（这是>>=定义的一部分）。仅当所有的函数调用成功，我们才会和n3调用return。它把n3转化为Just n3然后宣称计算成功并封装了最终的结果。

You might say that using

return

instead of

Just n3

is an overkill, but there are good reasons to do that. One is to encapsulate and hide direct access to the implementation of

Maybe

. The other has to do with the ways this pattern is generalized beyond

Maybe

.

你可能会说使用return而不是直接的Just n3有点小题大做，但是这样做是有充分理由的。其一是封装并隐藏对Maybe实现的直接访问；其二是这是种通用的处理方式，适用于除了Maybe的其他情况。

The Maybe Monad

Maybe单子

What does

Maybe

have to do with monads? Let’s see what we have done so far from a more general perspective.

这个Maybe和单子有什么关联呢？我们从更一般的角度看一下我们所做的一切。

We started from a computation which didn’t behave like a function– here, it was not defined for all arguments. We had found a clever way to turn it into a function by enriching its return type. Such general “enriching” of types can be expressed as a type constructor.

我们从一个行为不像函数（并没有对所有的参数都有定义）的计算开始。我们找到一种巧妙的办法，通过强化它的返回值类型来使之变成一个函数。这种类型强化方法可以使用类型构造器来表达。

From a category-theoretical point of view, defining a type constructor, which is a mapping from types to types, gets us half way towards defining an endofunctor. The other part is the mapping of functions (morphisms). For any function that takes values of type

a

and returns values of type

b

we need a corresponding function that acts between the enriched types. In Haskell, the mapping of functions to functions can be expressed as a higher-order function. When this mapping is part of an endofunctor, the corresponding higher-order function is called

fmap

.

从范畴论的角度看，定义类型构造器（比一个类型对应到另一个类型）已经让我们走在了通往自函子的大道上。另一部分是函数（映射）的对应。对于任何的带类型为a的参数，并且返回类型为b的函数，我们需要一个相应的作用在增强的类型上的函数。Haskell中，函数到函数的对应可以表达为稿件函数。当这种对应是自函子的一部分的时候，对应的高阶函数被称为fmap。

Let’s call the type constructor

M

. It constructs the enriched type

M a

from any type

a

. The function

fmap

has the following signature:

我们把类型构造器称为M。它从任意的类型a可以构造一个增强的类型M a。函数fmap有如下签名：

fmap :: (a -> b) -> (M a -> M b)      

It maps a function from

a

to

b

to a function from

M a

to

M b

. In the case of

Maybe

we already know the type constructor part, and

fmap

will follow soon.

它把一个从a到b的函数对应到一个从M a到M b的函数。在Maybe的例子中，已经知道类型构造器部分，fmap部分下面给出。

Let’s go back to our computation turned function returning an enriched type. In general, its signature is:

我们先回到返回增强类型的函数。它的签名一般是：

f :: a -> M b      

Since we care about composability of computations, we need a way to glue the enriched functions together. In the process of gluing we usually have to inspect the enriched type and make decisions based on its value. One of such decisions might be whether to continue with the rest of the computation or not. So the general

bind

operation must take two arguments: the result of the previous enriched function and the rest of the computation– a continuation:

因为我们只关心计算的可组合性，我们需要一种机制把增强的函数黏在一起。在黏结的过程中，我们一般要检查增强的类型，并且依据其值作出判断。其中的一种判断是要不要继续执行余下的计算。因此泛化的bind操作符必须带两个参数：前一个增强函数的返回值以及后面的计算部分——延续体。

bind :: M a -> (a -> M b) -> M b      

If you squint enough, you can see a similarity between

bind

and

fmap

.

多看几眼，就会发现bind和fmap的相似之处。

Here’s how you do it: Imagine that you supply

bind

with its second argument, the continuation. There is still one free parameter of the type

M a

. So what’s left is a function that takes

M a

and returns

M b

. (This is not exactly currying, since we are binding the second argument rather than the first, but the idea is the same.) That’s exactly the type of function that occurs on the right hand side of the signature of

fmap

. Seen from that point of view,

bind

maps functions into functions:

你这一这么做。想象你仅仅提供第二个参数，就是延续体那部分。现在还有一个空余的类型为M a的参数。所以我们得到的是一个带一个M a类型的参数，返回M b类型的函数。（这不是真正意义上的Currying，我们绑定了第二个而非第一个参数，不过思想是一致的）这恰恰是fmap签名右边的函数的类型。从这个观点看，bind把函数对应到函数。

(a -> M b) -> (M a -> M b)      

The function of the left hand side is our continuation, the one on the right hand side is

bind

with the second argument plugged by the continuation.

左边的函数就是延续体，右边的一个是bind，其第二个参数已经被延续体占据。

This signature is really close to that of

fmap

, but not quite. Luckily, we still have a second family of functions at our disposal, the polymorphic

return

. The signature of

return

is:

这个签名和fmap非常相近，但是还有点不一样。幸运的是，我们还有另一簇没有提及的函数，那就是多态的return。Return的签名是

return :: a -> M a      

Using both

bind

and

return

we can lift any function

f

:

把bind和return联合起来，我们可以提升任何函数f：

f :: a -> b      

to a function

g

:

为函数g：

g :: M a -> M b      

Here’s the magic formula that defines

g

in terms of

f

,

bind

, and

return

(the dot denotes regular function composition):

这就是使用f，bind和return来定义g的神奇公式（点表示一般的函数组合）

g ma = bind ma (return . f)      

Or, using infix notation:

使用中缀形式：

g ma = ma >>= (return . f)      

This mapping of

f

into

g

becomes our definition of

fmap

. Of course,

fmap

must obey some axioms, in particular it must preserve function composition and interact correctly with unit (of which shortly). These axioms translate back into corresponding conditions on

bind

and

return

, which I’m not going to discuss here.

从f到g的对应变成了fmap的定义。当然，fmap必须遵循一些基本的原则，特别它必须保证函数的可组合性以及与（其）单元的正确交互。这些公理翻译成相应的关于bind和return的条件TODO。 这些这里不会讨论。

Now that we have recovered the functor, we need the two other parts of a monad: unit and join. Guess what,

return

is just another name for unit. For any type, it lifts an element of that type to an element of the enriched type in the most natural manner (incidentally, the word natural has a very precise meaning in category theory; both unit and join are natural transformation of the functor (M, fmap)).

现在我们找回了函子，我们还需要单子的另外两部分：单元和联合。猜猜怎么样，return就是单元的另一个名字。对于任何类型，它以一种最自然的方式把该类型元素提升为增强类型的元素（很是巧合，自然这个词在范畴论中有非常准确的含义，单元和联合是函子(M, fmap)的自然转换）。

To recover join, let’s look at its type signature in Haskell:

要找回联合，先看看Haskell中它的类型签名：

join :: M (M a) -> M a      

It collapses one layer of the type constructor. In the case of

Maybe

it should map a double

Maybe

to a single

Maybe

. It’s easy to figure out that it should map

Just (Just x)

into

Just x

and anything else to

Nothing

. But there is a more general way of defining

join

using

bind

combined with the identity function:

这是重叠的类型构造器。在Maybe的例子中，它把双Maybe对应到单Maybe。很容易发现它会把just (Just x)对应到Just x，把其他所有都对应到Nothing。但是还有一种更通用的适应bind和单位元函数定义联合的方式

join :: M (M a) -> M a      

join mmx = mmx >>= id      

We are binding a value of type

M (M a)

to a function

id

. This function, when acting on

M a

returns

M a

. You can convince yourself that these signatures match the general signature of

bind

; and that this definition, when applied to

Maybe

, produces the correct result.

我们把类型为M (M a)的类型绑定到函数id。该函数对M a返回M a。现在可以确信这些签名可以等价于bind的一般签名。该定义作用于Maybe的时候，也得到了正确的结果。

To summarize: What we have done here is to show that

Maybe

together with

bind

and

return

is a monad in the category-theory sense. Actually, we have shown something far more general: Any triple that consists of a type constructor and two functions

bind

and

return

that obey certain identities (axioms) define a monad. In category theory this triple is called a Kleisli triple and can be used as an alternative definition of a monad.

总结：我们这里展示了Maybe，再加上bind和return就是一个范畴论意义上的单子。实际上，我们展示更为一般的东西，任何由类型构造器以及两个函数bind和return组成的满足单位元公理的三元组都是一个单子。范畴论中这样的三元组叫做Kleisli三元组，当作单子的另一种定义。

Syntactic Sugar

语法糖衣

So far you’ve seen only the

Maybe

example, so it might seem like we are pulling out a monadic cannon to kill a mosquito. But, as you’ll see later, this same pattern pops up in a lot of places in various guises. In fact it’s so common in functional languages that it acquired its own syntactic sugar. In Haskell, this sugar is called the do notation. Let’s go back to the implementation of our function

compose

:

目前我们只看了Maybe的例子，这有点像用单子大炮只为打死一只蚊子。不过，稍后依旧会看到同样的模式会在许多地方以不同的方式出现。事实上这种情况在函数式语言中如此普遍，需要专门的简化语法。Haskell中，这样的语法糖衣叫做do记号。回过头去看compose的实现：

compose n =      

    f n >>= /n1 ->      

        g n1 >>= /n2 ->      

            h n2 >>= /n3 ->      

                return n3      

Here’s exactly the same code in do notation:

这是使用do记号的相同的代码：

compose n = do      

    n1 <- f n      

    n2 <- g n1      

    n3 <- h n2      

    return n3      

This looks deceptively similar to an imperative program. In fact here’s a C++ version of it (for the sake of the argument let’s assume that

f

takes a pointer to

Foo

and

h

returns an integer) :

非常有欺骗性，这个看起来很像命令式语言。实际上C++的版本就是（假设f带一个指向Foo的指针而h返回一个整数）：

int compose(Foo * n)      

{      

    auto n1 = f(n);      

    auto n2 = g(n1);      

    auto n3 = h(n2);      

    return n3;      

}      

Uh, one more thing. This is how you would call it:

哦，还有一点。你应该这样调用：

try {      

    compose(pFoo);      

}      

In C++ you get virtually the same functionality not by modifying the return type, but by throwing an exception. (Now you may utter your first cry, “Hey, that looks like a monad!”, when looking at C++ code.)

C++中你实际上并不是通过修改返回值类型而是抛出异常而得到相同的结果（现在你看到C++代码的时候，就可以惊叹说“嗨，这不就是单子嘛！”）。

Just like in our Haskell example, once any of the functions reports an error (throws an exception), the rest of the body of 

compose

 is skipped. You might say that C++ exceptions offer more power than the 

Maybe

 monad and you’ll be right. But that’s because I haven’t shown you the 

Error

 monad and the 

Exception

 monad.

和Haskell的例子一样。一旦其中一个函数报告一个错误（抛出异常），compose的余下部分就会被跳过。你可能要说C++异常要比Maybe单子更强大，这一点是你的对的。仅仅因为我还没有给你展示错误单子和异常单子。

Where Haskell’s 

Exception

 monad beats C++ exceptions is in type checking. Remember the unfortunate attempt at adding exceptions specification to the C++ type system? (Java went the same way.) Here’s what the C++ standard says:

Haskell异常单子胜过C++异常在于其类型检查。还记得曾经往C++中增加异常规范的不幸的尝试吗（Java重蹈了C++的覆辙）？看看C++标准是怎么说的:

An implementation shall not reject an expression merely because when executed it throws or might throw an exception that the containing function does not allow.

实现不应该仅仅因为一个表达式在执行的时抛出或者可能抛出一个其容器函数不允许的异常而拒绝它。

In other words, exceptions specifications are bona fide comments. Not so in Haskell! If a function returns a 

Maybe

 or 

Exception

, that becomes part of its type signature which is checked both at the call site and at the function definition site. No cheating is allowed, period.

换句话说，异常规范不过是一个诚实的注释而已。Haskell却不是这样！当一个函数返回Maybe或异常的时候，这就是其类型签名的一部分，在调用和定义的时候都会被检查。没有协商的余地，句号。

But the major difference between Haskell’s and C++’s approach is that the 

do

 notation generalizes to all monads, whereas C++ neat 

try/catch

 syntax applies only to exceptions.

不过Haskell和C++的方法的最大的区别是do记号一般化了所有的单子，而C++齐整的try/catch语法仅仅适用于异常。

A word of caution when reading Haskell monadic code. Despite similarities in usage, Haskell’s left arrow is not an assignment. The left hand side identifier corresponds to the argument of the continuation (which is the rest of the 

do

 block). It is the result of unpacking the outcome of the right hand side expression. This unpacking always happens inside 

bind

.

阅读Haskell单子型的代码的要注意一点。除去用法上的相似，Haskell的左箭头并不是赋值。左边的标识符对应于延续体的参数（也就是do代码块余下的部分）；它是右边的表达式执行后的解包结果。解包过程总是在隐藏的bind中实现。

Non-deterministic Computations

非确定性计算

In the previous post I introduced the list monad by defining a functor and two families of functions. The type constructor part of the functor mapped any type 

a

 into the list of 

a

, 

[a]

. The part that acted on functions (now we know that, in general, it’s called 

fmap

; but for lists it’s just 

map

) worked by applying the function to each element of the list. The 

unit

 and the 

join

 were polymorphic functions. 

unit

 was defined as:

上一篇文章中，通过定义一个函子以及两簇函数，我引出了列表单子。函子的类型构造器部分把任意类型a对应到a的列表[a]。作用在函数上的那部分（我们现在知道，一般来说叫做fmap，但是对于列表，就叫map）通过在列表中的每一个元素上调用起作用。单位和联合是多态函数。单位定义如下：

 unit x = [x]      

and 

join

 as 

concat

.

而联合就是concat。

Now I can tell you that the list monad provides the solution to the problem of implementing non-deterministic computations. Imagine parsing a non-deterministic grammar. A production might offer multiple alternative parse trees for the same input.

现在我和你说列表单子提供了处理非确定性计算问题的办法。想想非确定性语法解析。对于同样的输入，一个过程可能产生多个可互换的解析树。

These types of computations may be simulated with functions returning lists of possible results. Here’s the same trick again: whatever type is returned by a deterministic parser (e.g., a parse-tree type), it’s now turned into an enriched type (a parse tree list).

这种类型的计算可以通过返回一个可能结果的列表来模拟。还是那个技巧，确定性的解析器返回的任何结果类型（如解析树类型），都被转化为强化的类型（解析树列表）。

We’ve already seen the category-theory construction of the list monad but here we are facing a slightly different problem: how to string together functions that return lists. We know that we have to define 

bind

. It’s signature, in this case, would be:

我们已经看到列表的单子的范畴论构造，不过稍有不同：如何把返回列表的函数链在一起。我们知道必须定义bind。这种情况下，其签名应该是：

bind :: [a] -> (a -> [b]) -> [b]      

It takes a list (which is the result of a previous function) and a continuation, 

(a -> [b])

, and must produce another list. The obvious thing is to apply the continuation to each element of the input list. But since the continuation also produces a list, we’ll end up with a list of lists. To get a single list as the result, we’ll simply concatenate the sublists. Here’s the final implementation:

它带一个列表（这是上一个函数的结果）和一个延续体参数(a -> [b])，产生另一个列表。很明显，要在输入列表的每一个函数上应用延续体。不过由于延续体的输出是列表，我们最后得到的是列表的列表。要得到一个简单列表，我们需要把子列表连接在一起。这是最后的实现：

xs >>= cont = concat (map cont xs)      

The application of the continuation to each element of the input list is done using 

map

.

在输入列表上应用延续体的操作是通过map来完成的。

Is this a coincidence that we were able to define bind in therms of join and fmap? Not at all. The general formula for converting the functor definition of a monad to a Kleisli triple is:

使用联合和fmap来定义并bind是一个巧合吗？完全不是。把单子的函子定义转换为Kleisli三元组的一般公式是：

• Take the object-mapping part of the functor (the type constructor)
• 取函子的映射对象的部分（类型构造器）
• Define bind as
• 把bind定义为

bind x f = join ((fmap f) x))      

where 

fmap

 is the part of the functor that maps morphisms.

这儿fmap是函子中把映射对应起来的那部分

• Define return as unit
• 把return定义为单元

Now we know how to move between those two definitions back and forth.

现在我们可以在这两种定义之间来回移动了。

Just as in the case of 

Maybe

, we can apply the do notation to functions returning lists:

就和Maybe的情况一样，对于返回列表的函数也可以使用do记号：

toss2Dice = do      

    n <- tossDie      

    m <- tossDie      

    return n + m      

Here, 

tossDie

 returns the list of all possible outcomes of a die toss, and 

toss2Dice

 returns the list of all possible sums of the outcomes of a two-die toss.

这里tossDie返回仍一个色子的所有可能输出的列表，而toss2Dice返回仍两个色子的结果的所有可能和的列表。

An interesting observation is that the list monad is closely related to list comprehensions, down to the use of left arrows (in Haskell). For instance, the above example is equivalent to:

一个有趣的特点是列表单子和列表推断很相关。例如，上面的例子等价于：

toss2Dice = [n + m | n <- tossDie, m <- tossDie]      

Conclusions

结论

There is a large class of computations that convert input to output in a non-functional way. Many of those can be expressed as functions that return “enriched” output. This enrichment of the output can be expressed in terms of a type constructor. This type constructor defines the first component of a monad.

存在大量的以非函数的方式对输入进行处理的计算。其中很多都可以表达为返回一个“增强”的返回类型的函数。这种输出类型的增强可以使用类型构造器来比表达，它定义了单子的第一个组件。

Computations have to be composable, so we need a way of composing the enriched functions. This introduces the second component of the monad, the 

bind

 family of higher-order functions.

计算必须可组合，因此我们需要要中这增强的函数方法。这引出了单子的第二个组件，高阶函数的bind函数簇。

Finally, we should be able to construct functions that return enriched types, and for that we need the third component of the monad, the 

return

 family of functions. They convert regular values into their enriched counterparts.

最后，我们应当构造返回增强类型的函数，为此，我们需要单子的第三个组件，函数的return函数簇。它们把普通的类型转换为增强的对应类型。

I’ve shown you two examples of Haskell monads in action, but the real treat will come in the third installment of my mini-series. I’ll show you how to define and compose functions that, instead of returning regular values, return functions that calculate those values.

我想你展示了两个Haskell单子的实际例子，不过真正的重点是在我这里迷你系列的第三部分。我将向你展示如何定和组合函数，不是返回常规类型，而是返回计算这些类型值的函数。

Bibliography

文献

1. Eugenio Moggi, Notions of Computation and Monads. This is a hard core research paper that started the whole monad movement in functional languages. 这是函数式语言中开启单子运动的核心论文。
2. Philip Wadler, Monads for Functional Programming. The classic paper introducing monads into Haskell.该经典论文在Haskell中引入了单子
3. Tom Adams, What Does Monad Mean?
4. Brian Beckman, Don’t fear the Monad
5. Graham Hutton, Erik Meijer, Monadic Parsing in Haskell.
6. Brian McNamara, Yannis Smaragdakis, Syntax sugar for FC++: lambda, infix, monads, and more. A C++ template library for functional programming that imitates Haskell pretty closely.极好地模拟了Haskell的用于函数式编程的C++模板库