Scala 学习笔记——惰性求值

继续阅读《Scala 函数式编程》，记录些有趣的新玩意。这书某些地方的翻译实在连机翻都不如，但原书实在太好了，之后去看英文版。

该篇笔记记录关于惰性求值以及传名调用，传值调用等概念的学习。惰性求值的重要性在于，它能够使我们操作集合时在使用原有的高阶函数进行操作的基础上尽量保证性能，不用在操作过程中临时创建集合。而这种优化在不使用命令式的代码时是很难做到的。惰性求值使我们能同时保证抽象性和性能。那代价是什么呢？

关于 Call By Value, Call By Name

某些语句或操作符具有短路的特性，比如对 if 语句，如果 cond 为true，则 else 子句就不会被求值；对&&，如果前一个参数为false，则后一个参数不会被求值；对||，如果前一个参数是true，则第二个参数不会被求值。借助短路特性，我们甚至可以写出false && 1 / 0 == 0这样合法且不会抛出异常的表达式。

在大多数语言里，我们无法定义具有 if，&&，||这样的语句/操作符的行为的函数，比如，假如我们试图定义一个 and，并利用这个 and 去编写一个 head 函数：

boolean and(boolean condA, boolean condB) {
  return condA && condB;
}

int head(List<Integer> lst) {
  if (and(lst != null, lst.size() != 0)) {
    return lst.get(0);
  }
  throw new IllegalArgumentException("list can't be null!")
}

当我们试图调用这里的 head 函数时：

List<Integer> lst = null; // 生产环境可不能这么干！
System.out.println(head(lst));

能够发现，该代码抛出了空指针异常，这发生在 and 函数调用时。为什么会这样呢？这是因为大多数语言都是 Call By Value（传值调用），这是说，在函数调用之前，它会对各个参数进行求值并将结果值传递给函数，在这里，就是先求值lst != null和lst.size() != 0这两个表达式，将其结果传递给 and 函数，其中在求值lst.size()时就会抛出空指针异常。

与此相对的就是 Call By Name（传名调用），这是说，函数参数的表达式会被原样传递给函数，直到被求值时才真正对表达式执行计算，换句话说，在这个情形中，传值调用传递给函数的是false和Nothing，传名调用传递给函数的是lst != null和lst.size() != 0。

Call By Name 的行为和() => A的函数完全一致，比如我们可以这样实现 if——

// 考虑到清晰性的需要，使用 Scala 描述，但行为仍旧同 java 的 if 一致。使用 Java 的话得写 Runnable，不太痛快
def myIf(cond: Boolean, onTrue: () => Unit, onFalse: () => Unit): Unit {
  if (cond) {
    onTrue()
  } else {
    onFalse()
  }
}

可以认为 Call By Value 就是严格求值，Call By Name 就是非严格求值或惰性求值。说它是非严格求值，是因为函数调用时可以不对一个或多个参数进行求值，而严格求值的函数对所有参数都将求值。Scala 为非严格求值提供了独特的语法（类型定义）=> A，这样定义的参数只有在被调用的时候才会被求值，但其使用方法没有任何改变，比如我们可以定义一个类似 Rust 中的 loop 语句——

def loop(block: => Unit): Unit = 
  while(true) {
    block // 直接写出来就是调用了
  }

loop {
  println("hello!")
}

非严格求值中表达式的未求值形式称为thunk。

也需注意，=> A定义的变量每次调用时其都会被求值，这在某些时候可能并非我们想要的，有时候我们会想要把值只执行一次并缓存，之后都用缓存的值，这时候我们就可以结合lazy val进行使用。

严格求值在很多时候都是满足需求的，但在某些时候会有性能问题。比如，我们经常会对列表进行链式调用，如果是严格求值，则每次调用时我们都创建了一个新的列表，这在性能上可能会很差，更别说我们无法中途中断某些函数，无法表达无限长度列表等。以现有的工具，如果想要优化的话只能将操作都组合在同一个函数调用中，比如通过 reduce 可以模拟其它所有操作，或者使用命令式的方式。

于是，在像 Lodash，Spark 的 RDD 或 Java8 的 Stream 等场景/技术里，它们进行链式调用时，中途的操作并非是立刻就进行的，所有计算都在最后的行动/终端/取值操作中才进行，因而可以进行各种优化。

而函数式编程中对于这种情况的优化可以使用惰性求值去实现，对列表的每一个元素，只有在求值时才会被计算，Scala 默认就提供了惰性的列表——Stream（当前已过期，使用LazyList替代），它的行为和 Haskell 中的一致。

sealed trait Stream[+A] {
  /* ... */
}
case object Empty extends Stream[Nothing]
case class Cons[+A](h: () => A, t: () => Stream[A]) extends Stream[A]

我们可以对 Stream 定义一个惰性的右折叠（以方法的形式），它的行为和 Haskell 中的一致但比 Haskell 中更容易看出来——如果没有对 f 的第二个参数进行求值，则 tail 的部分根本不会被计算。

def foldRight[B](z: => B)(f: (A, => B) => B): B = this match {
  case Cons(h, t) => f(h(), t().foldRight(z)(f))
  case _ => Empty
}

借助 foldRight，我们可以对无限的列表进行折叠操作，只要在其中某一步中没有对 tail 进行求值即可，比如这里拷贝一个自然数列表：

def Nat: Stream[Int] = {
  def go(n: Int): Stream[Int] =
    cons(n, go(n + 1))
  go(0)
}

def copy[A](l: Stream[A]): Stream[A] = 
  l.foldRight(Empty)(cons(_, _))

println(copy(Nat).take(10).toList()) // List(0, 1, 2, 3, 4, 5, 6, 7, 8, 9)

但更重要的是，考虑到 map，filter 操作也是使用折叠去定义的，我们可以去对无限列表进行map-filter-reduce操作！比如下面定义了 filter，并定义了自然数中奇数的集合：

def filter[A](f: A => Boolean)(l: Stream[A]): Stream[A] =
  l.foldRight(Empty: Stream[A])((x, acc) => if (f(x)) cons(x, acc) else acc)
def Odd: Stream[Int] =
  filter[Int](_ % 2 == 1)(Nat)
println(Odd.take(10).toList())

关于foldRight为何能处理无限流，可以考虑这样的场景，对Nat.takeWhile(_ < 5)，会得到这样的序列：

0 <=< 1 <=< 2 <=< 3 <=< ... <=< n <=< []

对后面的任意大于等于5的n，n <=< []都返回[]，因此最后得到的计算序列仍旧是：

0 <=< 1 <=< 2 <=< 3 <=< 4 <=< 5 <=< []

在特定情况下<=<会返回[]，这是处理无穷列表的关键之处。

推导 Stream 的链式调用

要真正理解 Stream 在链式调用时的行为，我们需要对一些示例去进行推导以去增长感性经验。根据之前的感觉，使用 OOP 的形式进行的推导好像更容易一些，为此我们先实现作为方法的 map 和 filter，使用递归的形式：

def map[B](f: A => B): Stream[B] = this match {
  case Empty => Empty
  case Cons(h, t) => Stream.cons(f(h()), t().map(f))
}
def filter(p: A => Boolean): Stream[A] = this match {
  case Empty => Empty
  case Cons(h, t) => {
    val head = h()
    if (p(head)) Stream.cons(h(), t().filter(p))
    else t().filter(p)
  }
}

对Stream(1,2,3,4).filter(_ % 2 == 0).map(_ + 10).toList()，推导如下，其中 Cons 忽略了() =>的部分。

Stream(1,2,3,4).filter(_ % 2 == 0).map(_ + 10).toList()
Cons(1, Stream(2,3,4)).filter(_ % 2 == 0).map(_ + 10).toList()         // 解构 Stream
Stream(2,3,4).filter(_ % 2 == 0).map(_ + 10).toList()                  // 应用 filter，容易发现，元素 1 在这里直接扔掉了
Cons(2, Stream(3, 4)).filter(_ % 2 == 0).map(_ + 10).toList()          // 解构 Stream
Cons(2, Stream(3, 4).filter(_ % 2 == 0)).map(_ + 10).toList()          // 应用 filter
Cons(12, Stream(3, 4).filter(_ % 2 == 0).map(_ + 10)).toList()         // 应用 map
12 :: Stream(3, 4).filter(_ % 2 == 0).map(_ + 10).toList()             // 应用 toList
12 :: Cons(3, Cons(4, Empty)).filter(_ % 2 == 0).map(_ + 10).toList()  // 解构 Stream，并对 Stream(4) 转换为 Cons 的模式
12 :: Cons(4, Empty).filter(_ % 2 == 0).map(_ + 10).toList()           // 应用 filter，丢弃 3
12 :: Cons(4, Empty.filter(_ % 2 == 0)).map(_ + 10).toList()           // 应用 filter
12 :: Cons(14, Empty.filter(_ % 2 == 0).map(_ + 10)).toList()          // 应用 map
12 :: 14 :: Empty.filter(_ % 2 == 0).map(_ + 10).toList()              // 应用 toList
12 :: 14 :: Nil
[12, 14]

这种推导感觉挺容易写错的，但容易发现，它的行为就像构造了一个管道，对每个元素，它都将依序通过这些管子并执行各种操作。

惰性列表使许多方法的定义在保持原有性能的基础上可以使用高阶函数去组合出来，比如考虑一个 find 方法，我们可以直接结合 filter 和 headOption 去定义它（实际上，我们在 Java 的 Stream 里也可以这么玩嘛！新玩具 get），这无论在性能上还是在优雅性上都是十分高的，因为对于 Stream，filter 等操作是惰性的，并不会真的遍历整个列表。

def find(p: A => Boolean): Option[A] = 
  filter(p).headOption