高阶函数（一）

1 什么是高阶函数

1.1 高阶函数的基本概念

高阶函数其实看着挺吓人，不过就是把函数作为参数或者返回值的一类函数而已。其实这样的函数我们都见过很多了，来看个例子：

public inline fun <T> Array<out T>.forEach(action: (T) -> Unit): Unit { 
    for (element in this) action(element) 
}

这是我们的老朋友了，forEach，传入了一个 Lambda 表达式，之后在迭代数组的时候调用这个 Lambda。你可千万别把 Lambda 不当函数，人家可是正儿八经的 FunctionN 的实例，这个我们在前面一篇文章细说 Lambda 表达式已经介绍过了

如果使用 forEach，我们就这么写：

array.forEach{ 
    print("$it, ") 
}

输出结果就类似：

1, 2, 3, 4,

forEach 其实就是一个把函数当参数传入的高阶函数了。

1.2 函数引用

下面我们要来思考一个问题。为什么 Kotlin 可以有高阶函数？

其实这个问题，我们早就有答案了，因为在 Kotlin 当中，函数是“一等公民”，函数的引用可以自由传递，赋值，并在合适的时候调用。为什么这么说呢？难道仅仅是因为我们可以任性的定义 Lambda 表达式这种匿名函数，并把它赋值为一个变量，然后可以随便传递和调用吗？

当然不能完全是这样了。其实 Kotlin 当中的任何方法、函数都是有其名字和引用的，我们前面其实看到过一个 forEach 的例子，我再给大家拿出来：

array.forEach(::println)

这个例子当中，我们其实是想要把元素挨个打印一遍，forEach 传入的是一个 (T) -> Unit，这并不是说它只能传入一个符合参数和返回值的 Lambda，而是说符合参数和返回值定义的任意函数。println 有很多版本，其中有一个符合上面的条件：

public inline fun println(message: Any?) { 
    System.out.println(message) 
}

所以我们可以把它当参数传入。这个意义上讲，::println 跟 Function1 是什么关系呢？很明显接口实现的关系了，同时 ::println 因为可以具名引用到一个函数，所以我们也把类似的写法叫做函数引用。

我们再来看一个类成员的例子：

class Hello{ 
    fun world(){ 
        println("Hello world.") 
    } 
} 
　 
val helloWorld: (Hello)-> Unit = Hello::world

我们同样可以用 <TypeName>::<FunctionName> 的方式来引用类成员方法，当然扩展方法也是可以的。这个要怎么用呢？

fun Int.isOdd(): Boolean = this % 1 == 0 
　 
... 
val ints = intArrayOf(1,3,4,5,8) 
ints.filter(Int::isOdd)

注意到 filter 的参数类型：

public inline fun IntArray.filter(predicate: (Int) -> Boolean): List<Int> { 
    return filterTo(ArrayList<Int>(), predicate) 
}

跟我们前面 Hello::World 的例子是不是一模一样呢？

不过相比包级函数，这种引用在 Kotlin 1.1 以前显得有些苍白，为什么这么说呢？

class PdfPrinter{ 
    fun println(any: Any?){ 
        println(any) 
    } 
} 
　 
... 
　 
array.forEach(PdfPrinter::println) //错误！！

请问，这种情况下，我该如何像 ::println 一样将 PdfPrinter::println 传递给 forEach 呢？我们知道，所有的类成员方法，它们其实都有一个隐含的参数，即类的实例本身，所以它的类型应该是下面这样：

val pdfPrintln: (PdfPrinter, Any?)-> Unit = PdfPrinter::println

那么，有人就会说，我干脆构造一个 PdfPrinter 的实例，然后这么写看看：

array.forEach(PdfPrinter()::println)// Since Kotlin 1.1

看着很不错了吧？可惜，这个在 1.1 才支持哦，不过距离 1.1 正式发布应该不久了！

2 常见的内置高阶函数

Kotlin 为我们内置了不少好用的高阶函数，这一节我们就给大家简要介绍一下。

2.1 map

我们经常用 forEach 来迭代一个集合，如果我们想要把一个集合映射成另外一个集合的话，通常我们会这么写：

val list = listOf(1,3,4,5,10,6,8,2) 
　 
val newlist = ArrayList<Int>() 
list.forEach {  
    val newElement = it * 2 + 3 
    newlist.add(newElement) 
}

看上去还是挺简单的，不过终究不够简洁，而且还在 Lambda 表达式内部访问了外部变量，这其实都不是很好的编程习惯。

map 其实就是对类似的操作做了一点封装，类似的集合映射的操作用 map 再合适不过了：

val newlist  =  list.map { 
    it * 2 + 3 
}

Lambda 的参数是原集合的元素，返回值是对应位置的新集合的元素，新集合是 map 的返回值。我们再来看个例子：

val stringlist = list.map(Int::toString)

上面这个例子，我们把一个整型的集合映射成了一个字符串类型的集合。不管你做何种变换，map 的返回值始终是一个大小与原集合相同的集合。

2.2 flatMap

如果我手头有一个整型集合的集合，我想把他们打平，变成一个整型集合，用我们传统的方法就是两层循环。如果我还想要做点儿变换，那么这代码写起来就更丑了。

如果我们要用 flatMap，那么这个故事就直截了当得多：

val list = listOf( 
        1..20, 
        2..5, 
        100..232 
) 
　 
val flatList = list.flatMap { it } 
println(flatList)

flatMap 后面的 Lambda 参数是 list 的元素，也就 1..20、2..5 这些 range，返回的值呢是一个 Iterable，flatMap 会把这些 Lambda 返回的 Iterable 统统添加到它自己的返回值也就是 flatList 当中，这样就相当于把 list 做了一次打平。

结果：

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 2, 3, 4, 5, 100, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126, 127, 128, 129, 130, 131, 132, 133, 134, 135, 136, 137, 138, 139, 140, 141, 142, 143, 144, 145, 146, 147, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 160, 161, 162, 163, 164, 165, 166, 167, 168, 169, 170, 171, 172, 173, 174, 175, 176, 177, 178, 179, 180, 181, 182, 183, 184, 185, 186, 187, 188, 189, 190, 191, 192, 193, 194, 195, 196, 197, 198, 199, 200, 201, 202, 203, 204, 205, 206, 207, 208, 209, 210, 211, 212, 213, 214, 215, 216, 217, 218, 219, 220, 221, 222, 223, 224, 225, 226, 227, 228, 229, 230, 231, 232]

那么这么直白的打平也不见得是我们的目标，比如我们要把这些数都做一些运算再打平，那么这个也简单：

val flatList = list.flatMap { iterable ->  
    iterable.map { element -> 
        element * 2 + 3 
    } 
}

我们只需要对 iterable 做一次 map 即可。

2.3 fold / reduce

其实 fold 就是折叠的意思嘛，把一个集合的元素折叠起来并得到一个最终的结果，这就是 fold 要做的事情。

fun main(args: Array<String>) { 
    val ints = intArrayOf(1,2,3,4,5) 
    val r = ints.fold(5){ 
        sum, element -> 
        println("$sum, $element") 
        sum + element 
    } 
    println(r) 
}

结果呢？就是从 5 开始，每次返回的结果又成了 sum，一直这么折叠下去，直到最后输出 20。

5, 1 
6, 2 
8, 3 
11, 4 
15, 5 
20

当然，对于fold来说，我们还可以得到其他类型的结果，不一定要与集合的元素类型相同：

val r1 = ints.fold(StringBuilder()){ 
    sb, element-> 
    sb.append(element).append(",") 
} 
　 
println(r1)

大家看到，我们的初始值实际上是一个 StringBuilder，后续一直在做字符串追加的操作，最后得到的 r1 其实就是一个追加了所有元素的 StringBuilder，我们把它打印出来：

1,2,3,4,5,

我们再来看下 reduce。

val r2 = ints.reduce { sum, element -> sum + element } 
println(r2)

输出的最终结果是 15，也即元素之和。显然，reduce 每次求值的结果都作为下一次迭代时传入的 sum，这个看上去跟 fold 极其的类似，只不过 reduce 没有额外的初始值，并且返回值类型也需要保持与集合的元素相同。

如果我们要求一个数的阶乘，那代码其实很容易写：

fun factorial(n: Int): Int{ 
    if(n == 0) return 1 
    return (1..n).reduce { factorial, element -> factorial * element } 
}

2.4 filter / takeWhile

如果我们有一个很大的集合，想要过滤掉其中的一些元素，那么通常的做法也是构造一个新集合来，然后遍历原集合。

显然，我们有更好的写法：

val evens = (1..100).filter {  
    it % 2 == 0 
}

找出 1 到 100 之间的所有偶数，我们只需要用 filter，并传入判断条件，那么符合条件的元素就会被保留到返回的集合当中。

类似的，takeWhile 则返回的集合是原集合中从第一个元素开始到第一个不符合条件的元素之前的所有元素。例如：

println((1..10).takeWhile { it % 5 != 0 })

这表明，从 1..10 当中取元素，只要遇到一个是 5 的倍数的元素，那么立即返回，即结果为：

[1, 2, 3, 4]

2.5 let

let 实际上比较简单，我们先来看下它的定义：

public inline fun <T, R> T.let(block: (T) -> R): R = block(this)

我们看到 let 实际上传入了一个 Lambda，而这个 Lambda 传入的参数就是 let 的调用者本身，返回值随便你。这个 let 有什么用呢？

val person: Person? = findPerson()

我们看到 person 这个变量是可空的，我们需要做一些判断才能对其进行操作。通常的写法可能是这样的：

person?.name = "张三" 
person?.age = 18 
...

不过，这种问号满天飞的写法，看着其实并不是很让人舒服。

我们还可以这么写：

if(person != null){ 
    person.name = "张三" // person 被智能转换成 Person 类型 
    person.age = 18 
    ... 
}

当然，我们还有一种写法就是：

person?.let{ 
    it.name = "张三" 
    it.age = 18 
    ... 
}

let 比较简单，其用法也是很灵活的，大家可以自行发挥。

2.6 apply / with

下面我们来看 apply。

public inline fun <T> T.apply(block: T.() -> Unit): T { block(); return this }

注意到 apply 传入的 Lambda 也是 apply 的调用者的扩展方法，所以，apply 相当于给了我们一个灵活切换上下文的机会，

class Options{ 
    var scale: Float = 1f 
    var offsetX: Double = 0.0 
    var offsetY: Double = 0.0 
    var rotationX: Float = 0f 
    var rotationY: Float = 0f 
}

假设我们有这么一个类，我们在操作一个地图变换的时候需要传入这个东西，告诉地图该怎么变换。

mapView.animateChange(Options().apply {  
    //Options 的作用域 
    scale = 2f 
    rotationX = 180f 
})

而 with 呢？

public inline fun <T, R> with(receiver: T, block: T.() -> R): R = receiver.block()

跟 apply 比较类似，不同之处在与 Lambda 返回值。with 只是单纯的获取 receiver 的上下文，而 apply 则同时也把它本身返回了。

val br = BufferedReader(FileReader("hello.txt")) 
with(br){ 
    var line: String? 
    while (true){ 
        line = readLine()?: break 
    } 
    close() 
}

我们看到在 with 当中，readLine 和 close 方法可以直接调用。

内置高阶函数其实非常多，这几个比较常用，剩下的大家可以自行学习。

3 尾递归优化

递归大家都熟悉，一说递归大家都容易哆嗦：你可别递归的层次太深了啊，不然小心 StackOverflow！没错，StackOverflow 这个异常实在是太常见了，所以你最熟悉的程序员社交网站当中就有一个叫 StackOverflow 的。

其实大家肯定也都知道，递归能实现的，用迭代也基本上能实现，这个感觉就好像做小学数学题，用递归就好比设个 x，列个方程求解；而用迭代呢，就好比用算式生生的去把结果给算出来。前者思考起来比较直接，编写起来也自然更符合人的思维模式，后者呢往往编写困难，代码可读性差。

如果有一天，我能写出递归程序，编译器呢，却能够按照迭代的方式给我运行，那么我岂不是既能获得递归的简洁性，又不失迭代的运行效率，那该。。。想得美啊。

我们今天就要给大家看一种特定条件下的编译优化措施。其实前面我们的设想并不是完全做不到，对于某些比较简单的场景，编译器是可以直接把我们的递归代码翻译成迭代代码的，而这种场景其实就是“尾递归”。

什么叫“尾递归”？函数在调用自己之后，没有任何操作的情形就是尾递归。

比如：

data class ListNode(val value: Int, var next: ListNode?) 
　 
fun findListNode(head: ListNode?, value: Int): ListNode?{ 
    head?: return null 
    if(head.value == value) return head 
    return findListNode(head.next, value) 
}

我们随便定义了一个链表，ListNode 是它的元素，findListNode 目的是找到对应值的元素。我们看到最后一行只有 findListNode 的调用，没有其他任何操作，这就是尾递归。

我们再来看几个例子：

fun factorial(n: Long): Long{ 
    return n * factorial(n - 1) 
}

求阶乘，因为 factorial 调用之后还有乘以 n 的操作，所以这个不是尾递归。

data class TreeNode(val value: Int){ 
    var left: TreeNode? = null 
    var right: TreeNode? = null 
} 
　 
fun findTreeNode(root: TreeNode?, value: Int): TreeNode?{ 
    root?: return null 
    if(root.value == value) return root 
    return findTreeNode(root.left, value) ?: return findTreeNode(root.right, value) 
}

这个算不算尾递归呢？好像最后一行的两个 return 都是之调用了 findTreeNode，没有其他操作了啊，这个应该是尾递归吧？答案当然不是。。因为第一个 findTreeNode 的结果拿到之后，我们要看下他是不是为 null，实际上这个判断操作在 findTreeNode 之后，所以不能算尾递归。对于不是尾递归的情况，编译器是没有办法做优化的。

而对于尾递归的情况，我们该如何启用编译器优化呢？

要说告诉编译器需要尾递归优化，其实非常简单，加一个关键字即可：

tailrec fun findListNode(head: ListNode?, value: Int): ListNode?{ 
    head?: return null 
    if(head.value == value) return head 
    return findListNode(head.next, value) 
}

这个看起来真的很简单，简单到没有说服力。我们看一段小程序：

val MAX_NODE_COUNT = 100000 
val head = ListNode(0) 
var p = head 
for (i in 1..MAX_NODE_COUNT){ 
    p.next = ListNode(i) 
    p = p.next!! 
} 
//前面先构造了一个链表，节点个数有 10 万个 
//后面进行查找，查找值为 MAX_NODE_COUNT - 2 的节点 
println(findListNode(head, MAX_NODE_COUNT - 2)?.value)

对于没有 tailrec 关键字的版本，结果非常抱歉：

Exception in thread "main" java.lang.StackOverflowError 
    at net.println.kotlin.RecursiveKt.findListNode(Recursive.kt:34) 
    at net.println.kotlin.RecursiveKt.findListNode(Recursive.kt:34)

而对于有 tailrec 的版本，结果是：

99998

显然，对于尾递归优化的版本，即使你递归再多的层次，都不会有 StackOverflow，原因也很简单，编译器其实已经把这种递归编译成迭代来运行了，迭代怎么会有 StackOverflow 呢？

接着我们再来讨论一下非尾递归代码可以改写为尾递归代码的条件。大家仔细观察我们前面给出的两个例子，一个是求阶乘，一个是超找树的节点。二者最后一句：

return n * factorial(n - 1)

return findTreeNode(root.left, value) ?: return findTreeNode(root.right, value)

虽然都不是尾递归，但还是有差异的。前者在调用完自己之后进行了跟调用自己无关的运算；后者调用完一次自己之后，还有可能调用一次自己。注意，如果调用完自己，又进行了其他操作，也即没有再次调用自己，那么这种递归其实有希望转换为尾递归代码，下面我们就改写一下求阶乘的代码，让它变成尾递归代码。

fun factorial(n: Long): Long{ 
    class Result(var value: Long) 
　 
    tailrec fun factorial0(n: Long, result: Result){ 
        if(n > 0) { 
            result.value *= n 
            factorial0(n - 1, result) 
        } 
    } 
    val result = Result(1) 
    factorial0(n, result) 
    return result.value 
}

这个例子当中有一些比较有意思的概念哈，我们在一个函数当中定义了一个函数和一个类，它们被称作“本地函数”和“本地类”，由于定义在函数内部，因此在外部无法使用它们。接着我们对内部的 factorial0 加了 tailrec 关键字，由于最后一行只有对自己的调用，因此符合尾递归优化的条件。

我们看到，之前 n * 的这部分操作通过 Result 携带的中间结果被移到了自身调用的前面，这样做让原本的递归代码符合了尾递归优化的条件，却也让代码本身复杂了许多。而对于此类操作，我个人更倾向于直接使用迭代。

fun factorial(n: Long): Long{ 
    var result: Long = 1 
    for (i in 1..n){ 
        result *= i 
    } 
    return result 
}

迭代的代码显然也直截了当得多。

总而言之，使用递归是为了让我们的代码更直接，更自然，使用迭代往往是为了追求效率（空间效率）。对于类似查找链表节点这样的场景，它很自然的就是一个尾递归的结构，我们可以使用尾递归优化来提升它的性能；而对于求阶乘这样的场景，它本来就不是尾递归的结构，我们尽管可以通过某种方式改写它，但这样做其实根本没必要；而对于查找树节点这样的场景，尾递归基本上是无能无力了。

4 闭包

对象是要携带状态的。比如：

val string = "HelloWorld"

string 这个对象它有值，这个值就是它的状态。那么同样作为对象的函数，它有什么状态呢？我们看个例子：

fun makeFun(): ()->Unit{ 
    var count = 0 
    return fun(){ 
        println(++count) 
    } 
} 
　 
... 
　 
val x = makeFun() 
x() 
x() 
x() 
x()

输出的结果会是什么呢？从函数当中返回一个函数，这在 Java 当中简直不能想象，不过这在函数为“一等公民”的 Groovy、JavaScript 当中确实寻常可见。

1 
2 
3 
4

每次调用 x，打印的值都不一样，这说明函数也是可以保存状态的。受到这个启发，我们是不是可以继续写出这样的例子：

fun fibonacci(): ()->Long{ 
    var first = 0L 
    var second = 1L 
    return fun(): Long{ 
        val result = second 
        second += first 
        first = second - first 
        return result 
    } 
} 
... 
　 
val next = fibonacci() 
for (i in 1..10){ 
    println(next()) 
}

输出结果：

1 
1 
2 
3 
5 
8 
13 
21 
34 
55

我们干脆再进一步吧：

fun fibonacciGenerator(): Iterable<Long>{ 
    var first = 0L 
    var second = 1L 
    return Iterable { 
        object : LongIterator(){ 
            override fun hasNext() = true 
　 
            override fun nextLong(): Long { 
                val result = second 
                second += first 
                first = second - first 
                return result 
            } 
        } 
    } 
} 
　 
... 
　 
for(x in fibonacciGenerator()){ 
    println(x) 
    if(x > 100) break 
}

这个例子我们干得更彻底，通过返回一个 Iterable，我们甚至可以用 for 循环迭代这个结果。

不管我们怎么写，请注意，每次调用同一个函数的结果都不一样，而承载返回结果的 first 和 second 这两个变量是定义在最外层的函数当中的，按说这个函数一旦运行完毕，它所在的作用域就会被回收，如果真是那样，前面的这两段代码一定是我们产生的幻觉。如果不是幻觉，那只能说明一个问题：这个作用域没有被回收。

这个作用域包含了所有函数运行的状态，包括变量、本地类、本地函数等等，那这个作用域其实就是闭包。

我们再来看个好玩的例子：

fun add(x: Int) = fun(y: Int) = x + y 
　 
... 
val add5 = add(5) 
println(add5(2))

很显然，结果是 7，这个 add 的定义其实写得有些令人迷惑，我把它改写一下给大家看：

fun add(x: Int): (Int)->Int{ 
    return fun(y: Int): Int{ 
        return x + y 
    } 
}

很显然，当我们调用 add(5) 返回 add5 这个函数时，它是持有了 add 函数的运行环境的，不然它怎么知道 x 的值是多少呢？

通过这几个小例子，相信大家对闭包有了一定的了解。闭包其实就是函数运行的环境。

下周我们还会继续跟大家讨论函数编程相关的一些话题，谢谢大家的关注~