Swift 中的 Sequence（二）

发表于 | 分类于 | | 阅读次数: |
字数统计: 13k | 阅读时长 ≈ 13 mins.

接上篇 Swift 中的 Sequence 基础篇

撰写本文时 Swift 版本是 4.0 beta。

值类型 Iterator 和引用类型 Iterator

值类型 Iterator

一般 Iterator 都是值类型的，值类型的 Iterator 的意思是：当把 Iterator 赋值给一个新变量时，是把原 Iterator 的所有状态拷贝了一份赋值给新的 Iterator，原 Iterator 在继续迭代时不会影响新的 Iterator。

例如用 stride 函数创建一个简单的 Sequence，它从 0 开始，到 9 截止，每次递增 1，即为 [0, 1, 2, …, 8, 9]。
然后获取到它的 Iterator，调用 next() 进行迭代。

1
2
3
4
let seq = stride(from: 0, to: 10, by: 1)
var i1 = seq.makeIterator()
i1.next() // Optional(0)
i1.next() // Optional(1)

然后做一个赋值操作，创建一个新的 i2，并把 i1 的值赋给 i2：

1
var i2 = i1

再用下面代码做测试

1
2
3
4
i1.next() // Optional(2)
i1.next() // Optional(3)
i2.next() // Optional(2)
i2.next() // Optional(3)

从打印的结果会发现：i1 和 i2 是两个独立的 Iterator，他们互不影响，赋值时对 i1 做了一份完整的拷贝。

所以这里的 Iterator 是一个值类型 Iterator。

引用类型 Iterator

可以把任何一个值类型 Iterator 用 AnyIterator 这个包一下就形成了一个引用类型的 Iterator。

1
2
var i3 = AnyIterator(i1)
var i4 = i3

做以下测试：

1
2
3
4
i3.next() // Optional(4)
i4.next() // Optional(5)
i3.next() // Optional(6)
i3.next() // Optional(7)

引用类型的 Iterator，再赋值给一个新的变量后，新的 Iterator 和原 Iterator 在进行迭代时会互相对对方产生影响。

基于函数的 Sequence、Iterator

AnyIterator 有一个初始化器，可以传入一个闭包，AnyIterator 会把这个闭包的内容作为调用 next() 时执行的内容。
这样创建一个 Iterator 时可以不用创建一个新的 class 或 struct。

例如我们可以这样创建一个斐波那契数列的 Iterator：

1
2
3
4
5
6
7
8
func fibsIterator() -> AnyIterator<Int> {
    var state = (0, 1)
    return AnyIterator {
        let upcomingNumber = state.0
        state = (state.1, state.0 + state.1)
        return upcomingNumber
    }
}

这样创建出来的 Iterator 是引用类型的。

然后可以用 AnySequence 来创建 Sequence，AnySequence 也有一个支持传入闭包的初始化器，于是可以把上面的函数名作为参数传入。

1
2
3
let fibsSequence = AnySequence(fibsIterator)
Array(fibsSequence.prefix(10))
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

另外，还有一种更简单的方法来创建 Sequence，用 Swift 标准库中的 sequence 函数。

这个函数有两个变体：
第一个是 sequence(first:next:)
第一个参数是 Sequence 中的第一个值，第二个参数传入一个闭包作为 next() 的内容。

例如创建一个从大到小的随机数 Sequence。

1
2
3
4
5
6
7
8
9
10
let randomNumbers = sequence(first: 100) { (previous: UInt32) in
    let newValue = arc4random_uniform(previous)
    guard newValue > 0 else {
        return nil
    }
    return newValue
}

Array(randomNumbers)
// [100, 90, 60, 35, 34, 21, 3]

第二个变体是 sequence(state:next:)
这个要更为强大，它可以在迭代过程中修改状态。

1
2
3
4
5
6
7
8
let fibsSequence2 = sequence(state: (0, 1)) { (state: inout (Int, Int)) -> Int? in
    let upcomingNumber = state.0
    state = (state.1, state.0 + state.1)
    return upcomingNumber
}

Array(fibsSequence2.prefix(10))
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

sequence(frist:next:) 和 sequence(state:next:) 的返回值类型是一个 UnfoldSequence。
在函数式编程中有 fold 和 unfold 的概念。
fold 是把一系列的值变为一个值，例如 reduce 就是一个 fold 操作。
unfold 是 fold 的反操作，把一个值展开成一系列的值。

无穷 Sequence 和有穷 Sequence

上面创建的斐波那契数列 Sequence 是一个无穷 Sequence，意思是如果不设置一个范围，它可以无限的迭代下去。

因此上面跑测试代码时用了 prefix 方法来取得一个有限的范围。

有穷 Sequence 则会在迭代完最后一个值后自动停止迭代。

SubSequence

Sequence 的 protocol 定义中有另一个 associatedtype 叫 SubSequence

1
2
3
4
5
6
protocol Sequence {
    associatedtype Iterator: IteratorProtocol
	
    associatedtype SubSequence
    //...
}

SubSequence 指定了对原 Sequence 切片后的返回值类型。

对原 Sequence 进行切片的操作有：

  • prefix and suffix
  • dropFirst and dropLast
  • split

如果没有指定 SubSequence 的类型，编译器会将其推导为 AnySequence<Iterator.Element> 类型

Sequence 的稳定性

由于 Sequence 的协议并没有要求 Sequence 一定是稳定的，所以 Sequence 也可以是不稳定的，也就是说，对 Sequence 进行多次迭代，每次迭代的结果可能会不一样。

1
2
3
4
5
6
7
for element in sequence {
    if ... some condition { break }
}

for element in sequence {
    // No defined behavior
}

看上面代码，对一个 sequence 进行两次 for-in 循环，如果第一次循环中做了某些破坏稳定性的操作，比如改变了状态，那么进行第二次 for-in 循环的结果是不可预知的。

如果一个 Sequence 也符合了 Collection 协议，那它一定是稳定的，例如 Array，Collection 协议会确保它是稳定的。

Swift 标准库中有一些函数创建出来的 Sequence 也能保证是稳定的，比如 stride(from:to:by:) 和 stride(from:through:by:)