Lesson 21. Grouping and Folding

Mission link: Stage 4 closes here: these are the operations where the choice between a collection pipeline and a sequence has real consequences, so this lesson asks you to make that choice and defend it.
Primary source: Docs: "Aggregate operations", Kotlin
Prerequisites: Lesson 20, Lesson 19, Lesson 14

Warm-up

1. ▢ What makes a sequence chain actually start doing work, and what is the name for the operations that do not?

2. ▢ What does partition return, and what does it save you over calling filter and filterNot with the same predicate?

3. ▢ x.let { ... } and x.also { ... }: which one gives you the lambda's result, and which gives you x back?

Know this

Aggregates first, because most of the time you do not need a fold at all. The standard library already has count(), sum(), average(), sumOf { }, and the min and max family (Aggregate operations). Two distinctions inside that family are worth getting right, because the names look interchangeable and are not. maxByOrNull { } returns the element for which the selector is largest; maxOf { } returns the largest value the selector produced. And the ...OrNull forms return null on an empty collection, while the minOf/maxOf alternatives do not have a null to give you. That is a lesson 1 decision wearing a different hat: take the OrNull form where empty is genuinely possible and let the type system make you handle it.

fold and reduce are for the aggregate the library does not have. Both apply an operation to the elements in sequence, where the operation takes the accumulated value so far and the current element. The whole difference is the start: fold takes an initial value and uses it on the first step, while reduce uses the first and second elements as the operation's two arguments on the first step. The docs' own example is the trap: numbers.fold(0) { sum, element -> sum + element * 2 } sums the doubled elements correctly, and passing that same lambda to reduce quietly does not, because the first element never gets doubled.

Two consequences follow from that one difference. reduce has no initial value, so its accumulator is stuck at the element type, whereas fold's accumulator is whatever you seeded it with: a Map, a StringBuilder, a domain object. Build anything other than a bigger element with fold. And reduce on an empty collection has nothing to return at all, so it throws rather than inventing a value; reduceOrNull() is the variant that hands back null instead, while fold simply returns the initial value and needs no special case.

Three variants worth recognising:

Grouping is where the cost argument of this stage bites. groupBy { } returns a Map whose keys are the lambda's results and whose values are the List of elements that produced each key, and a second lambda transforms those values instead of keeping the original elements (Grouping). That is exactly what you want when you need the members of each group. When you only need one value per group, it is the wrong tool, because it builds every member list first: groupBy { it.status }.mapValues { it.value.size } allocates a list of every element in each group and then throws all of them away for their sizes.

groupingBy { } is the answer to that. It returns a Grouping rather than a Map, and the operations you then call on it, eachCount() most commonly, accumulate one value per key without ever materialising the member lists (Grouping). The same Grouping also carries fold, reduce and aggregate, which is how you get a per-group total, or a per-group anything, on the same terms.

So the stage's question, made concrete. Folding streams: it consumes one element at a time and keeps one accumulator, so it is terminal on a sequence and costs nothing extra there. Grouping does not stream: it has to hold a slot for every key it has seen before it can answer anything, which is precisely lesson 20's stateful category, so its result is materialised wherever you put it. What asSequence() still buys you in front of a grouping step is everything upstream of it: the filters and maps that would otherwise each have built a full intermediate list. That is the shape of a defensible answer, and defending it is what closes this stage.

Practice

1. ▢ For val numbers = listOf(5, 2, 10, 4), predict both results: numbers.reduce { sum, element -> sum + element * 2 } and numbers.fold(0) { sum, element -> sum + element * 2 }.

2. ▢ numbers.foldRight(0) { sum, element -> sum + element * 2 } compiles and returns 81 instead of 42. Why?

3. ▢ On an empty list of Int, what do fold(0) { a, b -> a + b }, reduce { a, b -> a + b }, and maxByOrNull { it } each give you?

4. ▢ You need the number of log entries per status code. Compare entries.groupBy { it.status }.mapValues { it.value.size } with entries.groupingBy { it.status }.eachCount(). What does the first one allocate that the second does not?

5. ▢ Which claim correctly describes groupingBy?

   • a) groupingBy builds a list of members per key, then reduces each list down
   • b) groupingBy accumulates one value per key, without ever building the member lists
   • c) groupingBy returns a map immediately, so a later fold reads that map twice
   • d) groupingBy streams its input lazily, so its final result is also never materialised

6. ▢ Stage capstone. Ten million log lines are read from a file, filtered to the ones from today, mapped to a status code, and counted per code. Write the pipeline you would use, then defend it: name what each decision avoids building, and name the one thing that gets materialised no matter what you choose.

Real-world reps

• [ ] Find a groupBy in code you have access to. Decide whether the caller uses the member lists or only one value per group, and say which of groupBy and groupingBy that code should be using.
• [ ] Find a hand-written accumulation loop in your own work, the kind with a var outside a for. Rewrite it as a fold on paper, then decide honestly which version you would rather read in six months.
• [ ] Tomorrow: take the pipeline from the capstone item and re-argue it for an input of fifty elements instead of ten million. Write down the point at which your answer flips, and what you would need to measure to find it exactly.

Going further

• Docs: "Aggregate operations", Kotlin
• Docs: "Grouping", Kotlin
• Docs: "Sequences", Kotlin
• Resources

Not landing? Reread the primary source at the top, since this lesson compresses it and compression is where understanding leaks. Check the glossary for any term that felt slippery.

If the lesson itself is unclear rather than the material, that is a defect: open an issue.