這篇文章會用 TDD 手刻 myFold 和 myFoldIndexed，理解聚合操作的核心模式。聚合篇從這裡開始

Kotlin ↔ C# 對照表

fold 的概念

前面寫的 filter、map、groupBy 都是「集合進，集合出」。fold 不一樣，它是「集合進，單一值出」。把整個集合壓縮成一個結果

過程像滾雪球

初始值: 0
  ↓ + 1 = 1
  ↓ + 2 = 3
  ↓ + 3 = 6
  ↓ + 4 = 10
  ↓ + 5 = 15
結果: 15

每一步拿「目前的累積值」和「下一個元素」丟進 Lambda，Lambda 回傳新的累積值，繼續往下滾。初始值決定第一步從哪裡開始

為什麼需要初始值？兩個原因。第一，如果集合是空的，沒有初始值就沒東西可回傳。第二，初始值的型別決定了回傳型別，讓 fold 可以把 List<Employee> 折疊成 Int、String 或任何你想要的型別

fold 從哪裡來？

fold 不是 Kotlin 發明的概念。在函式程式語言裡，這個操作有個更正式的名字叫 catamorphism，意思是「在遞迴結構上的通用摺疊」

這個概念可以追溯到 Lisp 家族的 reduce，後來 ML、Haskell 把它正式化。Haskell 的 foldl/foldr 直接對應 Kotlin 的 fold/foldRight，連 Lambda 參數順序都一樣

-- Haskell
foldl (+) 0 [1, 2, 3, 4, 5]  -- 15

// Kotlin
listOf(1, 2, 3, 4, 5).fold(0) { acc, n -> acc + n }  // 15

Kotlin 用 fold 不用 reduce 是有講究的。函式程式設計傳統的區分是：fold 帶初始值，reduce 不帶。Scala(fold / reduce)和 F#(List.fold / List.reduce)都遵循這個慣例，Kotlin 也跟著走，所以下一篇的 reduce 沒有 initial 參數。Haskell 沒有叫 reduce 的函式，對應的是另外命名的 foldl1 / foldr1，區分方式一樣是「有沒有初始值」

C# 跟 Java 走的是另一條路。LINQ 的 Aggregate 同一個方法既能帶 seed 也能不帶，靠多載區分；Java 8 Stream 的 reduce 也類似。Kotlin 把兩個概念拆成 fold 與 reduce 兩個函式，看名字就知道有沒有初始值

至於 catamorphism 這個名字來自範疇論，對 Kotlin 開發者不重要。知道 fold 是「函式程式語言對遞迴摺疊的標準抽象」，不是某個語言的奇怪發明，就夠了

TDD 實作 myFold

Red：先寫測試

@Test
fun `fold sum of numbers`() {
    val numbers = listOf(1, 2, 3, 4, 5)
    val result = numbers.myFold(0) { acc, num -> acc + num }
    assertEquals(15, result)
}

@Test
fun `fold string concatenation`() {
    val words = listOf("Hello", " ", "World")
    val result = words.myFold("") { acc, word -> acc + word }
    assertEquals("Hello World", result)
}

@Test
fun `fold with different result type`() {
    val result = employees.myFold(0) { acc, emp -> acc + emp.salary }
    assertEquals(507000, result)
}

@Test
fun `fold employees to department salary map`() {
    val result = employees.myFold(mutableMapOf<String, Int>()) { acc, emp ->
        acc[emp.department] = (acc[emp.department] ?: 0) + emp.salary
        acc
    }
    assertEquals(249000, result["Engineering"])
    assertEquals(143000, result["Marketing"])
    assertEquals(115000, result["HR"])
}

@Test
fun `fold empty list returns initial value`() {
    val empty = emptyList<Int>()
    val result = empty.myFold(42) { acc, num -> acc + num }
    assertEquals(42, result)
}

第一個測試是數字加總，初始值 0。第二個是字串拼接，初始值空字串

第三個測試把 List<Employee> 折疊成 Int(薪水總和)。T 是 Employee，R 是 Int，兩個型別完全不同。這就是 fold 比 reduce 強的地方(day 18 會比較)

第四個更進一步，把員工列表折疊成部門薪水的 Map。Lambda 裡面操作可變的 Map 當作累加器，每次把員工的薪水加上去

第五個測試空集合。fold 空集合直接回傳初始值，不會出錯

Green：最小實作

inline fun <T, R> Iterable<T>.myFold(initial: R, operation: (acc: R, T) -> R): R {
    var accumulator = initial
    for (element in this) {
        accumulator = operation(accumulator, element)
    }
    return accumulator
}

結構非常單純。用 var accumulator 追蹤目前的累積值，每次用 Lambda 算出新值覆蓋回去。迴圈結束回傳最終的累積值

泛型簽名是 <T, R>。T 是集合元素的型別，R 是累積值(也是回傳值)的型別。Lambda 簽名 (acc: R, T) -> R 說明：吃進一個 R 和一個 T，吐出一個 R

跟之前的函式比起來，fold 的實作反而更簡單。沒有容器要建立，沒有條件要判斷，就是一個迴圈加一個變數

Refactor：往 stdlib 的寫法靠近

這次沒有東西要重構。Green 的版本已經跟 stdlib 一模一樣，後面的原始碼比較會證明這件事

TDD 實作 myFoldIndexed

Red：先寫測試

@Test
fun `foldIndexed with index weighting`() {
    val numbers = listOf(10, 20, 30)
    val result = numbers.myFoldIndexed(0) { index, acc, num -> acc + num * index }
    // 10*0 + 20*1 + 30*2 = 0 + 20 + 60 = 80
    assertEquals(80, result)
}

@Test
fun `foldIndexed only even indices`() {
    val numbers = listOf(1, 2, 3, 4, 5)
    val result = numbers.myFoldIndexed(0) { index, acc, num ->
        if (index % 2 == 0) acc + num else acc
    }
    // index 0: 1, index 2: 3, index 4: 5 → 9
    assertEquals(9, result)
}

@Test
fun `foldIndexed empty list returns initial value`() {
    val empty = emptyList<Int>()
    val result = empty.myFoldIndexed(100) { index, acc, num -> acc + num * index }
    assertEquals(100, result)
}

第一個測試用 index 做加權。第二個只累加偶數位置的元素。Lambda 簽名多了 index 參數，順序是 (index, acc, element)。第三個測試空集合，跟 myFold 一樣直接回傳初始值，Lambda 連跑都不會跑

Green：最小實作

inline fun <T, R> Iterable<T>.myFoldIndexed(
    initial: R,
    operation: (index: Int, acc: R, T) -> R
): R {
    var accumulator = initial
    var index = 0
    for (element in this) {
        accumulator = operation(index, accumulator, element)
        index++
    }
    return accumulator
}

跟 myFold 差一個 var index = 0 和 index++，其他一模一樣。手刻 Indexed 版本都是從計數器起手的，day 05 的 filterIndexed 就是這樣開始

Refactor：往 stdlib 的寫法靠近

同樣沒有要改的。結構上這已經是 stdlib 的形狀

不過這裡可以順便對照一件事。day 05 的 filterIndexed 在 Refactor 時把手動計數器換掉了，因為 stdlib 的 filterIndexedTo 是呼叫 forEachIndexed。但同樣是 Indexed 家族，mapIndexedTo 和 foldIndexed 都是自己維護 var index = 0

foldIndexed 有它的理由：forEachIndexed 的 Lambda 回傳 Unit，要拿它做 fold 就得從 Lambda 裡去改外面捕捉到的 accumulator。能動，但比直接寫迴圈難讀。mapIndexedTo 就沒有這個限制，卻也還是用手動計數器

回想 day 03 提過的，_Collections.kt 開頭有一行 auto-generated 註記。這些函式是從樣板產生出來的，看起來同一個 index 概念在不同樣板裡並沒有統一寫法

foldRight 的概念

stdlib 還有 foldRight，從集合的最後一個元素開始往前折疊

val numbers = listOf(1, 2, 3)
numbers.fold(0) { acc, num -> acc + num }       // 0→1→3→6
numbers.foldRight(0) { num, acc -> acc + num }   // 0→3→5→6

加法的話結果一樣，但順序不同的操作(像字串拼接、除法)結果就會不同

注意 foldRight 的 Lambda 參數順序是 { element, acc -> }，跟 fold 的 { acc, element -> } 相反。這個設計是刻意的，讓你在讀程式碼時能直覺知道「元素從右邊來」

我們在這裡不實作 foldRight，它需要反向遍歷，對 List 可以用 listIterator(size) 從尾巴開始走，但對一般的 Iterable 就得先轉成 List 再反向。知道它存在就好

與 stdlib 原始碼比較

原始碼位置：kotlin.collections 的 _Collections.kt

public inline fun <T, R> Iterable<T>.fold(
    initial: R,
    operation: (acc: R, T) -> R
): R {
    var accumulator = initial
    for (element in this) accumulator = operation(accumulator, element)
    return accumulator
}

跟我們的一模一樣，連變數名都相同。fold 就是這麼簡單，沒什麼好最佳化的

用 fold 重新實作其他函式

fold 是最通用的聚合操作。前面寫過的很多函式都能用 fold 來實作

// myCount 用 fold
fun <T> Iterable<T>.myCountWithFold(predicate: (T) -> Boolean): Int =
    fold(0) { acc, element -> if (predicate(element)) acc + 1 else acc }

// myMap 用 fold
fun <T, R> Iterable<T>.myMapWithFold(transform: (T) -> R): List<R> =
    fold(ArrayList()) { acc, element -> acc.apply { add(transform(element)) } }

// myFilter 用 fold
fun <T> Iterable<T>.myFilterWithFold(predicate: (T) -> Boolean): List<T> =
    fold(ArrayList()) { acc, element -> acc.apply { if (predicate(element)) add(element) } }

能不能這樣寫？能。該不該這樣寫？不該，用 for 迴圈寫更清楚。效能倒不是理由：fold 是 inline 函式，編譯後跟手寫迴圈幾乎一樣，真要比的話，差別在 stdlib 的 map 會預先分配 ArrayList 容量，fold 版的 ArrayList() 沒有。但這個練習說明了 fold 的表達能力：只要你能定義「初始值」和「怎麼合併」，fold 就能幹任何事

小結

fold 的實作只有四行，但它是整個聚合操作的基礎。有了初始值和一個 (acc, element) -> acc 的 Lambda，就能把任意集合壓成任意型別的結果

下一篇(day 18)講 reduce。如果初始值就是集合的第一個元素呢？省掉 initial 參數，但要處理空集合的問題

參考資料

• Kotlin 官方文件：Aggregate operations
• Kotlin 官方文件：Collection transformations
• Kotlin 官方文件：Higher-order functions and lambdas
• Kotlin 官方文件：Inline functions
• Kotlin 官方文件：Generics
• Kotlin API：fold
• Kotlin API：foldIndexed
• Kotlin API：foldRight
• Kotlin stdlib 原始碼：_Collections.kt
• Java API：Stream.reduce
• .NET API：Enumerable.Aggregate
• .NET API：Enumerable.Sum
• C# 官方文件：標準查詢運算子
• Haskell：Data.Foldable
• Haskell Wiki：Fold
• Scala API：List(fold / reduce)
• F# 官方文件：List.fold / List.reduce
• Common Lisp HyperSpec：reduce
• Wikipedia：Fold(higher-order function)
• Wikipedia：Catamorphism

同步刊登於 Blog

圖片來源：AI 產生