# 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

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

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

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

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

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

Empty collections result in an exception

Accumulator initialized to first element of collection

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``(``)````
````         ``}``        ````
````    ``}``)````
````}````

Validation for array of `Int`

Throws exception for no arguments

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.

Recipe 4.1 discusses the `fold` function.

# 4.3 Applying Tail Recursion

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

##### 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``)`` ``}``}`` ````
````    ``)````
````}````

High-enough number results in a `StackOverflowError`

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

Annotation allows invoking the function from Java with only one argument

Uses the `tailrec` keyword

Tail-recursive call

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

Checks number of digits in result

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:

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

Get Kotlin Cookbook now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.