Swift 进阶【八】泛型

发表于 2018-04-03 分类于编程语言 Disqus：

和大多数先进语言一样，Swift 拥有不少能被归类于泛型编程下的特性。使用泛型代码，你可以写出可重用的函数和数据结构，只要它们满足你所定义的约束，它们就能够适用于各种类型。比如，像是 Array 和 Set 等多个类型，实际上是它们中的元素类型就是泛型抽象。我们也可以创建泛型方法，它们可以对输入或者输出的类型进行泛型处理。func identity<A>(input: A) -> A 就定义了一个可以作用于任意类型 A 的函数。某种意义上，我们甚至可以认为带有关联类型的协议是“泛型协议”。关联类型允许我们对特定的实现进行抽象。IteratorProtocol 协议就是一个这样的例子：它所生成的 Element 就是一个泛型。

泛型编程的目的是表达算法或者数据结构所要求的核心接口。比如，考虑内建集合一章中的 last(where:) 函数。将它写为 Array 的一个扩展原本是最明显的选择，但是 Array 其实包含了很多 last(where:) 并不需要的特性。通过确认核心接口到底是什么，也就是说，找到想要实现的功能的最小需求，我们可以将这个函数定义在宽阔得多的类型范围内。在这个例子中，last(where:) 只有一个需求：它需要能够逆序遍历一系列元素。所以，将这个算法定义为 Sequence 的扩展是更好的选择 (我们也可以为 BidirectionalCollection 添加一个更高效的实现)。

在本章中，我们会研究如何书写泛型代码。我们会先看一看什么是重载 (overloading) ，因为这个概念和泛型紧密相关。然后我们会使用泛型的方式，基于不同的假设，来为一个算法提供多种实现。之后我们将讨论一些你在为集合书写泛型算法时会遇到的常见问题，了解这些问题后你就将能使用泛型数据类型来重构代码，并使它们易于测试，更加灵活。最后，我们会谈一谈编译器是如何处理泛型代码的，以及要如何优化我们的泛型代码以获取更高性能的问题。

重载

拥有同样名字，但是参数或返回类型不同的多个方法互相称为重载方法，方法的重载并不意味着泛型。不过和泛型类似，我们可以将多种类型使用在同一个接口上。

自由函数的重载

Swift 有一系列的复杂规则来确定到底使用哪个重载函数，这套规则基于函数是否是泛型，以及传入的参数是怎样的类型来确定使用优先级。整套规则十分复杂，不过它们可以被总结为一句话，那就是“选择最具体的一个”。也就是说，非通用的函数会优先于通用函数被使用。

来看下面这个例子：

func log<View: UIView>(_ view: View) {
    print("It's a \(type(of: view)), frame: \(view.frame)")
}

func log(_ view: UILabel) {
    let text = view.text ?? "(empty)"
    print("It's a label, text: \(text)")
}

传入 UILabel 将会调用专门针对 label 的重载，而传入其他的视图将会调用到泛型函数：

let label = UILabel(frame: CGRect(x: 20, y: 20, width: 200, height: 32))
label.text = "Password"
log(label) // It's a label, text: Password
let button = UIButton(frame: CGRect(x: 0, y: 0, width: 100, height: 50))
log(button) // It's a UIButton, frame: (0.0, 0.0, 100.0, 50.0)

要特别注意，重载的使用是在编译期间静态决定的。也就是说，编译器会依据变量的静态类型来决定要调用哪一个重载，而不是在运行时根据值的动态类型来决定。我们如果将上面的 label 和 button 都放到一个 UIView 数组中，并对它们迭代并调用 log 的话，使用的都是泛型重载的版本：

let views = [label, button] // Type of views is [UIView]
for view in views {
    log(view)
}
/*
 It's a UILabel, frame: (20.0, 20.0, 200.0, 32.0)
 It's a UIButton, frame: (0.0, 0.0, 100.0, 50.0)
 */

view 的静态类型是 UIView，UILabel 本来应该使用更专门的另一个重载，但是因为重载并不会考虑运行时的动态类型，所以两者都使用了 UIView 的泛型重载。

运算符的重载

当使用操作符重载时，编译器会表现出一些奇怪的行为。Matt Gallagher 指出，即使泛型版本应该是更好的选择（而且应该在一个普通函数调用时被选择）的时候，类型检查器也还是会去选择那些非泛型的重载，而不去选择泛型重载。

我们来看一个幂运算的例子：

// 幂运算比乘法运算优先级更高
precedencegroup ExponentiationPrecedence {
    associativity: left
    higherThan: MultiplicationPrecedence
}
infix operator **: ExponentiationPrecedence
func **(lhs: Double, rhs: Double) -> Double {
    return pow(lhs, rhs)
}
func **(lhs: Float, rhs: Float) -> Float {
    return powf(lhs, rhs)
}

现在我们添加一个整数的重载，让它对所有的整数类型有效，这里我们对所有满足 BinaryInteger 的类型定义了一个重载。

func **<I: BinaryInteger>(lhs: I, rhs: I) -> I {
    // 转换为 Int64，使用 Double 的重载计算结果
    let result = Double(Int64(lhs)) ** Double(Int64(rhs))
    return I(result)
}

上面的泛型看起来没什么问题，但是在我们使用整型调用 ** 的时候，编译器会报错说 ** 存在歧义

1	2 3 // 错误：操作符 '' 的使用存在歧义。

要解释原因，我们需要回到我们在本节一开头说道的：对于重载的运算符，类型检查器会去使用非泛型版本的重载，而不考虑泛型版本。显然，编译器忽略了整数的泛型重载，因此它无法确定是去调用 Double 的重载还是 Float 的重载，因为两者对于整数字面量输入来说，是相同优先级的可选项（Swift 编译器会将整数字面量在需要时自动向上转换为 Double 或者 Float ），所以编译器报错说存在歧义。要让编译器选择正确的重载，我们需要至少将一个参数显式地声明为整数类型，或者明确提供返回值的类型：

1	let intResult: Int = 2 ** 3 // 8

使用泛型约束进行重载

当你在写一些可以被用多种算法表达的同样的操作，并且算法对它们的泛型参数又有不同的要求的代码的时候，你可能经常会遇到带有泛型代码的重载。假设我们要写一个算法，来确定一个数组中的所有元素是不是都被包含在另一个数组中。换句话说，我们想要知道第一个数组是不是第二个数组的子集 (这里元素的顺序不重要)。标准库中提供了一个叫做 isSubset(of:) 的方法，不过这个方法只适用于像 Set 这样满足 SetAlgebra 协议的类型。

我们可以写一个适用于更宽广范围的 isSubset(of:)，它看起来可能是这样的：

extension Sequence where Element: Equatable {
    /// 当且仅当 `self` 中的所有元素都包含在 `other` 中，返回 true
    func isSubset(of other: [Element]) -> Bool {
        for element in self {
            guard other.contains(element) else {
                return false
            }
        }
        return true
    }
}
let oneToThree = [1,2,3]
let fiveToOne = [5,4,3,2,1]
oneToThree.isSubset(of: fiveToOne) // true

这个 isSubset 的版本有一个重大缺陷，那就是性能。这里的算法的时间复杂度是 O(nm)，其中 n 和 m 分别代表两个数组的元素个数。也就是说，随着输入的增多，这个函数的最坏情况的耗时将成平方增加。这是因为 contains 在数组中的复杂度是线性的 O(m)，这个函数会迭代源序列中的元素，逐个检查它是够匹配给定的元素。而 contains 是在另一个迭代最初数组的元素的循环中被调用了，这个循环也很类似，是一个线性时间复杂度的循环。所以我们是在一个 O(n) 循环里执行了一个 O(m) 的循环，结果这个函数的复杂度就是 O(nm)。

我们可以通过要求元素满足 Hashable 来收紧序列元素类型的限制来写出性能更好的版本。

extension Sequence where Element: Hashable {
    /// 如果 `self` 中的所有元素都包含在 `other` 中，则返回 true
    func isSubset(of other: [Element]) -> Bool {
        let otherSet = Set(other)
        for element in self {
            guard otherSet.contains(element) else {
                return false
            }
        }
        return true
    }
}

这样查找操作就可以在常数时间内进行了。

类型检查器会使用它所能找到的最精确的重载。这里 isSubset 的两个版本都是泛型函数，所以非泛型函数先于泛型函数的规则并不适用。不过因为 Hashable 是对 Equatable 的扩展，所以要求 Hashable 的版本更加精确。有了这些约束，我们可能可以像例子中的 isSubset 这样写出更加高效的算法，所以编译器假设更加具体的函数会是更好的选择。

isSubset 还可以更加通用，到现在位置，它只接受一个数组并对其检查。但是 Array 是一个具体的类型。实际上 isSubset 并不需要这么具体，在两个版本中只有两个函数调用，那就是两者中都有的 contains 以及 Hashable 版本中的 Set.init。这两种情况下，这些函数只要求输入类型满足 Sequence 协议：

extension Sequence where Element: Equatable {
    /// 根据序列是否包含给定元素返回一个布尔值。
    func contains(_ element: Element) -> Bool
}
struct Set<Element: Hashable>:
    SetAlgebra, Hashable, Collection, ExpressibleByArrayLiteral
{
    /// 通过一个有限序列创建新的集合。
    init<Source: Sequence>(_ sequence: Source)
    where Source.Element == Element
}

所以，isSubset 中 other 只需要是遵守 Sequence 的任意类型就可以了。另外，self 和 other 这两个序列类型并不需要是同样的类型。我们只需要其中的元素类型相同就能进行操作。下面是针对任意两种序列重写的 Hashable 版本的函数：

extension Sequence where Element: Hashable {
    /// 如果 `self` 中的所有元素都包含在 `other` 中，则返回 true
    func isSubset<S: Sequence>(of other: S) -> Bool
        where S.Element == Element
    {
        let otherSet = Set(other)
        for element in self {
            guard otherSet.contains(element) else {
                return false
            }
        }
        return true
    }
}

现在两个序列不需要有相同的类型了，这为我们开启了更多的可能性。比如，你可以传入一个数字的 CountableRange 来进行检查：

1	[5,4,3].isSubset(of: 1...10) // true

我们可以对可判等的元素的函数作出同样的更改。

使用闭包对行为进行参数化

使用闭包对行为参数化，指的就是闭包表达式，类似于 Array 的 map ，filter ，reduce 这些函数。我们的 isSubset 函数还有更加通用化的可能，对于那些不遵循 Equatable 的序列要怎么办？比如 Array 的元素也是 Array 的时候，本身 Array 无法遵循 Equatable ，因为 Array 元素本身就可能不能判等。

遇到这种情况的时候，我们可以将判等的工作交给调用者去实现，使用闭包。标准库中的 contains 函数就是一个很好的例子：

extension Sequence {
    /// 根据序列是否包含满足给定断言的元素，返回一个布尔值。
    func contains(where predicate: (Element) throws -> Bool)
        rethrows -> Bool
}

这个 contains 函数很强大，你可以用它来对一个序列进行各种条件的检查。用于我们的 isSubset 函数上后，就像下面这样：

extension Sequence {
    func isSubset<S: Sequence>(of other: S,
                               by areEquivalent: (Element, S.Element) -> Bool)
        -> Bool
    {
        for element in self {
            guard other.contains(where: { areEquivalent(element, $0) }) else {
                return false
            }
        }
        return true
    }
}

现在，我们可以将 isSubset 用在数组的数组上了，只需要为它提供一个闭包表达式，并使用 == 来对数组进行比较。不幸的是，如果我们导入了 Foundation，另一个对类型检查器的性能优化将会导致编译器不再确定到底应该使用哪个 ==，从而使编译发生错误。我们需要在代码的某个地方加上类型标注：

1	[[1,2]].isSubset(of: [[1,2] as [Int], [3,4]]) { $0 == $1 } // true

对集合采用泛型操作

集合上的泛型算法通常会带出一些特殊的问题，特别在与索引和切片一起使用时更是如此。在这节中，我们通过两个依赖于正确处理索引和切片的例子，来看看如何解决这些问题。

二分查找

说到二分查找，相信大家都会马上想起自己写的最简单的二分查找法。例如下面这个例子：

extension Array {
    /// 返回 `value` 第一次出现在 `self` 中的索引值，
    /// 如果 `value` 不存在，返回 `nil`
    ///
    /// - 要求: `isOrderedBefore` 是在 `self` 中元素上
    /// 的严格弱序，且数组中的元素已经按它进行过排序
    /// - 复杂度: O(log `count`)
    func binarySearch(for value: Element,
                      areInIncreasingOrder: (Element, Element) -> Bool) -> Int?
    {
        var left = 0
        var right = count - 1
        while left <= right {
            let mid = (left + right) / 2
            let candidate = self[mid]
            if areInIncreasingOrder(candidate,value) {
                left = mid + 1
            } else if areInIncreasingOrder(value,candidate) {
                right = mid - 1
            } else {
                // 由于 isOrderedBefore 的要求，如果两个元素互无顺序关系，那么它们一定相等
                return mid
            }
        }
        // 未找到
        return nil
    }
}

extension Array where Element: Comparable {
    func binarySearch(for value: Element) -> Int? {
        return self.binarySearch(for: value, areInIncreasingOrder: <)
    }
}

这个简单的二分查找算法，其实有一个 Bug。

在数组非常大的情况下，将两个索引值相加有可能会造成溢出 (比如 count 很接近 Int.max，并且要搜索的元素是数组最后一个元素时的情况)。不过，将距离的一半加到左侧索引时，这个问题就不会发生。当然了，想要触发这个 bug 的机会其实很小。

现在我们来改善一下既有的算法设计，以前二分查找算法都是基于普通数组的，但是在 Swift 中，有一些特殊的数组，像是 ArraySlice ，上面的算法是无法直接在 ArraySlice 数组中运行的，当我们在计算中间下标的时候，会出现一个 Bug，因为 ArraySlice 的下标并不一定是从 0 开始。所以我们定义二分查找算法的时候，不能定义在普通的数组 Array 上，我们应该定义在 RandomAccessCollection。

泛型二分查找

如果你把 Int 索引的要求去掉，将会发生一些编译错误。原来的代码需要进行一些重写才能完全满足泛型的要求。下面是完全泛型化之后的版本：

extension RandomAccessCollection {
    
    public func binarySearch(for value: Element, areInIncreasingOrder: (Element, Element) -> Bool) -> Index? {
        guard !isEmpty else {
            return nil
        }
        
        var left = startIndex
        var right = index(before: endIndex)
        while left <= right {
            let dist = distance(from: left, to: right)
            let mid = index(left, offsetBy: dist / 2)
            let candidate = self[mid]
            if areInIncreasingOrder(candidate, value) {
                left = index(after: mid)
            } else if areInIncreasingOrder(value, candidate) {
                right = index(before: mid)
            } else {
                return mid
            }
        }
        
        return nil
    }
}

extension RandomAccessCollection where Element: Comparable {
    
    func binarySearch(for value: Element) -> Index? {
        return binarySearch(for: value, areInIncreasingOrder: <)
    }
}

let strAry = ["a", "b", "c", "d", "e", "f", "g"]
strAry.binarySearch(for: "d") // 3

// ArraySlice 并不一定是从下标为 0 开始
let subStrAry = strAry[3..<5] // ["d", "e"]
subStrAry.binarySearch(for: "d") // 3

改动虽小，意义重大。首先，left 和 right 变量现在不再是整数类型了。我们使用了起始索引和结束索引值。这些值可能是整数，但它们也可能是像是 String 的索引，Dictionary 的索引，或者是 Set 的索引这样的非透明索引，它们是无法随机访问的。

使用泛型进行代码设计

让我们来写一些与网络服务交互的函数。比如，获取用户列表的数据，并将它解析为 User 数据类型。我们创建一个 loadUsers 函数，它可以从网上异步加载用户，并且在完成后通过一个回调来传递获取到的用户列表。

func loadUsers(callback: ([User]?) -> ()) {
    let usersURL = webserviceURL.appendingPathComponent("/users")
    let data = try? Data(contentsOf: usersURL)
    let json = data.flatMap {
        try? JSONSerialization.jsonObject(with: $0, options: [])
    }
    let users = (json as? [Any]).flatMap { jsonObject in
        jsonObject.flatMap(User.init)
    }
    callback(users)
}

这个函数有个严重的问题，代码的重用性非常差，如果我们想要写一个相同的函数来加载其他资源，我们可能需要复制这里的大部分代码。打个比方，我们需要一个加载博客文章的函数，它看起来是这样的：

1	func loadBlogPosts(callback: ([BlogPost])? -> ())

提取共通功能

相比于复制粘贴，将函数中 User 相关的部分提取出来，将其他部分进行重用，会是更好的方式。我们可以将 URL 路径和解析转换的函数作为参数传入。因为我们希望可以传入不同的转换函数，所以我们将 loadResource 声明为 A 的泛型：

func loadResource<A>(at path: String,
                     parse: (Any) -> A?, callback: (A?) -> ())
{
    let resourceURL = webserviceURL.appendingPathComponent(path)
    let data = try? Data(contentsOf: resourceURL)
    let json = data.flatMap {
        try? JSONSerialization.jsonObject(with: $0, options: [])
    }
    callback(json.flatMap(parse))
}

现在，我们可以将 loadUsers 函数基于 loadResource 重写：

1
2
3

func loadUsers(callback: ([User]?) -> ()) {
    loadResource(at: "/users", parse: jsonArray(User.init), callback: callback)
}

我们使用了一个辅助函数，jsonArray，它首先尝试将一个 Any 转换为一个 Any 的数组，接着对每个元素用提供的解析函数进行解析，如果期间任何一步发生了错误，则返回 nil：

func jsonArray<A>(_ transform: @escaping (Any) -> A?) -> (Any) -> [A]? {
    return { array in
        guard let array = array as? [Any] else {
            return nil
        }
        return array.flatMap(transform)
    }
}

对于加载博客文章的函数，我们只需要替换请求路径和解析函数就行了：

1
2
3

func loadBlogPosts(callback: ([BlogPost]?) -> ()) {
    loadResource(at: "/posts", parse: jsonArray(BlogPost.init), callback: callback)
}

创建泛型数据类型

loadResource 函数中的 path 和 parse 耦合非常紧密，一旦你改变了其中一个，你很可能也需要改变另一个。我们可以将它们打包进一个结构体中，用来描述要加载的资源。和函数一样，这个结构体也可以是泛型的：

struct Resource<A> {
    let path: String
    let parse: (Any) -> A?
}

extension Resource {
    func loadSynchronously(callback: (A?) -> ()) {
        let resourceURL = webserviceURL.appendingPathComponent(path)
        let data = try? Data(contentsOf: resourceURL)
        let json = data.flatMap {
            try? JSONSerialization.jsonObject(with: $0, options: [])
        }
        callback(json.flatMap(parse))
    }
}

extension Resource {
    func loadAsynchronously(callback: @escaping (A?) -> ()) {
        let resourceURL = webserviceURL.appendingPathComponent(path)
        let session = URLSession.shared
        session.dataTask(with: resourceURL) { data, response, error in
            let json = data.flatMap {
                try? JSONSerialization.jsonObject(with: $0, options: [])
            }
            callback(json.flatMap(self.parse))
            }.resume()
    }
}

相比于之前的用顶层函数来定义资源，我们现在可以定义 Resource 结构体实例，这让我们可以很容易地添加新的资源，而不必创建新的函数。