這篇文章會用 TDD 手刻 Grouping 介面和 myGroupingBy，再把 aggregate、fold、reduce、eachCount 四個操作依序實作出來

這是 day 14 留下的伏筆

Kotlin ↔ C# 對照表

為什麼拖到現在才做

day 14 介紹 groupBy 時提過 groupingBy，但當時沒有動手實作，理由是順序

Grouping 的四個操作裡，fold 和 reduce 是主角。day 14 那個時間點還沒講過折疊，硬要在那裡手刻 Grouping.fold，等於要先把 day 17、day 18 的內容講完一輪。現在 fold 和 reduce 的基礎都有了，可以直接接上

先把 day 14 的結果搬過來。groupBy 回傳完整的 Map<K, List<T>>，所有元素都被收集進各自的 List。如果你要的只是每組的數量或總和，那些 List 建完就丟，純屬浪費。groupingBy 把「怎麼分組」和「分完要做什麼」拆成兩步，中間不建出 List

Grouping 是什麼

groupingBy 回傳的不是 Map，而是一個 Grouping<T, K> 物件

val grouping = employees.groupingBy { it.department }

這個介面只有兩個方法

interface MyGrouping<T, out K> {
    fun sourceIterator(): Iterator<T>
    fun keyOf(element: T): K
}

sourceIterator() 交出原始集合的 Iterator，keyOf() 回答某個元素該歸到哪一組。就這樣，沒有第三個方法，也沒有任何欄位

換句話說，Grouping 不是一個「已經分好組的容器」，它是一份「怎麼分組」的說明書。真正的分組動作發生在後面的聚合操作裡，而且是邊走邊分，走完就直接得到聚合結果

K 標成 out 是型變(variance)修飾，代表 MyGrouping<T, String> 可以當成 MyGrouping<T, Any> 用。這個系列到 day 34 才會完整處理型變，這裡先照抄 stdlib 的簽名就好

像 LINQ 的 deferred execution，但只像一半

從 C# 過來的人看到這份說明，第一個聯想通常是 deferred execution。方向沒錯，但兩邊的相似只到某個程度為止

一樣的地方有兩處。一是建立的當下什麼事都不做，keySelector 一次都不會被呼叫，要等到有人真的去問某個元素的 key 才開始算。這跟 LINQ 把 query 組好但還沒列舉是同一回事，後面的 Red 小節會有一個測試專門驗這件事

二是重複使用的行為。Grouping 身上沒有任何欄位可以存狀態，sourceIterator() 的語意是「跟來源要一個 Iterator」而不是「手上握著一個 Iterator」，所以同一個 Grouping 可以拿去做好幾次聚合，每次都從頭重走一遍來源。這跟同一條 LINQ query 被 foreach 兩次會重跑整條管道一樣。連帶的坑也一樣：來源本身不能重複走訪的時候，第二次不是拋例外就是拿到空的

不一樣的地方也是兩處。第一處是延後的範圍。LINQ 延後的是整條 Where / Select 管道，想接多長就接多長；Grouping 只延後分組這一步，後面掛一個終端聚合(fold、reduce、aggregate、eachCount)就到底了，沒辦法再往下串。Kotlin 這邊真正對得上 LINQ 那種可串接管道的是 Sequence，day 27 之後才登場

第二處差別更要注意：記憶體。day 14 提過，LINQ 的 GroupBy 雖然同樣是 deferred，但一被列舉就會把整個來源緩衝成 Lookup，每個 IGrouping 手上都握著那一組的全部元素；Grouping 則是邊走邊聚合，中間集合根本不存在

TDD 實作 myGroupingBy

Red：先寫測試

@Test
fun `groupingBy exposes source iterator`() {
    val grouping = listOf(1, 2, 3).myGroupingBy { it % 2 }
    val iterator = grouping.sourceIterator()
    assertEquals(1, iterator.next())
    assertEquals(2, iterator.next())
    assertEquals(3, iterator.next())
    assertFalse(iterator.hasNext())
}

@Test
fun `groupingBy computes key on demand`() {
    val grouping = employees.myGroupingBy { it.department }
    assertEquals("Engineering", grouping.keyOf(employees[0]))
    assertEquals("HR", grouping.keyOf(employees[4]))
}

@Test
fun `groupingBy does not touch elements before terminal operation`() {
    var calls = 0
    employees.myGroupingBy { calls++; it.department }
    assertEquals(0, calls)
}

前兩個測試分別驗證兩個方法。第一個確認 sourceIterator() 走訪的就是原始集合，第二個確認 keyOf() 會套用你給的 keySelector

第三個測試才是重點：建完 Grouping 之後 keySelector 一次都沒被呼叫。這就是「說明書」的意思，跟 day 27 之後的 Sequence 是同一種思路，只是 Sequence 延後的是轉換，Grouping 延後的是分組

Green：最小實作

inline fun <T, K> Iterable<T>.myGroupingBy(
    crossinline keySelector: (T) -> K
): MyGrouping<T, K> = object : MyGrouping<T, K> {
    override fun sourceIterator(): Iterator<T> = this@myGroupingBy.iterator()
    override fun keyOf(element: T): K = keySelector(element)
}

這是這個系列第一次在 Collection 操作裡回傳匿名物件。object : MyGrouping<T, K> { ... } 建立一個沒有名字的實作，把兩個方法補上就交出去

this@myGroupingBy 是標籤化的 this。在匿名物件裡面，單寫 this 指的是匿名物件自己，要拿到外層的 receiver(那個 Iterable<T>)就得標明是哪一層

真正要注意的是 crossinline

myGroupingBy 標了 inline，照理說 keySelector 會被直接展開到呼叫端。但這裡 keySelector 不是在函式本體裡被呼叫，而是被塞進 keyOf() 這個方法裡，等到後面的聚合操作才執行。時間點已經跟呼叫端脫鉤了

問題出在 non-local return。day 04 講過，inline 函式的 Lambda 裡可以直接寫 return 跳出外層函式。可是 keyOf() 在 myGroupingBy 早就回傳之後才被呼叫，那個 return 沒有地方可以跳。crossinline 就是在跟 compiler 說：這個 Lambda 我要帶去別的地方執行，請禁止裡面寫 non-local return

沒有 crossinline 這行編譯不過，而且錯誤訊息會直接點名原因

error: cannot inline 'keySelector: (T) -> K' here: it might contain non-local returns.
Add 'crossinline' modifier to parameter declaration 'keySelector: (T) -> K'

加上之後 Lambda 仍然是被內聯的，只是內聯到 keyOf() 的方法本體裡。反組譯出來的匿名類別，keyOf() 裡面是直接展開的運算，看不到任何 Function1.invoke 呼叫

Refactor：往 stdlib 的寫法靠近

跟 stdlib 的 groupingBy 結構一致，crossinline 和 this@ 標籤都在，差別只有 stdlib 用 block body 加 return，這裡用 expression body。這輪沒有東西可以重構

TDD 實作 myAggregate

四個操作裡，aggregate 是最底層的那一個，另外三個都可以用它做出來。所以先做它

Red：先寫測試

@Test
fun `aggregate reports first only once per key`() {
    val firstSeen = mutableListOf<String>()
    listOf(1, 2, 3, 4, 5, 6).myGroupingBy { if (it % 2 == 0) "even" else "odd" }
        .myAggregate { key, acc: Int?, _, first ->
            if (first) { firstSeen.add(key); 1 } else acc!! + 1
        }
    assertEquals(listOf("odd", "even"), firstSeen)
}

@Test
fun `aggregate treats null accumulator as a real value`() {
    val result = listOf("a", "bb", "a").myGroupingBy { it }
        .myAggregate { _, _: String?, _, first ->
            if (first) null else "seen twice"
        }
    assertEquals(mapOf("a" to "seen twice", "bb" to null), result)
}

@Test
fun `aggregate sums salary per department`() {
    val result = employees.myGroupingBy { it.department }
        .myAggregate { _, acc: Int?, emp, first ->
            if (first) emp.salary else acc!! + emp.salary
        }
    assertEquals(
        mapOf("Engineering" to 249_000, "Marketing" to 143_000, "HR" to 115_000),
        result
    )
}

@Test
fun `aggregate empty source returns empty map`() {
    val result = emptyList<Employee>().myGroupingBy { it.department }
        .myAggregate { _, acc: Int?, emp, first ->
            if (first) emp.salary else acc!! + emp.salary
        }
    assertEquals(emptyMap<String, Int>(), result)
}

Lambda 有四個參數，比前面幾天的操作都多，先一個一個對清楚

• key：這次的元素被分到哪一組
• accumulator：這一組目前的累積值，型別是 R?
• element：這次走到的元素
• first：這一組是不是第一次遇到

累積值標成 R? 而不是 R，就是為了 first 為 true 的那一次：這一組還沒有任何累積結果，只能給 null。那個 null 的意思是「還沒開始」，不是「值是空的」

參數多，每個元素又都要判斷一次，光看簽名不容易有畫面。拿第一個測試的 listOf(1, 2, 3, 4, 5, 6) 依奇偶分組，Lambda 一共跑六次，每次的參數和回傳值是這樣

一列一列看下來，其實只有兩種狀況：first 為 true 時建立這一組的起始值，first 為 false 時把 accumulator 接著算下去。accumulator 永遠是這一組上一次的回傳值，不會跟別組混到

這個測試不驗最後的 {odd=3, even=3}，只驗 firstSeen 這份名單。因為重點在 first 的行為：每個 key 只能為 true 一次，多一次就代表某一組的累積值被蓋掉重來。名單的順序也有意義，是各組第一次建組的先後。1 屬於 odd，最先進來；2 屬於 even，第二個進來，所以 firstSeen 是 ["odd", "even"]

第二個測試專門踩坑。這次 Lambda 第一次遇到某組時回傳的就是 null："a" 第一次進來，存進 Map 的值是 null。等 "a" 第二次出現，如果只靠 acc == null 判斷，會誤以為又是第一次。正確的結果是 "a" 要走到 "seen twice"，而只出現一次的 "bb" 停在 null。要分清楚「這個 key 還不存在」和「這個 key 存在，值剛好是 null」，光看累積值是分不出來的

後面兩個測試是常規的驗收。employees 那個確認實際聚合算得對，空集合那個確認一組都沒有時回傳空 Map，不是拋例外

Green：最小實作

inline fun <T, K, R> MyGrouping<T, K>.myAggregate(
    operation: (key: K, accumulator: R?, element: T, first: Boolean) -> R
): Map<K, R> {
    val destination = mutableMapOf<K, R>()
    for (element in this.sourceIterator()) {
        val key = keyOf(element)
        val accumulator = destination[key]
        val first = accumulator == null && !destination.containsKey(key)
        destination[key] = operation(key, accumulator, element, first)
    }
    return destination
}

for (element in this.sourceIterator()) 這行看起來怪，直接對 Iterator 跑 for 迴圈。這在 Kotlin 是合法的，stdlib 給 Iterator<T> 掛了一個回傳自己的 operator fun iterator() 擴充函式。for 迴圈認的就是這個 operator 慣例，所以它認得 Iterator

關鍵在 first 那一行

val first = accumulator == null && !destination.containsKey(key)

Map 的 get 回傳 null 有兩種意思：這個 key 不存在，或者這個 key 存在但值就是 null。要分辨只能再問一次 containsKey。前面那個「累積值是 null」的測試逼出來的就是這個判斷

順序也有講究。&& 會短路，所以只有在 accumulator 真的是 null 時才會多做一次 containsKey。累積值不是 null 的常見情況只查一次 map

destination[key] = operation(...) 把 Lambda 的結果寫回去。mutableMapOf() 建的是 LinkedHashMap，所以結果 Map 的 key 順序就是各組第一個元素出現的順序

Refactor：往 stdlib 的寫法靠近

myAggregate 把迴圈寫死在自己身上，沒照這個系列一路看到的 xxxTo 模式拆開，可以把迴圈搬進 myAggregateTo，讓呼叫端可以自己指定容器

inline fun <T, K, R, M : MutableMap<in K, R>> MyGrouping<T, K>.myAggregateTo(
    destination: M,
    operation: (key: K, accumulator: R?, element: T, first: Boolean) -> R
): M {
    for (element in this.sourceIterator()) {
        val key = keyOf(element)
        val accumulator = destination[key]
        val first = accumulator == null && !destination.containsKey(key)
        destination[key] = operation(key, accumulator, element, first)
    }
    return destination
}

inline fun <T, K, R> MyGrouping<T, K>.myAggregate(
    operation: (key: K, accumulator: R?, element: T, first: Boolean) -> R
): Map<K, R> = myAggregateTo(mutableMapOf(), operation)

多出來的 M : MutableMap<in K, R> 跟 day 10 的 mapTo 是同一套約束寫法

抽出 To 版本還有一個附帶效果：傳進來的 map 如果已經有某個 key 的值，那一組的 first 就會是 false，等於接續既有的累積值繼續算。stdlib 把這個行為寫進了每個 To 版本的說明，非 To 版因為自己建新 map，就沒有這一段

TDD 實作 myFold 與 myReduce

這兩個都是 aggregate 的專用版，差別只在怎麼處理「第一次」

Red：先寫測試

@Test
fun `fold joins strings per group`() {
    val result = listOf("apple", "avocado", "banana").myGroupingBy { it.first() }
        .myFold("") { acc, s -> if (acc.isEmpty()) s else "$acc, $s" }
    assertEquals(mapOf('a' to "apple, avocado", 'b' to "banana"), result)
}

@Test
fun `fold sums salary per department`() {
    val result = employees.myGroupingBy { it.department }
        .myFold(0) { acc, emp -> acc + emp.salary }
    assertEquals(
        mapOf("Engineering" to 249_000, "Marketing" to 143_000, "HR" to 115_000),
        result
    )
}

@Test
fun `reduce finds highest paid per department`() {
    val result = employees.myGroupingBy { it.department }
        .myReduce { _, acc, emp -> if (emp.salary > acc.salary) emp else acc }
    assertEquals("Grace", result["Engineering"]?.name)
    assertEquals("Diana", result["Marketing"]?.name)
    assertEquals("Eve", result["HR"]?.name)
}

@Test
fun `reduce single element group returns that element`() {
    val result = listOf(42).myGroupingBy { "all" }
        .myReduce { _, acc, n -> acc + n }
    assertEquals(mapOf("all" to 42), result)
}

@Test
fun `reduce empty source returns empty map`() {
    val result = emptyList<Employee>().myGroupingBy { it.department }
        .myReduce { _, acc, emp -> if (emp.salary > acc.salary) emp else acc }
    assertEquals(emptyMap<String, Employee>(), result)
}

myFold 的 Lambda 只收兩個參數，跟 day 17 的 fold 一樣。myReduce 收三個，多的那個是 key，因為分組之後你可能想知道現在在處理哪一組

最後那個測試可以對比 day 18。Iterable.reduce 遇到空集合會拋 UnsupportedOperationException，因為沒有第一個元素可以當起點。但 Grouping.reduce 不會拋，空來源就是零組，回傳空 Map。「每組至少有一個元素」是分組這件事本身保證的，所以那個例外在這裡根本不會發生

Green：最小實作

inline fun <T, K, R> MyGrouping<T, K>.myFold(
    initialValue: R,
    operation: (accumulator: R, element: T) -> R
): Map<K, R> =
    @Suppress("UNCHECKED_CAST")
    myAggregate { _, acc, e, first ->
        operation(if (first) initialValue else acc as R, e)
    }

inline fun <S, T : S, K> MyGrouping<T, K>.myReduce(
    operation: (key: K, accumulator: S, element: T) -> S
): Map<K, S> =
    myAggregate { key, acc, e, first ->
        @Suppress("UNCHECKED_CAST")
        if (first) e else operation(key, acc as S, e)
    }

兩個都是一行的委派

myFold 第一次遇到某組時，用你給的 initialValue 當起點，然後照樣呼叫一次 operation。所以每個元素都會經過 Lambda，包括第一個

myReduce 第一次遇到某組時直接把元素本身當結果，operation 完全不執行，從第二個元素才開始折疊。跟 day 18 的 Iterable.reduce 是同一個規則，只是這裡每一組各自算各自的

acc as R 和 acc as S 是不得已的轉型。aggregate 的 Lambda 簽名把累積值宣告成 R?，但走到 else 分支時它一定不是「不存在」。compiler 看不出這件事，所以要轉型加 @Suppress("UNCHECKED_CAST") 把警告壓掉。stdlib 也是這樣寫的

myReduce 的泛型 <S, T : S, K> 就是 day 18 那個 <S, T : S> 多帶一個 key 型別。累積值型別 S 只要能容納元素型別 T 就行

Refactor：往 stdlib 的寫法靠近

stdlib 的 fold 多一個多載，初始值不是固定值而是一個函式 (key, element) -> R，讓每一組可以依 key 算出不同的起始值。四個函式(兩個 fold 多載，各配一個 foldTo)骨架都一樣，這裡不逐一重寫

TDD 實作 myEachCount

Red：先寫測試

@Test
fun `eachCount counts numbers by even odd`() {
    val result = listOf(1, 2, 3, 4, 5, 6)
        .myGroupingBy { if (it % 2 == 0) "even" else "odd" }
        .myEachCount()
    assertEquals(mapOf("odd" to 3, "even" to 3), result)
}

@Test
fun `eachCount counts employees per department`() {
    val result = employees.myGroupingBy { it.department }.myEachCount()
    assertEquals(mapOf("Engineering" to 3, "Marketing" to 2, "HR" to 2), result)
}

@Test
fun `eachCount empty source returns empty map`() {
    val result = emptyList<Employee>().myGroupingBy { it.department }.myEachCount()
    assertEquals(emptyMap<String, Int>(), result)
}

三個測試都是前面那套模式的複製，沒有新東西。唯一要注意的是最後一個：空來源回傳空 Map，不是拋例外。理由跟 myReduce 那邊一樣

Green：最小實作

fun <T, K> MyGrouping<T, K>.myEachCount(): Map<K, Int> =
    myFold(0) { acc, _ -> acc + 1 }

一行。初始值 0，每個元素不看內容直接加一

這個函式沒有標 inline，因為它自己不收 Lambda 參數，沒有東西要內聯。裡面呼叫的 myFold 是 inline，那個 { acc, _ -> acc + 1 } 還是會被展開

Refactor：往 stdlib 的寫法靠近

stdlib 的 common 版 eachCountTo 骨架一模一樣，只差它是 To 版

public fun <T, K, M : MutableMap<in K, Int>> Grouping<T, K>.eachCountTo(destination: M): M =
    foldTo(destination, 0) { acc, _ -> acc + 1 }

但 JVM 版的 eachCount() 不是這樣寫的，而且原始碼裡直接留了註解說明理由

public actual fun <T, K> Grouping<T, K>.eachCount(): Map<K, Int> =
// fold(0) { acc, e -> acc + 1 } optimized for boxing
    foldTo(destination = mutableMapOf(),
           initialValueSelector = { _, _ -> kotlin.jvm.internal.Ref.IntRef() },
           operation = { _, acc, _ -> acc.apply { element += 1 } })
        .mapValuesInPlace { it.value.element }

問題是裝箱。Map<K, Int> 的 value 在 JVM 上是 Integer 物件，acc + 1 每加一次就要產生一個新的 Integer 塞回 map。元素多的時候這些短命物件全部落在 heap 上

stdlib 的解法是換一個可變的盒子。Ref.IntRef 裡面是一個 element: Int 欄位，每組只配置一個，之後都是 element += 1 原地改。全部數完再用 mapValuesInPlace 把盒子拆掉換成數字。mapValuesInPlace 是 stdlib 的內部函式，一般程式碼呼叫不到

這是那種「知道就好」的優化。上面那個一行版本語意完全正確，差別只在 heap 上多了一些垃圾。真的要學的是它示範了另一個多載的用途：initialValueSelector 讓每組拿到自己專屬的那個盒子

與 stdlib 原始碼比較

原始碼位置：kotlin.collections 的 Grouping.kt(介面與四個操作)、_Collections.kt(groupingBy)、GroupingJVM.kt(JVM 版 eachCount)

aggregateTo 的核心迴圈

public inline fun <T, K, R, M : MutableMap<in K, R>> Grouping<T, K>.aggregateTo(
    destination: M,
    operation: (key: K, accumulator: R?, element: T, first: Boolean) -> R
): M {
    for (e in this.sourceIterator()) {
        val key = keyOf(e)
        val accumulator = destination[key]
        destination[key] = operation(key, accumulator, e, accumulator == null && !destination.containsKey(key))
    }
    return destination
}

差別只有一個：stdlib 把 first 的判斷直接寫在參數位置，這裡拉出來給了它一個名字。行為完全一致

groupingBy 那邊也對一下

public inline fun <T, K> Iterable<T>.groupingBy(crossinline keySelector: (T) -> K): Grouping<T, K> {
    return object : Grouping<T, K> {
        override fun sourceIterator(): Iterator<T> = this@groupingBy.iterator()
        override fun keyOf(element: T): K = keySelector(element)
    }
}

crossinline、匿名物件、this@groupingBy.iterator() 三個要素都在，只有 body 的寫法不同

整個 Grouping.kt 不到 300 行，扣掉註解和被註解起來的 eachSumOf / sumEachBy 系列，實際程式碼大概 70 行。一個介面、兩個方法，撐起 eachCount、fold、reduce、aggregate 加上各自的 To 版本

為什麼同名不會衝突？

這篇的 myFold 和 myReduce 跟 day 17、day 18 同名，但它們不會打架

// day 17：receiver 是 Iterable<T>
inline fun <T, R> Iterable<T>.myFold(initial: R, operation: (acc: R, T) -> R): R

// day 19：receiver 是 MyGrouping<T, K>
inline fun <T, K, R> MyGrouping<T, K>.myFold(
    initialValue: R,
    operation: (accumulator: R, element: T) -> R
): Map<K, R>

擴充函式是靠 receiver 型別解析的，List 上找不到 Grouping 版本，反之亦然。day 03 講擴充函式時提過這件事，這裡是第一次真的用上

stdlib 自己也是這樣安排的，fold 和 reduce 都同時存在 Iterable 版和 Grouping 版

groupBy 還是 groupingBy？

要完整的分組結果，之後還要對每一組做別的事，用 groupBy。它回傳 Map<K, List<T>>，拿到手就是普通的 Map，後續怎麼操作都行

只要聚合結果，不需要分組列表，用 groupingBy，少建立了中間過度的 List

兩間間差多少？資料量 n、分組數 k 時，groupBy { }.mapValues { it.value.size } 會配置 k 個 ArrayList，塞進 n 個元素的參考，然後整個丟掉。groupingBy { }.eachCount() 從頭到尾只維護 k 個計數器

如果 n 只有幾百的時候這個差別可能差別不太，groupBy 的可讀性反而比較好，會有感的是 n 很大的時候，這個時候就要注意效能的問題了

小結

前面手刻的都是擴充函式，Grouping 是這個系列第一次自己定義介面、再自己實作出來：兩個方法，沒有欄位。它不存資料，只描述「元素從哪來」和「怎麼分組」，真正的工作留給後面的聚合操作

四個操作是一棵樹。aggregate 在根部，一個迴圈搭配 first 旗標；fold 把第一次的起始值固定下來；reduce 把第一個元素直接當起始值；eachCount 再把累積值寫死成一個計數器。往上每一層都只是把下一層的自由度窄化一點

實作上最容易踩到的是 first 的判斷。accumulator == null 不夠，因為累積值本身可能就是 null，得補 containsKey 才分得出「沒有這個 key」和「有這個 key 但值是 null」。這在 stdlib 的簽名裡：Lambda 的累積值參數宣告成 R?，就是在提醒你這件事

下一篇回到聚合篇的主線，講 sum、sumOf、maxBy、minBy、average 這些數值專用的聚合函式。它們底層都可以用 fold 或 reduce 做出來

參考資料

• Kotlin 官方文件：Grouping
• Kotlin API：groupingBy
• Kotlin API：Grouping
• Kotlin API：aggregate
• Kotlin API：aggregateTo
• Kotlin API：fold
• Kotlin API：foldTo
• Kotlin API：reduce
• Kotlin API：eachCount
• Kotlin API：eachCountTo
• Kotlin 官方文件：Inline functions(crossinline)
• Kotlin 官方文件：Object expressions(匿名物件)
• Kotlin stdlib 原始碼：Grouping.kt
• Kotlin stdlib 原始碼：GroupingJVM.kt
• Kotlin stdlib 原始碼：_Collections.kt
• .NET API：Enumerable.CountBy
• .NET API：Enumerable.AggregateBy

同步刊登於 Blog

圖片來源：AI 產生