本系列的最后一篇文章，我们来了解一下 Swift 4.1 的最后一个重要特性，它也和泛型相关：关联类型的递归约束。该特性解决了 Swift 泛型中的一大尴尬，关联类型无法递归定义。

1. Sequence 的关联类型

Swift 4.1 之前，我们是这样约束 Sequence 的 SubSequence 关联类型的：用注释。

protocol Sequence {
  // SubSequences themselves must be Sequences...
  associatedtype SubSequence
  
  // The subsequence conforms to Sequence...
  func dropFirst(_ n: Int) -> Self.SubSequence
}

在 Swift 4.1 之前，如果 Sequence 的关联类型 SubSequence 定义成 SubSequence : Sequence 这样的递归形式，就会报以下错误：
Type may not reference itself as a requirement，这就造成了实际的类型约束只能写成注释，而且需要在类型使用的地方都写明注释，叮嘱大家需要遵循的规范。

Swift 4.1 对关联类型的递归约束做了正式的支持，于是乎 Sequence 的 SubSequence 可以递归定义了，Sequence 的关联类型完整定义如下：

protocol Sequence {
  associatedtype Element

  associatedtype Iterator : IteratorProtocol 
    where Iterator.Element == Element

  associatedtype SubSequence : Sequence = AnySequence<Element>
    where Element == SubSequence.Element,
          SubSequence.SubSequence == SubSequence
 // ...          
}

在上面代码中，我们看到了3个关联类型，并且看到了一系列的约束，梳理如下：

1. Iterator 关联类型约束了它必须是个 IteratorProtocol，
2. Iterator 关联类型约束了它的Element跟Sequence的Element必须一致，建立起了关联类型间的连接。
3. SubSequence 关联类型约束了它必须是个 Sequence，这里形成了关联类型的约束的递归定义，也就是本文所提及的 Swift 4.1 的新特性。
4. SubSequence 关联类型约束了它的Element跟 Sequence的 Element一致。
5. SubSequence.Iterator.Element 关联类型，由于上述约束以及递归定义，自动和之前所提及的所有Element 保持了一致，因此无需显式申明。
6. SubSequence.SubSequence 与 SubSequence 是同一个类型。
7. SubSequence 的默认类型推断是 AnySequence，这就意味着 AnySequence<Element> 满足所有对 SubSequence 的要求，特别值得注意的是它对于上一条约束的满足： AnySequence 的 dropFirst 方法的返回值类型必须是 AnySequence。还有个值得一提的例子是：Array的 SubSequence 是ArraySlice，它也满足上述特征。

新特性介绍完了，接下来是一些衍生的相关知识。

2. 打造一个 DummySequence

好不容易做好了关联类型的递归约束，试试看实现一个 struct DummySequence : Sequence 吧， 越简单越好，只求编译通过，你会怎么做呢？

希望茫茫多的 Sequence 的方法没有吓着你，多亏了有默认实现，只要技巧正确，那么大多数的方法我们的 DummySequence 不需要实现。我的参考答案如下：

struct DummySequence<Element>: Sequence {

  typealias Iterator = AnyIterator<Element>
      
  typealias SubSequence = AnySequence<Element>
    
  func makeIterator() -> AnyIterator<Element> {
    return AnyIterator<Element> { return nil }
  }
}

其实还有优化空间，两处的 typealias 也都可以删除，只剩下 makeIterator。第一处可以删除，是因为后续的makeIterator可以推导出此处的类型；第二处也可以删除，是因为 AnySequence<Element> 就是不指定时的默认选择类型。

3. Why AnySequence?

说到这里，希望 AnySequence 已经引起了你足够的好奇，标准库中不会随随便便指定一个类型为默认类型的。但是AnySequence 不是一个新的特性，对于了解 AnySequence 的前世今生的同学，本文已经结束了。对于不太了解的同学，我们一起来继续学习，我想先举一个简单的例子。

protocol List {
  associatedtype Element
  func element(at index: Int) -> Element?
}

struct IntArrayList: List {
  func element(at index: Int) -> Int? {
    return nil
  }
}

struct IntLinkedList: List {
  func element(at index: Int) -> Int? {
    return nil
  }
}

struct DoubleLinkedList: List {
  func element(at index: Int) -> Double? {
    return nil
  }
}

上述是个足够简化的仿造示例，对于这个例子，我想写出以下的代码，如何定义intLists呢？

for l in intLists {
    _ = l.element(at: 0)
}

似乎很简单，这样不就行了？

// compile error
let intLists = [IntArrayList(), IntLinkedList()]

这样写的同学已经得到了编译错误，似乎明确指定类型就可以了？

// compile error
let intLists: [List] = [IntArrayList(), IntLinkedList()]
// compile error
let intLists2: [List<Int>] = [IntArrayList(), IntLinkedList()]

依然是编译错误，看过新特性第一篇的同学或许已经想到了些什么。是的，List不是泛型类型，仅仅是泛型约束。这时候就要出动 Type eraser 技术了。 代码如下：

struct AnyList<Element>: List {
    private let elementFunc: (Int) -> Element?
    init<L>(_ base: L) where Element == L.Element, L : List {
        elementFunc = base.element(at:)
    }
    func element(at index: Int) -> Element? {
        return elementFunc(index)
    }
}

它是一个包装类型 (Wrapper)，所以它还有个名字叫做 Type-erased wrapper，在我看来它有两个作用：

1. 帮助隐藏具体类型
2. 用通用的泛型类型表达泛型约束

于是我们的问题解决：

// 编译通过
let intLists = [AnyList(IntArrayList()),AnyList(IntLinkedList())]
for l in intLists {
    _ = l.element(at: 0)
}

// 预期中的编译不过
let mixedLists = [AnyList(IntLinkedList()), AnyList(DoubleLinkedList())]

在 Swift 标准库中，有许多 Type eraser，例如：AnySequence、AnyIterator、AnyHashable 等等，希望上面已经用AnyList已经阐明了它们的设计初衷。

小结

在本文中，我们讨论了：

1. 什么是关联类型的递归约束
2. 关联类型的递归约束在 Sequence 上的应用
3. 如何实现一个最简单的 Sequence 类型
4. 什么是Type Eraser，为什么要设计 AnySequence。

至此，Swift 4.1 的主要新特性介绍完毕了，回顾一下，所有的特性其实都与泛型相关，希望大家有所收获。预告下番外篇：向 Swift 4.1 迁移。

欢迎关注公众号

Swift 4.1 新特性系列文章

Swift 4.1 新特性 (1) Conditional Conformance
Swift 4.1 新特性 (2) Sequence.compactMap
Swift 4.1 新特性 (3) 合成 Equatable 和 Hashable
Swift 4.1 新特性 (4) Codable的改进