[toc]

2.1 高阶函数

把其他函数作为参数或返回值的函数称为高阶

高阶求和函数

// 求a到b之间的整数的和
def sumInts(a: Int, b: Int): Int = 
  if (a > b) 0 else a + sumInts(a + 1, b)

// 求a到b之间的整数的立方的和
def cube(x: Int): Int = x * x * x
def sumCubes(a: Int, b: Int): Int = 
  if (a > b) 0 else cube(a) + sumCubes(a + 1, b)

// 求a到b之间的整数的阶乘的和
def sumFactorials(a: Int, b: Int): Int = 
  if (a > b) 0 else fact(a) + sumFactorials(a + 1, b)

以上属于

的不同 值特例

提取共同的模式

def sum(f: Int => Int, a: Int, b: Int): Int = 
  if (a > b) 0
  else f(a) + sum(f, a + 1, b)

重写各类求和函数

def sumInts(a: Int, b: Int)         = sum(id, a, b)
def sumCubes(a: Int, b: Int)        = sum(cube, a, b)
def sumFactorials(a: Int, b: Int)   = sum(fact, a, b)

辅助函数

def id(x: Int): Int     = x
def cube(x: Int): Int   = x * x * x
def fact(x: Int): Int   = if (x == 0) 1 else fact(x - 1)

函数类型

类型 A => B ：
A为函数的参数类型
B为函数的返回值类型

匿名函数

def str = "abc"
println(str)

// 我们可以直接写成
println("abc")

写一个函数而不给它命名，称为匿名函数

(x: Int) => x * x * x

(x: Int)为函数参数， x * x * x 为函数体
如果编译器可以从上下文中推断参数的类型，则参数的类型可以

匿名函数是语法糖

一个匿名函数(x1: T1, ..., xn: Tn) => E 可以用以下方式表示：

// 末尾的f是可选的，新的函数名
{def f(x1: T1, ..., xn: Tn) = E; f}

匿名函数求和

使用匿名函数写出更短的求和函数：

def sumInts(a: Int, b: Int)  = sum(x => x, a, b)
def sumCubes(a: Int, b: Int) = sum(x => x * x * x, a, b)

将sum函数写成尾递归的形式：

object tailsum{
  def sum(f: Int => Int, a: Int, b: Int): Int = {
    def loop(a: Int, acc: Int): Int = {
      if (a > b) acc
      else loop(a + 1, f(a) + acc)
    }
    loop(a, 0)
  }
  sum(x => x * x, 3, 5)
}

2.2 柯里化

动机

能扔掉参数变得更短吗？

def sumInts(a: Int, b: Int)         = sum(id, a, b)
def sumCubes(a: Int, b: Int)        = sum(cube, a, b)
def sumFactorials(a: Int, b: Int)   = sum(fact, a, b)

重写sum函数如下：

/**
  * 只接收一个参数f，返回一个函数，参数函数f作用于返回函数sumF，并将结果加起来
  * @param f 参数函数
  * @return 另一个函数sumF
  */
def sum(f: Int => Int): (Int, Int) => Int = {
  def sumF(a: Int, b: Int): Int = 
    if (a > b) 0
    else f(a) + sumF(a + 1, b)
  sumF
}

定义各类求和函数：

def sumInts       = sum(x => x)
def sumCubes      = sum(x => x * x * x)
def sumFactorials = sum(fact)

这些函数可以像任何其他函数一样应用：

sumCubes(1, 10) + sumFactorials(10, 20)

可以怎样避免调用sumInts, sumCubes等中间函数？

sum(cube)(1, 10)

sum(cube)将sum作用于cube，并返回立方函数的和
因此sum(cube)等价于sumCubes
该函数下一步作用于参数(1, 10)

sum(cube)(1, 10) == (sum(cube))(1, 10)

多参数列表

下面定义的sum与之前的内嵌sumF的函数等价，但是更短

def sum(f: Int => Int)(a: Int, b: Int): Int = 
  if (a > b) 0
  else f(a) + sum(f)(a + 1, b)

一个多参数列表函数的一般定义：

def f(args_1, ..., args_n) = E

当 n > 1 时，它等价于：

// 前面为n-1个参数列表，最后一个则创建一个新的函数g
def f(args_1)...(args_n-1) = {def g(args_n) = E;g}

g是一个新的函数标识，可以更短的表示为：

def f(args_1)...(args_n-1) = (args_n => E)

多参数列表扩展

重复处理n次：

def f(args_1)...(args_n-1)(args_n) = E

它等价于：

def f = (args_1 => (args_2 => ...(args_n => E)...))

以上的函数定义方式称为 柯里化（currying）

函数类型问题
给定下面的定义，sum的类型是什么？

def sum(f: Int => Int)(a: Int, b: Int): Int = ...

答案：
(Int => Int) => (Int, Int) => Int
函数类型与右侧相关：
Int => Int => Int
等价于
Int => (Int => Int)

def product(f: Int => Int)(a: Int, b: Int): Int = {
  if a > b 1
  else f(a) * product(f)(a + 1, b)
}

练习：

1. 写一个乘积函数product计算给定区间内所有数的乘积
2. 写一个阶乘函数factorials，使用product的形式
3. 写一个通用的函数，概括sum和factorials

object curring {

  def productV1(f: Int => Int)(a: Int, b: Int): Int = {
    if (a > b) 1
    else f(a) * product(f)(a + 1, b)
  }

  def mapReduce(f: Int => Int, combine: (Int, Int) => Int, zero: Int)(a: Int, b: Int): Int = {
    if (a > b) zero
    else combine(f(a), mapReduce(f, combine, zero)(a + 1, b))
  }

  def product(f: Int => Int)(a: Int, b: Int): Int = mapReduce(f, (x, y) => x * y, 1)(a, b)
  product(x => x)(1, 4)

  def fact(n: Int) = product(x => x)(1, n)
  fact(5)
}

2.3 例子：找到固定点（Finding Fixed Points)

如果 f(x) = x ，则称数字x是函数f的固定点
对于一些函数f，我们可以从一个初始估计值开始，循环的将f作用于估计值：
x, f(x), f(f(x)), f(f(f(x))), ...
直到值不再变化（或变化足够小）

回到平方根

平方根函数：
sqrt(x) = y， 其中 y * y = x
两侧除以y：
sqrt(x) = y， 其中 y = x / y
因此，sqrt(x)是函数(y => x / y)的一个固定点

object FindingFixedPoints {

  val tolerance = 0.0001
  def isCloseEnough(x: Double, y: Double) =
    math.abs((x - y) / x) / x < tolerance

  def fixedPoint(f: Double => Double)(firstGuess: Double) = {
    def iterate(guess: Double): Double = {
      val next = f(guess)
      if (isCloseEnough(guess, next)) next
      else iterate(next)
    }
    iterate(firstGuess)
  }
  fixedPoint(x =>1 + x / 2)(1)

  // 消除振荡
  def averageDamp(f: Double => Double)(x: Double) = (x + f(x)) / 2

  def sqrt(x: Double) =
    fixedPoint(averageDamp(y => x / y))(1)
    
  sqrt(2)    // 1.4142135623746899
}

2.4 Scala语法总结

语言元素

扩展巴科斯-诺尔范式（Extended Backus-Naur form - EBNF）中的上下文无关语法：

| 表示二选一的
[...] 可选的(0 or 1)
{...} 重复的(0 or more)

之前遇到的类型

Type         = SimpleType | FunctionType
FunctionType = SimpleType '=>' Type | '(' [Types] ')' '=>' Type
SimpleType   = Identifier
Types        = Type {',' Type}

类型可以是：

表达式

Expr         = InfixExpr | FunctionExpr | if '(' Expr ')' else Expr
InfixExpr    = PrefixExpr | InfixExpr Operator InfixExpr
Operator     = ident
PrefixExpr   = ['+' | '-' | '!' | '~'] SimpleExpr
SimpleExpr   = ident | literal | SimpleExpr '.' ident | Block
FunctionExpr = Bindings '=>' Expr
Bindings     = ident [':' SimpleType] | '(' [Binding {',' Binding}] ')'
Binding      = ident [':' Type]
Block        = '{' {Def ';'} '}'

表达式可以是：

定义

Def        = FunDef | ValDef
FunDef     = def ident { '(' [Parameters] ')' } [':' Type] '=' Expr
ValDef     = val ident [':' Type] '=' Expr
Parameter  = ident ':' ['=>'] Type
Parameters = Parameter {',' Parameter}

定义可以是：

参数可以是：

2.5 函数和数据

类(Classes)

Scala中定义一个类：

// 有理数类
class Rational(x: Int, y: Int) {
  def numer = x   // 分子
  def denom = y    // 分母
}

这个定义产生两个实体：

• 一个新的类型，叫做Rational
• 一个Rational构造器，用来创建这个类型的元素

Scala将类型名和值保存在不同的命名空间，这样两个Rational的定义就不会起冲突

对象 (Objects)

类型在编程语言中本质上是值的集合，属于class类型的值（元素）称为objects

通过在类的构造器前加上操作符new来创建一个对象

new Rational(1, 2)

Rational中有numer和denom两个成员

有理数算术

RationalArithmetic.png

实现：

def addRational(r: Rational, s: Rational): Rational = 
  new Rational(
    r.numer * s.denom + s.numer * r.denom,
    r.denom * s.denom)

def makeString(r: Rational) =
  r.numer + "/" + r.denom

makeString(addRational(new Rational(1, 2), new Rational(2, 3)))
>> 7/6

方法(Methods)

可以

object rationals {
  val x = new Rational(1, 3)
  val y = new Rational(5, 7)
  val z = new Rational(2, 4)
  x.numer
  x.denom
  x.sub(y).sub(z)
}

class Rational(x: Int, y: Int) {
  def numer = x
  def denom = y

  def add(that: Rational) =
    new Rational(
      numer * that.denom + that.numer * denom,
      denom * that.denom)

  def sub(that: Rational) = add(that.neg)

  def neg: Rational = new Rational(-numer, denom)

  override def toString = numer + "/" + denom
}

构造器

在Scala中，一个类会隐式的引入一个构造器，这个构造器称为这个类的私有构造器。私有构造器获取类的参数，并执行类体中的所有语句

class Rational(x: Int, y: Int) {
  def this(x: Int) = this(x, 1)   // 调用私有构造器
  ...
}

new Rational(2)  // Rational = 2/1

2.6 求值和操作符

Infix Notation

两种操作方式等价