# Writing Loops Functionally in Kotlin

From Functional Programming in Kotlin by Marco Vermeulen

__________________________________________________________________

Take 37% off Functional Programming in Kotlin by entering fccvermeulen into the discount code box at checkout at manning.com.
__________________________________________________________________

## Writing loops functionally

In order to adapt our existing program to demonstrate HOFs, we’ll introduce some new behavior. We do this by adding a new function which calculates the nth factorial. To write this simple function, we need to take a short detour by showing how loops are written in a purely functional way. We do this by introducing recursion.

First, let’s write :

Listing 1. A factorial function

`fun factorial(i: Int): Int {     fun go(n: Int, acc: Int): Int = ❶             if (n <= 0) acc             else go(n - 1, n * acc)     return go(i, 1) ❷ }`

An inner or local function definition.

Calling the local function.

The way we write loops functionally, without mutating a loop variable, is with a recursive function. Here we’re defining a recursive helper function inside the body of the factorial function. This function typically handles recursive calls that require an accumulator parameter or some other signature change which the enclosing function doesn’t have. Such a helper function is often called or by convention. In Kotlin, we can define functions inside any block, including within another function definition. Because it’s local, the function can only be referred to from within the scope of the body of the factorial function, like a local variable does. The definition of consists of a call to with the initial conditions for the loop.

The arguments to are the state for the loop. In this case, they’re the remaining value , and the current accumulated factorial . To advance to the next iteration, we call recursively with the new loop state (here, , and to exit from the loop, we return a value without a recursive call (here, we return in the case that ).

Kotlin doesn’t manually detect this sort of self-recursion, but requires the function to declare the modifier. This in turn instructs the compiler to emit the same kind of bytecode as is found in a while loop 2, provided that the recursive call is in tail position.

See the sidebar for the technical details on this, but the basic idea is that this optimization 3 (or tail call elimination) can be applied when there’s no additional work left to do after the recursive call returns.
Exercise 1.

Write a recursive function to get the nth Fibonacci number (https://en.wikipedia.org/wiki/ Fibonacci_number). The first two Fibonacci numbers are 0 and 1. The nth number is always the sum of the previous two — the sequence begins 0, 1, 1, 2, 3, 5, 8, 13, 21. Your definition should use a local tail-recursive function.

`fun fib(i: Int): Int = TODO()`

Kotlin provides us with a convenient way to mark something as TODO. A built-in function called is provided which results in a being thrown when evaluated. The result is that that such unimplemented code always compiles, but results in the exception being thrown as soon as it’s evaluated in a program. This gives us a useful way of putting reminder placeholders in our code without affecting the compilation of our code or breaking the build.

## Writing our first higher-order function

The code which we wrote has only one specific purpose. How can we adapt it to handle several scenarios? In this section, we follow an iterative approach where we crudely introduce a new requirement, then gradually improve the design until we’re left with a functional solution using a higher-order function.

Now that we’ve a function which calculates the nth factorial called , let’s introduce it to the code from before. In addition, we’ll do some naive duplication by introducing , like for the function. The new function is called from as we did for .

Listing 2. A simple program including the factorial function

`object Example {           private> fun abs(n: Int): Int =                 if> (n < 0) -n                 else> n           private> fun factorial(i: Int): Int {         ❶             fun go(n: Int, acc: Int): Int =                     if> (n <= 0) acc                     else> go(n - 1, n * acc)             return go(i, 1)         }           fun formatAbs(x: Int): String {             val msg = "The absolute value of %d is %d"             return> msg.format(x, abs(x))         }           fun formatFactorial(x: Int): String {        ❷             val msg = "The factorial of %d is %d"             return> msg.format(x, factorial(x))         }     }       fun main() {         println(Example.formatAbs(-42))         println(Example.formatFactorial(7))       ❸     }`

Add the factorial function, making it private.

Add the formatFactorial function, open by default.

Call formatFactorial from the main method.

The two functions, and , are almost identical. If we like, we can generalize these to a single function, , which accepts as an argument the function to apply to its argument:

`fun formatResult(name: String, n: Int, f: (Int) -> Int): String {         val msg = "The %s of %d is %d."     return msg.format(name, n, f(n)) }`

Our function is a higher-order function (HOF) which takes another function, called (see sidebar on variable-naming conventions). We give a type to , as we do for any other parameter. Its type is (pronounced “int to int” or “int arrow int”), which indicates that expects an integer argument and also returns an integer.

Our function matches that type; it accepts an and returns an .

Likewise, accepts an and returns an , which also matches the type. We can therefore pass or as the argument to as we do in the following two cases inside our method:

`fun main() {         println(formatResult("factorial", 7, ::factorial))     println(formatResult("absolute", -42, ::abs)) }`

A namespace prefix, , is added in order to reference the and functions. You can find more explanation about accessing and namespacing function references in the sidebar.

## Heap Sort

Get the Medium app