Monad

Posted on | In |

Monad

对于很多人来说，“Monad”是一个“神奇”的概念。这个概念首先在数学中被提出，用来简化一些复杂定理的描述。后来在Haskell中被使用。而实际上，所有主流高级语言都有Monad，只不过不一定被明确的标注出来，例如：ES6的Promise、Java的Optional。本文会通俗的描述什么是Monad，以及如何定义和使用。

The Easy Way: 抽象和拆分

可以参考youtube这个视频

普通的函数复合

假设我们现在有三个类型a、b、c。

现在定义两个函数，

1
2
f :: a -> b
g :: b -> c

可能有人不理解这组符号的含义。f :: a -> b 指的是：f具有类型a -> b。其中a -> b指的是一个函数，接收a类型的参数，返回b类型的参数。

用java的话来说，f :: a -> b 就相当于

1
<A, B> B f(A a);

后面我们都以haskell写法，也就是f :: a -> b来做描述。

我们都知道，函数可以复合。比如我现在有一个值x，类型为a，我就可以调用f x，得到一个类型为b的值，记作y。然后我调用g y，得到一个类型为c的值，记作z。假如我只想得到z，我可以把f和g复合起来，从而忽略中间值y。

1
2
h = g . f          -- h = g (f x)
z = h x

所以，如果我们想把两个函数拼起来，很简单，只要用.号即可。这解决了编程过程中的一个问题：逻辑拆分。将一个大逻辑拆分成小逻辑，然后再用.把这些小逻辑串起来。

返回“在某个空间里的数据类型”的函数的复合

我们把函数和类型拓展一下：

1
2
f :: a -> m b
g :: b -> m c

现在我们有两个函数，一个接收a类型，并返回m b类型。什么是f :: a -> m b？这在java中没有对应，因为java的类型系统不支持kind。但是如果一定要写的话，可以写成这样：

1
<A,B,M> M<B> f(A a);

B作为M的类型参数，也可以说，B在M空间里。

现在我们再定义两个函数：

1
2
\x -> f x        (lambda 1)
\y -> g y        (lambda 2)

很显然，lambda 1 返回m x，lambda 2 接收y，而非m y，所以这两个函数没有办法简单的使用之前提到的.进行复合。我们在这里给出一个新的符号：bind: >>=

1
\x -> f x >>= \y -> g y

可以看到\y -> g y除了调用g外什么也没做，所以我们可以直接将其简写为g

1
\x -> f x >>= g

但是左边的\x -> f x并不能进行合并。因为我们必须要一个x作为参数传入，即：

1
\x -> (f x >>= g)

于是，我们得到了一个运算符>>=。让我们看看它的类型签名。

这是一个二元运算符，所以接收两个参数，并会返回一个结果：

接收: 1) f x 2) g，即: 1) m x 2) y -> m y
返回: m y （原因可能没有那么直观，这里描述下。因为我们想把两个函数复合起来，复合的结果一定是后一个函数的返回结果，所以这个运算符的返回类型一定是后一个函数的返回类型）

根据lambda的阿尔法变换规则，我们可以随意修改参数名称，我们写得好看一些，可以是这样：

1
>>= ::  m a -> (a -> m b) -> m b

到此，monad中最重要的一个运算符>>= (bind)被我们“推”出来了。

Monad的bind，和普通的函数复合，想要做的事情是一样的。了解了这一点，Monad的理解上就没什么难度了。

The Hard Way: 自函子范畴上的幺半群

我们换一个角度来认识Monad。

网上对于Monad，流传着这句话：

A monad is just a monoid in the category of endofunctors

不过它的最初版本是这样的：

All told, a monad in X is just a monoid in the category of endofunctors of X, with product × replaced by composition of endofunctors and unit set by the identity endofunctor.

这句话其实对学习Monad没有什么用，但是还是给了我们一个方向。

首先看看什么是幺半群。

幺半群 Monoid

有一个运算符*，作用在一个集合S上。
1) 对S中任意的三个元素a、b、c，都有： (a * b) * c = a * (b * c)
2) S中存在e，使得任意S中的元素a，都有：(a * e) = (e * a) = a

满足上述条件的运算符和集合，就是一个幺半群。

实际上，对于幺半群，在Haskell中也有相应的定义：

1
2
3
4
5
class Monoid m where
  mempty :: m
  mappend :: m -> m -> m
  mconcat :: [m] -> m
  mconcat = foldr mappend mempty

mempty返回幺元，就是那个e
mappend对应幺半群中的那个运算符
mconcat是haskell库的需要，已经有默认实现，通常不需要我们关注。

除了类型上要满足，还需要程序保证：

  1. a mappend (b mappend c) == (a mappend b) mappend c
  2. a mappend mempty == mempty mappend a == a

即幺半群的定义。

光看定义可能有些抽象，我们举个例子。比如说List

在Java里，我们可能写：Arrays.<String>asList("a", "b", "c")。List结构 加上 连接运算，就是一种Monoid。

  1. 存在一个空链表
  2. 空链表连接任何链表，不管在左边连接还是在右边连接，最后都返回相同的链表
  3. 链表的连接符合运算符结合律

Monoid抽象出了“像List那样的数据结构”的共有特征，使得数据处理变得容易。

函子 Functor

我们熟悉的函数表示的是类型间的映射，例如Int -> String。
而函子表示的是范畴间的映射，例如List<Int> -> List<String>。可以简单的看成：

函数：a -> b
函子：t a -> t b

其实函子很好理解，例如map就是一种函子，接收一种List，返回另一种List

在Haskell中，函子是这样定义的：

1
2
class Functor f where
    fmap :: (a -> b) -> f a -> f b

很清晰，fmap这个函数接收一个把a映射到b的函数，并接收一个带有a类型的Functor实例，返回一个带有b类型的Functor实例。

在面向对象编程中，我们通常会有list.map(a->a.toString())之类的写法，这两者是完全相同的。其中的list就是f a，a -> a.toString就是(a -> b)，返回的结果就是f b。

Applicative

除了上述两个我们需要了解以外，还有一样东西我们需要了解一下：Applicative

在上面的Functor中，我们有处理包装起来的数据的能力。但是如果函数也被包装起来，我们就需要Applicative。

1
2
3
class (Functor f) => Applicative f where  
    pure :: a -> f a  
    (<*>) :: f (a -> b) -> f a -> f b

函数pure将任意一种类型的值包装到Applicative的实例中。

函数<*>接收包装起来的函数，和一个包装起来的数据，最终返回包装起来的另一种数据。

一个很有效的应用场景是Maybe，在java中对应了Optional。这里拿Maybe来讲。

Maybe可以有两类数据类型，一种是Just a，这种数据类型包装了一个值；另一种是Nothing，表示没有值在其中。
对一个Maybe类型做操作时，若每个操作都判断是Just还是Nothing未免太过麻烦（就像java中，每个操作都判断一次null值）。使用Applicative会让代码清晰很多。

Maybe的Applicative实现：由于实现Applicative首先要实现Functor，所以这里给出两个instance。

1
2
3
4
5
6
7
8
instance Functor Maybe where  
    fmap f (Just x) = Just (f x)  
    fmap f Nothing = Nothing  

instance Applicative Maybe where  
    pure = Just  
    Nothing <*> _ = Nothing  
    (Just f) <*> something = fmap f something

可以看到，如果遇到了Nothing，那么不管后面传什么，最终都返回Nothing。仅当拿到Just时才会进行动作。

有了Maybe，我们就可以清晰明了的书写代码，而不用关注空值，也不用关心空函数。

回到Monad

有了上面这些基础，那么到底什么是Monad呢？

回想下Applicative，事实上，我们写代码时还是会有些不舒服：实际上，我们通常关注的入参主要是普通的值，而出参是包装起来的值。例如上面的Maybe，我们对于入参只关心“有值”的情况，但出参时，可能值会变得不合法，我们会给出Nothing。这在Functor或Applicative中都没办法做到。

Monad解决了这一点，它和Functor非常相近，只不过实际做动作的函数会接收一个值，并返回一个包装起来的值。

1
2
3
class (Applicative m) => Monad m where
    return :: a -> m a
    (>>=) :: m a -> (a -> m b) -> m b

还有两个带默认实现的函数签名没有展示。通常我们也没有必要关心它们，使用默认实现即可。
return和Applicative 的 pure功能是一样的，都是将一个值放到包装里面去。（GHC 7.10中，return已有默认实现: return = pure）
bind接收一个包装，和一个函数，其中，这个函数接收一个普通值，并返回一个包装。bind函数最终返回一个包装。

既然Monad是自函子范畴上的幺半群，那么它必须要有幺半群的特性。幺半群需要一个有幺元的集合、一个满足结合律的运算符。

很显然，Monad实例一定作用在函子范畴上（需要实现Functor），此外，Haskell类型集合是Hask范畴，函子一定是自函子，那么此处幺半群的集合便是自函子范畴。但运算符就有点难找了，因为>>=参数1和参数2类型不同，没有办法满足通常意义上的结合律。不过，我们可以观察得知，如果等号左边有：(a >>= f) >>= g，那么等号右边一定是a >>= (x)。根据类型签名，x是一个函数。根据功能，它需要将f的返回值与g进行bind。所以，我们可以写：x = \n -> f n >>= g

结合律搞定了，接着我们找下幺元。

由于>>=作用在自函子范畴上，所以幺元是个函数。实际上，return这个函数就是当作幺元而定义的。

综上，我们对Monad实现有如下限制条件：

1
2
3
return a >>= f      === f a
m        >>= return === m
(m >>= f) >>= g     === m >>= (\x -> f x >>= g)

Monad composition operator

说实话，上面的这些式子看起来的确不像Monoid中那么直观。于是Haskell还给出了另一个运算符：>=>。

1
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c)

它有默认实现，即对入参调用第一个函数，然后和第二个函数bind，此处就不写出来了，有兴趣可以看看Haskell的Monad文档。

它需要满足：

1
2
3
return >=> f    === f
f >=> return    === f
(f >=> g) >=> h === f >=> (g >=> h)

这看起来就没有任何问题了，非常清晰的幺半群规则。

Monad在Java、ES中的实现

Monad并非Haskell专属，它在任何编程语言的标准库中都有广泛的应用（虽然设计者可能自己都没认识到）。

Java Optional

java 8的Optioanlhe和haskell的Maybe要解决的问题几乎一样。Optional提供了如下函数：

1
2
3
4
static <T> Optional<T> empty();
static <T> Optional<T> of(T value);
<U> Optional<U> map(Function<? super T, ? extends U> mapper);
<U> Optional<U> flatMap(Function<? super T, Optional<U>> mapper);

这里的of即为return，map即为Functor的fmap，flatMap即为Monad的>>=。

虽然缺失了Applicative的<*>，但问题不大，毕竟没啥人会用它，我们选择性忽略即可。。。

1
2
3
4
5
6
Optional<Integer> safeDiv(int a, int b) {
  if (b == 0) return Optional.empty();
  return Optional.of(a / b);
}

Optional.of(a).flatMap(a-> safeDiv(15, a))

ES6 Promise

Promise在ES6中作为标准库的一员，我们在这里忽略其冗长的实现规则，仅看其常见用法：

1
2
3
4
5
6
7
8
const readFile = function(fileName) {
  const content = fs.readFileSync(fileName, 'utf8')
  return Promise.resolve(content)
}

function httpHandler(req, resp) {
  readFile(req.query.name).then(content => db.coll.findOne(content.split(',')[0])).then(data => resp.send(data))
}

js没有类型签名，但我们在上述用法中能看出：

  1. Promise.resolve 即为 return
  2. then 即为 >>=

同时，虽然上述用法中没有明确写出，不过then还可以接收a -> b这样的函数，比如content => content + '\nhello world'，这便是Functor的fmap。和Java的Optional一样，Promise不支持接受类似于Promise (a -> b)的参数，不过问题不大，我们同样选择性忽视即可。

附录：数学上的monoid和monad

monoid

一个集合 S
一种运算 : S S -> S
一个幺元 e : 1 -> S

并满足如下条件：

对于任意S中的a,b,c 都有(a b) c = a (b c)
对于任意S中的a 都有e a = a e = a

monad

一个自函子 T : X -> X
一种变换 u : T x T -> T （x是指函子复合）
一种变换 n : I -> T (I是X范畴上的幺自函子)

并满足如下条件：

u . Tu = u . uT
u . Tn = u . nT = 1