Filter / Reduce / FlatMap的实现和扩展

filter和与filter类似的语义

之前，我们提到过filter的用法，用于在Array中，过滤满足特定条件的元素。而这个条件，就是通过filter的closure参数来确定的：

var fibonacci = [0, 1, 1, 2, 3, 5]

// [0, 2]
fibonacci.filter { $0 % 2 == 0 }

按照上一节中实现map的思路，我们可以自己来实现一个filter：

extension Array {
    func myFilter(_ predicate: (Element) -> Bool) -> [Element] {
        var tmp: [Element] = []

        for value in self where predicate(value) {
            tmp.append(value)
        }

        return tmp
    }
}

在上面的实现里，最核心的环节就是通过带有where条件的for循环找到原数组中符合条件的元素，然后把它们一一添加到tmp中，并最终返回给函数的调用者。然后，我们测试下myFilter：

fibonacci.myFilter { $0 % 2 == 0 } // [0, 2]

结果，应该是和标准库中自带的filter是一样的。理解了filter之后，我们就可以自行定义一些标准库中没有的方法。例如：

剔除掉数组中满足条件的元素：

extension Array {
    func reject(_ predicate: (Element) -> Bool) -> [Element] {
        return filter { !predicate($0) }
    }
}

我们只要把调用转发给filter，然后把指定的条件取反就好了。这样，剔除元素的代码语义上就会更好看一些：

fibonacci.reject { $0 % 2 == 0 } // [1, 1, 3, 5]

另一个基于filter语义的常用操作是判断数组中是否存在满足条件的元素。下面的代码可以完成任务：

fibonacci.filter { $0 % 2 == 0 }.count > 0 // true

但这样做在性能上并不理想，因为即便找到了满足条件的元素，也要遍历完整个数组，这显然是没必要的。Swift标准库中，提供了一个更方便的方法：

fibonacci.contains { $0 % 2 == 0 } // true

contains的一个好处就是只要遇到满足条件的元素，函数的执行就终止了。基于这个contains，我们还可以给Array添加一个新的方法，用来判断Array中所有的元素是否满足特定的条件：

extension Array {
    func allMatch(_ predicate: (Element) -> Bool) -> Bool {
        return !contains { !predicate($0) }
    }
}

在allMatch的实现里，只要没有不满足条件的元素，也就是所有元素都满足条件了。我们可以用下面的代码测试一下：

let evens = [2, 4, 6, 8]
evens.allMatch { $0 % 2 == 0 } // true

reduce和与reduce相关的语义

除了用一个数组生成一个新的数组，有时，我们会希望把一个数组变成某种形式的值。例如，之前我们提到的求和：

fibonacci.reduce(0, +) // 12

了解reduce的进一步用法之前，我们先来自己实现一个：

extension Array {
    func myReduce<T>(_ initial: T, _ next: (T, Element) -> T) -> T {
        var tmp = initial

        for value in self {
            tmp = next(tmp, value)
        }

        return tmp
    }
}

从上面的实现就可以看出，reduce的实现也没有什么神奇之处。无非就是把for循环迭代相加的过程封装了起来。然后，用下面的代码测试一下，就会发现和标准库中的reduce一样了。

fibonacci.myReduce(0, +) // 12

除了求和之外，我们还可以把fibonacci reduce成一个字符串：

let str = fibonacci.myReduce("") { str, num in 
    return str + "\(num) "
}
// "0 1 1 2 3 5 "

甚至，我们还可以用reduce模拟map和filter的实现：

extension Array {
    func myMap2<T>(_ transform: (Element) -> T) -> [T] {
        return reduce([], { $0 + [transform($1)] })
    }

    func myFilter2(_ predicate: (Element) -> Bool) -> [Element] {
        return reduce([], { predicate($1) ? $0 + [$1] : $0 })
    }
}

然后，简单测试一下：

// [0, 1, 1, 4, 9, 25]
fibonacci.myMap2 { $0 * $0 }
// [0, 2]
fibonacci.myFilter2 { $0 % 2 == 0 }

它们的结果和标准库中的map和filter是一样的。但是，这种看似优雅的写法却没有想象中的那么好。在它们内部的reduce调用中，每一次$0的参数都是一个新建的数组，因此整个算法的复杂度是O(n²)，而不再是for循环版本的O(n)。所以，这样的实现方法最好还是用来作为理解reduce用法的例子。

flatMap

最后，我们来了解flatMap。简单来说，如果你用在map中的closure参数不返回一个数组元素，而是也返回一个数组，这样，你就会得到一个数组的数组，但如果你只需要一个一维数组，flatMap就可以派上用场了，而这，也就是flat的含义。先来看一个例子：

FlatMap demo

假设，我们要给animals数组中的动物都使用ids中的数字进行编号。一开始，可能我们会写下这样的代码：

animals.map { animal in
    return ids.map { id in (animal, id) }
}

但如果是这样，由于animals.map使用的closure参数返回的是一个Array，而不是单一元素，最终，我们会得到一个“数组的数组”：

FlatMap demo

但这并不是我们想要的，我们只是需要一个一维数组表示所有的(animal, id)。此时，就可以让flatMap派上用场了：

animals.flatMap { animal in
    return ids.map { id in (animal, id) }
}

这样，我们就能得到期望的内容了：

FlatMap demo

实际上，flatMap的实现很简单，只要在map内部的for循环里，不断把closure参数生成的数组的内容，添加到要返回的结果里就好了：

extension Array {
    func myFlatMap<T>(_ transform: (Element) -> [T]) -> [T] {
        var tmp: [T] = []

        for value in self {
            tmp.append(contentsOf: transform(value))
        }

        return tmp
    }
}

用下面的代码测试，得到的结果，应该和之前使用flatMap是一样的：

animals.myFlatMap { animal in
    return ids.map { id in (animal, id) }
}