Jade Dungeon

重温for表达式

重温for表达式

先讨论一个例子，Person类有名字，性别，孩子三个成员： 

  case class Person(name: String, isMale: Boolean, children: Person*)

根据这个类建立一些实例： 

  val lara = Person("Lara", false)
  val bob = Person("Bob", true)
  val julie = Person("Julie", false, lara, bob)
  val persons = List(lara, bob, julie)

如果要找出所有母亲与孩子的结对，方案一是使用map、flatMap和filter这样的高阶 函数组成这样的查询操作： 

  scala> persons filter (p => !p.isMale) flatMap (p =>
       |     (p.children map (c => (p.name, c.name))))
  res5: List[(String, String)] = List((Julie,Lara),
      (Julie,Bob))

上面的代码很看起来挺难理解的，用for表达式来实现另一个版本： 

  scala> for (p <- persons; if !p.isMale; c <- p.children) 
       | yield (p.name, c.name)
  res6: List[(String, String)] = List((Julie,Lara),
      (Julie,Bob))

for循环比高阶函数可读性更加好一些。但实际上Scala编译器把循环版本转为高阶函数版本 ：

  • 所有有yield结果的for表达式会被转为map、flatMap与filter组合的调用。
  • 所有无yield结果的for表达式被转为filter与foreach的调用。

For表达式

for表达式的一般形式： 

  for ( seq ) yield expr

其中的seq部分由生成器、定义、过滤器组成，以分号分隔： 

  for (p <- persons; n = p.name; if (n startsWith "To")) 
  yield n

小括号可以由大括号代替，并且在用大括号的情况下还能省略分号： 

  for {
    p <- persons              // 生成器
    n = p.name                // 定义
    if (n startsWith "To")    // 过滤器
  } yield n

如果有多个生成器，后面的生成器在内层的循环： 

  scala> for (x <- List(1, 2); y <- List("one", "two")) 
       | yield (x, y)
  res0: List[(Int, java.lang.String)] = 
    List((1,one), (1,two), (2,one), (2,two))

8皇后问题

8皇后问题：标准棋盘上放8个皇后，相互之间不能处理叫吃的位置上（同行、同列、 同对角线）。

对于这个问题，把它扩展为任意尺寸的棋盘：在N*N的棋盘上放N个皇后，反而更加简单。设 左上角的坐标是(1,1)，右下角是(N,N)。

定义好了问题以后再看解决方案：

同一行的会被叫吃，所以每行只能放一个。那就一行一行地放皇后并检查会不会被叫吃。在 处理过程中还会遇到第K行的皇后把从1到k-1行的皇后全都叫吃的局面，这时就要放弃 这部分操作继续另外一种从1到k-1行皇后的配置方案。

另外一个方案更加具有函数式风格：

穷举出所有在N*N棋盘上放k个皇后的方案0<k<N。那么每个方案都可以用长度的k的 列表表示，为了处理方便顺序要按堆栈的方式把第k行在最顶层，k-1到k行依次向下。 所有的堆栈在一起组成了所有解决方案的列表。

现在我们把在第k+1行放皇后的操作变为对前一个方案多加一个皇后的所有可能的扩展。 这会产一个长度为k+1的列表。

下面的placeQueens函数实现了这一算法： 

  def queens(n: Int): List[List[(Int, Int)]] = {
    def placeQueens(k: Int): List[List[(Int, Int)]] =
      if (k == 0) 
        List(List())
      else 
        for {
          queens <- placeQueens(k - 1)
          column <- 1 to n
          queen = (k, column)
          if isSafe(queen, queens) 
        } yield queen :: queens

    placeQueens(n)
  }

两个生成器：

  • queens <- placeQueens(k - 1)遍历所有行（递归调用）。
  • column <- 1 to n遍历所有列。

过滤器来检查有没有叫吃情况发生： 

  def isSafe(queen: (Int, Int), queens: List[(Int, Int)]) = 
    queens forall (q => !inCheck(queen, q))

  def inCheck(q1: (Int, Int), q2: (Int, Int)) = 
    q1._1 == q2._1 ||                          // 同一行
    q1._2 == q2._2 ||                          // 同一列
    (q1._1 - q2._1).abs == (q1._2 - q2._2).abs // 对角线

使用for表达式进行查询

模拟一个查找图书的应用： 

  case class Book(title: String, authors: String*)

  val books: List[Book] =
    List(
      Book(
        "Structure and Interpretation of Computer Programs",
        "Abelson, Harold", "Sussman, Gerald J."
      ),
      Book(
        "Principles of Compiler Design",
        "Aho, Alfred", "Ullman, Jeffrey"
      ),
      Book(
        "Programming in Modula-2",
        "Wirth, Niklaus"
      ),
      Book(
        "Elements of ML Programming",
        "Ullman, Jeffrey"
      ),
      Book(
        "The Java Language Specification", "Gosling, James",
        "Joy, Bill", "Steele, Guy", "Bracha, Gilad"
      )
    )

查找作者姓「Gosling」的书名： 

  scala> for (b <- books; a <- b.authors
       |      if a startsWith "Gosling")
       | yield b.title
  res0: List[String] = List(The Java Language Specification)

查找书名含「Program」： 

  scala> for (b <- books if (b.title indexOf "Program") >= 0)
       | yield b.title
  res4: List[String] = List(Structure and Interpretation of
    Computer Programs, Programming in Modula-2, Elements
      of ML Programming)

查找编写了两本书以上的作者： 

  scala> for (b1 <- books; b2 <- books if b1 != b2;
       |     a1 <- b1.authors; a2 <- b2.authors if a1 == a2)
       | yield a1
  res5: List[String] = List(Ullman, Jeffrey, Ullman, Jeffrey)

上面的代码有缺陷，同一个作者会出现多次。下面的代码完成去重： 

  scala> def removeDuplicates[A](xs: List[A]): List[A] = {
       |   if (xs.isEmpty) xs
       |   else
       |     xs.head :: removeDuplicates(
       |       xs.tail filter (x => x != xs.head)
       |     )
       | }
  removeDuplicates: [A](List[A])List[A]

  scala> removeDuplicates(res5)
  res6: List[java.lang.String] = List(Ullman, Jeffrey)

最后一个表达式可以使用for表达式表现为： 

   xs.head :: removeDuplicates(
     for (x <- xs.tail if x != xs.head) yield x
   )

for表达式的转译

每个for表达式都可以换成map、flatMap、filter这三个高阶的形式表达。

简单变量生成器

x <- exp1这种生成器生成到简单变量的情况下，大概有三种情况。

一个生成器
for (x <- exp1) yield exp2

相当于： 

exp1 .map(x => exp2)
以一个生成器和过滤器载开头
for (x <- exp1 if exp2) yield exp3

相当于： 

for (x <- exp1 filter(x => exp2)) yield exp3

相当于： 

exp1 filter (x => exp2) map (x => exp3)

如果过滤器后有更多的元素同理。设seq为任意序列生成器、定义或过滤器，则： 

for (x <- exp1 if exp2 ; seq) yield exp3

相当于： 

for (x <- exp1 filter exp2 ; seq) yield exp3
以两个生成器开始
for (x <- exp1 ; y <- exp2 ; seq) yield exp3

设seq为任意序列生成器、定义或过滤器。则相当于flatMap的应用： 

exp1 .flatMap(x => for (y <- exp2 ; seq) yield exp3)
组合应用生成变量的例子

组合上面三种情况来处理「找出所有出版过至少两本书的作者」： 

for (b1 <- books; b2 <- books if b1 != b2;
     a1 <- b1.authors; a2 <- b2.authors if a1 == a2)
yield a1

相当于： 

books flatMap (b1 =>
  books filter (b2 => b1 != b2) flatMap (b2 =>
    b1.authors flatMap (a1 =>
      b2.authors filter (a2 => a1 == a2) map (a2 =>
        a1))))

生成器转译中的模式

如果生成器不是x <- expq这样生成到简单变量x的情况。转译起来就麻烦了。

变量元组

这种情况还简单，看起来像变量差不多。 

for ((x1, ..., xn) <- exp1) yield exp2

相当于： 

exp1 .map { case(x1, ..., xn) => exp2 }
单个模式匹配的情况

单个模式匹配的情况下： 

for (pat <- exp1) yield exp2

相当于： 

exp1 filter {
	case pat => true
	case _   => false
} map {
	case pat => exp2
}

基本思路是只有匹配于pat的情况才会被映射，所以也保证了模式匹配不会抛出 MatchError。

注意这只在单个模式匹配的情况下讨论。其他的情况参考Scala语言规格书「Ode08」。

多层内嵌定义

for (x <- exp1; y = exp2; seq) yield exp3

设seq为任意序列生成器、定义或过滤器。上面相当于： 

for((x,y) <- for (x <- exp1) yield (x, exp2); seq) yield exp3

因为exp2用到了x所以每次产x的时候exp2要重新计算。这样浪费了性能，所以： 

  for (x <- 1 to 1000; y = expensiveComputationNotInvolvingX)
  yield x * y

更好的写法是： 

  val y = expensiveComputationNotInvolvingX
  for (x <- 1 to 1000) yield x * y

没有返回值的情况

前面描述了通过yield生成值的情况。在不产值的情况下一般更简单，只要foreach： 

for (x <- exp1) body

相当于： 

exp1 foreach (x => body)

更加复杂的情况： 

for (x <- exp1 ; if exp2 ; y <- exp3) body

相当于： 

exp1 filter (x => exp2) foreach (
	x => exp3 foreach (y => body)
)

例子，把列表形式的矩阵所有元素累加在一起： 

  var sum = 0
  for (xs <- xss; x <- xs) sum += x

相当于： 

  var sum = 0
  xss foreach (xs => 
    xs foreach (x =>
      sum += x))

把高阶函数转为for循环

下面的三个函数是用for循环分别实现map、flatMap、filter的演示： 

  object Demo {
    def map[A, B](xs: List[A], f: A => B): List[B] =
      for (x <- xs) yield f(x)

    def flatMap[A, B](xs: List[A], f: A => List[B]): List[B] =
      for (x <- xs; y <- f(x)) yield y

    def filter[A](xs: List[A], p: A => Boolean): List[A] =
      for (x <- xs if p(x)) yield x
  }

for的应用

for表达式的实现是基于map、flatMap、filter这些高阶函数。所以可以把for用在 大批量数据上。for可以应用在数组和列表上也是因为这些这两个数组结构实现了这三个 高阶函数，其实可用的还有范围（Range）、迭代器（Iterator）、流（Stream）还有集 （Set）。

如果没有实现那三个方法的话要实现以后才能使用for，具体规则为：

  • 有map可以用单一生成器。
  • 有flatMap和map可以有多个生成器。
  • 有foreach可以有单一或多个生成器。
  • 有filter可以有过滤器。

设一个集合类C，典型的方法签名： 

  abstract class 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(b: A => Unit): Unit
  }

注意：对于参数类型A，方法返回的结果类型为有可能是A、B或Unit。

函数式编程里个概念叫单体（monad）有很广泛地应用，包括从集合、IO操作、状态操作、 回溯计算及交易等。map、flatMap、filter这三个方法可以用来定制单体功能。

© 2015 jade-dungeon.net. Valid CSS & XHTML
Website template by Arcsin