“身首异处”的序列（Swift）

声明：文章开头部分内容翻译自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中吧^ ^。