# Chapter 4. Functional Programming

The term *functional programming* refers to a style of coding that favors immutability, is easy to make concurrent when using pure functions, uses transformations over looping, and uses filters over conditional statements. This book uses functional approaches throughout, especially in Chapters 5, 6, and 13. Many of the functions used by Kotlin in functional programming, like `map`

and `filter`

, are discussed where they arise in individual recipes of those chapters and others.

This chapter contains recipes that involve functional features that are either unique to Kotlin (as opposed to Java), like tail recursion, or are implemented somewhat differently, like the `fold`

and `reduce`

functions.

# 4.1 Using fold in Algorithms

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

##### Example 4-1. Summing integers by using `fold`

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

##### Example 4-2. Testing the `sum`

operation

`@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.

##### Example 4-3. The `sum`

function that prints each value

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

###### Note

Although the first argument to `fold`

is called `initial`

and initializes the accumulator, technically it should be the identity value for the lambda operation.

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.

##### Example 4-4. Implementing the factorial by using `fold`

`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`

.

##### Example 4-5. Computing Fibonacci numbers 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.

# 4.2 Using the reduce Function for Reductions

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

##### Example 4-6. Implementation of the `reduce`

function

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

##### Example 4-7. Implementing `sum`

using `reduce`

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

##### Example 4-8. Testing the `sum`

function implemented with `reduce`

`@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.

##### Example 4-9. Doubling values before adding

`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`

.

###### Tip

Use `reduce`

only when it is acceptable to initialize the accumulator with the first value of the collection and no additional processing is done on the other values.

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.

# 4.3 Applying Tail Recursion

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

##### Example 4-10. Implementing a factorial as a recursive function

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

##### Example 4-11. Testing the recursive factorial implementation

`@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`

`(`

`1`

`2`

`0`

`)`

`)`

`)`

`}`

`,`

`{`

`assertThrows`

`<`

`StackOverflowError`

`>`

`{`

`recursiveFactorial`

`(`

`1`

`0`

`_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.

##### Example 4-12. Implementing a factorial with a tail call algorithm

`@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.

###### Tip

The `tailrec`

keyword tells the compiler to optimize away the recursive call. The same algorithm expressed in Java will still be recursive, with the same memory limitations.

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.

##### Example 4-13. Testing the tail-recursion implementation

`@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`

`(`

`1`

`2`

`0`

`)`

`)`

`)`

`}`

`,`

`// ...`

`{`

`assertThat`

`(`

`factorial`

`(`

`1`

`5`

`0`

`0`

`0`

`)`

`.`

`toString`

`(`

`)`

`.`

`length`

`,`

``is``

`(`

`5`

`6`

`1`

`3`

`0`

`)`

`)`

`}`

`,`

`{`

`assertThat`

`(`

`factorial`

`(`

`7`

`5`

`0`

`0`

`0`

`)`

`.`

`toString`

`(`

`)`

`.`

`length`

`,`

``is``

`(`

`3`

`3`

`3`

`0`

`6`

`1`

`)`

`)`

`}`

`)`

`}`

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

##### Example 4-14. Decompiled Java from the Kotlin bytecodes (rewritten)

`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:

Get *Kotlin Cookbook* now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.