# # Folding Lists

`fold()` combines all elements of a list, in order, to generate a single result.

A common exercise is to implement operations such as `sum()` or `reverse()` using `fold()`. Here, `fold()` sums a sequence:

``````// FoldingLists/SumViaFold.kt
import atomictest.eq

fun main() {
val list = listOf(1, 10, 100, 1000)
list.fold(0) { sum, n ->
sum + n
} eq 1111
}
``````

`fold()` takes the initial value (its argument, `0` in this case) and successively applies the operation (expressed here as a lambda) to combine the current accumulated value with each element. `fold()` first adds `0` (the initial value) and `1` to get `1`. That becomes the `sum`, which is then added to the `10` to get `11`, which becomes the new `sum`. The operation is repeated for two more elements: `100` and `1000`. This produces `111` and `1111`. The `fold()` will stop when there is nothing else in the list, returning the final `sum` of `1111`. Of course, `fold()` doesn’t really know it’s doing a “sum”—the choice of identifier name was ours, to make it easier to understand.

To illuminate the steps in a `fold()`, here’s `SumViaFold.kt` using an ordinary `for` loop:

``````// FoldingLists/FoldVsForLoop.kt
import atomictest.eq

fun main() {
val list = listOf(1, 10, 100, 1000)
var accumulator = 0
val operation =
{ sum: Int, i: Int -> sum + i }
for (i in list) {
accumulator = operation(accumulator, i)
}
accumulator eq 1111
}
``````

`fold()` accumulates values by successively applying `operation` to combine the current element with the accumulator value.

Although `fold()` is an important concept and the only way to accumulate values in pure functional languages, you may sometimes still use an ordinary `for` loop in Kotlin.

`foldRight()` processes elements starting from right to left, as opposed to `fold()` which processes the elements from left to right. This example demonstrates the difference:

``````// FoldingLists/FoldRight.kt
import atomictest.eq

fun main() {
val list = listOf('a', 'b', 'c', 'd')
list.fold("*") { acc, elem ->
"(\$acc) + \$elem"
} eq "((((*) + a) + b) + c) + d"
list.foldRight("*") { elem, acc ->
"\$elem + (\$acc)"
} eq "a + (b + (c + (d + (*))))"
}
``````

`fold()` first applies the operation to `a`, as we can see in `(*) + a`, while `foldRight()` first processes the right-hand element `d`, and processes `a` last.

`fold()` and `foldRight()` take an explicit accumulator value as the first argument. Sometimes the first element can act as an initial value. `reduce()` and `reduceRight()` behave like `fold()` and `foldRight()` but use the first and last element, respectively, as the initial value:

``````// FoldingLists/ReduceAndReduceRight.kt
import atomictest.eq

fun main() {
val chars = "A B C D E F G H I".split(" ")
chars.fold("X") { a, e -> "\$a \$e"} eq
"X A B C D E F G H I"
chars.foldRight("X") { a, e -> "\$a \$e" } eq
"A B C D E F G H I X"
chars.reduce { a, e -> "\$a \$e" } eq
"A B C D E F G H I"
chars.reduceRight { a, e -> "\$a \$e" } eq
"A B C D E F G H I"
}
``````

`runningFold()` and `runningReduce()` produce a `List` containing all the intermediate steps of the process. The final value in the `List` is the result of the `fold()` or `reduce()`:

``````// FoldingLists/RunningFold.kt
import atomictest.eq

fun main() {
val list = listOf(11, 13, 17, 19)
list.fold(7) { sum, n ->
sum + n
} eq 67
list.runningFold(7) { sum, n ->
sum + n
} eq "[7, 18, 31, 48, 67]"
list.reduce { sum, n ->
sum + n
} eq 60
list.runningReduce { sum, n ->
sum + n
} eq "[11, 24, 41, 60]"
}
``````

`runningFold()` first stores the initial value (`7`), then stores each intermediate result. `runningReduce()` keeps track of each `sum` value.

Exercises and solutions can be found at www.AtomicKotlin.com.