Monad
对于很多人来说,“Monad”是一个“神奇”的概念。这个概念首先在数学中被提出,用来简化一些复杂定理的描述。后来在Haskell中被使用。而实际上,所有主流高级语言都有Monad,只不过不一定被明确的标注出来,例如:ES6的Promise、Java的Optional。本文会通俗的描述什么是Monad,以及如何定义和使用。
The Easy Way: 抽象和拆分
可以参考youtube这个视频
普通的函数复合
假设我们现在有三个类型a、b、c。
现在定义两个函数,
1 | f :: a -> b |
可能有人不理解这组符号的含义。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 | h = g . f -- h = g (f x) |
所以,如果我们想把两个函数拼起来,很简单,只要用.
号即可。这解决了编程过程中的一个问题:逻辑拆分。将一个大逻辑拆分成小逻辑,然后再用.
把这些小逻辑串起来。
返回“在某个空间里的数据类型”的函数的复合
我们把函数和类型拓展一下:
1 | f :: a -> m b |
现在我们有两个函数,一个接收a类型,并返回m b
类型。什么是f :: a -> m b
?这在java中没有对应,因为java的类型系统不支持kind
。但是如果一定要写的话,可以写成这样:
1 | <A,B,M> M<B> f(A a); |
B
作为M
的类型参数,也可以说,B
在M
空间里。
现在我们再定义两个函数:
1 | \x -> f x (lambda 1) |
很显然,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 | class Monoid m where |
mempty返回幺元,就是那个e
mappend对应幺半群中的那个运算符
mconcat是haskell库的需要,已经有默认实现,通常不需要我们关注。
除了类型上要满足,还需要程序保证:
- a mappend (b mappend c) == (a mappend b) mappend c
- a mappend mempty == mempty mappend a == a
即幺半群的定义。
光看定义可能有些抽象,我们举个例子。比如说List
在Java里,我们可能写:Arrays.<String>asList("a", "b", "c")
。List结构 加上 连接运算,就是一种Monoid。
- 存在一个空链表
- 空链表连接任何链表,不管在左边连接还是在右边连接,最后都返回相同的链表
- 链表的连接符合运算符结合律
Monoid抽象出了“像List那样的数据结构”的共有特征,使得数据处理变得容易。
函子 Functor
我们熟悉的函数
表示的是类型间的映射,例如Int -> String
。
而函子
表示的是范畴间的映射,例如List<Int> -> List<String>
。可以简单的看成:
函数:a -> b
函子:t a -> t b
其实函子很好理解,例如map就是一种函子,接收一种List,返回另一种List
在Haskell中,函子是这样定义的:
1 | class Functor f where |
很清晰,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 | class (Functor f) => Applicative f where |
函数pure将任意一种类型的值包装到Applicative的实例中。
函数<*>
接收包装起来的函数,和一个包装起来的数据,最终返回包装起来的另一种数据。
一个很有效的应用场景是Maybe
,在java中对应了Optional。这里拿Maybe来讲。
Maybe可以有两类数据类型,一种是Just a
,这种数据类型包装了一个值;另一种是Nothing
,表示没有值在其中。
对一个Maybe类型做操作时,若每个操作都判断是Just还是Nothing未免太过麻烦(就像java中,每个操作都判断一次null值)。使用Applicative会让代码清晰很多。
Maybe的Applicative实现:由于实现Applicative首先要实现Functor,所以这里给出两个instance。
1 | instance Functor Maybe where |
可以看到,如果遇到了Nothing,那么不管后面传什么,最终都返回Nothing。仅当拿到Just时才会进行动作。
有了Maybe,我们就可以清晰明了的书写代码,而不用关注空值,也不用关心空函数。
回到Monad
有了上面这些基础,那么到底什么是Monad呢?
回想下Applicative,事实上,我们写代码时还是会有些不舒服:实际上,我们通常关注的入参主要是普通的值,而出参是包装起来的值。例如上面的Maybe,我们对于入参只关心“有值”的情况,但出参时,可能值会变得不合法,我们会给出Nothing
。这在Functor或Applicative中都没办法做到。
Monad解决了这一点,它和Functor非常相近,只不过实际做动作的函数会接收一个值,并返回一个包装起来的值。
1 | class (Applicative m) => Monad m where |
还有两个带默认实现的函数签名没有展示。通常我们也没有必要关心它们,使用默认实现即可。
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 | return a >>= f === f a |
Monad composition operator
说实话,上面的这些式子看起来的确不像Monoid中那么直观。于是Haskell还给出了另一个运算符:>=>
。
1 | (>=>) :: Monad m => (a -> m b) -> (b -> m c) -> (a -> m c) |
它有默认实现,即对入参调用第一个函数,然后和第二个函数bind,此处就不写出来了,有兴趣可以看看Haskell的Monad文档。
它需要满足:
1 | return >=> f === f |
这看起来就没有任何问题了,非常清晰的幺半群规则。
Monad在Java、ES中的实现
Monad并非Haskell专属,它在任何编程语言的标准库中都有广泛的应用(虽然设计者可能自己都没认识到)。
Java Optional
java 8的Optioanlhe和haskell的Maybe要解决的问题几乎一样。Optional提供了如下函数:
1 | static <T> Optional<T> empty(); |
这里的of
即为return
,map
即为Functor的fmap
,flatMap
即为Monad的>>=
。
虽然缺失了Applicative的<*>
,但问题不大,毕竟没啥人会用它,我们选择性忽略即可。。。
1 | Optional<Integer> safeDiv(int a, int b) { |
ES6 Promise
Promise在ES6中作为标准库的一员,我们在这里忽略其冗长的实现规则,仅看其常见用法:
1 | const readFile = function(fileName) { |
js没有类型签名,但我们在上述用法中能看出:
- Promise.resolve 即为 return
- 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