From Functional Programming in Kotlin by Marco Vermeulen This article explores how to write loops functionally in Kotlin. |
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
:
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 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
.
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, 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.