目录
1. 问题的由来
我们在上一节中提到，其实函数和变量在更高一级的抽象上是一样的，它们的声明和定义都有关键词，名称，类型，字面值。那么你或许会问，那什么是区别于函数和数据的本质呢？答案是有无输入。如果仔细看下图(函数有输入不是常识么？别急，我们一步一步剖析函数和数据的异同)，你会发现函数有输入，这体现在函数的类型和完整字面值(Block)上。
这一不同将打开一扇崭新的大门，引出一系列深刻的问题：
- 函数作用在数据上可以输入数据和输出数据，函数能否作用在函数上？
- 函数有输入，那么输入的参数个数之间有没有关系呢？
这就是我们下面要讨论的高阶函数(函数输入输出与函数有关)和柯里化(函数输入个数的关系)。
2. 高阶函数和柯里化
2.1 高阶函数
在scala里，函数作为一等公民，享有和其他数据(也是一等公民)一样的待遇，包括作为函数的输入和输出。这样使得函数的输入输出除了可以是数据外，还可以是函数。这就引出一个函数阶级的问题：
一阶函数：输入输出都为数据；
高阶函数：输入输出至少有一个为函数。
我们先从一个简单的求和问题来，下面是两个求和函数，上下界分别是a和b：
- sumInts = ∑k=ab k；
- sumCube = ∑k=ab k3； 它们的实现如下：
1
2
3
4
5
6
7
8
9
10
11
12
13
def sumInts(a:Int,b:Int):Int = {
if (a > b) 0
else a + sumInts(a+1,b)
}
sumInts(1,3) // 1+2+3 = 6
def sumCube(a:Int,b:Int):Int = {
if (a > b) 0
else a*a*a + sumCube(a+1,b)
}
sumCube(1,3) // 1*1*1 + 2*2*2 + 3*3*3 = 35
这两个函数可以看到都是一阶函数。但是这两个函数有共性：都是求和，且上下界都为a和b。不同的是求和的单项不一样。我们能不能把它的共性抽象出来，使得任何满足这种共性的函数不用每次都写递归求和呢？请看下面代码：
1
2
3
4
5
6
7
8
9
10
11
def sum(f:Int=>Int, a:Int,b:Int):Int = { //高阶函数，输入是一个函数，a，b
if(a>b) 0 else f(a)+sum(f,a+1,b)
}
def sumInts(a:Int,b:Int) = sum((x:Int) => x, a, b) //一阶函数，输入两个Int，输出一个Int
sumInts(1,3) //6
def sumCube(a:Int,b:Int) = sum((x:Int)=>x*x*x,a,b) //一阶函数，输入两个Int，输出一个Int
sumCube(1,3) //35
这里我们写了一个高阶函数sum(f:Int=>Int, a:Int,b:Int):Int，输入是一个函数(Int=>Int)，a，b，输出是Int。相比于上例的sumCube和sumInt，我们将他们的不同点用函数f抽象出来，剩下的共同点的实现还是一样。因此本例中一阶函数sumInt和一阶函数sumCube可以用高阶函数sum表示，输入分别是block(x:Int)=>x和(x:Int)=>x*x*x。
这样高阶函数就很好地抽象了低阶函数，使得低阶函数的实现变的简单而不重复。
2.2 柯里化
在上面的例子中，我们可以看到高阶函数sum(f:Int=>Int, a:Int,b:Int):Int有三个输入参数，如何将三个输入函数变成一个输入函数而不影响其实现呢？这个时候，我们不要忘了函数的返回也可以是函数。我们能否使其输入是f，输出变成(a:Int,b:Int)=>Int呢？请看下面代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
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
} //sum: (Int => Int)=>(Int, Int) => Int
def sumInts = sum((x:Int)=>x) //sumInts: (Int, Int) => Int
sumInts(1,3) //6
sum((x:Int)=>x)(1,3) //6
def sumCube = sum((x:Int)=> x*x*x) //sumCube: (Int, Int) => Int
sumCube(1,3) //36
sum((x:Int)=> x*x*x)(1,3) //36
由上例可以看出sum输入一个函数(类型为(Int=>Int))，返回一个函数(类型为(Int,Int)=>Int)，即输入为单参数，返回的一阶函数输入也是单参数。因此，对于最终的执行有两种形式：
sumCube = sum((x:Int)=> x*x*x)，用一个函数名sumCube获取这个返回函数，然后再调用它sumCube(1,3)；- 不需要这个中间变量，直接用
sum((x:Int)=> x*x*x)(1,3)调用。
第二种情况实现了我们上面提到的高阶函数也只需输入1个参数而不影响其最终实现。这样，所有阶级的函数(包括低阶和高阶)都可以完美的统一起来用单参数表示。
柯里化：将n参数函数转成单参数函数的过程。方法是通过不断转换成一个包含n个单参数的函数的嵌套树形结构。每一个树形结构的上层节点的输入参数对所有下层节点的函数可见(参数之间先后关系更立体)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def sum(f:Int=>Int, a:Int,b:Int):Int = { //多参数
if(a>b) 0 else f(a)+sum(f,a+1,b)
}
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
}
//在Scala里，第二种单参数形式可以写成以下形式的语法糖，使单参数调用的形式更直观。
def sum(f:Int=>Int)(a:Int,b:Int): Int = { //单参数
if (a>b) 0 else f(a)+sum(f)(a+1,b)
}
def sumInts = sum((x:Int)=>x)(_,_) //中间函数的语法稍微不同，用(_,_)表示第二个单参数没有
sumInts(1,3) //6
sum((x:Int)=>x)(1,3) //6
def sumCube = sum((x:Int)=>x*x*x)(_,_)
sumCube(1,3) //36
sum((x:Int)=> x*x*x)(1,3) //36
对于为什么有Currying的存在，结合上篇文章对λ-Calculus的介绍，我们来整理下思路：
- λ calculus可以完成所有的计算，它是建立在函数基础上；
- λ calculus的重要形式之一是函数只能是单参数；
- 那么既然λ calculus可以完成所有的计算，它如何表达多参数函数呢？
- 答案是用Currying(多次返回高阶函数)。
这也就是我们为什么要用Currying。
3 Assignment
这次的作业是用函数式编程完成数据结构Set(集合)。Type Set: Int=>Boolean，Set被定义成一个输入Int返回Boolean的函数。若包含输入Int，返回true；反之false。(是不是有点脑洞大开的感觉？)
它有一系列操作：
def singleton(elem:Int):Set，单例的构造方法，输入一个elem，返回一个Set；def contains(elem:Int, s:Set):Boolean；def union(s:Set,p:Set):Set；- …
def forall(s:Set,p:Int=>Boolean):Boolean，是否所有的s中的元素都满足p。def exist(s:Set,p:Int=>Boolean):Boolean，是否在s中有元素不满足p。def map(s:Set,f:Int=>Int):Set，输入一个set，返回一个经过f变换后的set。
具体代码见这里。
map函数需要遍历s，由于Set的定义，不能直接完成这个操作，因此作业中设定了我们要处理的数字的上下界。
这要借助exist函数，而exist函数本身又建立在forall函数上。这真是有种虚无生两极，两极生四象，四象生八卦的感觉，上帝创造了Alonzo Church，Alanzo Church创造了λ-Calculus，λ-Calculus催生了现在的函数式编程，函数式编程又用函数实现了数据结构Set，Set中的复杂函数又建立在一个个基础函数上。任何事物都有一个源头，顺着时间的长河回溯，上帝之前又是什么呢？
4 总结
Currying是伴随高阶函数而存在的。最后，我们将Currying和高阶函数总结成一句话和一幅图：
高阶函数是纯函数式编程的核心。
Currying(即嵌套高阶函数)：纯函数式编程中对多参数函数的实现。
