Collection processing in Kotlin: Folding and reducing
// fold implementation from Kotlin stdlib
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 is the most universal method in our collection processing toolbox. We use it rarely because Kotlin standard library has already provided most important aggregate operations for us, but if we are missing a method for a specific task, fold is at our service.
Let's see it practice. fold is a method that accumulates all elements into a single variable (called an "accumulator") using a defined operation. For instance, let's say that our collection contains the numbers from 1 to 4, our initial accumulator value is 0, and our operation is addition. So fold will:
- add the first value 1 to the initial accumulator value 0,
- then it will add the result 1 to the next value 2,
- then it will add the result 3 to the next value 3,
- then it will add the result 6 to the next value 4,
- and the result is 10.
As you can see, fold(0) { acc, i -> acc + i } calculates the sum of all the numbers.
Since you can specify the initial value, you can decide the result type. If your initial value is an empty string and your operation is addition, then the result will be a "1234" string.
fun main() {
val numbers = listOf(1, 2, 3, 4)
val sum = numbers.fold(0) { acc, i -> acc + i }
println(sum) // 10
val joinedString = numbers.fold("") { acc, i -> acc + i }
println(joinedString) // 1234
val product = numbers.fold(1) { acc, i -> acc * i }
println(product) // 24
}
fold is very universal. Nearly all collection processing methods can be implemented using it.
// simplified `filter` implemented with `fold`
inline fun <T> Iterable<T>.filter(
predicate: (T) -> Boolean
): List<T> = fold(emptyList()) { acc, e ->
if (predicate(e)) acc + e else acc
}
// simplified `map` implemented with `fold`
inline fun <T, R> Iterable<T>.map(
transform: (T) -> R
): List<R> = fold(emptyList()) { acc, e -> acc + transform(e) }
// simplified `flatMap` implemented with `fold`
inline fun <T, R> Iterable<T>.flatMap(
transform: (T) -> Iterable<R>
): List<R> = fold(emptyList()) { acc, e -> acc + transform(e) }
On the other hand, thanks to the fact that the Kotlin standard library has so many collection processing functions, we rarely need to use fold. Even the functions we presented before that calculate a sum and join elements into a string have dedicated methods.
fun main() {
val numbers = listOf(1, 2, 3, 4, 5)
println(numbers.sum()) // 15
println(numbers.joinToString(separator = "")) // 12345
}
There is currently no standard library method to calculate the product of all the numbers in a collection, so this is where fold can be used. We might use it directly, or we might use it to implement the product method ourselves.
fun Iterable<Int>.product(): Int =
fold(1) { acc, i -> acc * i }
If you want to reverse the order of accumulation (to start from the end of the collection), use foldRight.
In some situations, you might want to have not only the result of fold accumulations but also all the intermediate values. For that, you can use the runningFold method or its alias1 scan.
fun main() {
val numbers = listOf(1, 2, 3, 4)
println(numbers.fold(0) { acc, i -> acc + i })
// 10
println(numbers.scan(0) { acc, i -> acc + i })
// [0, 1, 3, 6, 10]
println(numbers.runningFold(0) { acc, i -> acc + i })
// [0, 1, 3, 6, 10]
println(numbers.fold("") { acc, i -> acc + i })
// 1234
println(numbers.scan("") { acc, i -> acc + i })
// [, 1, 12, 123, 1234]
println(numbers.runningFold("") { acc, i -> acc + i })
// [, 1, 12, 123, 1234]
println(numbers.fold(1) { acc, i -> acc * i })
// 24
println(numbers.scan(1) { acc, i -> acc * i })
// [1, 1, 2, 6, 24]
println(numbers.runningFold(1) { acc, i -> acc * i })
// [1, 1, 2, 6, 24]
}
runningFold(init, oper).last() and scan(init, oper).last() always give the same result as fold(init, oper).
// simplified reduce implementation from Kotlin stdlib
public inline fun <S, T : S> Iterable<T>.reduce(
operation: (acc: S, T) -> S
): S {
val iterator = this.iterator()
if (!iterator.hasNext())
throw UnsupportedOperationException(
"Empty collection can't be reduced."
)
var accumulator: S = iterator.next()
while (iterator.hasNext()) {
accumulator = operation(accumulator, iterator.next())
}
return accumulator
}
reduce is a very similar function to fold: it also accumulates all elements using a defined transformation. The difference is that in reduce we do not define the initial value, and so reduce uses the first element as the initial value. There are two consequences of this fact:
- If a collection is empty,
reduce throws an exception. If we are not certain that a collection has elements, we should use reduceOrNull , which returns null for an empty collection. - The result from
reduce must be of the same type as its elements. reduce is slightly faster than fold because it has one operation less to do.
fun main() {
val numbers = listOf(1, 2, 3, 4, 5)
println(numbers.fold(0) { acc, i -> acc + i }) // 15
println(numbers.reduce { acc, i -> acc + i }) // 15
println(numbers.fold("") { acc, i -> acc + i }) // 12345
// Here `reduce` cannot be used instead of `fold`
println(numbers.fold(1) { acc, i -> acc * i }) // 120
println(numbers.reduce { acc, i -> acc * i }) // 120
}
list.reduce(oper) is a lot like list.drop(1).fold(list[0], oper).
In general, I prefer using fold whenever there is a "zero" value because fold does not face the risk of an empty collection and it is able to control the result type.
Just like for fold, there is runningReduce and reduceRight.
// simplified sample sum implementation from Kotlin stdlib
fun Iterable<Int>.sum(): Int {
var sum: Int = 0
for (element in this) {
sum += element
}
return sum
}
// simplified sample sumOf implementation from Kotlin stdlib
inline fun <T> Iterable<T>.sumOf(
selector: (T) -> Int
): Int {
var sum: Int = 0.toInt()
for (element in this) {
sum += selector(element)
}
return sum
}
I mentioned that there is already a function to calculate the sum of all the numbers in a collection, and its name is sum. It is implemented for all the basic ways of representing numbers, like Int, Long, Double, etc.
fun main() {
val numbers = listOf(1, 6, 2, 4, 7, 1)
println(numbers.sum()) // 21
val doubles = listOf(0.1, 0.6, 0.2, 0.4, 0.7)
println(doubles.sum()) // 1.9999999999999998
// It is not 2, due to limited JVM double representation
val bytes = listOf<Byte>(1, 4, 2, 4, 5)
println(bytes.sum()) // 16
}
When you have a list of elements and you want to calculate the sum of one of their properties, you could first map the elements onto the values of these properties, but it is more efficient to use sumOf, which extracts a countable value for each element and then sums these values.
import java.math.BigDecimal
data class Player(
val name: String,
val points: Int,
val money: BigDecimal,
)
fun main() {
val players = listOf(
Player("Jake", 234, BigDecimal("2.30")),
Player("Megan", 567, BigDecimal("1.50")),
Player("Beth", 123, BigDecimal("0.00")),
)
println(players.map { it.points }.sum()) // 924
println(players.sumOf { it.points }) // 924
// Works for `BigDecimal` as well
println(players.sumOf { it.money }) // 3.80
}
Marcin Moskala is a highly experienced developer and Kotlin instructor as the founder of Kt. Academy, an official JetBrains partner specializing in Kotlin training, Google Developers Expert, known for his significant contributions to the Kotlin community. Moskala is the author of several widely recognized books, including "Effective Kotlin," "Kotlin Coroutines," "Functional Kotlin," "Advanced Kotlin," "Kotlin Essentials," and "Android Development with Kotlin."
Beyond his literary achievements, Moskala is the author of the largest Medium publication dedicated to Kotlin. As a respected speaker, he has been invited to share his insights at numerous programming conferences, including events such as Droidcon and the prestigious Kotlin Conf, the premier conference dedicated to the Kotlin programming language.
