translation
translation copied to clipboard
SwiftGGTeam
【中】Infinite Collections
无穷集合（Infinite Collections）
在 Swift Evolution 上有很多关于 Sequence(序列) 和 Collection(集合) 未来可能性的一些讨论，有许多问题，社区正在尝试解决并且已经提出了各种解决方案。其中一些方法包括创建无穷集合，每次有人提出时，总有人问他们如何工作。在类型系统中没什么能阻止我们创建无穷集合 —— 这只不过是一个语义上的约束 —— 这意味着我们现在就可以用 Swift 写出无穷集合，但我们不应该这么做。它让其他人书写代码时对我们的对象产生错误的假设。在这篇文章中，我将演示如何将一个无穷序列变成一个无穷集合。
斐波那契(Fibonacci)数列是一个伟大的无穷序列，快速复习下，该序列中的每个元素都是前两个数字的和。
Swift 提供了优雅易用的方式快速定义一个新序列，有两个实用方法分别是 sequence(state:next:) 和 sequence(first:next) 。在这里我们将使用 state 版本:
let fib = sequence(state: (0, 1), next: { state -> Int? in
let next = state.0 + state.1
state = (state.1, next)
return next
})
调用 fib.prefix(10) 将得到前10个斐波那契数。
注意这是一个无穷序列！如果你尝试 map 这个序列(类型系统完全允许)，你的程序将会无限执行直到它耗尽整数或宇宙热寂，无论哪个先出现。
要转换成一个无穷集合，我们需要考虑一些事情。首先，我们如何将一个索引表示为一个值？对于一个数组，它可能是一个表示内存偏移量的数字。对于字符串，它可能表示该字符首地址的字节偏移量。它需要是一些值让我们在常数时间内检索出索引处的值，或者是时间复杂度O(1)。
关于迭代器一个有趣的事情是，它们的当前状态表示在常数时间得到下一个值所需的数据。因此，任何确定性序列都可以表示成一个集合，通过使用迭代器的状态当作索引。我们的 state 之前是 (Int, Int) ，所以我们可以开始使用该类型作为我们的 Index 。我们用以下四个方法来定义一个集合：
struct FibonacciCollection: Collection {
typealias Index = (Int, Int)
var startIndex: Index {
return (0, 1)
}
func index(after previous: Index) -> Index {
return (previous.1, previous.0 + previous.1)
}
var endIndex: Index {
fatalError("This collection has no endIndex, because it is infinite")
}
subscript(index: Index) -> Int {
return index.0 + index.1
}
}
我们可以使用 (Int, Int)（我们的状态是斐波那契数列时的序列）当作索引，并使用 (0, 1) 作为起始值（就像我们的序列一样）。
但使用这种方法也有一些问题。要遍历任意集合，你可以想象构建一个大的 while 循环：
var index = collection.startIndex
while index < endIndex {
let value = collection[index]
// use `value` somehow
index = collection.index(after: index)
}
（这不是我们使用集合的方式，因为我们知道它是无穷的，但这就是标准集合的工作方式。）有两个问题特别明显，首先我们需要 Index 类型实现 Comparalbe —— 因此我们不能使用元组(Tuple) —— 并且我们需要定义 endIndex 这样我们就可以对它进行检查 —— 因此我们不能使用fatalError（叮！）。
现在我们需要一种新的索引类型：具有可比性 Comparable 的和不可达（unreachable）的。不可达（unreachable）的值应该“大于”所有可达值（因为它在集合的"末尾"）。我们首先尝试将它构建成拥有两个整型成员变量的 struct 结构体，来解决可比性问题：
struct FibIndex {
let first: Int
let second: Int
}
extension FibIndex: Comparable {
static func == (lhs: FibIndex, rhs: FibIndex) -> Bool {
return lhs.first == rhs.first && lhs.second == rhs.second
}
static func < (lhs: FibIndex, rhs: FibIndex) -> Bool {
return lhs.first < rhs.first
}
}
这解决了可比性问题，但没有解决不可达性问题。我们需要一种方式来表示一个更大的值，一个与其他所有值不同的值。让我们从头开始，但这次使用枚举enum:
enum FibIndex {
case reachable(Int, Int)
case unreachable
}
这能够解决我们两个问题。不幸地是，它在书写 == 和 < 时相当麻烦:
extension FibIndex: Comparable {
static func == (lhs: FibIndex, rhs: FibIndex) -> Bool {
switch (lhs, rhs) {
case (.unreachable, .unreachable):
return true
case let (.reachable(l1, l2), .reachable(r1, r2)):
return l1 == r1 && l2 == r2
case (.reachable, .unreachable):
return false
case (.unreachable, .reachable):
return false
}
}
static func < (lhs: FibIndex, rhs: FibIndex) -> Bool {
switch (lhs, rhs) {
case (.unreachable, .unreachable):
return false
case let (.reachable(l1, l2), .reachable(r1, r2)):
return l1 < r1
case (.reachable, .unreachable):
return true
case (.unreachable, .reachable):
return false
}
}
}
通过更好的模式匹配，有一些方法可以简化代码，但是在这里我将使用完整的模式来保证明确性。
让我们添加一些辅助方法：
extension FibIndex {
var sum: Int {
switch self {
case .unreachable:
fatalError("Can't get the sum at an unreachable index")
case let .reachable(first, second):
return first + second
}
}
var next: FibIndex {
switch self {
case .unreachable:
fatalError("Can't get the next value of an unreachable index")
case let .reachable(first, second):
return .reachable(second, first + second)
}
}
}
现在我们可以完成我们的斐波纳契数列了：
struct FibonacciCollection: Collection {
typealias Index = FibIndex
var startIndex: Index {
return .reachable(0, 1)
}
func index(after previous: Index) -> Index {
return previous.next
}
var endIndex: Index {
return .unreachable
}
subscript(index: Index) -> Int {
return index.sum
}
}
这是相当好的！我们免费获得 Sequence 和 Collection 协议中所有方法。不幸地是，这仍然是个无穷集合，就像一个无穷序列一样，我们不能在它上面使用 map , 否则我们将永远循环。有一些新的东西在 Collection 协议上我们也不能用 —— 比如获取集合元素的 count。它也将永远循环。
在这里还有一个我想要展示的调整，它提取了斐波纳契数列的特殊部分并创建一个泛型的 InfiniteCollectionIndex 。为此，我们将保留基本的枚举结构，但是将 .reachable 的 (Int, Int) 类型替换成一个泛型 ，我们需要在这里放一个通用的占位符。又会是怎么样呢？
让我们调用内部索引类型 WrappedIndex 。我们需要确保包装后的 Index 具有可比性：
enum InfiniteCollectionIndex<WrappedIndex: Comparable>: Comparable {
case reachable(WrappedIndex)
case unreachable
}
Equatable 和 Comparable 的实现几乎相同，但取代了对整数的比较，它们直接转为 WrappedIndex的比较 ：
extension InfiniteCollectionIndex: Comparable {
static func == (lhs: InfiniteCollectionIndex, rhs: InfiniteCollectionIndex) -> Bool {
switch (lhs, rhs) {
case (.unreachable, .unreachable):
return true
case let (.reachable(left), .reachable(right)):
return left == right
case (.reachable, .unreachable):
return false
case (.unreachable, .reachable):
return false
}
}
static func < (lhs: InfiniteCollectionIndex, rhs: InfiniteCollectionIndex) -> Bool {
switch (lhs, rhs) {
case (.unreachable, .unreachable):
return false
case let (.reachable(left), .reachable(right)):
return left < right
case (.reachable, .unreachable):
return true
case (.unreachable, .reachable):
return false
}
}
}
还有一些辅助方法，因为会在很多情况下我们会假设.unreachable的值是恰当的，不可达的。
extension InfiniteCollectionIndex {
func assumingReachable<T>(_ block: (WrappedIndex) -> T) -> T {
switch self {
case .unreachable:
fatalError("You can't operate on an unreachable index")
case let .reachable(wrapped):
return block(wrapped)
}
}
func makeNextReachableIndex(_ block: (WrappedIndex) -> WrappedIndex) -> InfiniteCollectionIndex {
return .reachable(assumingReachable(block))
}
}
这个函数接受一个 block，假设该值是 .reachable ，则返回该 block 返回的内容。如果值是 .unreachable ，它会崩溃。
我们现在可以使用上面 struct 形式的 FibIndex ：
struct FibIndex {
let first: Int
let second: Int
}
extension FibIndex: Comparable {
static func == (lhs: FibIndex, rhs: FibIndex) -> Bool {
return lhs.first == rhs.first && lhs.second == rhs.second
}
static func < (lhs: FibIndex, rhs: FibIndex) -> Bool {
return lhs.first < rhs.first
}
}
在这里我不想深入过多细节，但这里允许我们定义简单地 Comparable 索引类型，并很容易使它们成为无穷索引。
struct FibonacciCollection: Collection {
typealias Index = InfiniteCollectionIndex<FibIndex>
var startIndex: Index {
return .reachable(FibIndex(first: 0, second: 1))
}
func index(after previous: Index) -> Index {
return previous.makeNextReachableIndex({
FibIndex(first: $0.second, second: $0.first + $0.second)
})
}
var endIndex: Index {
return .unreachable
}
subscript(index: Index) -> Int {
return index.assumingReachable({ $0.first + $0.second })
}
}
目前还不清楚 Swift 的集合模型的趋势最终转变到哪一个方向，但如果当无穷集合在 Swift 里成为合法时，这个技巧将帮助你容易地定义它们。
无穷集合（Infinite Collections）
在 Swift Evolution 上有很多关于 Sequence(序列) 和 Collection(集合) 未来可能性的一些讨论，社区针对这些问题做了大量的尝试，同时也提出了各种解决方案。其中一些方案包括创建无穷集合的可行性，每次有人提出创建无穷集合这个方案时，总有人问他们如何工作。实际上在类型系统中创建无穷集合并没有什么障碍 —— 这只不过是一个纯粹的语义约束 —— 这意味着我们现在就可以用 Swift 写出无穷集合，但现实中我们不建议这么做。它让其他人书写代码时对我们的对象产生错误的假设。在这篇文章中，我将演示如何将一个无穷序列变成一个无穷集合。
斐波那契(Fibonacci)数列是一个伟大的无穷序列，我们快速回忆一下，斐波那契数列中的每个元素都是前两个数字的和。
Swift 提供了优雅易用的方式快速定义一个新序列，有两个实用方法分别是 sequence(state:next:) 和 sequence(first:next) 。在这里我们将使用 state 版本:
let fib = sequence(state: (0, 1), next: { state -> Int? in
let next = state.0 + state.1
state = (state.1, next)
return next
})
调用 fib.prefix(10) 将得到前10个斐波那契数。
注意这是一个无穷序列！虽然类型系统允许，但是如果你尝试 map 这个序列()，你的程序将会陷入无尽的循环中，直到耗尽世间所有的整数，或者直至宇宙毁灭，鬼知道哪件事先发生。
要转换成一个无穷集合，我们需要考虑一些事情。首先，我们如何将一个索引表示为一个值？对于一个数组，它可能是一个表示内存偏移量的数字。对于字符串，它可能表示该字符首地址的字节偏移量。它需要是一些值让我们在常数时间内检索出索引处的值，或者说时间复杂度是 O(1)。
关于迭代器一个有趣的事情是，它们的当前状态表示在常数时间得到下一个值所需的数据。因此，任何确定性序列都可以表示成一个集合，通过使用迭代器的状态当作索引。我们的 state 之前是 (Int, Int) ，所以我们可以开始使用该类型作为我们的 Index 。我们用以下四个方法来定义一个集合：
struct FibonacciCollection: Collection {
typealias Index = (Int, Int)
var startIndex: Index {
return (0, 1)
}
func index(after previous: Index) -> Index {
return (previous.1, previous.0 + previous.1)
}
var endIndex: Index {
fatalError("This collection has no endIndex, because it is infinite")
}
subscript(index: Index) -> Int {
return index.0 + index.1
}
}
我们可以使用 (Int, Int)（我们的状态是斐波那契数列时的序列）当作索引，并使用 (0, 1) 作为起始值（就像我们的序列一样）。
但使用这种方法也有一些问题。要遍历任意集合，你可以想象成一个大的 while 循环：
var index = collection.startIndex
while index < endIndex {
let value = collection[index]
// use `value` somehow
index = collection.index(after: index)
}
（这不是我们使用集合的方式，因为我们知道它是无穷的，可标准集合的工作方式就是这样。）同时有两个问题特别明显，首先我们需要 Index 类型实现 Comparalbe —— 因此我们不能使用元组(Tuple) 。其次我们需要定义 endIndex 这样我们才可以对它进行检查 —— 因此我们不能使用fatalError（叮！）。
现在我们需要一种新的索引类型：具有可比性 Comparable 的和不可访问性（unreachable）。不可访问（unreachable）的值应该“大于”所有可访问的值（因为它在集合的"末尾"）。我们首先尝试将它构建成拥有两个整型成员变量的 struct 结构体，来解决可比性问题：
struct FibIndex {
let first: Int
let second: Int
}
extension FibIndex: Comparable {
static func == (lhs: FibIndex, rhs: FibIndex) -> Bool {
return lhs.first == rhs.first && lhs.second == rhs.second
}
static func < (lhs: FibIndex, rhs: FibIndex) -> Bool {
return lhs.first < rhs.first
}
}
这解决了可比性问题，但没有解决不可访问性问题。我们需要一种方式来表示一个更大的值，一个与其他所有值不同的值。让我们从头开始，但这次使用枚举enum:
enum FibIndex {
case reachable(Int, Int)
case unreachable
}
这能够解决我们两个问题。不幸地是，它在书写 == 和 < 时相当麻烦:
extension FibIndex: Comparable {
static func == (lhs: FibIndex, rhs: FibIndex) -> Bool {
switch (lhs, rhs) {
case (.unreachable, .unreachable):
return true
case let (.reachable(l1, l2), .reachable(r1, r2)):
return l1 == r1 && l2 == r2
case (.reachable, .unreachable):
return false
case (.unreachable, .reachable):
return false
}
}
static func < (lhs: FibIndex, rhs: FibIndex) -> Bool {
switch (lhs, rhs) {
case (.unreachable, .unreachable):
return false
case let (.reachable(l1, l2), .reachable(r1, r2)):
return l1 < r1
case (.reachable, .unreachable):
return true
case (.unreachable, .reachable):
return false
}
}
}
通过更好的模式匹配，有一些方法可以简化代码，但是在这里我将使用完整的模式来保证明确性。
让我们添加一些辅助方法：
extension FibIndex {
var sum: Int {
switch self {
case .unreachable:
fatalError("Can't get the sum at an unreachable index")
case let .reachable(first, second):
return first + second
}
}
var next: FibIndex {
switch self {
case .unreachable:
fatalError("Can't get the next value of an unreachable index")
case let .reachable(first, second):
return .reachable(second, first + second)
}
}
}
现在我们可以完成我们的斐波纳契数列了：
struct FibonacciCollection: Collection {
typealias Index = FibIndex
var startIndex: Index {
return .reachable(0, 1)
}
func index(after previous: Index) -> Index {
return previous.next
}
var endIndex: Index {
return .unreachable
}
subscript(index: Index) -> Int {
return index.sum
}
}
这看起来很不错！我们获得了 Sequence 和 Collection 协议中所有方法。然而不幸地是，这仍然是个无穷集合，就像一个无穷序列一样，我们不能在它上面使用 map , 否则我们将永远循环。有一些新的东西在 Collection 协议上我们也不能用 —— 比如获取集合元素的 count。
在这里还有一处调整，它提取了斐波纳契数列的特殊部分并创建一个泛型的 InfiniteCollectionIndex 。为此，我们将保留基本的枚举结构，而不是具有（Int，Int）类型的 .reachable 案例 ，我们需要在这里放一个通用的占位符。
让我们调用内部索引类型 WrappedIndex 。我们需要确保包装后的 Index 具有可比性：
enum InfiniteCollectionIndex<WrappedIndex: Comparable>: Comparable {
case reachable(WrappedIndex)
case unreachable
}
Equatable 和 Comparable 的实现几乎相同，但同对整数的比较而言，它们直接转为对 WrappedIndex的比较 ：
extension InfiniteCollectionIndex: Comparable {
static func == (lhs: InfiniteCollectionIndex, rhs: InfiniteCollectionIndex) -> Bool {
switch (lhs, rhs) {
case (.unreachable, .unreachable):
return true
case let (.reachable(left), .reachable(right)):
return left == right
case (.reachable, .unreachable):
return false
case (.unreachable, .reachable):
return false
}
}
static func < (lhs: InfiniteCollectionIndex, rhs: InfiniteCollectionIndex) -> Bool {
switch (lhs, rhs) {
case (.unreachable, .unreachable):
return false
case let (.reachable(left), .reachable(right)):
return left < right
case (.reachable, .unreachable):
return true
case (.unreachable, .reachable):
return false
}
}
}
还有一些辅助方法，因为会在很多情况下我们会假设.unreachable的值是恰当的，不可访问的。
extension InfiniteCollectionIndex {
func assumingReachable<T>(_ block: (WrappedIndex) -> T) -> T {
switch self {
case .unreachable:
fatalError("You can't operate on an unreachable index")
case let .reachable(wrapped):
return block(wrapped)
}
}
func makeNextReachableIndex(_ block: (WrappedIndex) -> WrappedIndex) -> InfiniteCollectionIndex {
return .reachable(assumingReachable(block))
}
}
这个函数接收一个 block，假设该值是 .reachable ，则返回该 block 返回的内容。如果值是 .unreachable ，它会崩溃。
我们现在可以使用上面 struct 形式的 FibIndex ：
struct FibIndex {
let first: Int
let second: Int
}
extension FibIndex: Comparable {
static func == (lhs: FibIndex, rhs: FibIndex) -> Bool {
return lhs.first == rhs.first && lhs.second == rhs.second
}
static func < (lhs: FibIndex, rhs: FibIndex) -> Bool {
return lhs.first < rhs.first
}
}
在这里我不想深入过多细节，但这里允许我们定义简单地 Comparable 索引类型，并很容易使它们成为无穷索引。
struct FibonacciCollection: Collection {
typealias Index = InfiniteCollectionIndex<FibIndex>
var startIndex: Index {
return .reachable(FibIndex(first: 0, second: 1))
}
func index(after previous: Index) -> Index {
return previous.makeNextReachableIndex({
FibIndex(first: $0.second, second: $0.first + $0.second)
})
}
var endIndex: Index {
return .unreachable
}
subscript(index: Index) -> Int {
return index.assumingReachable({ $0.first + $0.second })
}
}
目前还不清楚 Swift 的集合模型的趋势最终转变到哪一个方向，但如果当无穷集合在 Swift 里成为合法时，这个技巧将帮助你容易地定义它们。
第一次翻译的文章，感觉水平真的棒棒！但是部分语句还是翻译的比较生硬，建议能够跳出原文的局限，用简单易懂的语言去描述，加油。原文有部分被我修改了，建议重头再看一下。