美文网首页iOS专题Swift语法iOS知识
“身首异处”的序列(Swift)

“身首异处”的序列(Swift)

作者: Sheepy | 来源:发表于2015-11-27 22:56 被阅读529次

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

    相关文章

      网友评论

      • 曾樑:swift现在有开发正式用了伐
        Sheepy:@曾樑 嗯啊,我用纯Swift写了一个项目了,在等审核。

      本文标题:“身首异处”的序列(Swift)

      本文链接:https://www.haomeiwen.com/subject/mqkkhttx.html