Yifu's Blog
0%

Monad in FP, Part I

Posted on In

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也出现在很多地方（比如List，Option，Future，Either等等等），我们自然也想把共性抽象出来，这个抽象，就是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]来说，map和flatMap的签名，仅仅是传入的f的返回类型不一样：

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

直观来讲，flatMap将List内的每一个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的定义

在上述的例子中，我们使用flatMap将Option[Int]串了起来。

如果我们只有Int，flatMap岂不是毫无作用？

没关系，我们还有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。

因为我们可以使用unit和flatMap实现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

答案：通过unit和flatMap实现map

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