Разработчик вручную реализует ключевые операции Kotlin Sequence для демонстрации принципов ленивой оценки

這篇文章會用 TDD 手刻 Sequence 版的 myTake(中間操作)、myFirst 和 myToList(終端操作)，把中間操作和終端操作的分類搞清楚 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，每個 Sequence 都有 iterator()，Iterator 又只有 hasNext() 和 next() 兩個方法 整個 lazy pipeline 就建在這兩個方法的拉取鏈上，可以看 filter 接 take 和 first 怎麼跑 seq.filter { ... }.take(3).first() first()(終端)向 take 的 iterator 喊 next() filter 的 iterator 喊 短路就是這麼做到的。first() 拿到結果就停；take 沒被再喊就不再拉；filter 沒被再喊也不再 evaluate，一串「不主動」累積起來就是 lazy C# LINQ 的 IEnumerator 也用 MoveNext() 與 Current 逐步取得資料，Java Stream 對外則以 Spliterator、pipeline 與 Sink 進行遍歷，sequential Stream 同樣支援延遲執行與短路，但底層機制不是這裡的 Iterator 包裝鏈 take 在 Sequence 裡面特別有用，因為它能讓無限序列變安全 @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。負數沒有合理語意，所以擋在前面 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，概念一樣，但機制完全不同 這個版本其實已經很接近 stdlib 的 TakeSequence 了。同樣用 var left 倒數，next() 先擋 left == 0，hasNext() 同時檢查 left > 0 和上游 如果有人不先 hasNext() 就直接 next()，處理方式也跟 stdlib 一樣：left == 0 由自己擋下，上游沒元素時就讓 sourceIterator.next() 的 NoSuchElementException 透出去，符合 Iterator 約定 stdlib 讓 TakeSequence 實作 DropTakeSequence 介面，take 接 take 時可以合併成一次運算，這純粹是效能最佳化，後面對照原始碼時再看 @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 處理 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 那個測試驗證的就是這件事 兩個 myFirst 已經是直觀的最小寫法。stdlib 的無參數 first() 也是先檢查 hasNext() 再取 next()，帶 predicate 的版本也是 for 迴圈逐一比對，跟我們一致。唯一差別是 stdlib 把「空序列」和「找不到符合元素」的錯誤訊息寫得更明確，這裡照樣保留兩種訊息就夠了，沒有要再最佳化的地方 @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) } fun <T> Sequence<T>.myToList(): List<T> { val result = ArrayList<T>() for (element in this) { result.add(element) } return result } toList() 是最常用的終端操作，它把整條 pipeline 的結果收進一個 ArrayList 裡 我們的 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 能做到的最直接寫法 大部分中間操作都是 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，只是無法逐元素串流輸出 原始碼位置：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 的效能差異 同步刊登於 Blog 圖片來源：AI 產生