Scala函数式编程

纯函数

副作用

「副作用」（side effect）是指对相关环境产生的改变：

val s  = "hello, world"               //> s  : String = hello, world
val s1 = s.reverse                    //> s1 : String = dlrow ,olleh
val s2 = s.reverse                    //> s2 : String = dlrow ,olleh

val x  = new StringBuilder("hello")   //> x  : StringBuilder = hello
val r1 = x.append(", world").toString //> r1 : String = hello, world
val r2 = x.append(", world").toString //> r2 : String = hello, world, world

引用透明

可以使用「引用透明」（referential transparency）的概念对纯函数进行形式化：

• 2 + 3是一个表达式。
• 2和3也可以视为表达式。
• 2 + 3的值只会是5，而且没有副作用，所以可以用5替换掉程序中所有的2 + 3。

所有程序中所有符合引用透明的表达式都可以由它的结果来取代， 而不改变程序的含意。当调用一个函数时所传入的参数是引用透明的， 并且函数的调用也是引用引用透明的，那么这个函数就是一个纯函数。

有副作用的例子，不是引用透明：

// 信用卡 id 信用卡的卡号
class CreditCard(val id: String)

// 咖啡 price 咖啡的价格
class Coffee(val price: Double)

def buyCoffee(cc: creditCard): Coffee = {
	val cup = new Coffee(5.5)
	cc.sentChargeInfo(cup.price) // 发送消费记录给信用卡公司，有副作用
	cup
}

既然付费操作是副作用，那么就把它放到其它的地方。 在当前的函数中只记录下消费的金额。没有副作用，是引用透明的：

// 买咖啡 cc 信用卡 return (咖啡,信用卡消费记录)
def byCoffee(cc: CreditCard): (Coffee, Charge) = {
	val cup = new Coffee(5.5)
	val charge = Charge(cc, cup.price)
	(cup, charge)
}

消费记录可以单独抽象出来，还有一个好处，就是同一张信用卡的消费金额还可以加起来：

// 消费记录，指定一张信用卡与这张信用卡消息的金额
// param  cc 信用卡 param  amount 金额
case class Charge(val cc: CreditCard, val amount: Double) {

	// 同一张信用卡的金额加起来 
	def combine(other: Charge): Charge = {
		if (cc == other.cc)
			Charge(cc, amount + other.amount)
		else // 不同信用卡上的消息不能合并
			throw new Exception("Not same Credit Card")
	}

}

有了合并金额功能，可以不带副作用地买多杯咖啡：

// param cc 信用卡 param count 要买的咖啡的数量 
// return (多杯咖啡列表,信用卡消费金额)
def byCoffees(cc: CreditCard, count: Int): (List[Coffee], Charge) = {
	val puschases: List[(Coffee, Charge)] = List.fill(count)(byCoffee(cc))
	val (coffees, charges) = puschases.unzip // 咖啡与金额分成两个列表 
	(coffees, charges.reduce((c1, c2) => c1.combine(c2)))
}

多个信用卡消费还可以按每张卡汇总到一起：

def coalsece(charges: List[Charge]): List[Charge] = {
	charges.groupBy(_.cc).values.map(_.reduce(_ combine _)).toList
}

// 上面的相当于：

def coalsece2(charges: List[Charge]): List[Charge] = {
	// 按卡号相同分组
	val chargeGroup: Map[CreditCard, List[Charge]] = charges.groupBy(_.cc)
	// 同一组内把金额加起来
	val chargeListGrp: Iterable[Charge] = chargeGroup.values.map(
			                                             _.reduce(_ combine _))
	// 把集合容器转为列表
	chargeListGrp.toList
}

代换模型

引用透明要求函数的任何操作都可以用它的返回值（value）代替， 这种形式称为「代换模型」（subsitution model）。 所以引用透明使得程序具备了「等式推理」（equational reasoning）能力。

代换模型因为没有副作用，所以只要进行局部的推理就可以得到结果， 不用跟踪函数执行过程中其他局部状态或是全局状态的变化。

高阶函数

函数也是值，可以像变量一样赋值、存储在数据结构中、或是作为参数传递给另一个函数。

把函数作为参数传递给别一个函数，被称为「高阶函数」（higher-order function， 缩写为HOF）。

def abs(n: Int): Int = if (n < 0) -n else n
                         //> abs: (n: Int)Int

def formatFunc(x: Int, func: Int => Int) = {
	val msg = "The absolute value of %d is %d"
	msg.format(x, func(x))
}                        //> formatFunc: (x: Int, func: Int => Int)String

formatFunc(-5, abs)      //> res0: String = The absolute value of -5 is 5

一般函数参数都用func、func1、func2或是f、g、h等命名， 因为只确定函数参数类型和返回值类型，具体逻辑是末定的，所以不用特别描述。

高阶函数的缺点：

高阶函数把函数作为参数，这在很多情况很难用参数名来描述作为参数的函数的功能与特性 。所以在找不到能恰当描述的参数名字的时候就干脆用比较短的参数名， 这样至少看起来比较整齐。

尾递归优化

递归调用发生于最后一个操作时，可以进行优化为循环：

def factorial(n: Int): Int = {
	@annotation.tailrec // 注释强制对尾递归调用进行优化
	def go(n: Int, acc: Int): Int = {
		if (n <= 0) acc else go(n - 1, n * acc)
	}
	go(n, 1)
}

多态函数：函数的泛型

单态（monomorphic）函数的例子，查找数组中的第一个符合的元素，元素的类型待定：

def findFirst[A](as: Array[A], p: A => Boolean): Int = {
	@annotation.tailrec
	def loop(n: Int): Int = {
		if (n >= as.length) -1
		else if (p(as(n))) n
		else loop(n + 1)
	}
	loop(0)
}

部分应用函数

部分应用函数（partial application）也叫偏函数：

def partialFunction[A, B, C](a: A, f: (A, B) => C): B => C =
		(b: B) => f(a, b)

帮助理解：

def partialFunction[A, B, C](a: A, f: (A, B) => C): B => C = {

	def func2(b: B): C = { // 包装成新的函数，缺少的参数`b`
		f(a, b)              // 已经有的参数`a`
	}

	func2
}

应用：

def f002(a: Int, b: Double): String = {
	s"${a}-${b}"
}                              //> f002: (a: Int, b: Double)String

f002(3, 0.2)                   //> res0: String = 3-0.2

// 部分应用函数返回的结果是一个函数
def f003 = partialFunction(3, f002) //> f003: => Double => String

val v3 = f003(0.2)             //> v3  : String = 3-0.2

柯里化与反柯里化

柯里化（currying）把带有两个参数的函数func(a:A, b:B): C 转换为只有一个一个参数的偏应用函数partialFunc(a: A): B => C：

注意A => B => C按Scala语法来说相当于A => (B => C)：

def curry[A, B, C](f: (A, B) => C): A => (B => C) = {
	(a: A) => {
		(b: B) => {
			f(a, b)
		}
	}
}

简写为：

def curry[A, B, C](f: (A, B) => C): A => B => C =
	a => b => f(a, b)

反柯里化：

def uncurry[A, B, C](f: A => B => C): (A, B) => C =
	(a, b) => f(a)(b)

应用：

def f002(a: Int, b: Double): String = {
	s"${a}-${b}"
}                          //> f002: (a: Int, b: Double)String

// 测试柯里化
val f005 = curry(f002)     //> f005  : Int => (Double => String)
val f006 = f005(3)         //> f006  : Double => String 
val f007 = f006(0.2)       //> f007  : String = 3-0.2

// 测试反柯里化
val f008 = uncurry(f005)   //> f008  : (Int, Double) => String
val v7 = f008(3, 0.2)      //> v7  : String = 3-0.2

组合函数

组合compose(f, g)相当于f(g())：

def compose[A, B, C](f: B => C, g: A => B): A => C =
	a => f(g(a))

Scala为只有一个参数的函数提供了现在的抽象Function1， 它自带compose()方法，compose(f,g)可以表现为f.compose(g)并简写为 f compose g。

功能类似的还有andThan()函数。f andThan g等价于g compose f。

def andThen[A, B, C](g: A => B, f: B => C): A => C =
	a => g(f(a))

通过部分应用函数强化类型推导

@annotation.tailrec
def foldLeft[A, B](l: List[A], z: B, f: (B, A) => B): B = l match {
	case Nil => z
	case Cons(h, t) => foldLeft(t, f(z, h), f)
}
//> foldLeft: [A, B](l: List[A], z: B, f: (B, A) => B)B

foldLeft(List(1, 2, 3), "", (a: String, b: Int) => { b + ("" + a) })
//> res0: String = 321

通过柯里化把参数列表拆分成两个偏函数，scala编译器可以通过传入的第一个参数列表 的实参List(1, 2, 3), ""推导出[A, B]是[Int, String]，这样第二个参数f 的类型就一定是f:(String, Int) => String。不用手动指定了：

@annotation.tailrec
def foldLeft[A, B](l: List[A], z: B)(f: (B, A) => B): B = l match {
	case Nil => z
	case Cons(h, t) => foldLeft(t, f(z, h))(f)
}
//> foldLeft: [A, B](l: List[A], z: B)(f: (B, A) => B)B

foldLeft(List(1, 2, 3), "")((a, b) => { b + ("" + a) })
//> res0: String = 321

函数式数据结构

函数式编程的特点是数据结构不可变，函数的操作每次都生成新的值作为返回值， 而不会去修改传入的实参的值。

单向链表

列表类型抽象为特质，内容类型为泛型A：

sealed trait List[+A]

空列表，作为列表类子类的单例实现：

case object Nil extends List[Nothing]

非空列表类型，构造器由表头第一个元素和其他元素列表两部分组成：

case class Cons[+A](head: A, tail: List[A]) extends List[A]

列表的常用方法：

/* 返回新列表，删除列表的第一个元素 */
def tail[A](l: List[A]): List[A] = l match {
	case Nil => sys.error("tail of empty list")
	case Cons(_, t) => t
}

/* 返回新列表，替换列表的第一个元素 */
def setHead[A](l: List[A], h: A): List[A] = l match {
	case Nil => sys.error("setHead on empty list")
	case Cons(_, t) => Cons(h, t)
}

/* 返回新列表，删除列表前n个元素 */
def drop[A](l: List[A], n: Int): List[A] = if (n <= 0) l else l match {
	case Nil => Nil
	case Cons(_, t) => drop(t, n - 1)
}

/* 返回新列表，删除列表前缀所有符合条件的元素 */
def dropWhile1[A](l: List[A], f: A => Boolean): List[A] = l match {
	case Cons(h, t) if f(h) => dropWhile1(t, f)
	case _ => l
}

/* 返回新列表，构建列表，以可变长的多个参数拼接成列表 */
def apply[A](as: A*): List[A] = if (as.isEmpty) Nil else {
	Cons(as.head, apply(as.tail: _*))
}

/* 返回新列表，拼接列表，把a1的元素都加到a2里 */
def append[A](a1: List[A], a2: List[A]): List[A] = a1 match {
	case Nil => a2
	case Cons(h, t) => Cons(h, append(t, a2))
}

通过柯里化，在使用用这个函数时，第二个参数的类型可以直接类型推导出来，不用注明类型：

def dropWhile[A](l: List[A])(f: A => Boolean): List[A] = l match {
	case Cons(h, t) if f(h) => dropWhile(t)(f)
	case _ => l
}

val ld = List(1, 2, 3, 4)
val ls = dropWhile(ld)(x => x < 4)

折叠操作

def foldRight2[A, B](as: List[A], z: B)(f: (A, B) => B): B = as match {
	case Nil => z
	case Cons(x, xs) => f(x, foldRight2(xs, z)(f)) // 无法尾递归优化
}

foldRight2函数替换为它的定义，来演示折叠过程：

foldRight2(Cons(1, Cons(2, Cons(3, Nil))), Nil: List[Int])(Cons(_, _))
Cons(1, foldRight2(Cons(2, Cons(3, Nil)), Nil: List[Int])(Cons(_, _)))
Cons(1, Cons(2, foldRight2(Cons(3, Nil), Nil: List[Int])(Cons(_, _))))
Cons(1, Cons(2, Cons(3, foldRight2(Nil, Nil: List[Int])(Cons(_, _)))))
Cons(1, Cons(2, Cons(3, Nil)))

flodRight不是尾递归，改进为可以尾递归优化的foldLeft：

@annotation.tailrec
def foldLeft[A, B](l: List[A], z: B)(f: (B, A) => B): B = l match {
	case Nil => z
	case Cons(h, t) => foldLeft(t, f(z, h))(f)
}

通过foldLeft来实现foldRight：

def foldRightViaFoldLeft_1[A, B](l: List[A], z: B)(f: (A, B) => B): B =
	foldLeft(reverse(l), z)((b, a) => f(a, b))

另一种实现的代码：

def foldRightViaFoldLeft_2[A, B](l: List[A], z: B)(f: (A, B) => B): B = {

	def identity(p1: B): B = { p1 }   // 把值包装为函数`B=>B`

	// 匹配到的类型应该为：
	// foldLeft(
	//   l: List[A], fun: B=>B
	// )(
	//   (g: B=>B, a:A) => (B=>B)
	// )
	def func: B => B = foldLeft(
		l, identity(_)    // 把函数`identity: B => B`作为不动点
	)(
		(g, a) => {       // 实参`identity: B=>B`代入形参`g: B=>B`
			b => { g(f(a, b)) }
		}
	)

	func(z)             // `z`作为一开始代入`identity`
}

简写为：

def foldRightViaFoldLeft[A, B](l: List[A], z: B)(f: (A, B) => B): B =
	foldLeft(l, (b: B) => b)((g, a) => b => g(f(a, b)))(z)

通过foldRight来实现foldLeft：

def foldLeft2[A, B](l: List[A], z: B)(f: (B, A) => B): B =
	foldRight(l, (b: B) => b)((a, g) => b => g(f(b, a)))(z)

通过foldRight来实现append：

def append2[A](l: List[A], r: List[A]): List[A] =
	foldRight(l, r)(Cons(_, _))

常用的折叠操作有三种，主要的区别是fold函数操作遍历问题集合的顺序：

• foldLeft是从左开始计算。
• foldRight是从右开始算。
• fold遍历没有特殊的次序，所以对fold的初始化参数和返回值都有限制。

以Scala自带的源代码来说明：

def fold[A1 >: A](z: A1)(op: (A1, A1) => A1): A1 = foldLeft(z)(op)
 
def foldLeft[B](z: B)(op: (B, A) => B): B = {
  var result = z
  this.seq foreach (x => result = op(result, x))
  result
}
 
def foldRight[B](z: B)(op: (A, B) => B): B =
  reversed.foldLeft(z)((x, y) => op(y, x))

由于fold函数遍历没有特殊的次序，所以对fold的初始化参数和返回值都有限制。 在这三个函数中，初始化参数和返回值的参数类型必须相同。

• 第一个限制是初始值的类型必须是list中元素类型的超类。在我们的例子中，我们的对 List[Int]进行fold计算，而初始值是Int类型的，它是List[Int]的超类。
• 第二个限制是初始值必须是中立的(neutral)。也就是它不能改变结果。比如对「数字」 这个范围与「加法」这个操作组成的「范畴」来说，中立的值是0（在范畴论中被称为 幺元），因为任何数加上0都等于它本身；而对于数字与乘法组成的范畴来说， 中立值则是1。

val lst = ch03.List(1, 2, 3)

ch03.List.foldLeft(lst, ch03.Nil: ch03.List[Int])((acc, o) => ch03.Cons(o, acc))
//> res0: fpinscala.ch03.datastructure.List[Int] = Cons(3,Cons(2,Cons(1,Nil)))

ch03.List.foldRight(lst, ch03.Nil: ch03.List[Int])((o, acc) => ch03.Cons(o, acc))
//> res1: fpinscala.ch03.datastructure.List[Int] = Cons(1,Cons(2,Cons(3,Nil)))

/* 加法 */
def sum(l: List[Int]) = foldLeft(l, 0)(_ + _)

/* 乘法 */
def product(l: List[Double]) = foldLeft(l, 1.0)(_ * _)

/* 计算长度 */
def length[A](l: List[A]): Int = foldLeft(l, 0)((acc, h) => acc + 1)

/* 反转列表 */
def reverse[A](l: List[A]): List[A] = 
                        foldLeft(l, List[A]())((acc, h) => Cons(h, acc))
	
// 拼接多个列表为一个列表
def concat[A](l: List[List[A]]): List[A] = foldRight(l, Nil: List[A])(append)

映射操作

// 列表中的每个元素值加1
def add1(l: List[Int]): List[Int] =
	foldRight(l, Nil: List[Int])((h, t) => Cons(h + 1, t))

// 列表中double转为字符串
def doubleToString(l: List[Double]): List[String] =
	foldRight(l, Nil: List[String])((h, t) => Cons(h.toString, t))

def map[A, B](l: List[A])(f: A => B): List[B] =
	foldRight(l, Nil: List[B])((h, t) => Cons(f(h), t))

def map_2[A, B](l: List[A])(f: A => B): List[B] = {
	val buf = new collection.mutable.ListBuffer[B]
	def go(l: List[A]): Unit = l match {
		case Nil => ()
		case Cons(h, t) => buf += f(h); go(t)
	}
	go(l)
	List(buf.toList: _*) // 从Scala内部的List转为我们自己实现的List
}

过滤操作

def filter[A](l: List[A])(f: A => Boolean): List[A] =
	foldRight(l, Nil: List[A])((h, t) => if (f(h)) Cons(h, t) else t)

def filter_1[A](l: List[A])(f: A => Boolean): List[A] =
	foldRightViaFoldLeft(l, Nil: List[A])((h, t) => if (f(h)) Cons(h, t) else t)

def filter_2[A](l: List[A])(f: A => Boolean): List[A] = {
	val buf = new collection.mutable.ListBuffer[A]
	def go(l: List[A]): Unit = l match {
		case Nil => ()
		case Cons(h, t) => if (f(h)) buf += h; go(t)
	}
	go(l)
	List(buf.toList: _*) // 从Scala内部的List转为我们自己实现的List
}

flatMap

flatMap与映射很像，区别是函数f返回的是列表而不是单个结果

def flatMap[A, B](l: List[A])(f: A => List[B]): List[B] =
	concat(map(l)(f))

调用：

flatMap(List(1, 2, 3))(i => List(i, i))
// > List(1, 1, 2, 2, 3, 3)

用flatMap实现Filter

def filterViaFlatMap[A](l: List[A])(f: A => Boolean): List[A] =
	flatMap(l)(a => if (f(a)) List(a) else Nil)

zip操作

把两个列表按索引相同的值加加起来，形成一个新的列表：

def addPairwise(a: List[Int], b: List[Int]): List[Int] = (a, b) match {
	case (Nil, _) => Nil
	case (_, Nil) => Nil
	case (Cons(h1, t1), Cons(h2, t2)) => Cons(h1 + h2, addPairwise(t1, t2))
}

addPairwise(List(1, 2, 3), List(4, 5, 6))
// > List(5, 7, 9)

抽像成更通用的方法zipWith：

def zipWith[A, B, C](a: List[A], b: List[B])(f: (A, B) => C): List[C] = 
{
	(a, b) match {
		case (Nil, _) => Nil
		case (_, Nil) => Nil
		case (Cons(h1, t1), Cons(h2, t2)) => {
			Cons(f(h1, h2), zipWith(t1, t2)(f))
		}
	}
}

二叉树

用二元组分别指向左右子树：

sealed trait Tree[+A]

case class Leaf[A](value: A) extends Tree[A]

case class Branch[A](left: Tree[A], right: Tree[A]) extends Tree[A]

// 递归遍历统计节点数
def size[A](t: Tree[A]): Int = t match {
	case Leaf(_) => 1
	case Branch(l, r) => 1 + size(l) + size(r)
}

// 找到最大值
def maximum(t: Tree[Int]): Int = t match {
	case Leaf(n) => n
	case Branch(l, r) => maximum(l) max maximum(r)
}

// 层数
def depth[A](t: Tree[A]): Int = t match {
	case Leaf(_) => 0
	case Branch(l, r) => 1 + (depth(l) max depth(r))
}

// 映射
def map[A, B](t: Tree[A])(f: A => B): Tree[B] = t match {
	case Leaf(a) => Leaf(f(a))
	case Branch(l, r) => Branch(map(l)(f), map(r)(f))
}

树的折叠

和列表一样，fold函数通过递归处理Tree类型构造器的参数来折叠树形结构：

def fold[A, B](t: Tree[A])(f: A => B)(g: (B, B) => B): B = t match {
	case Leaf(a) => f(a)
	case Branch(l, r) => g(fold(l)(f)(g), fold(r)(f)(g))
}

def sizeViaFold[A](t: Tree[A]): Int =
	fold(t)(a => 1)(1 + _ + _)

def maximumViaFold(t: Tree[Int]): Int =
	fold(t)(a => a)(_ max _)

def depthViaFold[A](t: Tree[A]): Int =
	fold(t)(a => 0)((d1, d2) => 1 + (d1 max d2))

def mapViaFold[A, B](t: Tree[A])(f: A => B): Tree[B] =
	fold(t)(a => Leaf(f(a)): Tree[B])(Branch(_, _))

对于像是Leaf(f(a))这样的表达式要注明类型，不然Scala的类型推导会出错：

  type mismatch;
    found   : fpinscala.datastructures.Branch[B]
    required: fpinscala.datastructures.Leaf[B]
       fold(t)(a => Leaf(f(a)))(Branch(_,_))
                                      ^

这是Scala使用一个类的子类应用到代数数据类型 （subtyping to encode algebraic data types）时引发的错误。在不注明的情况下fold的 返回值被推导为Leaf[B]。在这个基础上假定fold的第二个函数的返回值类型也是 Leaf[B]（但实际上应该是Branch[B]）。

从期望上讲，如果Scala的类型推导出Tree[B]是最好的情况，因为这样可以适用到Tree 的所有子类。当在Scala中使用代数数据类型时，常常会定义一些辅助函数直接调用恰当的 构造函数，同时让返回值的类型是更加通用的类型：

def leaf[A](a: A): Tree[A] = Leaf(a)

def branch[A](l: Tree[A], r: Tree[A]): Tree[A] = Branch(l, r)

异常处理

异常处理的优点：

• 把错误处理逻辑整合集中在一起。

异常处理的缺点：

• 破坏了引用透明，并引入了对上下文的依赖。所以替代模型的简单代换不再适用。 业界最基本的共识是异常处理应该只用于处理错误而不是流程控制。
• 无法检查异常类型是否安全，编译器也不会强制函数的调用者处理被调用函数可能抛出 的异常。编写代码时没有处理的异常赶到程序运行时才被发现。
• 高阶函数以函数用为参数，但是不适用对参数函数可能抛出的异常进行处理。 例：f(g())中g()可能抛出各种异常，f()中应该如何处理。

用返回值类型代替抛出异常

Scala中可以把抛出的异常设置为任何的类型。比如设定为整数：

def func01(i: Int): Int = {
	try {
		val x = 42 + 5
		x + ((throw new Exception("fail!")): Int) //异常作为整数返回
	} catch {
		case e: Exception => 42
	}
}

func01(12)            // res1: Int 43

用Option表示函数无定义

如果要自己实现Scala中已经有的Option，表示函数并不对所有的参数都有定义：

sealed trait Option[+A]

// 有定义
case class Some[+A](get: A) extends Option[A]

// 无定义
case object None extends Option[Nothing]

Option基本操作

取值，如果为None则返回参数指定的default：

seald trait Option[+A] {

	// .... 

def getOrElse[B>:A](default: => B): B = this match {
  case None => default
  case Some(a) => a
}

	// .... 

}

映射操作的返回类型还是Some(A)：

seald trait Option[+A] {

	// .... 

def map[B](f: A => B): Option[B] = this match {
  case None => None
  case Some(a) => Some(f(a))
}

def flatMap[B](f: A => Option[B]): Option[B] =
  map(f) getOrElse None


// Of course, we can also implement `flatMap` 
// with explicit pattern matching.
def flatMap_1[B](f: A => Option[B]): Option[B] = this match {
  case None => None
  case Some(a) => f(a)
}

	// .... 

}

orElse(ob)避免对参数ob求值（除非必要的情况下）：

seald trait Option[+A] {

	// .... 

def orElse[B>:A](ob: => Option[B]): Option[B] =
  this map (Some(_)) getOrElse ob

/*
Again, we can implement this with explicit pattern matching.
*/
def orElse_1[B>:A](ob: => Option[B]): Option[B] = this match {
  case None => ob
  case _ => this
}

	// .... 

}

过滤不符合的内容：

seald trait Option[+A] {

	// .... 

def filter(f: A => Boolean): Option[A] = this match {
  case Some(a) if f(a) => this
  case _ => None
}

/*
This can also be defined in terms of `flatMap`.
*/
def filter_1(f: A => Boolean): Option[A] =
  flatMap(a => if (f(a)) Some(a) else None)

	// .... 

}

Option应用场景

Option类型的链式调用，None类型的map、flatMap、filter返回的都是None。 所以链式调用中间有一步的结果为None会中断调用：

case class Employee(name: String, department: String, manager: String)

def lookupByName(name: String): Option[Employee] = name match {
	case "Joe" => Some(new Employee("Joe", "R&D Dept.", "Jade"))
	case _ => None
}

lookupByName("Joe").map(_.department)
                       //> res0: Option[String] = Some(R&D Dept.)
lookupByName("Joe").map(_.department).getOrElse("Default Dept.")
                       //> res2: String = R&D Dept.

lookupByName("Teo").map(_.department)     //> res1: Option[String] = None
lookupByName("Teo").map(_.department).getOrElse("Default Dept.")
                                          //> res3: String = Default Dept.

lookupByName("Joe").map(_.department).filter(_ != "R&D Dept."
	).getOrElse("Default Dept.") //> res8: String = Default Dept.

lookupByName("Joe").map(_.department).filter(_ != "Accounting Dept."
	).getOrElse("Default Dept.") //> res9: String = R&D Dept.

lookupByName("Joe").flatMap(_ match {case t => Some(t)})
                      //> res4: Option[Employee] = Some(Employee(...))
lookupByName("Joe").flatMap(_.department match {case t => Some(t)})
                      //> res5: Option[String] = Some(R&D Dept.)
lookupByName("Teo").flatMap(_ match {case t => Some(t)})
                      //> res6: Option[Employee] = None
lookupByName("Teo").flatMap(_.department match {case t => Some(t)})
                      //> res7: Option[String] = None

使用flatMap实现方差（variance）函数。如果一个序列的平均值是\(m\)， 方差是对序列中的第个元素\(x\)进行\(math.pow(x-m, 2)\)。

方差调用的多个阶段中都有可能失败，运算是遇到第一个失败就中止， 因为None.flatMap(f)会返回None，不再调用函数f：

// 平均值
def mean(xs: Seq[Double]): Option[Double] =
  if (xs.isEmpty) None
  else Some(xs.sum / xs.length)

def variance(xs: Seq[Double]): Option[Double] =
  mean(xs) flatMap (m => mean(xs.map(x => math.pow(x - m, 2))))

把Option转回异常

必要的情况下，把Option转回为异常处理也不是不可以：

result.getOrElse(throw new Exception("Fail"))

Option与函数提升

用Option有很多好处，但是很多函数的参数与返回值并不是Option类型的。 lift函数可以把函数的参数与返回值都包装为Option，即把f: A => B 包装为g: Option[A] => Option[B]：

lift函数返回一个新的函数作为返回值，这个新函数以Option[A]为参数， 这样Option[A].map(f)的返回值类型就是Option[B]：

def lift2[A, B](f: A => B): Option[A] => Option[B] = {
	val newFunction = (t: Option[A]) => { t map f }
	newFunction
}                         //> lift2: [A, B](f: A => B)Option[A] => Option[B]

// 简写一下：
def lift[A, B](f: A => B): Option[A] => Option[B] = _ map f
                          //> lift: [A, B](f: A => B)Option[A] => Option[B]

val abs = lift(math.abs) //> absO  : Option[Int] => Option[Int] 

结合异常与提升Option

让异常返回None：

def parseStringAge(age: String): Int = age.toInt
                          //> parseStringAge: (age: String)Int

parseStringAge("33")      //> res10: Int = 33

parseStringAge("Hello")   //> java.lang.NumberFormatException: ........ 

def Try[A](a: => A): Option[A] = try Some(a) catch {
	case e: Exception => None   // 这样会丢弃异常信息，以后再改进
}                               //> Try: [A](a: => A)Option[A]

def parseStringAge2(age: String): Option[Int] = {
		Try(age.toInt)
}                               //> parseStringAge2: (age: String)Option[Int]

parseStringAge2("33")           //> res11: Option[Int] = Some(33)
parseStringAge2("hello")        //> res12: Option[Int] = None
parseStringAge2("world")        //> res13: Option[Int] = None

提升有多个参数的函数

lift只能提升单个参数的函数，如果函数有多个参数就不能通过lift提升：

/* 根据年龄与超速罚单的数量评价保险的评分 */
def insuranceRateQuote(age: Int, numberOfSpeedingTickets: Int): Double = ???
   //> insuranceRateQuote: (age: Int, numberOfSpeedingTickets: Int)Double

要通过新的工具函数map2把两个参数都提升为Option：

def map2[A,B,C](a: Option[A], b: Option[B])(f: (A, B) => C): Option[C] =
  a flatMap (aa => b map (bb => f(aa, bb)))     
//> map2: [A, B, C](a: Option[A], b: Option[B])(f: (A, B) => C)Option[C]
                                                
def parseInsuranceRateQuote(age: String, 
		numberOfSpeedingTickets: String): Option[Double] = 
{
	val optAge:  Option[Int] = Try(age.toInt)
	val optTick: Option[Int] = Try(numberOfSpeedingTickets.toInt)
	map2(optAge, optTick)(insuranceRateQuote)
}
//> parseInsuranceRateQuote: (age: String, 
 //|                numberOfSpeedingTickets: String)Option[Double]

合并多个Option为单个Option的列表

sequence函数把含有多个Option的列表List[Option[A]]结合为一个Option[List[A]] 如果原来的列表里有一个为None，那么sequence函数返回的结果也是None：

def sequence[A](lst: List[Option[A]]): Option[List[A]] = lst match {
	case Nil => Some(Nil)
	case h :: t => h flatMap (hh => sequence(t) map (hh :: _))
}     
//> sequence: [A](lst: List[Option[A]])Option[List[A]]

还可以通过 foldRight 和 map2来实现sequence ，在foldRight里要注明类型为 [Option[List[A]]]不然会被类型推导错误地推导为Some[Nil.type]

def sequence_1[A](a: List[Option[A]]): Option[List[A]] =
	a.foldRight[Option[List[A]]](Some(Nil))((x, y) => map2(x, y)(_ :: _))
//> sequence_1: [A](a: List[Option[A]])Option[List[A]]

sequence仅仅只适合用来合并列表为单个option，如果涉及到map操作，就要遍历两次， 例如下面的字符串转整数，map的时候遍历一遍lst，合并Option时又要遍历一遍：

def parseInts(lst: List[String]): Option[List[Int]] = 
		sequence(lst map (i => Try(i.toInt)))

定义新的工具traverse直接在一个遍历过程中map并合并Option：

def traverse[A, B](a: List[A])(f: A => Option[B]): Option[List[B]] = a match {
		case Nil => Some(Nil)
		case h :: t => map2(f(h), traverse(t)(f))(_ :: _)
}                                 
//> traverse: [A, B](a: List[A])(f: A => Option[B])Option[List[B]]

def traverse_1[A, B](a: List[A])(f: A => Option[B]): Option[List[B]] = {
	a.foldRight[Option[List[B]]](Some(Nil))((h, t) => map2(f(h), t)(_ :: _))
}
//> traverse_1: [A, B](a: List[A])(f: A => Option[B])Option[List[B]]

def sequenceViaTraverse[A](a: List[Option[A]]): Option[List[A]] = {
	traverse(a)(x => x)               
}
//> sequenceViaTraverse: [A](a: List[Option[A]])Option[List[A]]

Option提升与for推导

因为提升非常常见，所以scala自带的for推导已经自带提升效果：

def map2[A, B, C](a: Option[A], b: Option[B])(f: (A, B) => C): Option[C] =
	a flatMap (aa => 
			b map (bb => 
				f(aa, bb)))

任何的map与flatMap操作都可以替换为for推导：

def map2[A, B, C](a: Option[A], b: Option[B])(f: (A, B) => C): Option[C] =
	for {
		aa <- a
		bb <- b
	} yield f(aa, bb)

yield关键字可以使用<-符号左边绑定的值，编译器会把这些绑定操作的语法糖 转换为map调用。

Either数据类型

Either和Option一样可以用来替换异常或失败，区别是Option只能用None表示没有值 。不能传递更多关于产生错误原因的信息。Either可以带有更多关于失败的详细信息：

sealed trait Either[+E, +A] 
case class  Left[+E](get: E) extends Either[E, Nothing]
case class Right[+A](get: A) extends Either[Nothing, A]

父类Either的泛型E代表错误信息的类型，A代表有结果的结果类型。 两个子类Left和Right分别代表错误和正确。

// 求平均值，错误时返回的是相关错误信息的字符串：
def mean(xs: IndexedSeq[Double]): Either[String, Double] = 
  if (xs.isEmpty) 
    Left("mean of empty list!")
  else 
    Right(xs.sum / xs.length)

// 还可以把堆栈调用信息放进去
def safeDiv(x: Int, y: Int): Either[Exception, Int] = 
  try Right(x / y)
  catch { case e: Exception => Left(e) }

有时为了方便，当结果有两种类型的数据又不值得特地定义一个新的类的时候， 也常常用Either应付一下。

把之前的Option类型的Try函数改为用Either类型：

def Try[A](a: => A): Either[Exception, A] =
  try Right(a)
  catch { case e: Exception => Left(e) }

常用函数的实现：

sealed trait Either[+E, +A] {

	def map[B](f: A => B): Either[E, B] = this match {
			case Right(a) => Right(f(a))
			case Left(e) => Left(e)
		}

	// 对Right进行映射时，必须把Left的类型提升为父类型以满足`E+`的型变
	def flatMap[EE >: E, B](f: A => Either[EE, B]): Either[EE, B] =
		this match {
			case Right(a) => f(a)
			case Left(e) => Left(e)
		}
		
	// 对Right进行映射时，必须把Left的类型提升为父类型以满足`E+`的型变
	def orElse[EE >: E, AA >: A](b: => Either[EE, AA]): Either[EE, AA] =
		this match {
			case Right(a) => Right(a)
			case Left(_) => b
		}
		
	def map2[EE >: E, B, C](b: Either[EE, B])(f: (A, B) => C): Either[EE, C] = 
		for { a <- this; b1 <- b } yield f(a, b1)
	
}

有了这些定义Either也可以使用for推导：

def parseInsuranceRateQuote(age: String, 
		numberOfSpeedingTickets: String): Either[Exception, Double] = 
{
	for {
		a       <- Try(age.toInt)
		tickets <- Try(numberOfSpeedingTickets.toInt)
	} yield insuranceRateQuote(a, tickets)
}

通过Either还可以效验数据，比如检测构造函数是否有效：

sealed class Name(val value: String)
sealed class Age (val value: Int)
case   class Person(name: Name, age: Age)

def mkName(name: String): Either[String, Name] =
	if (name == "" || name == null) Left("Name is Empty.")
	else Right(new Name(name))

def mkAge(age: Int): Either[String, Age] =
	if (age < 0) Left("Age is out of range.")
	else Right(new Age(age))

def mkPerson(name: String, age: Int): Either[String, Person] =
	mkName(name).map2(mkAge(age))(Person(_, _))

严格求值与非严格求值

定义非严格示值

严格示值的正式定义：如果对一个表达式的求值一直运行或抛出错误而非返回一个定义的值 ，我们说这个表达式没有结束（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
	}

	// ... 
}

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