Problem

You want to implement an iterative algorithm in a functional way.

Solution

Use the fold function to reduce a sequence or collection to a single value.

Discussion

The fold function is a reduction operation that can be applied to arrays or iterables. The syntax of the function is given by the following:

inline fun <R> Iterable<T>.fold(
    initial: R,
    operation: (acc: R, T) -> R
): R

The same function is defined on Array, as well as all the typed arrays, like IntArray, DoubleArray, and so on.

The idea is that fold takes two parameters: an initial value for the accumulator, and a function of two arguments that returns a new value for the accumulator. The classic example of a fold operation is a sum. See Example 4-1.

fun sum(vararg nums: Int) =
    nums.fold(0) { acc, n -> acc + n }

In this case, the initial value is 0, and the supplied lambda takes two arguments, the first of which is an accumulator. The second iterates over each value in the parameter list. The test in Example 4-2 shows that the result is correct.

@Test
fun `sum using fold`() {
    val numbers = intArrayOf(3, 1, 4, 1, 5, 9)
    assertEquals(numbers.sum(), sum(*numbers))
}

The result from the provided sum function is compared to using the direct sum function defined on IntArray. Although this shows that the operation works, it doesn’t give much insight into how. For that, add a print statement to see the values as they go by, as in Example 4-3.

fun sumWithTrace(vararg nums: Int) =
    nums.fold(0) { acc, n ->
        println("acc = $acc, n = $n")
        acc + n
    }

Invoking a test similar to the preceding one results in this:

acc =  0, n = 3
acc =  3, n = 1
acc =  4, n = 4
acc =  8, n = 1
acc =  9, n = 5
acc = 14, n = 9

The acc variable is initialized to the first argument in fold, the n variable takes on each element of the collection, and the result of the lambda, acc + n, is the new value of acc on each iteration.

The lambda itself is a binary operator, because the data types of the accumulator, each element of the collection, and the return value are all the same.

As a more interesting example, consider computing the factorial of an integer. The factorial operation is easily expressed as a recursive operation, which you’ll see again in Example 4-10:

fun recursiveFactorial(n: Long): BigInteger =
    when (n) {
        0L, 1L -> BigInteger.ONE
        else -> BigInteger.valueOf(n) * recursiveFactorial(n - 1)
    }

This operation can be rewritten as an iterative operation using fold, as shown in Example 4-4.

fun factorialFold(n: Long): BigInteger =
    when(n) {
        0L, 1L -> BigInteger.ONE
        else -> (2..n).fold(BigInteger.ONE) { acc, i ->
            acc * BigInteger.valueOf(i) }
    }

The when condition checks the input argument for 0 or 1, and returns BigInteger.ONE in those cases. The else condition uses a range from 2 to the input number and applies a fold operation that starts at BigInteger.ONE. The accumulator in the lambda is set to the product of the previous accumulator and each value as it goes by. Again, although BigInteger.ONE is the initial value of the accumulator, it’s also the identity value of the multiplication (binary) operation.

To give one more fascinating example of fold, consider computing Fibonacci numbers, where each value is the sum of the previous two. Example 4-5 shows how to implement that algorithm by using fold.

fun fibonacciFold(n: Int) =
    (2 until n).fold(1 to 1) { (prev, curr), _ ->
        curr to (prev + curr) }.second

In this case, the initial value of the accumulator is a Pair whose first and second values are both 1. Then the lambda is able to create a new value for the accumulator without caring which particular index is being computed, which is why an underscore ( _ ) is used as a placeholder for that value. The lambda creates a new Pair by assigning the current value to the previous one, and making the new value of curr equal to the sum of the existing previous and current values. This process is repeated from 2 up to the desired index. In the end, the output value is the second property of the final Pair.

Another interesting feature of this example is that the accumulator is of a different type than the elements in the range. The accumulator is a Pair, while the elements are Int values.

Using fold like this shows it is far more powerful than as demonstrated in the typical sum example.

See Also

The factorial problem is also addressed in Recipe 4.3. Using reduce instead of fold is part of Recipe 4.2.

Problem

You want to perform a reduction on a non-empty collection of values, but don’t need to set an initial value for the accumulator.

Solution

Use the reduce operation rather than fold.

Discussion

The reduce function is similar to the fold function discussed in Recipe 4.1. Its signature on Iterable is as follows:

inline fun <S, T : S> Iterable<T>.reduce(
    operation: (acc: S, T) -> S
): S

The reduce function is almost exactly the same as the fold function, and it’s used for the same purpose. Its biggest difference is that it does not have an argument that provides an initial value for the accumulator. The accumulator is therefore initialized with the first value from the collection.

Example 4-6 shows an implementation of reduce in the standard library.

public inline fun IntArray.reduce(
    operation: (acc: Int, Int) -> Int): Int {
    if (isEmpty())                             
        throw UnsupportedOperationException(
            "Empty array can't be reduced.")
    var accumulator = this[0]                  
    for (index in 1..lastIndex) {
        accumulator = operation(accumulator, this[index])
    }
    return accumulator
}

The reduce function can therefore be used only when it is appropriate to initialize the accumulator with the first value of the collection. An example is an implementation of the sum operation, similar to that shown previously in Example 4-1, and shown here in Example 4-7.

fun sumReduce(vararg nums: Int) =
    nums.reduce { acc, i -> acc + i }

If this function is invoked with several arguments, the first argument initializes the accumulator, and the other values are added to it one by one. If this function is invoked with no arguments, it would throw an exception, as shown in Example 4-8.

@Test
fun `sum using reduce`() {
    val numbers = intArrayOf(3, 1, 4, 1, 5, 9)
    assertAll(
        { assertEquals(numbers.sum(), sumReduce(*numbers)) },  
        { assertThrows<UnsupportedOperationException> {
            sumReduce()
         }        
    })
}

There is another way that using reduce can go wrong. Say you want to modify all the input values before adding them together. For example, if you want to double each number before adding it to the sum, you might implement the function as in Example 4-9.

fun sumReduceDoubles(vararg nums: Int) =
    nums.reduce { acc, i -> acc + 2 * i }

Summing the values {3, 1, 4, 1, 5, 9}, while printing out the values of the accumulator and the i variable along the way, results in the following:

acc=3, i=1
acc=5, i=4
acc=13, i=1
acc=15, i=5
acc=25, i=9

org.opentest4j.AssertionFailedError:
Expected :46
Actual   :43

The result is off because the first value in the list, 3, was used to initialize the accumulator and therefore wasn’t doubled. For this operation, it would be more appropriate to use fold rather than reduce.

In Java, streams have a method called reduce that has two overloads—one that takes just a binary operator (a lambda is used here), and one that includes an initial value as provided to fold. Also, when you call the overload that does not have an initial value, the return type is Optional, so rather than throwing an exception on an empty stream, Java returns an empty Optional.

The designers of the Kotlin library decided to implement those capabilities as separate functions, and the reduce operation throws an exception on an empty collection. If you come from a Java background, keep those differences in mind when deciding which function to use.

See Also

Recipe 4.1 discusses the fold function.

Problem

You have a recursive process and want to minimize the memory required to execute it.

Solution

Express your algorithm by using tail recursion and add the tailrec keyword to your function.

Discussion

Developers tend to favor iterative algorithms when implementing a function, because they often are easier to understand and code. Some procedures, however, are most easily expressed recursively. As a trivial example, consider computing the factorial of a number, as in Example 4-10.

fun recursiveFactorial(n: Long): BigInteger =
    when (n) {
        0L, 1L -> BigInteger.ONE
        else -> BigInteger.valueOf(n) * recursiveFactorial(n - 1)
    }

The idea is pretty simple: the factorials of 0 and 1 are both equal to 1( 0! == 1, 1! == 1) and for every number greater than 1, the factorial is equal to the product of that number times the factorial of one less than the number. Since the result is going to grow quickly, the code here uses the BigInteger class for the return type, even though the argument is a long value.

Each new recursive call adds a new frame to the call stack, so eventually the process exceeds available memory. A sample test case to demonstrate this is given in Example 4-11.

@Test
fun `check recursive factorial`() {
    assertAll(
        { assertThat(recursiveFactorial(0), `is`(BigInteger.ONE)) },
        { assertThat(recursiveFactorial(1), `is`(BigInteger.ONE)) },
        { assertThat(recursiveFactorial(2), `is`(BigInteger.valueOf(2))) },
        { assertThat(recursiveFactorial(5), `is`(BigInteger.valueOf(120))) },
        { assertThrows<StackOverflowError> { recursiveFactorial(10_000) }} 
    )
}

The JVM crashes with a StackOverflowError once the process hits the stack size limit (which defaults to 1,024 kilobytes on OpenJDK 1.8).

The approach known as tail recursion is a special case of recursion that can be implemented without adding a new stack frame to the call stack. To do this, rewrite the algorithm so that the recursive call is the last operation performed. That way, the current stack frame can be reused.

In Kotlin, a factorial version suitable for tail recursion is shown in Example 4-12.

@JvmOverloads                                                 
tailrec fun factorial(n: Long,                                
                      acc: BigInteger = BigInteger.ONE): BigInteger =
    when (n) {
        0L -> BigInteger.ONE
        1L -> acc
        else -> factorial(n - 1, acc * BigInteger.valueOf(n)) 
    }

In this case, the factorial function needs a second argument that acts as the accumulator for the factorial computation. That way, the last evaluated expression can call itself with a smaller number and an increased accumulator.

The second argument is assigned a default value of BigInteger.ONE, and since it is a default value, the factorial function can be called without it. Because Java doesn’t have default function arguments, adding the @JvmOverloads annotation means the process works when invoked from Java too.

The key piece of the puzzle, however, is the addition of the tailrec keyword. Without that, the compiler would not know to optimize the recursion. With the keyword applied, the function becomes a fast and efficient loop-based version instead.

The tests in Example 4-13 show that the function can now be called for numbers so large that the test just verifies the number of digits in the answer.

@Test
fun `factorial tests`() {
    assertAll(
        { assertThat(factorial(0), `is`(BigInteger.ONE)) },
        { assertThat(factorial(1), `is`(BigInteger.ONE)) },
        { assertThat(factorial(2), `is`(BigInteger.valueOf(2))) },
        { assertThat(factorial(5), `is`(BigInteger.valueOf(120))) },
        // ...
        { assertThat(factorial(15000).toString().length, `is`(56130)) },  
        { assertThat(factorial(75000).toString().length, `is`(333061)) }  
    )
}

If you generate the bytecodes from the Kotlin implementation and decompile them back to Java, the result is similar to Example 4-14.

public static final BigInteger factorial(long n, BigInteger acc) {
    while(true) {
        BigInteger result;
        if (n == 0L) {
            result = BigInteger.ONE;
         } else {
            if (n != 1L) {
               result = result.multiply(BigInteger.valueOf(n));
               n = n - 1L;
               continue;
            }
         }
         return result;
      }
   }

The recursive call has been refactored by the compiler into an iterative algorithm using a while loop.

To summarize, the requirements for a function to be eligible for the tailrec modifier are as follows:

• The function must call itself as the last operation it performs.

• You cannot use tailrec inside try/catch/finally blocks.

• Tail recursion is supported only on the JVM backend.