Monad

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的类型参数,也可以说,BM空间里。

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

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 aa -> 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即为returnmap即为Functor的fmapflatMap即为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