Atomic Kotlin

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

← Recursion →