Swift面向协议设计的一个主要好处是，它使我们能够编写与多种类型兼容的通用代码，而不是仅为一种类型专门实现。特别是当这些泛型代码的目标是在标准库中找到的协议之一时——这将使它可以在内置类型和用户定义类型中使用。
这种协议的一个例子是Sequence，它被所有可以遍历的标准库类型所采用，例如Array、Dictionary、Set等等。本周，让我们看看如何在通用容器中封装序列，这将让我们在易于使用的api后面封装各种算法。
The art of being lazy
人们很容易陷入这样的误区，认为所有的序列都像数组一样，在序列创建时，所有的元素都立即加载到内存中。 然而，由于序列协议的唯一要求是采用者应该能够被迭代，所以我们不能对未知序列的元素如何加载或存储做出任何假设。
例如，就像我们在“Swift序列:懒惰的艺术”中看到的那样，序列有时可以惰性地加载它们的元素——要么是出于性能原因，或者因为不能保证整个序列都能装入内存。以下是一些可能做到这一点的序列的例子:
// A sequence of database records, in which pages of records are
// loaded as an iteration goes on, to avoid loading all search
// results into memory in order to iterate over them.
let records = database.records(matching: searchQuery)
// A sequence of subfolders within a folder on disk, in which each
// folder is only opened once the iteration has reached it.
let folders = folder.subfolders
// A sequence of nodes within a graph, which is lazy so that we
// don't need to evaluate the entire graph at the beginning of
// each iteration.
let nodes = node.children
```swift
由于上述所有序列都是惰性的，所以我们不希望将它们强制放入数组中，例如通过调用array (folder.subfolders)。但是，我们仍然可能希望以不同的方式修改和使用这些序列——因此，让我们看看如何通过创建序列包装器类型来实现这一点。
## Building a base
让我们首先构建一个基类型，我们可以使用它在任何序列上创建各种方便的api。我们将它命名为WrappedSequence，它将是一个泛型，包含我们要包装的序列的类型，以及我们希望新序列产生的元素类型。
包装器的核心特性将是它的IteratorFunction，它将使我们能够控制底层序列的迭代——通过改变每个迭代所使用的迭代器:
```swift
struct WrappedSequence<Wrapped: Sequence, Element>: Sequence {
typealias IteratorFunction = (inout Wrapped.Iterator) -> Element?
private let wrapped: Wrapped
private let iterator: IteratorFunction
init(wrapping wrapped: Wrapped,
iterator: @escaping IteratorFunction) {
self.wrapped = wrapped
self.iterator = iterator
}
func makeIterator() -> AnyIterator<Element> {
var wrappedIterator = wrapped.makeIterator()
return AnyIterator { self.iterator(&wrappedIterator) }
}
}
如上所述，Sequence使用工厂模式，通过makeIterator()方法，让每个序列为每个迭代创建一个新的迭代器实例。
上面我们使用了标准库的AnyIterator类型，这是一种类型删除的迭代器，可以使用任何底层迭代器协议实现来生成元素值。在我们的例子中，我们将通过调用IteratorFunction生成一个元素，并将包装序列自身的迭代器作为参数传递——由于该参数标记为inout，我们可以在函数中就地改变底层迭代器。
因为WrappedSequence也是一个序列，所以我们可以使用标准库的所有序列绑定功能——比如遍历它，或者使用map转换它的值:
let folderNames = WrappedSequence(wrapping: folders) { iterator in
return iterator.next()?.name
}
for name in folderNames {
...
}
let uppercasedNames = folderNames.map { $0.uppercased() }
现在，让我们开始使用新的WrappedSequence进行旋转!
Prefixing and suffixing
在处理序列时，很常见的情况是想要在我们正在处理的序列中插入一个前缀或后缀——但如果我们能够在不改变底层序列的情况下这么做不是很好吗? 既可以带来更好的性能，也可以让我们向任何序列添加前缀和后缀——而不仅仅是向常见类型(如数组)添加前缀和后缀。
使用WrappedSequence，我们可以很容易地做到这一点。我们所要做的就是使用一个方法来扩展Sequence，该方法产生一个包装序列，给定一个要作为前缀插入的元素数组。然后，在执行迭代时，首先遍历所有带有前缀的元素，然后再执行底层序列，如下所示:
extension Sequence {
func prefixed(
with prefixElements: Element...
) -> WrappedSequence<Self, Element> {
var prefixIndex = 0
return WrappedSequence(wrapping: self) { iterator in
// If we still have prefixed elements left to serve,
// then return the next one by incrementing our index:
guard prefixIndex >= prefixElements.count else {
let element = prefixElements[prefixIndex]
prefixIndex += 1
return element
}
// Otherwise, return an element from our underlying
// sequence's own iterator:
return iterator.next()
}
}
}
上面我们使用了可变参数(通过添加…可以将一个或多个元素传递给同一个方法。
类似地，我们也可以创建一个方法，将一组给定的后缀添加到序列的末尾——首先完成基础序列自己的迭代，然后遍历带后缀的元素:
extension Sequence {
func suffixed(
with suffixElements: Element...
) -> WrappedSequence<Self, Element> {
var suffixIndex = 0
return WrappedSequence(wrapping: self) { iterator in
guard let next = iterator.next() else {
// This is our exit condition, in which we return
// nil after both the underlying iteration, and
// the suffixed one, have been completed:
guard suffixIndex < suffixElements.count else {
return nil
}
let element = suffixElements[suffixIndex]
suffixIndex += 1
return element
}
return next
}
}
}
有了上述两个方法，我们现在可以向任何想要的序列添加前缀和后缀。以下是我们的新api可能使用的一些例子:
// Including the parent folder in a subfolder iteration:
let allFolders = rootFolder.subfolders.prefixed(with: rootFolder)
// Append a draft as a suffix to a message sequence:
let messages = inbox.messages.suffixed(with: composer.message)
// Enclosing a string in brackets before iterating over it,
// without having to create any new string instances:
let characters = code.prefixed(with: "{").suffixed(with: "}")
虽然上面的所有示例都可以使用具体类型(如数组和字符串)实现，但使用WrappedSequence类型的好处是所有事情都可以惰性地完成 - 我们不会为了添加前缀和后缀而执行任何突变或评估任何序列 - 在性能关键的情况下，或者在处理大型数据集时，这是非常有益的。
Segmentation
接下来，让我们看看如何包装序列以创建它们的分段版本。在某些迭代中，仅仅知道当前元素是什么是不够的——我们可能还需要知道下一个和之前的元素。
当处理有索引的序列时，我们通常可以通过使用enumerated() API来实现这一点——它也使用序列包装来让我们访问当前元素及其索引:
for (index, current) in list.items.enumerated() {
let previous = (index > 0) ? list.items[index - 1] : nil
let next = (index < list.items.count - 1) ? list.items[index + 1] : nil
...
}
然而，上述技术不仅在调用站点上非常冗长，而且它还再次依赖于使用数组——或者至少某种形式的序列，使我们能够随机访问其元素——而许多序列，尤其是惰性序列，通常不会这样做。
相反，让我们再次使用WrappedSequence——通过跟踪之前和当前的元素，并随着迭代的继续更新，来创建一个包装序列，它惰性地将分段视图提供到其底层序列中:
extension Sequence {
typealias Segment = (
previous: Element?,
current: Element,
next: Element?
)
var segmented: WrappedSequence<Self, Segment> {
var previous: Element?
var current: Element?
var endReached = false
return WrappedSequence(wrapping: self) { iterator in
// Here our exit condition is either that we've
// reached the end of the underlying sequence, or
// that a first current element couldn't be created,
// because the sequence was empty.
guard !endReached,
let element = current ?? iterator.next() else {
return nil
}
let next = iterator.next()
let segment = (previous, element, next)
// Before we return the new segment, we update our
// iteration state to be ready for the next element:
previous = element
current = next
endReached = (next == nil)
return segment
}
}
}
现在，我们可以使用上面的API来创建任何序列的分段版本，无论何时我们需要在执行迭代时向前或向后看。例如，以下是我们如何使用分割来方便地确定我们何时到达了列表的末尾:
for segment in list.items.segmented {
addTopBorder()
addView(for: segment.current)
if segment.next == nil {
// We've reached the end, time to add a bottom border
addBottomBorder()
}
}
分段序列对于可视化地图、路径或图表也非常有用。这里我们使用片段来计算和渲染路径中每个节点的进入和退出方向:
for segment in path.nodes.segmented {
let directions = (
enter: segment.previous?.direction(to: segment.current),
exit: segment.next.map(segment.current.direction)
)
let nodeView = NodeView(directions: directions)
nodeView.center = segment.current.position.cgPoint
view.addSubview(nodeView)
}
现在，我们开始看到包装序列的真正威力——它们让我们可以将越来越复杂的算法隐藏在真正简单的API后面。调用者要对序列进行分段所需要做的就是访问任何序列上的分段属性，我们的底层实现负责其余的工作。
Recursion
最后，让我们看看如何通过包装序列对递归迭代建模。假设我们想提供一种简单的方法来递归地遍历一个值层次结构——其中层次结构中的每个元素都包含一组子元素。这是一件非常棘手的事情，所以如果我们能够在代码库中使用单个实现来执行所有此类迭代，那就太好了。
使用WrappedSequence，我们可以通过使用使用相同类型泛型约束的方法扩展Sequence来实现这一点，以确保每个元素都能够提供一个嵌套序列，该序列具有与原始序列相同的迭代器类型。为了能够动态访问每个嵌套序列，我们还将要求调用者提供应该用于递归的属性的KeyPath——给我们一个像这样的实现:
extension Sequence {
func recursive<S: Sequence>(
for keyPath: KeyPath<Element, S>
) -> WrappedSequence<Self, Element> where S.Iterator == Iterator {
var parentIterators = [Iterator]()
func moveUp() -> (iterator: Iterator, element: Element)? {
guard !parentIterators.isEmpty else {
return nil
}
var iterator = parentIterators.removeLast()
guard let element = iterator.next() else {
// We'll keep moving up our chain of parents
// until we find one that can be advanced to
// its next element:
return moveUp()
}
return (iterator, element)
}
return WrappedSequence(wrapping: self) { iterator in
// We either use the current iterator's next element,
// or we move up the chain of parent iterators in
// order to obtain the next element in the sequence:
let element = iterator.next() ?? {
return moveUp().map {
iterator = $0
return $1
}
}()
// Our recursion is performed depth-first, meaning
// that we'll dive as deep as possible within the
// sequence before advancing to the next element on
// the level above.
if let nested = element?[keyPath: keyPath].makeIterator() {
let parent = iterator
parentIterators.append(parent)
iterator = nested
}
return element
}
}
}
使用上面的方法，我们现在能够递归地迭代任何序列，不管它是如何在内部构造的——并且不必预先加载整个层次结构。例如，下面是我们如何使用这个新的API来递归地遍历文件夹层次结构:
let allFolders = folder.subfolders.recursive(for: \.subfolders)
for folder in allFolders {
try loadContent(from: folder)
}
我们还可以使用它来遍历树中的所有节点，或者递归遍历一组数据库记录——例如枚举组织中的所有用户组:
let allNodes = tree.recursive(for: \.children)
let allGroups = database.groups.recusive(for: \.subgroups)
一件事我们必须小心在递归迭代最终是不要循环引用,当某一路径使我们回到我们已经遇到了一个元素,这将导致我们遍历循环反复。
解决这个问题的一种方法是跟踪所有遇到的元素(但这可能在内存方面有问题)，以确保我们的数据集中不存在循环引用，或在每个调用站点处理此类情况(通过使用break、continue或return结束任何循环迭代)。
Conclusion
Sequence是标准库中最简单的协议之一——它只有一个方法要求——但它仍然是最强大的协议之一，尤其是当我们在它之上创建多少功能时。就像标准库为枚举等内容包含包装序列一样，我们也可以创建自己的包装器——这让我们可以将高级功能隐藏在真正简单的api背后。
而抽象从来都不是免费的,重要的是要考虑(和或许更重要的是,当不是)引入一个,如果我们可以构建抽象上的标准库提供了使用相同的约定,那么这些抽象概念通常更有可能经受住时间的考验。