函数式编程

前言

函数式编程是一种编程范式，我们常见的编程范式有命令式编程（Imperative programming），函数式编程（Functional Programming），常见的面向对象编程也是一种命令式编程。相比之下，函数式编程更关心数据的映射，命令式编程则关心解决问题的步骤。

命令式编程是面向计算机硬件的抽象，有变量（对应着存储单元），赋值语句（获取，存储指令），表达式（内存引用和算术运算）和控制语句（跳转指令）。简单来说，命令式程序就是一个冯诺依曼机的指令序列。以下代码就是典型的命令式编程：

void sumOfPrices() {
    List<Integer> prices = Arrays.asList(10, 30, 17, 20, 15, 18, 45, 12);
    Double total = 0.0;
    for (Integer price : prices) {
        if (price > 20) {
            total = total + (price * 0.9);
        }
    }
}

而函数式编程是面向数学的抽象，将计算描述为一种表达式求值。函数式编程希望程序员用计算（函数）来表示程序，用计算（函数）的组合来表达程序的组合。而非函数式编程则习惯于用命令来表示程序，用命令的顺序执行来表达程序的组合。比如如下的 Scala 代码，通过filter()、map()、reduce()这些函数的组合，完成了从 prices 到 total 的映射关系。

object Prices {
  def main(args: Array[String]): Unit = {
    val prices = Array(10, 30, 17, 20, 15, 18, 45, 12)
    val total = prices.filter(x => x > 20)
      .map(x => x * 0.9)
      .reduce((x, y) => x + y)
    print("total is: " + total)
  }
}

什么是函数式编程

说到底，什么是函数式编程呢？这里借用廖雪峰老师在 Python函数式编程中的定义。

我们通过把大段代码拆成函数，通过一层一层的函数调用，就可以把复杂任务分解成简单的任务，这种分解可以称之为面向过程的程序设计，函数就是面向过程的程序设计的基本单元。而函数式编程（请注意多了一个“式”字）—— Functional Programming，虽然也可以归结到面向过程的程序设计，但其思想更接近数学计算。

我们首先要搞明白计算机（Computer）和计算（Compute）的概念。在计算机的层次上，CPU 执行的是加减乘除的指令代码，以及各种条件判断和跳转指令，所以，汇编语言是最贴近计算机的语言。而计算则指数学意义上的计算，越是抽象的计算，离计算机硬件越远。对应到编程语言，就是越低级的语言，越贴近计算机，抽象程度低，执行效率高，比如 C 语言；越高级的语言，越贴近计算，抽象程度高，执行效率低，比如 Lisp 语言。

函数式编程就是一种抽象程度很高的编程范式，纯粹的函数式编程语言编写的函数没有变量，因此，任意一个函数，只要输入是确定的，输出就是确定的，这种纯函数我们称之为没有副作用。而允许使用变量的程序设计语言，由于函数内部的变量状态不确定，同样的输入，可能得到不同的输出，因此，这种函数是有副作用的。

高阶函数

在 FP 语言中，函数作为一等公民，指的是函数与其他数据类型一样，处于同等地位。函数可以在任何地方定义，在函数内或函数外，可以作为函数的参数和返回值，因此可以对函数进行组合。高阶函数 (Higher-order Function) 就是指接受入参或者返回值为函数的函数。

用 Python 定义一个简单的高阶函数，接受一个入参函数 f 对 x, y 做操作后相加，使用时我可以使用已经定义好的绝对值函数 abs，或者自定义的匿名函数 lambda x : x * x 取平方。

>>> def f_add(x, y, f):
...     return f(x) + f(y)
... 
>>> f_add(1, -2, abs)
3
>>> f_add(1, 2, lambda x : x * x)
5

有了高阶函数，就可以将复用的粒度降低到函数级别，相对于面向对象语言，复用的粒度更低。

Currying

柯里化 (Currying) 是把多个参数的函数转变为只接受一个参数并返回接收剩余参数的函数的过程，这个过程持续多次直到收集到所有所需参数。在 FP 语言中函数（而不是类）被作为参数进行传递，Currying 常常用于转化一个函数的接口以便于其他代码调用。函数的接口就是它的参数，于是 Currying 通常用于减少函数参数的数量

在 JavaScript 中有一个实现函数式编程的库叫作 Ramda ，它有一个特性就是：所有方法都支持柯里化。

const R = require('ramda')

R.add(1)(2) // R.add(1, 2) => 3

const increment = R.add(1)
const addTen = R.add(10)

increment(2) // 3
addTen(2) // 12

这也归功于在 FP 语言中高阶函数的特性，我们来看看add()的实现，返回的是函数，所以不难理解如何实现 increment() 和 addTen() 对 add() 的复用。

const add = function(x) {
  return function(y) {
    return x + y
  }
}
const increment = add(1)
const addTen = add(10)

熟悉 JavaScript 的同学可能使用过 Lodash 类库，Ramda 和 Lodash 最大的区别就是两者的参数位置不同，在 Ramda 中数据一律放在最后一个参数，理念是： Function first，Data last 。而不管是 Lodash 还是 Underscore 都将处理的数据作为第一个参数。事实证明，Ramda 设计更加合理。

const R = require('ramda')
const _ = require('lodash')

const prices = [10, 30, 17, 20, 15, 18, 45, 12]

const total = R.pipe(
  R.filter(x => x > 20),
  R.map(x => x * 0.9),
  R.reduce((x, y) => x + y)(0))

total(prices) // 67.5
totalPrice = _.chain(prices)
  .filter(x => x > 20)
  .map(x => x * 0.9)
  .reduce((x, y) => x + y)
  .value() // 67.5

显然，将数据放在最后，再利用 Currying 的特性，我们将对 prices 的一系列操作封装成total()函数，要比 Lodash 更具复用性。这种风格也叫做 Pointfree：不使用所要处理的值，只合成运算过程。

λ演算

λ演算 (lambda calculus)是一套从数学逻辑中发展，以变量绑定和替换的规则，来研究函数如何抽象化定义、函数如何被应用以及递归的形式系统。它由数学家阿隆佐·邱奇在20世纪30年代首次发表。Lambda 演算可比拟是最根本的编程语言，它包括了一条变换规则（变量替换）和一条将函数抽象化定义的方式。因此普遍公认是一种更接近软件而非硬件的方式。Lambda 演算对函数式编程语言造成很大影响，比如 Lisp、ML 语言和 Haskell 语言。Lambda 演算作为一种广泛用途的计算模型，可以清晰地定义什么是一个可计算函数，而任何可计算函数都能以这种形式表达和求值。Lambda 演算和图灵机已经被证明了是具有同样能力的系统，因此指令式编程能做到的函数式编程也同样可以做到。

编程中提到的 Lambda 表达式，通常是在需要一个函数，但是又不想费神去命名一个函数的场合下使用，也就是指匿名函数，比如 Python 中的lambda关键字，JavaScript 和 Scala 中的箭头函数 =>。

>>> import functools
>>> prices = [10, 30, 17, 20, 15, 18, 45, 12]
>>> functools.reduce(lambda x, y : x + y, map(lambda x : x * 0.9, filter(lambda x : x > 20, prices)))
67.5

不变性

纯函数式编程语言中的变量也不是命令式编程语言中的变量，即存储状态的单元，而是代数中的变量，即一个值的名称。变量的值是不可变的 (immutable) ，也就是说不允许像命令式编程语言中那样多次给一个变量赋值。比如说在命令式编程语言我们写x = x + 1，这依赖可变状态的事实，拿给程序员看说是对的，但拿给数学家看，却被认为这个等式为假。严格意义上的函数式编程意味着不使用可变的变量，赋值，循环和其他命令式控制结构进行编程。就好比 Java 中所有变量都是final的

事实上函数式程序是可以保存状态的，只不过它们用的不是变量，而是函数。状态保存在函数的参数中，也就是说在栈上。如果你需要保存一个状态一段时间并且时不时的修改它，那么你可以编写一个递归函数。举个例子，试着用 Java 写一个函数用来反转字符串。记住咯，这个程序里的变量都是默认为final的。

String reverse(String arg) {
    if (arg.length() == 0) {
        return arg;
    } else {
        return reverse(arg.substring(1, arg.length())) + arg.substring(0, 1);
    }
}

从理论上说，函数式语言也不是通过冯诺伊曼体系结构的机器上运行的，而是通过λ演算来运行的，就是通过变量替换的方式进行，变量替换为其值或表达式，函数也替换为其表达式，并根据运算符进行计算。λ演算是图灵完全 (Turing completeness) 的，但是大多数情况，函数式程序还是被编译成冯诺依曼机的机器语言的指令执行的。

函数式编程的最主要的好处主要是不可变性带来的。没有可变的状态，函数就是引用透明 (Referential Transparency) 的和**无副作用 (No Side Effect)**。

引用透明

引用透明指的是函数的运行不依赖于外部变量或状态，值只依赖输入的参数，任何时候只要参数相同，引用函数所得的返回值总是相同的。这样在并发编程中就避免了有外部变量被其它线程调用后导致返回的结果不是期望值，在函数式编程中，纯函数构成的程序是不需要加线程锁的。

无副作用

所谓副作用，指的是函数内部与外部互动（最典型的情况，就是修改全局变量的值），产生运算以外的其他结果。函数式编程强调没有”副作用”，意味着函数要保持独立，所有功能就是返回一个新的值，没有其他行为，尤其是不得修改外部变量的值。在其他类型的语言中，变量往往用来保存状态 (state) 。不修改变量，意味着状态不能保存在变量中。函数式编程使用参数保存状态，最好的例子就是递归。因为 FP 语言不包含任何赋值语句，变量值一旦被指派就永远不会改变。而且，调用函数只会计算出结果 ── 不会出现其他效果。因此，FP 语言没有副作用。

惰性求值

由于函数是引用透明的，以及函数式编程不像命令式编程那样关注执行步骤，这个系统提供了优化函数式程序的空间，包括惰性求值 (Lazy evaluation) 和并性处理。惰性求值的目的是要最小化计算机要做的工作。在惰性计算中，表达式不是在绑定到变量时立即计算，而是在求值程序需要产生表达式的值时进行计算。除可以得到性能的提升外，惰性求值还可以以简单的方式表示无限的概念，这种方式有利于程序的模块化。

比如我们用 Python 的生成器去生成无穷的一个自然数序列，控制台将会一直打印除非你手动中断。

>>> def natural_nums():
...      n = 0
...      while True:
...          yield n
...          n = n + 1
...
>>> natural_nums()
<generator object f1 at 0x1033ed468>
>>> 
>>> for x in natural_nums():
...     print(x)
...

总结

命令式编程主要关心的是 how to do，也就是怎么做，告诉机器每一步的实现过程。而函数式编程主要关心的是 what to do，也就是实体与实体之间的对应关系（映射）。函数式编程是给软件开发者提供的另一套工具箱，为我们提供了另外一种抽象和思考的方式。如果你对函数式编程的起源感兴趣，强烈推荐阅读 Functional Programming For The Rest of Us 这篇文章，写的很幽默风趣。

芥子屋