This the multi-page printable view of this section. Click here to print.

Return to the regular view of this page.

Scala 函数式

1: CH00-精要
2: CH01-定义
3: CH02-函数
4: CH03-数据
5: CH04-异常

1 - CH00-精要

函数

一个函数是一个从“领域”到“代码域”的映射。函数将领域中的每个元素与代码域中的对应元素进行联结。在 Scala 中，领域和代码域都可以表示为type(类型)。

val square: Int => Int = x => x * x
square(2) 	// 4

高阶函数

高阶函数是接收一个函数作为参数或返回一个函数作为结果的函数。

trait List[A] {
  def filter(f: A => Boolean): List[A]
}

这个例子中，函数filter接收一个类型为A => Boolean的函数作为参数。

组合子

函数组合子是同时接收、返回函数的高阶函数。

type Conf[A] = ConfigReader => A
def string(name:String):Conf[String] = _.readString(name)
def both(left:Conf[A], right:Conf[B]):Conf[(A, B)] = c => (left(c), right(c))

函数both即为一个接收函数并返回函数的高阶函数。

多态函数

多态函数通常拥有一个或多个类型参数。Scala 本身对多态函数没有支持，但是可以通过特质的多态方法来实现。构造多态函数的特质通常拥有apply方法，因此，可以像普通的函数应用语法一样使用：

case object identity {
  def apply[T](value:T):T = value
}
identity(3)		// 3
indentity("3")	// "3"

这样，通过apply方法的便利，就可以实现多态函数。

类型

一个类型是一组值的运行时描述。比如Int表示从-2147483648到2147483647这样的一组整数集。值都拥有类型，或者说，每个值都表示一组值的一个成员。

2: Int

例子中，2是Int集合的一个成员，也即，2的类型为Int。

代数数据类型(ADT)

一个 ADT 是由产品和类型自合而成的类型。

乘积类型(product)

乘积类型是由两个或多个类型的笛卡尔积组合构造而成的。

type Point2D = (Int, Int)

例子中，一个二维点是一个数字与另一个数字的积。即每个该类型的值都有一个 x 轴坐标和 y 轴坐标。

样例类

在 Scala 中，样例类是更符合语言习惯的乘积类型表示。

case class Person(name:String, age:Int)

总和类型(sum)

总和类型通过两个或多个类型的不相交形式来定义。

type RequestResponse = Either[Error, HttpResponse]

例子中，定义的类型RequestResponse是Error和HttpResponse的总和构成，一个RequestResponse类型的值要么是一个 error，要么是一个 HTTP 响应。

密闭特质

在 Scala 中，密闭特质是更符合语言习惯的总和类型表示。

sealed trait AddressType
case object Home extends AddressType
case object Business extends AddressType

例子中，一个AddressType要么是一个Home，要么是一个Buiness，而不能同时是两者。

子类型

如果A是B的子集，A即为B的子类型。在 Scala 中，A必须继承自B。编译器允许在任何需要的地方使用子类型。

sealed trait Shape{
  def width:Int
  def height:Int
}
case class Rectangle(corner:Point2D, width:Int, height:Int) extends Shape

超类型

如果B是A的子集，A即为B的超类型，B必须继承自A。编译器支持无论在何处定义子类型，均可以使用超类型。

同样还是上面的例子，Shape即为Rectangle的超类。

Universals

一个通用(universally)量化类型定义了一个“由一些任意类型参数化的类型”的类别。在 Scala 中，类型构造器(比如特质)和方法必须是通用量化类型，尽管方法并不拥有一个类型，它只是类型的一部分。

类型构造器

一个类型构造器是一个通用量化类型，用于构造类型。

sealed trait List[A]
case class Nil[A]() extends List[A]
case class Cons[A](head: A, List[A]) extends List[A]

例子中，List是一个类型构造器，定义了一组List-类似的类型。因此可以认为，List是针对类型A的通用类型量化。

高阶类型

类型级别函数(Type-Level)

类型构造器可以看做一个类型级别函数，它接收类型并返回类型。这种解释对于理解高阶类型很有用。

比如，List是一个接收类型A并返回类型List[A]的类型级别函数。

类别(Kind)

类别可以认为是“类型的类型”。

*：类型的类别，所有类型的集合。
* => *：类型级别函数的类别(接收一个类型，返回一个类型)。
[*, *] => *：接收两个类型并返回一个类型的类型级别函数的类别。比如类型构造器Either的类别是[*, *] => *，Scala 语法表示成_[_, _]。

可以与函数的类型进行对比：A => B，A => B => C

高阶类别(Higher-Order Kinds)

就像函数能够是高阶函数一样，类型构造器也可以是高阶的。Scala 中使用下划线编码(encode)高阶类型构造器。trait CollectionModule[Collection[_]]表示CollectionModule的类型构造器需要提供一个* -> *类别的类型构造器，比如List。

(* => *) => *：类型构造器的类别，它接收一个* => * 类别的类型构造器。比如：trait Functor[F[_]] {...}或trait Monad[F[_]] {...}。

Existentials

一个“存在量化类型”定义一个基于一些明确但又未知的类型的类型。“存在判断的类型”用于隐藏一些并非全局相关的类型信息。

trait ListMap[A]{
  type B
  val list: List[B]
  val mapf: B => A
  def run: List[A] = list.map(mapf)
}

例子中，类型ListMap[A]#B是一些明确类型，但是有不能知道其真正类型，它可能是任何类型。

Skolemization

每个“存在判断的类型”都可以被编码为一个通用(universal)类型。这个过程称为Skolemization。

case class ListMap[B, A](list:List[B], mapf: B => A)

trait ListMapInspector[A,Z] {
  def apply[B](value: ListMap[B, A]):Z
}

case class AnyListMap[A] {
  def apply[Z](value:ListMapInspector[A, Z]): Z
}

例子中，除了我们直接使用ListMap，还可以使用AnyListMap，仅当能够为B处理任何类型参数时允许我们对ListMap进行检查。

Type Lambdas

函数可以通过使用下划线操作符编程“偏应用型(partially apply)”。比如，zip(a, _)。一个类型匿名函数是偏应用“高阶类别”类型的一种方式，使用较少的类型参数来生成一个新的类型构造器。

类型匿名函数之于类型构造器，相当于匿名函数之于函数。一个是类型、值的表达式，一个声明：

({type λ[α] = Either[String, α]})#λ

例子中，Either通过偏应用一个String作为第一个类型参数。

较多场景中，会使用**类型别名(type aliase)**替代类型匿名函数，比如：type EitherString[A] = Either[String, A]。

类别投影器(Projector)

类别投影器是一个常用的 Scala 编译器插件，提供了更易用的语法来创建类型匿名函数。比如，({type λ[α] = Either[String, α]})#λ可以表示为Either[String, ?]这样的语法。另外有更多语法来创建更复杂的类型匿名函数。

https://github.com/non/kind-projector

类型类

一个类型类是对类型和定义在该类上操作的收集。很多类型类会定义一些规则需要实现来遵守。

trait ShowRead[A] {
  def show(v: A): String
  def read(v: String): Either[String, A]
}

object ShowRead {
  def apply[A](implicit v: ShowRead[A]): ShowRead[A] = v
}

例子中，类型类ShowRead[A]定义了通过渲染字符串来显示类型A，并通过读取字符串来读取它，或是生成一个错误消息。

Right Identity
```
read(show(v)) == Right(v)
```

Left Partial Identity

read(v).map(show(_)).fold(_ => true, _ == v)

实例

一个类型类的实例就是通过提供一组类型来定义一个该类型类的实现。一般这些事例会被标记为imolicit，以便编译器能够自动为需要的函数提供这些实现。

implicit val ShowReadString:ShowRead[String] = new ShowRead[String] {
  def show(v:String):String = v
  def read(v:String): Either[String, String] = Right(v)
}

语法

便利的语法，或称为扩展方法，添加给类型以便这些类型类更加易用：

implicit class ShowOps[A:ShowRead](self:A){
  def show:String = ShowRead[A].show(self)
}
implicit class ReadOps(self:String){
  def read[A:ShowRead]:Either[String, A] = ShowRead[A].read(self)
}

函数式模式

Option、Either、Validation

这些类型均用来表示可选性和偏应用性：

seald trait Maybe[A]
final case class Just[A](value:A) extends Maybe[A]
final case class Empty[A]() extends Maybe[A]

sealed trait \/[A, B]
final case class -\/[A, B](value:A) extends \/[A, B]
fianl case class \/-[A, B](value:B) extends \/[A, B]

type Either[A, B] = A \/ B

sealed trait Validation[A, B]
final case class Failure[A, B](value:A) extends Validation[A, B]
final case class Success[A, B](value:B) extends Validation[A, B]

半群、幺半群(Semigroup, Monoid)

半群支持将两个相同类型的东西组合成另一个新的相同类型的东西。比如，加法操作构成一个基于整数的半群。幺半群怎加一个额外的拥有“零”元素的属性，比如添加给一个值而不改变该值。

trait Semigroup[A]

未完。。。

https://wiki.scala-lang.org/display/SW/Parser+Combinators–Getting+Started

2 - CH01-定义

介绍

函数式编程，只是用纯函数来构造程序，即函数是没有副作用的。

函数的副作用大致包括：

修改一个变量
直接修改数据结构
设置一个对象的成员
抛出一个异常或以一个错误停止
打印到终端或者接收用户的输入
读取或写入一个文件
在屏幕上绘图
…

函数式编程的益处

副作用函数的实例

class Cafe{
  def buyCoffee(cc:CreditCard):Coffee = {
  	val cup = new Coffee()
  	cc.charge(cup.price)		// 副作用，对信用卡进行扣费
  	cup
  }
}

扣费过程涉及与整个交易系统的交互，而这个方法的主要用途是为了得到一杯咖啡，因此，扣费动作在获取咖啡的过程中额外完成了，即副作用。

但是如果要测试这段程序，我们并不真的需要与交易系统进行交互，或者将交易信息进行持久。同时信用卡本身也不应该知道交易的细节，我们可以传递一个Payments对象给buyCoffe方法，让CreditCard忽略掉交易的细节，整个交易过程由Payments对象来完成：

class Cafe {
  def buyCoffe(cc:CreditCard, p: Payments) = {
  	val cup = new Coffe()
    p.charge(cc, cup.price)		// 副作用，有交易对象来完成扣费
    cup
  }
}

现在可以使用 mock 来对交易细节进行测试。但是真个程序很难被复用，比如我们要订购 12 杯咖啡。

去除副作用

在上面的例子中，我们可以在购买咖啡的过程中同时返回咖啡和对应的费用，而根据费用进行的交易过程则后续进行处理，这样，这个程序就不再存在副作用：

def buyCoffe(cc:CreditCard):(Coffe, Change) = {
  val cup = new Cup()
  (cup, Charge(cc, cup.price))
}

这样通过将费用的创建与执行分离，购买咖啡的过程就不再有副作用，而真正的扣费可以在后续的事务中进行。

现在我们对相同信用卡的计费进行合并，以便支持同时购买多杯咖啡：

case class Charge(cc:CreditCard, amount: Double){
  def combine(ohter:Charge): Charge = {
    if (cc == other.cc) Charge(cc, amount + other.amount)
    else throw new Exception("Can't combine charges to different cards.")
  }
}

然后实现buyCoffes来购买多杯咖啡，一次返回对应数量的咖啡和一个合并后的计费值：

def buyCoffes(cc:CreditCard, n:Int): (List[Coffe], Charge) = {
  val purchases:List[(Coffe, Charge)] = List.fill(n)(buyCoffe(cc))
  val (coffes, charges) = purchases.unzip
  (coffes, chargs.reduce((c1,c2) => c1.combine(c2)))
}

如果需要将不同信用卡的不同消费记录合并成一个计费列表，即将相同的信用卡计费合并：

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

如何消除副作用？
通过把副作用推到程序的最外层，来转换带有副作用的函数。对于很多必须的副作用都存在对应的函数式实现，如果没有对应的实现，也可以通过找到一种方式来构造代码，让副作用发生但不可见。

什么是纯函数

纯函数是没有副作用的，更易推理。

一个函数在执行过程中，除了根据给定的参数给出运算结果之外没有任何其他影响，即为无副作用。

引用透明：对于一个函数，无论何时调用，相同的参数都会返回一致的结果。同样也适用于表达式。

任何程序中符合引用透明的表达式都可以由它的结果替代，而不会改变程序的含义。

纯函数：当调用一个函数时，传入的参数是引用透明的，并且函数调用也是引用透明的，那么他就是一个纯函数。

引用透明与纯粹度
对于程序 p，如果它包含的表达式 e 满足引用透明，所有的 e 都能替换为它的计算结果而不会改变程序 p 的含义。假设存在一个函数 f，若表达式 f(x) 对所有引用透明的表达式 x 也是引用透明的，那么 f 是一个纯函数。

引用透明、纯粹度及替代模型

引用透明要求函数不论进行了何种操作都可以用它的返回值来代替。

比如一开始的咖啡例子：

def buyCoffee(cc:CreditCard):Coffee = {
  	val cup = new Coffee()
  	cc.charge(cup.price)		// 副作用，对信用卡进行扣费
  	cup
  }

它的返回值为cup，实际上就是new Coffe()。对于任何一个函数p(buyCoffee(cc:CreditCard))与p(new Coffe())显然不能进行替换，因为buyCoffee除了返回一杯咖啡，还进行了交易过程。

引用透明的限制使得推导一个程序的求值变得简单，称为替代模型。如果表达式是引用透明的，可以想象计算过程就像是在解代数方程。展开表达式的每一部分，使用指示对象代替变量，然后归约到最简单的形式。在这一过程中，每一项都可以被等价的值替代，计算的过程就像是被一个又一个等价的值替代的过程。引用透明使得程序具备了等式推理的能力。

3 - CH02-函数

高阶函数-把函数传递给函数

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

循环调用

使用循环方式实现阶乘：

def factirial(n:Int): Int = {
  def go(n:Int, acc:Int):Int = {	// 内部函数，跟一个函数内的变量含义相同
    if (n <= 0) acc
    else go(n-1, n * acc)
  }
  go(n, 1)
}

想不通过修改一个循环变量而实现循环功能，可以借助递归函数。这样的递归函数一般没命名为 go 或 loop。

上面的例子中，内部函数go实现循环，接收下一个n和和累积值acc。要退出循环时，返回一个不继续递归的值，即n <= 0。

编译器会检测到这种自递归，只要递归调用发生在尾部，即递归调用后面没有其他的调用，编译器会优化成类似while循环的字节码。

尾调用
指调用者在一个递归调用之后不做其他事，只是返回这个调用结果。
比如else go(n-1, n * acc)部分，是直接返回了go的递归调用，没有再做其他计算。如果是1 + go(n-1, n * acc)，则不再是尾调用，因为又进行了计算。
如果递归调用在尾部位置，则会自动编译为循环迭代，即不会每次进行栈的操作。可以通过@annotation.tailrec告诉编译器当没有成功编译成循环迭代时发出警告。

高阶函数

def formatResult(name:String, n:Int, f: Int => Int) = {
  val msg = "The %s of %d is %d."
  msg.format(name, n, f(n))
}

这里的参数f，其类型为Int => Int，表示接受一个整数并返回一个整数的函数。

因为高阶函数一般不能通过函数名来准确表示函数的功能，因此使用较短的函数命名，比如 g、h、f 等。

多态函数-基于类型的抽象

这里的多态跟继承中所说的“父类-子类继承”不同，这里是指类型的多态。

之前见到的函数都是单态的，因为函数只操作一种数据类型。适用于多种数据类型的函数，称为多态函数，或泛型函数。

多态函数的构建，一般是发现多个单态函数有相似的结构，这时，可以封装为一个多态函数。

实例

比如一个函数，返回数组中第一个匹配到 key 的索引，否则返回 -1:

def findFirst(ss:Array[String], key:String):Int = {
  @annotatin.tailrec
  def loop(n:Int):Int = {
    if (n >= ss.length) -1		// 到达数组尾部仍未匹配到 key，返回 -1
    else if (ss(n) == key) n	// 匹配到 key，返回索引
    else loop(n + 1)			// 递归调用
  }
}

这是从 String 数组中匹配，如果是从 Int 数组查找匹配，也是类似的结构，因此我们就可以将它改写为一个从 A 类型数组中查找对应索引的函数：

def findFirst[A](as:Array[A], p:A => Boolean):Int = {
  @annotatin.tailrec
  def loop(n:Int):Int = {
    if (n >= as.length) -1
    else if p(as(n)) n			// 使用传入的 测试函数 p 对当前元素进行判断
    else loop(n + 1)
  }
}

函数名后跟的是类型参数，由中括号包围，多个参数使用逗号分隔，一般使用单个大写字母表示一个类型参数。这些类型参数作为类型变量，可以在其他类型签名中引用，比如上面的as参数类型。

向高阶函数传入匿名函数

在调用高阶函数时，并没有必要提前定义一个有名函数然后再传入，可以在调用时直接定义一个函数值作为高阶函数的参数，这被称为匿名函数或函数字面量。比如：

findFirst(Array(1,2,3), (x:Int) => x == 9)

(x:Int) => x == 9即为一个匿名函数，或称为函数字面量。

匿名函数中，=>左边为该函数的参数列表，右边则会函数体。如果 Scala 可以推断参数的类型，则可以省略掉。

函数也是值
当定义一个函数字面量时，实际上是定义了一个包含一个apply方法的 Scala 对象。而当一个对象拥有apply方法，则可以把该对象当做方法一样调用。
比如我们定义一个函数字面量(a, b) => a < b，它事实上是创建函数对象的语法糖：
val lessThan = new Function2[Int, Int, Boolean] {
  def apply(a:Int, b:Int) = a < b
}
lessThan的类型为Function2[Int, Int, Boolean]，通常会写成(a, b) => Boolean。Function2特质拥有一个apply方法，在调用lessThan(10, 20)时实际上是对apply方法调用的语法糖：
lessThan.apply(10, 20) 		// true
这些类似Function2的特质，实际是由 Scala 标准库提供的普通特质，比如Function1、Funciton3等等。其中的数字是指接收的参数个数。
因为这些函数在 Scala 中是普通对象，因此他们也是一等值。

通过类型实现多态

在实现多态函数时，各种可能的实现方式明显比普通函数减少了。比如针对类型 A 的多态函数，唯一能够对 A 进行操作的方式是传入一个函数作为参数，通过这个传入的函数来操作 A。

比如一个例子，这个函数签名表示它只有一种实现方式。它是一个执行部分应用的高阶函数。函数partial1接收一个值和一个带有两个参数的函数，并返回一个带有一个参数的函数。

部分应用函数，表示函数被应用的参数并不是它需要的完整参数，即只提供了参数列表中的部分参数。

def partial1[A, B, C](a:A, f: (A, B) => c): B => C

我们该如何实现这个高阶函数呢。根据它的返回值类型，是接收一个类型 B 的参数并返回一个类型 C 的值的函数：

def partial1[A, B, C](a:A, f: (A, B) => c): B => C = {
  (b: B) => ???			// 根据返回值类型 B => C ，定义一个该返回值类型的函数
}

现在如何来实现方法体部分呢，根据声明，这个函数必须返回一个 C 类型的值。而在partial1的参数列表中，正好有一个函数f能够返回一个 C 类型的值。除此之外，我们没有其他方式来实现该函数体。因此：

def partial1[A, B, C](a:A, f: (A, B) => c): B => C = {
  (b: B) => f(a, b)		// 调用参数中的函数，实现符合返回类型的函数体
}

这也就是部分应用函数的实现过程，一个函数，接收两个参数，返回一个值。当我们只提供一个参数值时，在这个例子中，是a，这时会得到一个 “接收一个参数并返回一个值的” 函数。然后在提供原始函数需要的第二个参数，即b，就能得到最终的结果，即c。

4 - CH03-数据

定义函数式数据结构

函数式数据结构只能被纯函数操作，纯函数一定不能修改原始数据或产生副作用。因此，函数式数据结构被定义为不可变的。

比如单链表的实现：

sealed trait List[+A]
case object Nil extends List[Nothing]
case class Cons[+A](head:A, tail: List[A]) extends List[A]	// 递归引用自身类型

object List{
  def sum(ints: List[Int]):Int = ints match {
    case Nil => 0
    case Cons(x, xs) => x + sum(xs)
  }
  
  def product(ds:List[Double]): Double = ds match {
    case Nil => 1.0
    case Cons(0.0, _) => 0.0
    case Cons(x, xs) => x * product(xs)
  }
  
  def apply(as: A*): List[A] = 
    if (as.isEmpty) Nil
    else Cons(as.head, apply(as.tail:_*))
}

List[+A]表示它是一个泛型数据类型。同时拥有两种实现，或者说是两种构造器，每种都由case关键字定义，表示它的两种可能的形式。如果List为空，则用Nil表示，如果非空，则用构造器Cons表示。一个非空列表由初始元素head和后续紧跟的也是List结构的tail构成，并且，这个tail可能为空，即他可能是一个Nil。

这就是一个典型的数据构造器声明，为我们提供了一个函数来构造该类型数据的不同形式：

val ex1:List[Double] = Nil
val ex2:List[Int] = Cons(1, Nil)
val ex3:List[String] = Cons("a", Cons("b", Nil))

模式匹配

在List的伴生对象中定义了两个方法，sum和product，他们都使用了模式匹配。同时他们都是以递归的方式定义，这在编写操作递归数据类型的函数时很常见。

模式匹配类似于switch，他可以侵入到表达式的数据结构内部，对这个结构进行检验和提取子表达式。符号=>左边为模式，右边为结果。

如果将模式中的变量分配给目标子表达式，使得它在结构上与目标一致，模式与目标就是一致的。匹配上的话，结果表达式就可以访问这些模式中定义的局部变量。

函数式数据结构的数据共享

当一个新的元素添加到已有的列表时返回一个新的列表。既然列表是不可变的，并不需要真的去复制一份原有列表，而是直接去复用它，比如向原有的列表 xs 添加一个数字 1，返回一个Cons(1, xs)。

同样，删除列表的第一个元素，比如myList = Cons(x, xs)，这时只需要返回尾部的xs。并没有真的删除任何元素。原始的myList依然可用，不会受到任何影响。

这被称为数据共享。

“函数式数据结构是持久的”，是指：已存在的引用不会因数据结构的操作而改变。

数据共享的效率

？？？

高阶函数的类型推导

当向一个高阶函数传递函数类型的参数时，需要标识该函数的类型。比如高阶函数dropWhile：

def dropWhile[A](l: List[A], f: A => Boolean): List[A]

当调用该函数时，参数函数f必须制定它的参数类型：

val xs:List[Int] = List(1,2,3,4,5)
val ex1 = dropWhile(xs, (x:Int) => x < 4)	// (x:Int) 指定参数类型为 Int

因为dropWhile的两个参数都使用类型参数A，前一个参数l的类型为Int，因此第二个参数的类型也必须是Int。

当函数定义包含多个参数组时，参数组里的类型信息从左到右进行传递。

因此我们把dropWhile的参数列表分开，让他成为一个柯里化函数：

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

现在可以这样调用dropWhile，dropWhile(xs)(x => x < 4)。当调用dropWhile(xs)时他会返回一个函数，这时已经确定第一个参数的类型为A，因此第二个参数时就不再需要进行类型标注了，它的类型只能为A。

通过将函数参数分组排序成多个参数列表(将函数柯里化)，来最大化的利用类型推导。

基于 List 的递归并泛化为高阶函数

回顾前面的sum和product函数：

def sum(ints: List[Int]): Int = ints match{
  case Nil => 0
  case Cons(x, xs) => x + sum(xs)
}

def product(ds:List[Double]): Double = ds match{
  case Nil => 1.0
  case Cons(x, xs) => x * product(xs)
}

这两个函数的结构类似，不同在于他们操作的数据类型(Int/Double)、Nil时返回的值(0/1.0)、以及对结果的组合操作(+/*)。

对于这两个函数的抽象，首先将Int/Double泛化为类型参数A，而Nil的返回值，可以作为一个函数参数由客户端提供。

如果一个子表达式引用了任何局部变量，把子表达式放入一个接收这些局部变量作为参数的函数。

比如上面这两个函数中的x + sum(xs)和x * product(xs)部分，都是对局部变量的引用，因此可以抽象为函数f: (A, B) => B。最终，把上面两个函数改写成下面的方式：

def foldRight[A, B](as: List[A], z: B)(f: (A, B) => B): B = 
  as match {
    case Nil => z
    case Cons(x, xs) => f(x, foldRight(xs, z)(f))
  }

def sum2(ns: List[Int]) = foldRight(ns, 0)((x, y) => x + y)
def product2(ns: List[Double]) = foldRight(ns, 1.0)(_ * _)

这里需要注意的是，与之前遇到的泛化不同，该函数的最终计算结果类型与传入的列表类型并不相同，如函数签名foldRight[A, B](as: List[A], z: B)(f: (A, B) => B): B所示，它的最终计算结果与传入的参数z类型一致，即类型B。

因为整个函数的计算过程就是对列表进行循环，一直遍历到列表末尾，这个过程中不断压栈，直至列表的末尾，即Nil。而遇到Nil时返回的值为传入的参数z，套用传入的函数f，也就是通过传入列表的最后一个元素(Nil 之前的元素)与z来调用函数f，得到栈顶的值。然后依次出栈，完成整个计算过程。

可以函数的调用使用传入的函数f进行替换：

Cons(1, Cons(2, Nil))
f	(1, f   (2, z  ))

foldRight函数为 Scala 标准库中List的内置函数，上面的替换过程也就是它的计算过程。

比如我们调用sum2(List(1,2,3), 0)((x, y) => x + y)，跟踪其运算过程：

foldRight(Cons(1, Cons(2, Cons(3, Nil))), 0)((x, y) => x + y)
1 + foldRight(Cons(2, Cons(3, Nil)), 0)((x, y) => x + y)
1 + (2 + foldRight(Cons(3, Nil), 0)((x, y) => x + y))
1 + (2 + (3 + foldRight(Nil, 0)((x, y) => x + y)))) // Nil, 终止递归，替换为(0 + 0)
1 + (2 + (3 + (0))
6

树

List 是代数数据类型(ADT)的一种，有些场景或称为抽象数据类型。

ADT 是由一个或多个数据构造器所定义的数据类型，每个构造器可以包含零个或多个参数。数据构造器通过累加(sum)或联合(union)构成数据类型，而每个数据构造器又是其参数的乘积(product)。因此称为代数数据类型。

ADT 用于构造其他数据结构。定义一个二叉树数据结构：

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]

5 - CH04-异常

抛出异常会产生副作用，在函数式解决方案中，以值的方式返回错误更安全，符合引用透明，并且可以通过高阶函数保存异常的优点 - 统一错误处理逻辑。核心思想就是使用普票值来表现异常。

异常的优点与劣势

一个抛出异常的例子：

def failingFn(i: Int): Int = {
  val y:Int = throw new Exception("fail!") 	// 抛出异常
  try{
    val x = 42 + 5
    x + y
  } catch {
    case e:Exception => 43
  }
}

调用该函数会抛出预期的异常，为了证明异常会破坏引用透明，我们可以将y进行替换：

def failingFn2(i: Int) = {
  try{
    val x = 42 + 5
    x + (throw new Exception("fail!"): Int)	// 抛出异常的表达式可以声明为任何类型
  } catch {
    case e: Exception => 43
  }
}

运行结果会得到 43 而不是像替换前一样排除预期的异常，因此，异常并不是引用透明的。

引用透明的表达式不依赖上下文，可以本地推导，而那些非引用透明的表达式是依赖上下文的，并且需要全局推导。比如把42 + 5这个表达式嵌入到一个更大的表达式中，他不会受这个更大的表达式的影响，即对更大的表达式产生依赖，它永远等于 47。但是把throw new...嵌入到一个更大的表达式，比如嵌入到一个try/catch结构中，它的值取决于catch部分的处理，因此对更大的表达式产生了依赖。

异常的问题：

异常破坏了引用透明并且引入了上下文依赖。
异常不是类型安全的。函数failing，Int => Int并不会告诉我们会发生什么样的异常。因为没有受检异常，直到运行时才会发现异常。

我们希望其他选择能够排除异常的这些缺点，但是又不想失去异常最主要的好处：整合集中的错误处理逻辑，而不是在整个代码库发布这个逻辑。

异常的其他选择

比如一个计算列表平均值的函数：

def mean(xs:Seq[Double]): Double = 
  if (xs.isEmpty) throw new ArithmeticException("mean of empty list!")
  else xs.sum / xs.length

这是一个典型的偏函数，他对一些输入没有做定义。如果一个函数对那些非隐式的输入类型做了一些假设，那它就是一个典型的偏函数。

除了选择抛出异常，还有其他的选择。

第一种是返回某个伪造的 Double 类型的值。比如为空时返回Double.NaN，或者其他报警值，或者null。但是以下理由使我们放弃这种方案：

它允许错误无声的传播，如果忘了对这样的值进行检查也不会得到警告，会使后面的代码出错。
使用显式的if来检查是否得到了正确的结果会导致大量的模板代码，特别是调用多个函数时。
不适用与多态代码。比如一个查找最大值的泛型函数def max[A](xs:List[A])，当传入为空时无法发明一个 A 类型的值。也不能是null，因为null只对非基础类型有效，但是这里的 A 可能是Int或Double。
需要一个特定的策略或调用约定 - 告诉调用者如何合理的使用mean函数。这导致它不能传递给高阶函数，因为高阶函数对待所有参数都是一致的。

第二种是强迫调用者提供一个参数告诉我们该如何处理。比如：

def mean(xs:Seq[Double], onEmpty: Double): Double = 
  if (xs.isEmpty) onEmpty
  else xs.sum / xs.length

这使mean函数称为一个完全函数。调用者必须知道如何处理未定义的情况。

Option 数据类型

解决方案是在返回值类型明确表示该函数并不总是有结果。

sealed trait Option[+A]
case class Some[+A](get:A) extends Option[A]
case object None extends Option[A]

Option是一个最多只包含一个元素的List。

基础 Option 函数

trait Option[+A] {
  def map[B](f: A => B): Option[B]					// 如果 Option 不为 None，对其应用 f
  def flatMap[B](f: A => Option[B]): Option[B] 		// 如果 Option 不为 None，对其应用 f，可能会失败
  def getOrElse[B >: A](default: B): B				// 默认值类型 B 必须是 A 的父类
  def orElse[B >: A](ob: => Option[B]): Option[B]	// 不对 ob 求值，除非需要
  def filter(f: A => Boolean): Option[A] 			// 如果值不满足，转换 Some 为 None
}

基础函数使用场景

???

Option 组合、提升、面向异常的 API 封装

可能会认为，一旦开始使用Option，整个库都会受影响，因为一些方法必须改变为接收或返回Option。但是，我们可以把一个普通函数**提升(lift)**为一个对Option操作的函数。

比如，map函数支持我们用一个类型为A => B的函数来操作一个Option。从另一个角度看，map可以把一个A => B的函数转换为Option[A] => Option[B]类型的函数：

def lift[A, B](f: A => B): Option[A] => Option[B] = _ map f

现在，可以把普通的abs函数转换为处理Option的函数：

val absOpt:Option[Double] => Option[Double] = lift(math.abs)

而Try函数是一个通用目的的函数，用于将一个基于异常的 API 转换成一个面向Option的 API。

Either 数据类型

Option只能用来表示可能不存在的值，并不能表示异常条件下发生了什么错误。如果除了需要获取异常时可能的值，还需要知道异常时的错误信息，可以使用Either：

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

Either在两种情况都有值，它的值只能是两种情况中的一种，称他是两个类型的互斥并集。一般使用Left表示失败，而Right表示成功。

使用Either改写前面的mean函数：

def mean(xs:List[Double]): Either[String, Double] = 
  if (xs.isEmpty) Left("mean of empty list!")
  else Right(xs.sum / xs.length)

或者在Left中包含处理的异常以获取详细的调用栈信息：

def safeDiv(x:Int, y:Int):Either[Exception, Int] = 
  try Right(x / y)
  catch {case e:Exception => Left(e)}