Scala函数式编程

严格求值与非严格求值

定义非严格示值

严格示值的正式定义：如果对一个表达式的求值一直运行或抛出错误而非返回一个定义的值 ，我们说这个表达式没有结束（terminate），或说它是evaluates to bottom。 如果表达式f(x)对于所有evaluates to bottom的表达式x同样是evaluates to bottom 的，那么函数f是严格示值的。

说人话的版本：

• 严格求值（strictness）：函数收到的所有参数都会被求值。也叫传值参数（by value）
• 非严格求值（non-strictness）：函数可以选择不对一个或多个参数示值。 也叫传名参数（by name）

一般把一个表达式未求值的形式称为「thunk」。

如果把布尔运算符&&和||还有if表达式视为函数的话， 它们的短路特性就是明显的非严格求值：

false && { println("!!"); true  }        //> res0: Boolean = false
true  && { println("!!"); false }        //> !!
                                         //| res1: Boolean = false

if (true)  sys.error("aaa") else "bbb"   //> java.lang.RuntimeException: aaa
                                         //| ...
if (false) sys.error("aaa") else "bbb"   //> res2: String = bbb

实现非严格求值

手动实现非严格示值的方式是把函数作为参数传进去，只有符合条件时才对函数示值。 比如下面的例子就是把需要非严格示值的参数以一个没有参数的函数字面量的形式作为参数 ：

def if2[A](cond: Boolean, onTrue: () => A, onFalse: () => A): A = {
	if (cond) onTrue() else onFalse() 
}
         //> if2: [A](cond: Boolean, onTrue: () => A, onFalse: () => A)A

if2(true, () => println("a"), () => println("b"))                  //> a

可以发现Scala自带的语法用=> A作为语法糖，不用手动写为无参数的函数字面量， 也不用在用到时求值：

def if3[A](cond: Boolean, onTrue: => A, onFalse: => A): A = {
	if (cond) onTrue else onFalse
}
                //> if3: [A](cond: Boolean, onTrue: => A, onFalse: => A)A

if3(true, println("a"), println("b"))                              //> a

延迟求值与缓存

非严格示值不会缓存计算的值，所以同一个表示式可能会计算多次：

def maybeTwice(b: Boolean, i: => Int): Int = if (b) i + i else 0
                                //> maybeTwice: (b: Boolean, i: => Int)Int
                                              
maybeTwice(true, {println("hi"); 1 + 41})       //> hi
                                                //| hi
                                                //| res2: Int = 84

Scala提供了lazy关键字，变量在用到时才会计算与赋值，这样就可能缓存表达式的值：

def maybeTwice2(b: Boolean, i: => Int): Int = {
	lazy val j = i
	if (b) j + j else 0
}                               //> maybeTwice2: (b: Boolean, i: => Int)Int
                                                
maybeTwice2(true, {println("hi"); 1 + 41})      //> hi
                                                //| res3: Int = 84

非严格求值与流的应用

实现一个惰性的Stream：

import Stream._    // 隐藏scala版本的steam实现

trait Stream[+A] { /* ... */ }

case object Empty extends Stream[Nothing]

// 惰性流的head和tail都是非严格求值的thunk
case class Cons[+A](h: () => A, t: () => Stream[A]) extends Stream[A]

缓存Stream中的元素

缓存Stream中的元素，避免重复计算。

object Stream {

	def cons[A](hd: => A, tl: => Stream[A]): Stream[A] = {
		lazy val head = hd // 缓存head
		lazy val tail = tl // 缓存tail
		Cons(() => head, () => tail)
	}

	def empty[A]: Stream[A] = Empty

	def apply[A](as: A*): Stream[A] =
		if (as.isEmpty) empty
		else cons(as.head, apply(as.tail: _*))
}

Scala负责包装thunk中传给cons()的参数，所以as.head和apply(as.tail: _*) 这两个表达式在被Steam中强制求值之前不会被求值。

惰情求值流的常用工具函数

把Steam转为列表的toList：

trait Stream[+A] {
	// ... 

	// 有缺陷的版本，会爆栈
	def toListRecursive: List[A] = this match {
		case Cons(h, t) => h() :: t().toListRecursive
		case _ => List()
	}

	/* 尾递归优化 */
	def toList: List[A] = {
		@annotation.tailrec
		def go(s: Stream[A], acc: List[A]): List[A] = s match {
			case Cons(h, t) => go(t(), h() :: acc)
			case _ => acc
		}
		go(this, List()).reverse
	}

	/* 内部用可变类型存储，不会影响外部调用时的函数式风格。 */
	def toListFast: List[A] = {
		val buf = new collection.mutable.ListBuffer[A]
		@annotation.tailrec
		def go(s: Stream[A]): List[A] = s match {
			case Cons(h, t) =>
				buf += h()
				go(t())
			case _ => buf.toList
		}
		go(this)
	}

	// ... 
}

take(n)取得前n个元素，drop(n)得到n+1开始的所有元素：

trait Stream[+A] {
	// ... 

	/* 当`n<1`时返回空 */
	def take(n: Int): Stream[A] = this match {
		case Cons(h, t) if n > 1  => cons(h(), t().take(n - 1))
		case Cons(h, _) if n == 1 => cons(h(), empty)
		case _ => empty
	}

	/* */
	@annotation.tailrec
	final def drop(n: Int): Stream[A] = this match {
		case Cons(_, t) if n > 0 => t().drop(n - 1)
		case _ => this
	}

	// ... 
}

takeWhile(f: A => boolean)返回开头连续符合条件的元素：

trait Stream[+A] {
	// ... 

	/* `t() takeWhile f`是函数语法糖，相当于：`t().takeWhile(f)`  */
	def takeWhile(f: A => Boolean): Stream[A] = this match {
		case Cons(h, t) if f(h()) => cons(h(), t() takeWhile f)
		case _ => empty
	}

	// ... 
}

分离函数的描述与函数的求值