在工作中遇到一句代码有点迷:List(Some(3), None).flatMap(identity) 的结果是什么?为什么 ?

上面代码的结果是 List(3) 。之所以不理解这个结果有二个原因:为什么 flatMap 支持不同类型,外面是 List, 里面是 Option? 处理 None 的理论依据是什么 ?

Scala 是支持函数式编程的语言,很多的 Collection 类型定义了 map, flatMap, flatten, 加上 Class 或 Case Class 本身具有的构造函数等于 Monad 需要的 unitpure,这样 Monda 的方法齐备了。一个很自然的问题就是:一个 ListSet 是 Monad 吗? 上面问题的出发点其实在于尝试用 Monda 的理论去理解 Scala 的具体实现或编程时,发现无法适用。非常幸运的是,有人给出了很好的答案。

Collection 类型不是 Monad

这个 StackOverflow 问答 Is a collection with flatMap a monad? 给出了很好的回答:Scala 的 Collection 类型不是 Monad,因为其实现不符合 Monad 要求的结合律。比如下面的代码

1
2
3
4
5
6
7
8
val f: String => Iterable[String] = { s => List(s) }
val g: String => Iterable[String] = { s => Set(s) }
val h: String => Iterable[String] = { s => List("hi", "hi") }

val r1 = f("hi").flatMap(g).flatMap(h) // (f op g) op h
val r2 = f("hi").flatMap(x => g(x).flatMap(h)) // f op (g op h)
println(r1) // List(hi, hi)
println(r2) // List(hi)

可以看到,上面的操作不符合结合律,f op g op hf op (g op h) 的结果不一样,这里 op 代表函数的组合。其后果就是调用的顺序不能随意改变。实际使用中会出现下面的情形:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
val p = for {
  a <- f("hi")
  b <- g(a)
  } yield b
p: Iterable[String] = List("hi")

val q = for {
  c <- p
  d <- h(c)
  } yield d
q: Iterable[String] = List("hi", "hi")

val r = for {
  a <- f("hi")
  b <- g(a)
  c <- h(b)
  } yield c
r: Iterable[String] = List("hi")

这种看上去有点没有道理,for 里面先做头二步,再做后一步和三步顺序做的结果不一样。其根本原因就在于 Scala 的 for 表达式翻译成对应的 flatMap 为右边组合 (right-associative) 。而分成二步走则是左组合,就改变了语义,算是一种不应该有的 accidental complixity 偶然复杂度,会带来意想不到的错误。

Collection 的 flatMap 支持 F[G[A]] 而不仅仅是 F[F[A]]

既然 Collection 类型不是 Monad,那么就没有必要满足 Monad 的规则。其后果是二方面的,一方面如上所示不符合结合律的后果,另一方面则带来了一些灵活性。这个灵活性究其根本,还是因为 Scala 同时又是面向对象的编程语言。后果就是型变 Variance 和 Collection 类的 flatMap 支持 F[G[A]] 而不仅仅是 F[F[A]]。 回答最初的问题,ListflatMap 方法签名是 def flatMap[B](f: A => IterableOnce[B]): List[B],其组合函数 f 的返回值 IterableOnce[B]flatMap 的返回值 List[B] 可以不一样,所有 IterableOnce 的类型比如 Option, Set, Vector 都可以作为 List 的元素类型使用 flatMapflattenflatMap 方法的具体实现就是嵌套的循环遍历 IterableOnce[IterableOnce] 生成一个新的 List

这套 Slide 给出了更加详细的说明,比较了 Collection 类型 和 Monad 的 flatMapflatten 方法的不同。flatten 定义可以理解为 flatMap(identity)。总结起来就是 Colletion 的 flatMapflatten 方法支持 F[G[A]] 而不仅仅是 F[F[A]]

处理 None 的依据

可以想到二点,实践上就是一致性,理论上就是 Identity Element 幺元。对某个集 S 和某种操作 op, 对 S 集的任意 元素 x,幺元 e 满足 x op e = x = e op x。 比如,对整数集,x + 0 = x = 0 + x, x * 1 = x = 1 * x, 0 和分别是整数集上加法的幺元和乘法的幺元。

在实践中,List(List(3), List()).flatMap(identity) 的结果是 List(3)。那么 List(Some(3), None).flatMap(identity) 的结果是 List(3) 也可以理解了。因为都是表示没有正常值的状态。

理论上,flatMap(identity) 就是 flatten。如果把 flatten 看成一个类似 fold 这样的的普通方法,那么 List(), EmptySet, 和 None 作为操作的幺元就不会产生输出结果也就正常了。

小结

Scala 的 Collection 类型不是 Monad。Scala 的标准库不是严格按照函数式编程理论实现的。其根本原因在于 Monda 作为数学定义,有非常严格的规则需要遵守,而 Scala 的作为(OO + FP)的多范式编程语言,在 Collection 类型的设计上加入了 OO 的子类型多态,但是牺牲了函数式编程的严谨性。所以结论就是,用 Scala 语言的标准库作为多范式编程的时候,其函数式编程很多时候并不严格,需要小心上面那种重构 for 表达式带来的问题。

用 Scala 做函数式编程,看来比较好的办法还是用 Scala 的函数式库,比如 CatsZIO。否则,在应用函数式编程的思想重构时需要明确知道坑在哪里。