# # 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.**