声明：文章开头部分内容翻译自objc的一篇博客。当然，我并没有逐行翻译原文，只是说个大致意思，顺带阐述一些自己的理解和扩展思考，还有我自己的代码。
分解序列：
//分解成首元素和剩余数组
extension Array {
var decompose : (head: Element, tail: [Element])? {
return (count > 0) ? (self[0], Array(self[1..<count])) : nil
}
}
上面这个代码片段是对Array的一个扩展（对extension不熟悉对同学可以看看我以前的一篇文章）。decompose作为扩展的计算属性，返回一个可空元组（Tuple?），元组包含数组的首元素和一个由剩余元素组成的数组，如果数组为空则返回nil。这个分解操作配合if let和模式匹配将非常好用。譬如对序列数据的累加操作sum：
//累加
func sum(list: [Int]) -> Int {
if let (head, tail) = list.decompose {
return head + sum(tail)
} else {
return 0
}
}
let sumResult = sum([1, 2, 3, 4]) //10
在函数式编程的世界中，取序列的首元素和剩余序列是一个很重要的操作，许多高阶的序列操作都可以基于这个操作完成。上面说了累加，稍微扩展一下，累乘呢？当然也可以。甚至我们可以用它定义一个更抽象更一般化的函数，功能与Swift提供的全局函数reduce相同：
//山寨reduce
func reduce<T>(list: [T], initValue: T, function: (lhs: T, rhs: T) -> T) -> T {
if let (head, tail) = list.decompose {
return function(lhs: head, rhs: reduce(tail, initValue: initValue, function: function))
} else {
return initValue
}
}
let multiResult = reduce([2, 3, 5], initValue: 1, function: *) //30
reduce接收三个参数：序列list、初始值initValue、操作函数function。我以multiResult为例稍微讲解一下这个函数的过程。这个函数的重点当然是递归，事实上我认为递归可以说是函数式编程这种范式的核心之一。
运行reduce([2, 3, 5], initValue: 1, function: *)，先是递归分解：
- [2, 3, 5]被分解为元组(2, [3, 5])。
- 2和
reduce([3, 5], initValue: 1, function: *)的返回值将作为乘法操作*的两个参数。 - 执行
reduce([3, 5], initValue: 1, function: *)，[3, 5]被分解成元组(3, [5])。 - 3和
reduce([5], initValue: 1, function: *)的返回值将作为乘法的左右因数相乘。 - 执行
reduce([5], initValue: 1, function: *)，[5]被分解成元组(5, [])。 - 5和
reduce([], initValue: 1, function: *)的返回值将作为乘法的左右因数相乘，而[]是个空数组，它的decompose属性返回nil，所以执行else之后的代码块，即返回initValue1。
至此向下递归结束，接下来就是延递归栈往上计算各个function函数（此例中即乘法）的值。最终得到1 ＊ 5 ＊ 3 ＊ 2 ＝ 30。
当然，递归会消耗栈空间，如果递归很深的话，很有可能会导致栈溢出。有一种常见的优化方式是尾递归（简单来说，即把递归调用放到函数最后），如果编译器支持尾递归优化的话，就会把函数中的一些中间变量舍去甚至直接优化成循环形式。具体内容我就不展开来，大家可以看一下老赵早期的一篇《浅谈尾递归的优化方式》，想必会有所得。
以sum函数为例的话，进行尾递归优化我们可以将其改写为如下形式：
//累加
func sum(list: [Int]) -> Int {
guard let (head, tail) = list.decompose else {
return 0
}
return head + sum(tail)
}
新的sum函数使用Swift2的新特性guard进行提前返回，guard是我很喜欢的一个语法，哪怕不是为了尾递归优化，我也推荐大家使用guard语句处理边界条件然后提前返回，这也是所谓的防御式编程中所提倡的，我之前的一篇文章也有提到。
最后再说一个用到decompose的快排函数吧：
//快排
func quickSort(list: [Int]) -> [Int] {
guard let (pivot, rest) = list.decompose else {
return []
}
let lesser = rest.filter { $0 < pivot }
let greater = rest.filter { $0 >= pivot }
return quickSort(lesser) + [pivot] + quickSort(greater)
}
可以看到这个函数抽象度很高，而且思路非常清晰——选取首元素作为参照点，比参照点小的放参照点左边，大的放右边。函数的大致过程为：递归进行分解排序，最后延递归栈向上连接数组。之前我写过一篇快排的文章，里面的函数远没有上面这个版本简洁优雅。
快把decompose加入你的Code Snippet中吧^ ^。
网友评论