這篇文章會用 TDD 手刻 Sequence 版的 myTake(中間操作)、myFirst 和 myToList(終端操作)，把中間操作和終端操作的分類搞清楚

Kotlin ↔ C# 對照表

C# 文件裡把這兩種叫 deferred execution 和 immediate execution，意思一樣，中間操作延遲執行，終端操作立刻執行

中間操作和終端操作的差別

day 29 已經看過 filter 和 map 的 lazy 行為，這裡做個整理

中間操作(intermediate)：回傳一個新的 Sequence。不觸發任何計算，只是在 pipeline 上加一個節點

終端操作(terminal)：觸發整條 pipeline，從最外層往裡面拉元素，產出具體結果(List、數字、布林值等)

sequenceOf(1, 2, 3, 4, 5)
    .filter { it > 2 }    // 中間：回傳 FilteringSequence
    .map { it * 10 }      // 中間：回傳 TransformingSequence
    .toList()              // 終端：觸發整條 pipeline → [30, 40, 50]

沒有終端操作，前面的中間操作都不會執行，C# LINQ 的 deferred 運算子也有相同行為

stdlib 這兩類操作加起來一大串。中間操作有 filter、map、take、drop、distinct、sorted、zip、flatMap，終端操作有 toList、first、count、sum、find、any、fold，一篇文章不可能全部手刻一遍

所以這篇挑三個，各代表一種骨架：myTake 是中間操作，示範「包一層 Sequence class 加自訂 Iterator」；myFirst 是終端操作，示範「拉到就停」的短路；myToList 同樣是終端操作，但要走完全部才收得完

其他操作多半只是這三種骨架換個判斷條件，這三個看懂之後，剩下的可以自己推。例外是 sorted，它被歸在中間操作，卻要先收完上游才產得出第一筆，後面會單獨拿出來講。distinct 也要記狀態，但還能邊拉邊吐，不算這一類

Iterator Protocol 與短路

中間/終端的分工背後是 Iterator Protocol，每個 Sequence 都有 iterator()，Iterator 又只有 hasNext() 和 next() 兩個方法

整個 lazy pipeline 就建在這兩個方法的拉取鏈上，可以看 filter 接 take 和 first 怎麼跑

seq.filter { ... }.take(3).first()

1. first()(終端)向 take 的 iterator 喊 next()
2. take iterator 還有 quota，向 filter 的 iterator 喊 next()
3. filter iterator 從上游拉一個元素，套 predicate，符合就回傳
4. 元素一路被拉到 first()，first() 拿到值就回傳結果，後面沒人再喊 next()

短路就是這麼做到的。first() 拿到結果就停；take 沒被再喊就不再拉；filter 沒被再喊也不再 evaluate，一串「不主動」累積起來就是 lazy

C# LINQ 的 IEnumerator 也用 MoveNext() 與 Current 逐步取得資料，Java Stream 對外則以 Spliterator、pipeline 與 Sink 進行遍歷，sequential Stream 同樣支援延遲執行與短路，但底層機制不是這裡的 Iterator 包裝鏈

TDD 實作 myTake(中間操作)

take 在 Sequence 裡面特別有用，因為它能讓無限序列變安全

Red：先寫測試

@Test
fun `take from sequence`() {
    val seq = sequenceOf(1, 2, 3, 4, 5).myTake(3)
    assertEquals(listOf(1, 2, 3), seq.toList())
}

@Test
fun `take from infinite sequence`() {
    val seq = myGenerateSequence(1) { it + 1 }.myTake(5)
    assertEquals(listOf(1, 2, 3, 4, 5), seq.toList())
}

@Test
fun `take is lazy`() {
    var count = 0
    val seq = sequenceOf(1, 2, 3, 4, 5).myMap { count++; it }.myTake(2)
    assertEquals(0, count)
    val result = seq.toList()
    assertEquals(listOf(1, 2), result)
    assertEquals(2, count)
}

@Test
fun `take 0 returns empty`() {
    val seq = sequenceOf(1, 2, 3).myTake(0)
    assertEquals(emptyList<Int>(), seq.toList())
}

@Test
fun `take negative throws`() {
    assertThrows(IllegalArgumentException::class.java) {
        sequenceOf(1, 2, 3).myTake(-1)
    }
}

第二個測試的 myGenerateSequence(1) { it + 1 } 產出無限的自然數，搭配 myTake(5) 只取前 5 個。沒有 take，toList() 會跑到記憶體炸掉

後兩個是邊界和例外：myTake(0) 回傳空序列，myTake(-1) 拋 IllegalArgumentException。負數沒有合理語意，所以擋在前面

Green：最小實作

class MyTakingSequence<T>(
    private val source: Sequence<T>,
    private val count: Int
) : Sequence<T> {
    init {
        require(count >= 0) { "count must be non-negative, but was $count." }
    }

    override fun iterator(): Iterator<T> = object : Iterator<T> {
        var left = count
        val sourceIterator = source.iterator()

        override fun hasNext(): Boolean = left > 0 && sourceIterator.hasNext()

        override fun next(): T {
            if (left == 0) {
                throw NoSuchElementException()
            }
            left--
            return sourceIterator.next()
        }
    }
}

fun <T> Sequence<T>.myTake(count: Int): Sequence<T> {
    return MyTakingSequence(this, count)
}

left 追蹤還能拿幾個。每次 next() 就減一，減到 0 就停。hasNext() 同時檢查 left > 0 和 source 還有沒有元素

init 區塊的 require(count >= 0) 在建立 Sequence 的當下就擋下負數，不會等到開始拉元素才爆

跟 day 22 Collection 版的 myTake 比較：Collection 版用 break 跳出迴圈，Sequence 版用 left 計數器控制 Iterator，概念一樣，但機制完全不同

Refactor：往 stdlib 的寫法靠近

這個版本其實已經很接近 stdlib 的 TakeSequence 了。同樣用 var left 倒數，next() 先擋 left == 0，hasNext() 同時檢查 left > 0 和上游

如果有人不先 hasNext() 就直接 next()，處理方式也跟 stdlib 一樣：left == 0 由自己擋下，上游沒元素時就讓 sourceIterator.next() 的 NoSuchElementException 透出去，符合 Iterator 約定

stdlib 讓 TakeSequence 實作 DropTakeSequence 介面，take 接 take 時可以合併成一次運算，這純粹是效能最佳化，後面對照原始碼時再看

TDD 實作 myFirst(終端操作)

Red：先寫測試

@Test
fun `first from sequence`() {
    val result = sequenceOf(1, 2, 3).myFirst()
    assertEquals(1, result)
}

@Test
fun `first with predicate`() {
    val result = sequenceOf(1, 2, 3, 4, 5).myFirst { it > 3 }
    assertEquals(4, result)
}

@Test
fun `first empty throws`() {
    assertThrows(NoSuchElementException::class.java) {
        emptySequence<Int>().myFirst()
    }
}

@Test
fun `first triggers pipeline and stops early`() {
    var filterCount = 0
    val result = sequenceOf(1, 2, 3, 4, 5)
        .myFilter { filterCount++; it > 2 }
        .myFirst()
    assertEquals(3, result)
    assertEquals(3, filterCount)  // 只檢查到 3
}

最後一個測試驗證 first 拿到答案就停。filterCount 是 3 而不是 5，表示元素 4 和 5 根本沒被 filter 處理

Green：最小實作

fun <T> Sequence<T>.myFirst(): T {
    val iterator = this.iterator()
    if (!iterator.hasNext()) {
        throw NoSuchElementException("Sequence is empty.")
    }
    return iterator.next()
}

fun <T> Sequence<T>.myFirst(predicate: (T) -> Boolean): T {
    for (element in this) {
        if (predicate(element)) {
            return element
        }
    }
    throw NoSuchElementException("Sequence contains no element matching the predicate.")
}

終端操作比中間操作簡單。不需要建新的 Sequence class，直接從 Iterator 拉元素就好

myFirst() 拿到第一個就 return，後面的元素不會被碰到。這個 return 會讓整條 pipeline 停下來，因為沒有人再呼叫 Iterator 的 next() 了

跟 day 06 Collection 版的 first 比較很有意思，兩邊的 first 找到符合的元素都是立刻 return，看起來行為一樣，差別藏在前面的步驟

Collection 版 list.filter { ... }.first { ... } 的 filter 會先把整個 List 跑完，產生一個中間 List，first 才在那個中間 List 上找

Sequence 版 seq.filter { ... }.first { ... } 的 filter 是 lazy 的，first 拉到符合的就停，後面的元素連 filter 都沒進去，上面 first triggers pipeline and stops early 那個測試驗證的就是這件事

Refactor：往 stdlib 的寫法靠近

兩個 myFirst 已經是直觀的最小寫法。stdlib 的無參數 first() 也是先檢查 hasNext() 再取 next()，帶 predicate 的版本也是 for 迴圈逐一比對，跟我們一致。唯一差別是 stdlib 把「空序列」和「找不到符合元素」的錯誤訊息寫得更明確，這裡照樣保留兩種訊息就夠了，沒有要再最佳化的地方

TDD 實作 myToList(終端操作)

Red：先寫測試

@Test
fun `toList materializes sequence`() {
    val result = sequenceOf(1, 2, 3).myToList()
    assertEquals(listOf(1, 2, 3), result)
}

@Test
fun `toList triggers entire pipeline`() {
    var count = 0
    val result = sequenceOf(1, 2, 3, 4, 5)
        .myFilter { it % 2 == 0 }
        .myMap { count++; it * 10 }
        .myToList()
    assertEquals(listOf(20, 40), result)
    assertEquals(2, count)
}

Green：最小實作

fun <T> Sequence<T>.myToList(): List<T> {
    val result = ArrayList<T>()
    for (element in this) {
        result.add(element)
    }
    return result
}

toList() 是最常用的終端操作，它把整條 pipeline 的結果收進一個 ArrayList 裡

Refactor：往 stdlib 的寫法靠近

我們的 myToList 直接 ArrayList<T>() 加上 for-each。stdlib 的 Sequence.toList() 多繞一層：先 toMutableList() 收進 ArrayList，再 optimizeReadOnlyList() 收尾，讓空集合回傳 emptyList()、單元素集合回傳 listOf(this[0]) 這種更輕量的唯讀 List

差別在 stdlib 想省掉小集合的記憶體，但對 Sequence 來說我們事先不知道長度，沒辦法像 day 22 Collection 版那樣預先指定 ArrayList 容量，所以這裡的 for-each 版本已經是 Sequence 能做到的最直接寫法

sorted：需要緩衝的中間操作

大部分中間操作都是 lazy 的，但 sorted 是例外

val result = sequenceOf(3, 1, 4, 1, 5)
    .filter { it > 1 }
    .sorted()          // 必須先收集所有元素才能排序
    .take(2)
    .toList()

sorted() 回傳 Sequence，建立管線時仍不會讀取來源；但第一次開始走訪時，它必須先收集並排序所有上游元素，才能產出第一筆結果

stdlib 文件把這類操作稱為 stateful intermediate operation，它仍是 deferred execution，只是無法逐元素串流輸出

與 stdlib 原始碼比較

原始碼位置：kotlin.sequences 的 Sequences.kt 與 _Sequences.kt

我們手刻的三個函式跟 stdlib 的對應實作放在一起看，差異都很小

take 對應 stdlib 的 TakeSequence。骨架一樣是包一層 Sequence、Iterator 裡放一個 var left = count 倒數

internal class TakeSequence<T>(
    private val sequence: Sequence<T>,
    private val count: Int,
) : Sequence<T>, DropTakeSequence<T> {
    init {
        require(count >= 0) { "count must be non-negative, but was $count." }
    }

    override fun iterator(): Iterator<T> = object : Iterator<T> {
        var left = count
        val iterator = sequence.iterator()

        override fun next(): T {
            if (left == 0) throw NoSuchElementException()
            left--
            return iterator.next()
        }

        override fun hasNext(): Boolean = left > 0 && iterator.hasNext()
    }

    // 實作 DropTakeSequence 要求的兩個成員，此處省略
}

跟我們的 MyTakingSequence 幾乎逐行一致，連 require 的錯誤訊息都一樣。多出來的 DropTakeSequence 介面是給 stdlib 內部用的，它要求再實作 drop(n) 和 take(n) 兩個成員(上面省略了)，這樣 take 接 take、drop 接 take 時可以合併成一次運算，少包一層 Sequence。這是效能最佳化，不影響行為，所以我們的版本省掉它也跑得對

first() 對應 stdlib 的 Sequence.first()，一樣是先 hasNext() 再 next()，空序列就拋 NoSuchElementException；帶 predicate 的版本也是 for 迴圈逐一比對。toList() 對應 stdlib 的 Sequence.toList()，差別只在 stdlib 多包一層 toMutableList() 加 optimizeReadOnlyList()，前面 Refactor 已經說過

至於 sorted，stdlib 文件把它歸類成 stateful intermediate operation。它不像 filter 和 map 可以逐元素處理，排序得看到所有元素才能決定順序，所以第一次走訪時會先把整個上游收進一個 List 排好，再用排好的結果產生 Iterator

小結

Sequence 操作分兩種：中間操作回傳新的 Sequence，不做事；終端操作觸發整條 pipeline。take 是中間操作，可以讓無限序列變安全。first 和 toList 是終端操作，差別在 first 拿到答案就停，toList 走完全部。sorted 是特例，雖然回傳 Sequence 但內部必須收集所有元素

開頭說 stdlib 的操作一大串，這篇只手刻三個，是因為骨架就這三種。Sequence 的手刻到這篇為止，下一篇做 Sequence 篇的總結，比較 Collection 和 Sequence 的效能差異

參考資料

• Kotlin 官方文件：Sequences
• Kotlin API：Sequence.filter
• Kotlin API：Sequence.map
• Kotlin API：Sequence.take
• Kotlin API：Sequence.sorted
• Kotlin API：Sequence.toList
• Kotlin API：Sequence.first
• Kotlin API：Sequence.count
• Kotlin stdlib 原始碼：_Sequences.kt
• .NET API：Enumerable.Where
• .NET API：Enumerable.Select
• .NET API：Enumerable.Take
• .NET API：Enumerable.OrderBy
• .NET API：Enumerable.ToList
• .NET API：Enumerable.First
• .NET API：Enumerable.Count
• C# 官方文件：延遲執行與 Lazy Evaluation

同步刊登於 Blog

圖片來源：AI 產生