剖析for推导式

元素

意义

转译

应用

元素

在Scala里，一个for表达式可以包含1个或多个「生成器」(Generator)，及其一个可选的yield子句；其中，每个生成器可以包含0个或多个「守卫」(Guard)，及其0个或多个「定义」(Definition)。

领域模型

也就是说，for表达式可以描述为如下图所示的模型。

for表达式的模型

基本形式

依据yield是否存在，for表达式可以归结为两种基本形式。

for推导式(for comprehension)
for循环(for loop)

for推导式

如果for表达式存在yield子句，则称该for表达式为for推导式。它最终将使用yield子句收集结果，并将其作为for表达式的值。

for循环

如果for表达式不存在yield子句，则称该for表达式为for循环。for循环用于执行某种副作用，其返回值的类型为Unit。

意义

for表达式是一种重要的编程工具，在某些场景下能够极大地改善代码的表达力。

需求：查询所有产自中国，且价格在10元以内的咖啡名称，及其对应的供应商。

使用高阶函数

coffees filter { c =>
  c.nationality == "China" && c.price < 10 
} flatMap { c =>
  suppliers filter {
    c.supplierId == _.id 
  } map { 
    c.name -> _.name 
  }
}

使用for推导式

如果使用for推导式，可以进一步改善代码的表达力。

for {
  c <- coffees if c.nationality == "China" && c.price < 10
  s <- suppliers if s.id == c.supplierId
} yield c.name -> s.name

转译

事实上，对于任意的for推导式，都可以使用map, flatMap, filter进行表达；而对于任意的for循环，都可以使用foreach, filter进行表达。

转译生成器

一般地，for表达式可以包含1个或多个「生成器」(Generator)。

for (x1 <- exp1; x2 <- exp2; ...; xn <- expn) yield expr

当`n == 1`

for (x1 <- exp1) yield expr

转译为

exp1 map { x => expr }

当`n >= 2`

for (x1 <- exp1; x2 <- exp2; ...; xn <- expn) yield expr

首先，对生成器x1 <- exp1进行转译：

exp1 flatMap { x1 => 
  for (x2 <- exp2; ...; xn <- expn) yield expr 
}

依次类推，分别对x2 <- exp2; x3 <- exp3, ..., x(n_1) <- exp(n_1)进行转译：

exp1 flatMap { x1 =>
  exp2 flatMap { x2 =>
    ...
    exp(n-1) flatMap { x(n-1) => 
      for(xn <- expn) yield expr 
    }
  }
}

最后，对于最后一个生成器xn <- expn，则使用map进行转译。最终for表达式转译为：

exp1 flatMap { x1 =>
  exp2 flatMap { x2 =>
    ...
    exp(n-1) flatMap { x(n-1) => 
      expn map { xn => expr }
    }
  }
}

转译守卫

一般地，一个生成器可以附加0个或多个守卫。

for (x <- exp if guard1 if guard2 ... if guardn) yield expr

首先，在转译x <- exp之前，首先将guard1实施于exp，将其迭代范围缩小。

for { 
  x <- (exp filter guard1) 
  if guard2 
  ... 
  if guardn
} yield expr

以此类推，将guard2, ..., guardn依次实施于上一迭代的表达式，将其迭代范围逐渐缩小，最终for推导式转译为：

for { 
  x <- (exp filter guard1 filter guard2 ... filter guardn) 
} yield expr

合并守卫

但是，每次调用一次filter都将产生一个中间结果，效率非常低下。可以使用withFilter对所有的的守卫进行合并。

for { 
  x <- (exp withFilter guard1 withFilter guard2 ... withFilter guardn) 
} yield expr

它等价于：

for { 
  x <- exp.withFilter(guard1 && guard2 && ... && guardn) 
} yield expr

使用withFilter，虽然它也会生成中间人。但是，其相对于filter生成昂贵的中间集合，withFilter仅仅生成WithFilter的中间实例，其成本非常低廉。

转译定义

一般地，一个生成器可以附加0个或多个值定义。

for (x <- exp; y1 = exp1; y2 = exp2; ...; yn = expn) yield expr

首先，对y1 = exp1进行转译：

for {
  (x, y1) <- for (x <- exp) yield (x, exp1)
  y2 = exp2
  ...
  yn = expn
} yield expr

依次类推，将y2 = exp2, ..., yn = expn依次实施于上一迭代的表达式，最终for推导式转译为：

for {
  (x, y1, y2, ..., yn) <- for (x <- exp) yield (x, exp1, exp2, ..., expn)
} yield expr

转译for循环

一般地，当不存在yield子句时，转译使用map, flatMap进行转译；但是，不存在yield子句时，则使用foreach进行转译，相对简单。

for (x1 <- exp1; x2 <- exp2; ..., xn <- expn) expr

首先，对生成器x1 <- exp1进行转译：

exp1 foreach { x1 => 
  for (x2 <- exp2; ...; xn <- expn) expr 
}

依次类推，分别对x2 <- exp2; x3 <- exp3, ..., xn <- expn进行转译：

exp1 foreach { x1 =>
  exp2 foreach { x2 =>
    ...
    expn foreach { xn => 
      expr
    }
  }
}

转译模式

事实上，生成器是一个模式匹配的特殊应用。当对for表达式进行转译时，其对应的模式匹配规则将被转译为等价的偏函数，并应用于map, flatMap或foreach方法之上。

匹配元组

当生成器的模式是一个元组或者是一个变量(可以看成单元素的元组)时。

for { (x1, x2, ..., xn) <- exp } yield expr

经过转译，其模式匹配规则将被转译为等价的偏函数，它自动过滤了不匹配的元组。

exp map { case { (x1, x2, ..., xn) => expr }

一般模式

一般地，如果生成器中的模式不是元组或者变量时，它是一个一般的模式。

for { pat <- exp } yield expr

首先，模式匹配规则将被转译为等价的偏函数，并进行一次withFilter操作，以便过滤掉不匹配的元素；然后，再将该模式匹配转译为等价的偏函数。

exp withFilter {
  case pat => true
  case _   => false
} map {
  case pat => expr
}

泛化

事实上，for表达式是对容器C[A]操作的语法糖表示。其中，C[A]是一个拥有foreach, map, flatMap, filter方法集合的容器。

trait C[A] {
  def map[B](f: A => B): C[B]
  def flatMap[B](f: A => C[B]): C[B]
  def filter(p: A => Boolean): C[A]
  def foreach(op: A => Unit): Unit
}

在Scala的标准库中，满足这种特征的容器有很多。例如，Array, Seq, Set, Map, Range, Iterator, Stream, Option等所有容器。

接下来将以Option为例，讲解这几个算子的实现方式，及其加深理解for表达式的工作机制。

递归结构

sealed trait Option[+A] { self =>
  def isEmpty: Boolean
  def get: A
}

case class Some[+A](x: A) extends Option[A] {
  def isEmpty = false
  def get = x
}

case object None extends Option[Nothing] {
  def isEmpty = true
  def get = throw new NoSuchElementException("None.get")
}

实现算子

sealed trait Option[+A] {
  def isEmpty: Boolean
  def get: A
  
  def map[B](f: A => B): Option[B] =
    if (isEmpty) None else Some(f(get))
    
  def flatMap[B](f: A => Option[B]): Option[B] =
    if (isEmpty) None else f(get)
    
  def foreach[U](f: A => U): Unit = 
    if (!isEmpty) f(get)
    
  def filter(p: A => Boolean): Option[A] =
    if (isEmpty || p(get)) this else None
}

提升效率

使用filter将每次返回一个新的Option实例，成本相对昂贵。因此，可以使用withFilter替代filter，这样的设计实现如下三个效果。

合并for表达式中的所有过滤条件；
保证map, flatMap, foreach操作发生在过滤条件之后，以便提高效率；
操作withFilter，可以避免生成昂贵的，类型为Option的中间实例；而以相对廉价的，类型为WithFilter的中间实例代替。

sealed trait Option[+A] { self => 
  def withFilter(p: A => Boolean): WithFilter = new WithFilter(p)
  
  class WithFilter(p: A => Boolean) {
    def map[B](f: A => B): Option[B] = 
      self filter p map f
    
    def flatMap[B](f: A => Option[B]): Option[B] = 
      self filter p flatMap f
    
    def foreach[U](f: A => U): Unit = 
      self filter p foreach f
    
    def withFilter(q: A => Boolean): WithFilter = 
      new WithFilter(x => p(x) && q(x))
  }
}