Monad in FP, Part I

Monad ---- “the m-word”,“a monoid in the category of endofunctors”.
see A monad is just a monoid in the category of endofunctors, what’s the problem? for fun


在FP的路上,不可避免地会碰到monad这个拦路虎。绕是绕不过去的,那就学咯。

“我看了几十篇关于monad的文章,还是没懂。” – 某不知名FP爱好者

这篇文章也不是silver bullet,我只希望读者在读过以后,对monad能有个大致的、模糊的印象,今后能够持续地从多个角度去审视这个概念,加深认识。

什么是monad

我们在说functor的时候,有一个不那么准确的定义:map的,就是functor

当我们这样定义的时候,我们其实是在泛化map,将它们的共性抽象出来,这个抽象就是functor。

同样地,flatMap也出现在很多地方(比如ListOptionFutureEither等等等),我们自然也想把共性抽象出来,这个抽象,就是monad。所以可以类似地说:flatMap的,就是monad

好吧,如果要正式一点,引用下scala with cats里的定义:monad是一种将计算按顺序排列起来的机制(a mechanism for sequencing computations)

flatMap是什么

如果你熟悉flatMap,可以跳过这一小节。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
case class Person(name: String, friends: List[String])

val bob = Person("Bob", List("Alice", "Pika"))
// bob: Person = Person("Bob", List("Alice", "Pika"))
val harry = Person("Harry", List("Ron", "Hermione"))
// harry: Person = Person("Harry", List("Ron", "Hermione"))
val ps = List(bob, harry)
// ps: List[Person] = List(Person("Bob", List("Alice", "Pika")), Person("Harry", List("Ron", "Hermione")))

ps.map(_.friends)
// res4: List[List[String]] = List(List("Alice", "Pika"), List("Ron", "Hermione"))

ps.flatMap(_.friends)
// res5: List[String] = List("Alice", "Pika", "Ron", "Hermione")

对于List[A]来说,mapflatMap的签名,仅仅是传入的f的返回类型不一样:

1
2
def map[A, B](f: A => B): List[B]
def flatMap[A, B](f: A => List[B]): List[B]

直观来讲,flatMapList内的每一个A,转换成了一个List[B],然后将所有的List[B],连了起来。

举个栗子🌰

我们知道,Option可以用来表示结果是否存在。

考虑整数除法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// not pure, can throw exception
def naiveDiv(x: Int, y: Int): Int = x / y

naiveDiv(1, 0)
// java.lang.ArithmeticException: / by zero

// pure
def div(x: Int, y: Int): Option[Int] =
if (y == 0) None else Some(x / y)

div(1, 0)
// res13: Option[Int] = None
div(8, 2)
// res14: Option[Int] = Some(4)

现在我们不仅要做除法,还要让用户输入这两个值,我们需要一个parseInt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def naiveParseInt(s: String): Int = s.toInt

naiveParseInt("12")
// res17: Int = 42
naiveParseInt("aa")
// java.lang.NumberFormatException: For input string: "aa"

import scala.util.Try
def parseInt(s: String): Option[Int] = Try(s.toInt).toOption

parseInt("42")
// res24: Option[Int] = Some(42)
parseInt("aa")
// res25: Option[Int] = None

现在我们把他们串起来,自然地,我们也需要返回一个Option[Int]来涵盖结果的成功和失败。

1
2
3
4
5
6
7
8
9
10
11
12
13
def stringDiv(a: String, b: String): Option[Int] = 
parseInt(a).flatMap { x =>
parseInt(b).flatMap { y =>
div(x, y)
}
}

stringDiv("10", "2")
// res28: Option[Int] = Some(5)
stringDiv("a", "1")
// res29: Option[Int] = None
stringDiv("22", "0")
// res30: Option[Int] = None

stringDiv做了这些事情:

  1. parseInt(a)返回一个None或者Some(x)
  2. 如果是Some,将Some内的值x取出来,传递给后面的函数;
  3. parseInt(b)返回一个None或者Some(y)
  4. 如果是Some,将Some内的值y取出来,继续传给后面的函数;
  5. 计算div(x, y),返回最终结果None或者Some(x)

手动使用flatMap拼接比较繁琐,也不太容易看得清。Scala为我们提供了一个语法糖:for-comprehension。

下面的stringDiv2与stringDiv是等价的,编译器会帮我们把for-comprehension编译成flatMap(和map)的调用链。

1
2
3
4
5
6
def stringDiv2(a: String, b: String): Option[Int] = 
for {
x <- parseInt(a)
y <- parseInt(b)
res <- div(x, y)
} yield res

审视一下上面的例子,我们确确实实地将计算给串起来了。

flatMap起了什么作用呢?

flatMap将上游Option[Int]中的值抽出来,执行运算,再塞进Option[Int]中,传递给下游。

因为div只能接受Int,而传给div的是Option[Int],所以我们不能用简单的函数组合来解决问题。

using compose using flatMap
naiveParseInt: String => Int parseInt: String => Option[Int]
naiveDiv: (Int, Int) => Int div: (Int, Int) => Option[Int]
(a, b) => naiveDiv(naiveParseInt(a),naiveParseInt(b)) see stringDiv2

Monad的定义

在上述的例子中,我们使用flatMapOption[Int]串了起来。

如果我们只有IntflatMap岂不是毫无作用?

没关系,我们还有unit,可以把一个值A变成F[A],可以视作将一个纯粹的值提升到了monad上下文中。

1
2
3
4
5
trait Monad[F[_]] {
// `unit` is also known as `pure` or `return`
def unit[A](value: A): F[A]
def flatMap[A, B](ma: F[A])(f: A => F[B]): F[B]
}

我们说过,monad是特殊的functor。换言之,所有的monad都是functor,不是所有的functor都是monad。

因为我们可以使用unitflatMap实现map,有了map,自然就是functor。

1
def map[A, B](ma: F[A])(f: A => B): F[B] = ???

这个实现是显然且唯一的,答案在文章末尾。

小结

这次我们通过一个简单的例子阐述了monad的作用,并写下了monad的一种形式化定义。

接下来,我们还会研究monad定律,研究monad的不同表现形式。

最后,我们会研究大量的monad实例,来加深理解。

Reference

  1. Monads: Programmer’s Definition
  2. Monads – Chapter 3 in Scala with Cats
  3. Monad – Chapter 11 in Functional Programming in Scala

答案:通过unitflatMap实现map

1
2
def map[A, B](ma: F[A])(f: A => B): F[B] = 
flatMap(ma)(a => unit(f(a)))