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

 
 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 go or loop by convention. In Kotlin, we can define functions inside any block, including within another function definition. Because it’s local, the go 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 factorial consists of a call to go with the initial conditions for the loop.

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

Kotlin doesn’t manually detect this sort of self-recursion, but requires the function to declare the tailrec 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 TODO() is provided which results in a NotImplementedError 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.

Figure 1. Introducing new behavior to our program adding functions related to factorials.

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

 
 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, formatAbs and formatFactorial, are almost identical. If we like, we can generalize these to a single function, formatResult, 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 formatResult function is a higher-order function (HOF) which takes another function, called f (see sidebar on variable-naming conventions). We give a type to f, as we do for any other parameter. Its type is (Int) → Int) (pronounced “int to int” or “int arrow int”), which indicates that f expects an integer argument and also returns an integer.

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

Likewise, factorial accepts an Int and returns an Int, which also matches the (Int) → Int type. We can therefore pass abs or factorial as the f argument to formatResult as we do in the following two cases inside our main method:

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

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

That’s all for this article. If you want to learn more about the book, check it out on our browser-based liveBook reader here and see this slide deck.