怎样用简单的语言解释 monad?

关注者
698
被浏览
34789

24 个回答

使用 join 诠释的话,Monad 会有一个非常不同的理解:Monad 是可以增(return/unit,\mathrm{Id}\rightarrow T)减(join,T^2\rightarrow T)层数的「箱子」。而 unit 和 join 因为满足某些定律所以形成了一个幺半群(对,这就是那老梗)。所以,Monad 代表的是层次,而不是顺序。(回想下 CPS,是不是用层次表示顺序的?)
Haskell 的 bind 可以看作 fmap 和 join 的复合


首先解释 Endofunctor,Endofunctor 是(不加限制的)箱子,它把类型(一个类型范畴里的对象)T 装进去变成 F(T),同时还能保证所有函数(态射)A->B,都有一个带箱子的版本 F(A)->F(B)。
而 Monad 呢?就是除了前面的两个箱子,我们还能定义出把任意类型的数值装进箱子的 unit:T->F(T),以及把两层箱子只留一层的 join:F(F(T))->F(T)。
Endofunctor 们可以组成一个新的范畴,其中有个很简单的元素 Id,它代表的「箱子」就是「没箱子」,恒等变换。由于恒等变换 Id 存在,所以我们可以尝试着用「二阶」的手段去掉 unit 和 join 签名里面的 T,只关心 F 的部分,于是我们有了:
  • Unit : Id -> F
  • Join : F × F -> F
这个形式和幺半群很相似,所以我们说:A Monad is a monoid object in a category of endofunctors。

--
  • 对于数组,箱子就是数组本身,join 定义成 concat,把两层数组合并成一层
  • 对于 Maybe,箱子是 Nothing/Just 包围,join 定义成把整套结构排扁
  • 对于「副作用」,箱子是对某种状态的修改(用函数的形式表示),join 定义成副作用的复合
  • 对于 Cont,箱子是形如\lambda k.\,k\,x的一层封装(接受一个 continuation,把「里面的东西」丢给他;数学上是一个双对偶空间),join 就定义为\mathrm{join}\ f\ k=f\,(\lambda f'.\,f'\,k) =(\lambda k_2.\ k_2\ (\lambda k_1.\ k_1\ x))(\lambda f'.\,f'\,k)=(\lambda f'.\,f'\,k)(\lambda k_1.\ k_1\ x)=(\lambda k_1.\ k_1\ x)\,k=k\ x
  • Free monad 就是构造间隔的红绿两层盒子,在 join 那一步抽掉绿色的盒子(Free F),只留下红色的(F),然后根据你就可以自己决定怎么组合它们……
数学的定义其它答案都解释得很多了。这里,我提供一种从具体例子到抽象的解释。希望能帮 monad 除掉「the m-word」的名声。

1 为什么说列表是 Monad?
问题标签里有 Scala,这里我们就先来考察 Scala 里的 Seq 是否是 monad。

我们来看看 Seq 能干什么:
首先,我们可以用一个元素构造 Seq:
val persons = Seq(john)
注意这里的构造指:根据一个元素构造出仅含一个元素的 Seq。

第二,我们还可以在一个 Seq 对象上 flatMap(这里顺便提供一个 关于 flatMap 的直观解释
persons.flatMap(p => p.favoriteBooks)

Monad 就是对这两个行为的抽象。我们分别称呼上面两个函数为 idflatMap(这里我们不使用 return 和 bind 这两个不直观的名字)。

2 Monad 有什么好?
这样的抽象到底有什么好处?Monad 在数学上的优美这里不重复,请参考其它答案。这里只讲与程序员最相关的一个优点。在一些编程语言里,比如 Scala,Monad 是有专用语法糖的。我们以一个实际例子来说明:
假设你有一个语料库,它由不同的文档(类型为 Document)构成,每篇 Document 又有若干句子(类型为 Sentence),每个句子又由词构成(类型为 Word)。即,语料是由 Seq[Document] 组成,Document 里的 sentences 方法返回一个 Seq[Sentence],Sentence 里的 words 方法返回 Seq[Word]。现在你需要获取语料中每个长度大于 4 个字母的词的首字母。
传统的 for 嵌套写法这里就不提了。普遍的写法是利用 flatMap 和 map:
val lengths = 
  documents.flatMap(d => 
    d.sentences.flatMap(s => s.words.filter(w => w.length > 4)))
           .map(w => w(0))
然而这看着依然很乱。有没有更优雅的写法?有!Scala 语言里可以这样:
for {
  d <- documents
  s <- d.sentences
  w <- s.words
  if w.length > 4
} yield w(0)
凡是定义有 flatMap 和 map 的类,都可以在 Scala 里这么写。这不是一件激动人心的事情吗?

3 到底 Monad 是什么?
我们可以通过类比来试着猜一下,一个 monad 的 id 和 flatMap 分别具有怎样的参数和返回值。
在 Seq 的例子中,id 就是根据一个元素构造出 Seq 的函数,即
def id[X](x: X): Seq[X] = Seq(x)
如果我们把 Seq 的 flatMap 改写成一个全局函数,它会是这样
def flatMap[X, Y](xs: Seq[X], f: X => Seq[Y]): Seq[Y] = xs.flatMap(f)

好,现在我们来抽象一下这两个函数。假设现在有一种抽象的、行为类似 Seq 的类型,叫 M。在它上面我们可以类比 Seq,定义出抽象的 id 和 flatMap:
def id[X](x: X): M[X]
def flatMap[X, Y](xs: M[X], f: X => M[Y]): M[Y]
看,与具体的 Seq 的 id 和 flatMap 没有太大区别。事实上,列表就是最天然的 monad.

有了这两个函数的确切签名,我们就可以给出 monad 的定义了:
能定义出上面两个函数的类型 M 就是 monad。
当然,这两个函数还必须满足一些 monad 公理 <del>这里暂不关心</del>(见文末更新)。然而类型系统无法验证这些性质,实际使用中都是程序员自觉。

具体到代码上,我们可以用下面这个 typeclass 来定义:
trait Monad[M[_]] {
  def id[X](x: X): M[X]
  def flatMap[X, Y](xs: M[X], f: X => M[Y]): M[Y]
}

4 还有哪些 Monad 的实例?
有了这个定义,我们会瞬间发现,其实 Monad 无处不在。除了像 Seq 那样的列表类型,这里再多考察几个其它类型的。

4.1 Option Monad
我们来看看许多函数式语言里都有的 Option 是否是 monad。方便起见,这里仍然用 Scala 语言。我们试试能不能定义出 Option 的 id 和 flatMap:
def id[X](x: X): Option[X] = Some(x)
def flatMap[X, Y](ox: Option[X], f: X => Option[Y]): Option[Y] =
  os.flatMap(f)
看,我们成功定义出了这两个函数。所以 Option 是 monad。我们说明这个这又有什么用?

来,我们看看,究竟什么时候需要 Option?有返回 null 的需求,但不想看到 NullPointerException 时。比如 Java 代码中经常出现下面这种代码:
if (person.bestFriend != null) {
  if (person.bestFriend.favoriteBook != null) {
    return /* anything */
  }
  else return null
}
else return null
为了拯救这种代码,我们需要引入 Option。本来 person.bestFriend 返回的要么是一个 Person 对象,要么是一个邪恶的 null。我们可以将其返回类型改为 Option[Person]。关于 Option 是什么,请参考任意有 Option 的标准库文档。
有了 Option 是 monad 的证据,我们就可以写出如下的代码了:
for {
  bf <- person.bestFriend
  fb <- bf.favoriteBook
} yield /* whatever */
看,既不会导致运行时 NullPointer 错误,又不用手动检查 null,代码又易读。

4.2 分布 Monad
为了深化对 monad 的理解,我们再来丧病地考察分布(Distribution),看看它是不是个 monad。
我们明确一下 Distribution 到底是个什么东西。这里用 Scala 的 trait 定义:
trait Distribution[+X] { outer =>
  def sample: X
  def flatMap[Y](f: X => Distribution[Y]): Distribution[Y] = 
    new Distribution[Y] {
      def sample: Y = f(outer.sample).sample
    }
}

有了这个定义,我们很容易就能写出 id 和 flatMap 的 Distribution 版本:
我们先写出 flatMap。直接使用 Distribution 里的 flatMap 即可:
def flatMap[X, Y](xs: Distribution[X], f: X => Distribution[Y]) = 
  xs.flatMap(f)

然后是 id。函数 id 的作用就是:接收一个样本,构造出一个分布。那么一个样本能构造出来什么分布呢?答案就是抽样时永远返回同一个样本的分布:
def id[X](x: X): Distribution[X] = new Distribution {
  def sample: T = x
}
因此,我们意识到,分布也是 monad!

我们来定义两个常用的分布:Uniform 和 Gaussian:
case class Uniform(a: Double, b: Double) extends Distribution[Double] {
  def sample = scala.util.Random.nextDouble() * (b - a) + a
}

case class Gaussian(μ: Double, σ2: Double) extends Distribution[Double] {
  def sample = scala.util.Random.nextGaussian() * math.sqrt(σ2) + μ
}

哈哈,展示 monad 的威力的时候到了。我们可以非常自然地用现有分布定义一个新分布:
val d = for {
  x <- Uniform(0, 2)
  y <- Gaussian(x, 1)
} yield x + y
就像写数学公式一样自然。

Monad 为我们带来了类型安全,能让我们的程序易读。请不要以「the m-word」称呼它。

------- UPDATE --------
还是把 Monad 对 id 和 flatMap 的要求(即 Monad 公理)写出来吧:
第一条:id 是 flatMap 的左单位元
flatMap(id(x), f) 等于 f(x)
第二条:id 是 flatMap 的右单位元
flatMap(xs, id) 等于 xs
第三条:结合律
flatMap(flatMap(m, f), g) 等于 flatMap(m, x => flatMap(f(x), g))

当然,写成面向对象的形式可能更好理解:
id(x).flatMap(f)         等于 f(x)
xs.flatMap(id)           等于 xs
xs.flatMap(f).flatMap(g) 等于 xs.flatMap(x => f(x).flatMap(g))