Scala 就像一位武林中的集大成者，将过去几十年计算机语言发展历史中的精萃集于一身，化繁为简，为程序员们提供了一种新的选择。作者希望通过这个系列，可以为大家介绍 Scala 语言的特性，和 Scala 语言给我们带来的关于编程思想的新的思考。本文将带领大家一起回顾函数式编程的历史，清楚函数式编程的定义，并以一个例子，由易到难为大家展示函数式编程的优点，最后介绍了柯里化的概念。
函数式编程是这几年很受欢迎的一个话题，即使你是一个刚刚踏入职场的新人，如果在面试时能有意无意地透露出你懂那么一点点函数式编程，也会让你的面试官眼前一亮。然而函数式编程并不是一个新的概念，它的源头可以追溯到计算机尚未发明之前。本文将带领大家回顾一下函数式编程的历史，并使用 Scala 语言为大家讲解函数式编程的基本概念。
函数式编程的历史
有机会看到这篇文章的读者，大概都会知道阿兰·图灵（Alan Turing）和约翰·冯·诺伊曼（John von Neumann）。阿兰·图灵提出了图灵机的概念，约翰·冯·诺伊曼基于这一理论，设计出了第一台现代计算机。由于图灵以及冯·诺伊曼式计算机的大获成功，历史差点淹没了另外一位同样杰出的科学家和他的理论，那就是阿隆佐·邱奇（Alonzo Church）和他的λ演算。阿隆佐·邱奇是阿兰·图灵的老师，上世纪三十年代，他们一起在普林斯顿研究可计算性问题，为了回答这一问题，阿隆佐·邱奇提出了λ演算，其后不久，阿兰·图灵提出了图灵机的概念，尽管形式不同，但后来证明，两个理论在功能上是等价的，条条大路通罗马。如果不是约翰·麦卡锡（John McCarthy），阿隆佐·邱奇的λ演算恐怕还要在历史的故纸堆中再多躺几十年，约翰·麦卡锡是人工智能科学的奠基人之一，他发现了λ演算的珍贵价值，发明了基于λ演算的函数式编程语言：Lisp，由于其强大的表达能力，一推出就受到学术界的热烈欢迎，以至于一段时间内，Lisp 成了人工智能领域的标准编程语言。很快，λ演算在学术界流行开来，出现了很多函数式编程语言：Scheme 、SML、Ocaml 等，但是在工业界，还是命令式编程语言的天下，Fortran、C、C++、Java 等。随着时间的流逝，越来越多的计算机从业人员认识到函数式编程的意义，爱立信公司于上世纪八十年代开发出了 Erlang 语言来解决并发编程的问题；在互联网的发展浪潮中，越来越多的语言也开始支持函数式编程：JavaScript、Python、Ruby、Haskell、Scala 等。可以预见，如果过去找一个懂什么是函数式编程的程序员很困难，那么在不久的将来，找一个一点也没听过函数式编程的程序员将更加困难。
什么是函数式编程
狭义地说，函数式编程没有可变的变量、循环等这些命令式编程方式中的元素，像数学里的函数一样，对于给定的输入，不管你调用该函数多少次，永远返回同样的结果。而在我们常用的命令式编程方式中，变量用来描述事物的状态，整个程序，不过是根据不断变化的条件来维护这些变量。
广义地说，函数式编程重点在函数，函数是这个世界里的一等公民，函数和其他值一样，可以到处被定义，可以作为参数传入另一个函数，也可以作为函数的返回值，返回给调用者。利用这些特性，可以灵活组合已有函数形成新的函数，可以在更高层次上对问题进行抽象。本文的重点将放在这一部分。
函数式编程有什么优点
约翰·巴克斯（John Backus）为人熟知的两项成就是 FORTRAN 语言和用于描述形式系统的巴克斯范式，因为这两项成就，他获得了 1977 年的图灵奖。有趣的是他在获奖后，做了一个关于函数式编程的讲演：Can Programming Be Liberated From the von Neumann Style? 1977 Turing Award Lecture。他认为像 FORTRAN 这样的命令式语言不够高级，应该有新的，更高级的语言可以摆脱冯诺依曼模型的限制，于是他又发明了 FP 语言，虽然这个语言未获成功，但是约翰·巴克斯关于函数式编程的论述却得到了越来越多的认可。下面，我们就罗列一些函数式编程的优点。
首先，函数式编程天然有并发的优势。由于工艺限制，摩尔定律已经失效，芯片厂商只能采取多核策略。程序要利用多核运算，必须采取并发，而并发最头疼的问题就是共享数据，狭义的函数式编程没有可变的变量，数据只读不写，并发的问题迎刃而解。这也是前面两篇文章中，一直建议大家在定义变量时，使用 val 而不是 var 的原因。爱立信公司发明的 Erlang 语言就是为解决并发的问题而生，在电信行业取得了不俗的成绩。
其次，函数式编程有迹可寻。由于不依赖外部变量，给定输入函数的返回结果永远不变，对于复杂的程序，我们可以用值替换的方式（substitution model）化繁为简，轻松得出一段程序的计算结果。为这样的程序写单元测试也很方便，因为不用担心环境的影响。
最后，函数式编程高屋建瓴。写程序最重要的就是抽象，不同风格的编程语言为我们提供了不同的抽象层次，抽象层次越高，表达问题越简洁，越优雅。读者从下面的例子中可以看到，使用函数式编程，有一种高屋建瓴的感觉。
抽象，抽象，再抽象！
说了这么多，相信很多性急的读者都等不及想看看怎么使用 Scala 进行函数式编程了吧。那么，先请大家暂时忘掉以前命令式编程的经验，用一个全新的大脑来开始这段函数式编程之旅。
故事从我上初中的外甥小龙身上开始，像所有聪明的孩子一样，小龙身上具备了懒，不耐烦以及妄自尊大这些优秀特质。他厌倦了数学作业上那些大量没有意义的，重复的练习题。还好他有个当程序员的姨夫：在电脑上装个 Scala，写程序做吧。于是小龙把 Scala 当作一个计算器，写出了他有生以来第一段程序：
清单 1. 求立方
35 * 35 * 35 68 * 68 * 68 // 以下省去大量重复的，没有意义的练习题
作业做完了，虽然大脑得到了休息，但是小龙的手累坏了！作为一个懒人，小龙是不会满足于不动脑，但要动手这种状况的。于是，我教给了他最基本的抽象方式：将算法抽象为一个函数。小龙很快做完作业，高高兴兴跟小伙伴们打篮球去了。
清单 2. 求立方函数
def cube(n: Int) = n * n * n // 有了这个函数，小龙做起作业轻松多了 cube(35) cube(68) // 以下省去大量重复的，没有意义的练习题
随着教学进度的加快，小龙的作业也越来越难了，很快，小龙遇到了这样的题目：求出 1 到 10 的立方和。聪明如小龙，或者说懒惰如小龙，在前一个函数基础之上，很快又定义了个新函数，还是个递归函数！没错，在小龙还没看见过循环之前，我先教会了他递归，他理解起来毫不费力：对 a 到 b 之间的数求立方和，等于 a 的立方和，加上 (a + 1) 到 b 之间的数的立方和。如果读者对于递归还有疑惑，请参考作者的前一篇文章《使用递归的方式去思考》。小龙又很快做完作业，高高兴兴跟着小伙伴们打球去了。
清单 3. 求立方和
def cube(n: Int) = n * n * n def sumCube(a: Int, b: Int): Int = if (a > b) 0 else cube(a) + sumCube(a + 1, b) // 有了这个函数，小龙做起作业轻松多了 sumCube(1, 10)
塞翁失马，焉知非福，好事很快变坏事，由于小龙数学作业做得又快又好，被老师选拔为奥数培养对象，除过作业，小龙每天还要做大量的额外练习：求 1 到 10 的和，求 1 到 10 的平方和，求 1 到 10 的阶乘和等等。这时，小龙已经对定义函数很熟练了，三下五除二，小龙又定义出一堆函数出来。
清单 4. 各种求和函数
def cube(n: Int) = n * n * n def id(n: Int) = n def square(n : Int) = n * n def fact(n: Int): Int = if (n == 0) 1 else n * fact(n - 1) def sumCube(a: Int, b: Int): Int = if (a > b) 0 else cube(a) + sumCube(a + 1, b) def sumSquare(a: Int, b: Int): Int = if(a > b) 0 else square(a) + sumSquare(a + 1, b) def sumFact(a: Int, b: Int): Int = if (a > b) 0 else fact(a) + sumFact(a + 1, b) def sumInt(a: Int, b: Int): Int = if(a > b) 0 else id(a) + sumInt(a + 1, b) // 有了这些函数，小龙做起作业轻松多了 sumCube(1, 10) sumInt(1, 10) sumSquare(1, 10) sumFact(1, 10)
问题解决了，但小龙总觉得哪里不对劲，（这时，一个画外音高喊：Don ’ t Repeat Yourself!），是的，仔细观察小龙定义的这四个求和函数，几乎是一模一样的。能不能也将这些一模一样的东西抽象出来？我觉得是时候教给他第二项本领了：高阶函数（Higher-Order Function），所谓高阶函数，就是操作其他函数的函数。以求和为例，我们可以定义一个新的求和函数，该函数接受另外一个函数作为参数，这个作为参数的函数代表了某种对数据的操作。使用高阶函数后，抽象层次提高，代码变得更简单了。
清单 5. 使用高阶函数定义求和函数
def cube(n: Int) = n * n * n def id(n: Int) = n def square(n : Int) = n * n def fact(n: Int): Int = if (n == 0) 1 else n * fact(n - 1) // 高阶函数 def sum(f: Int => Int, a: Int, b: Int): Int = if (a > b) 0 else f(a) + sum(f, a + 1, b) // 使用高阶函数重新定义求和函数 def sumCube(a: Int, b: Int): Int = sum(cube, a, b) def sumSquare(a: Int, b: Int): Int = sum(square, a, b) def sumFact(a: Int, b: Int): Int = sum(fact, a, b) def sumInt(a: Int, b: Int): Int = sum(id, a, b) // 有了这些函数，小龙做起作业轻松多了 sumCube(1, 10) sumInt(1, 10) sumSquare(1, 10) sumFact(1, 10)