说一下函数式编程的一些基本概念，比如高阶函数，函数柯里化，闭包，尾递归等。

高阶函数 (Higher-order functions)

高阶函数是一种以函数作为参数，或者返回值是一个函数的函数。比如map，reduce，filter等以函数作为参数的函数，在Spark里我们通常称他们为算子。

下面我们用scala实现map函数，从中也可以看出scala的List :: 符号的威力巨大。

 
def map[T](f: T => T, list: List[T]): List[T] = list match {
  case Nil => Nil
  case head :: tail => f(head) :: map(f, tail)
}

def double(i: Int): Int = i * 2

val doubles = map(double, List.range(0, 10))  
// result:  List(0, 2, 4, 6, 8, 10, 12, 14, 16, 18)

类似的，我们再实现fitler和reduce函数：

 
def filter[T](f: T => Boolean, list: List[T]): List[T] = list match {
  case Nil => Nil
  case head :: tail =>
    if (f(head)) head :: filter(f, tail)
    else filter(f, tail)
}

@tailrec  // 尾递归标签
def reduce[T](f: (T, T) => T, list: List[T]): T = {
  assert(list.nonEmpty, "Error: Nil list is not allowed for reduce")

  list match {
    case head :: Nil => head
    case h1 :: h2 :: tail => reduce(f, f(h1, h2) :: tail)
  }
}

返回一个函数的函数理解起来稍微复杂一些，我们先用一个简单的示例。下面的next是这样一个函数，它会返回一个给一个数加1的函数。

 
def next(): Int => Int = {
  (x: Int) => x + 1
}

val nextIntFunc = next()
val nextInt = nextIntFunc(10) // 11

// or you can use it directly
val nextValue = next()(20)  // 21

下面是一个稍微复杂一些的例子，生成一个把函数f应用n次的函数：

 
def applyFuncNTimes(f: Int => Int, n: Int): Int => Int = {
  if (n <= 0) {
    (x: Int) => x
  } else {
    (x: Int) => f(applyFuncNTimes(f, n-1)(x))
  }
}

val doubleItThreeTimes = applyFuncNTimes(double, 3)
val double_9_3times = doubleItThreeTimes(9)   // 9 * 2 * 2 * 2 = 72

柯里化 (Currying)

函数柯里化是指将接收多个参数的函数转化成接收单个参数并返回另一个函数的技术，简单来讲，就是我们不再写f(a, b, c)这样的函数而是写f(a)(b)(c)，其中f(a)返回的是一个函数，f(a)(b)还是返回的函数，直到f(a)(b)(c) 才可能是我们通常意义上理解的结果。

比如我们把简单的add 函数

 
def add(x: Int, y: Int): Int = {
  x + y
}

写成下面的样子：

 
def add(x: Int)(y: Int): Int = {
  x + y
}

val _2plus3 = add(2)(3)  // 2 + 3 = 5

val addTwo = add(2)_
val threeAddTwo = addTwo(3) // 5

那么，进行函数柯里化的好处是什么？

  • 提高代码复用性
  • 得到一个部分函数，譬如上面的 addTwo 函数
  • 提高代码可读性
  • 方便实现函数组合

闭包 (Closure)

闭包是函数和其引用变量的一个封装。闭包允许函数在定义时捕获一些外部变量，其行为会根据外部环境变量的不同而不同。下面例子中，函数increCounterBy捕获了外部的counter，并且根据外部counter的不同，调用increCounterBy(1)得到的counter1和counter2也不同。

 
var counter = 0

def increCounterBy(n: Int): Int= {
  n + counter
}

counter = 100 
val counter1 = increCounterBy(1)  // 101

counter = 280 
val counter2 = increCounterBy(1)  // 281

闭包的作用：

  • 记住函数状态
  • 实现函数柯里化
  • 实现高阶函数
  • 实现回调函数

尾递归

函数式编程的逻辑方式经常会用到递归，递归是指在函数中包含对自身的调用。因为在递归时一般要保存栈上下文信息，因此，通常来讲，递归要比命令式程序执行时的效率差。

尾递归是一种特别的递归方式，它是指函数对自身的调用发生在最后的一步。因为在最后一步，编译器通常会对它进行优化，使之执行的效率要优于一般的递归函数而接近命令式。

我们以阶乘做例子。首先，普通递归方式的代码如下， 尽管 n*fac(n-1) 是最后一个语句，但 fac(n-1) 并不是最后一步，n与其乘积才是最后一步，所以下面这个例子是普通递归而不是尾递归。

 
def fac(n: Long): Long = {
  if (n == 1)
    1
  else
    n * fac(n - 1)
}

然后我们写一下尾递归的阶乘：

 
@tailrec
def facTail(n: Long, total: Long = 1): Long = {
  if (n == 1) total
  else facTail(n - 1, n * total)
}

对前20个数计算阶乘，可以看出两者执行效率差距极大，达到2个数量级。

1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = 479001600
13! = 6227020800
14! = 87178291200
15! = 1307674368000
16! = 20922789888000
17! = 355687428096000
18! = 6402373705728000
19! = 121645100408832000
20! = 2432902008176640000
fac time: 135 ms, facTail time: 1 ms

另外斐波那契数列的一般递归和尾递归实现方式如下：

def fabonacci(n: Long): Long = {
  if (n <= 2)
    1
  else
    fabonacci(n - 1) + fabonacci(n - 2)
}

@tailrec
def fabonacciTail(n: Long, a: Long = 1, b: Long = 1): Long = {
  if (n <= 2)
    b
  else
    fabonacciTail(n - 1, b, a + b)
}