本篇介紹 Rx 的重要基礎概念 Iterator pattern（迭代器模式）。

（撰於 2017-08-15，基於 Swift 3.1）

Definition

迭代器模式（Iterator pattern） 提供一個迭代器，讓使用者透過特定方式走訪序列（sequence）中的元素，而不需知道底層的演算法。

Application

Iterator pattern 是最基本的設計模式之一，基本上大部分語言的 for-in loop 都是 iterator pattern 的實作。我們可以說 Python 的 for x in iterable 符合 iterator pattern，因為 Python 將該 iterable 封裝起來，使用者對 iterator 如何取得下一個 element 並不知情；Swift 的 for x in Sequence 中 Sequence protocol 也有 iterator 介面，並提供了 default implementation。

相反地， C 的 for (int i = 0; i < n; i++) 通常不認為是 iterator pattern，因為使用者知道底層資料儲存在連續的記憶體空間中，也必須自行透過指針迭代。

透過 iterator 封裝的序列（或集合），讓調用者不需關係實作，只需使用統一的 for loop，或是 map、reduce、filter 等高階函數，即操作序列中的元素，完全與演算法解耦合。

Requirements

一般來說，要符合 iterator pattern 的實作，通常會有以下幾個介面：

  1. 一個取得下一個 element 的方法，通常是 next
  2. 告知使用者是否仍有下個 element 的方法，各語言有自己對應的實作，如：
  • 拋出 Exception（Python）
  • 主動 call hasNext 方法（Java）
  • 回傳 flag 判斷迭代是否完成（JavaScript）
  • 直接回傳 nil（Swift）

IteratorProtocol & Sequence

在深入 iterator pattern 前，先來理解 Swift 最重要的兩個 protocol：IteratorProtocol 與 Sequence。

Swift 實作 iterator 須符合 IteratorProtocol，該 protocol 要求一個 next method。雖然簡單，但要實作 iterator pattern 也是滿繁瑣的。我們直接看例子。

// 宣告一個 countdown 用的 iterator struct，每次迭代時會將當前計數減一。
struct CountdownIterator: IteratorProtocol {
    var count: Int
    mutating func next() -> Int? {
        guard count > 0 else { return nil }
        count -= 1
        return count
    }
}

其實這樣就做完我們的 iterator 了，我們可以嘗試使用 while loop 使用這個倒數計時器。

var it = CountdownIterator(count: 5)
while let v = it.next() {
  print(v)
}
/// 4 3 2 1 0

不過通常我們會希望將 next 方法藏起來，利用簡單的 for-in loop 迭代，這時候就該 Sequence protocol 出場。Sequence protocol 提供一個按序迭代的介面，讓調用者可好整以暇的使用。只要符合 Comparable、Equatable 等 protocol，Sequence 甚至提供許多方便的 default implementations。

一般來說，Sequence 需有 iterator 的 associatedType，以及 makeIterator 方法，提供 sequence 製造 iterator 的介面。

struct Countdown: Sequence {
    let count: Int

    func makeIterator() -> CountdownIterator {
        return CountdownIterator(countdown: self.count)

    }
}

let countdown = Countdown(count: 5)
for i in countdown {
    print(i)
}
/// 4 3 2 1 0
countdown.forEach { print($0) } // ⚠️： Sequence 並沒有保證 repeated access
/// 4 3 2 1 0

這些步驟看起來異常繁瑣，我們可以利用 Swift 提供的 default implementation 減少 trivial part。若同時符合 Sequence 與 IteratorProtocol，只要實作 next方法，則 Sequence 會自動產生 makeIterator。

struct Countdown: Sequence, IteratorProtocol {
    var count: Int
    mutating func next() -> Int? {
        guard count > 0 else { return nil }
        count -= 1
        return count
    }
}

// 可以透過 default implementation 直接使用 `map` 方法！
Countdown(count: 5).map { $0 * 5 }
/// [20, 15, 10, 5, 0]

Collection protocols

Sequence protocol 僅提供迭代方法，並不能保證序列能否走訪多遍，也沒有提供 subscript（下標）。Collection protocol 提供 subscript 的容器介面，並建議實作 access elements 預期為 O(1) 複雜度。
不過實際情況因實作而異，例如 Doubly linked-list 遵循繼承自 Collection 的 BidirectionalCollection protocol，卻無法如符合 RandomAccessCollection 的 Array 一樣有 O(1) 的隨機存取操作。

這些 Collection protocols 加強了 Iterator pattern 應用面的生產力，演算法能以更豐富的方式呈現給使用者。好比 Swift Standard Library 中的 Array、Dictionary 和 String 也都是實作 Collection protocol 的案例，而這些的集合實作就非常夠開發者使用了，幾乎不需考慮底層的演算法，更甚不必接觸任何 Iterator。

Conclusion

Iterator pattern 封裝了許多演算法，讓使用者能夠專注在更高層次的邏輯上；iterator pattern 同時也提供迭代完畢的訊息，許多程式間通訊得以透過 iterator 完成不同的任務。近來很流行的 generator／coroutine 都是建立於 iterator pattern 上，Rx 的設計理念也是吸收 iterator pattern 的精華，提供 Observable no data available 與 error 的重要特性。

Reference