Last week, we ported the migration of a Scala application from imperative to functional in Kotlin with the help of the Arrow library. This was pretty easy: the example was laid out for us. This week, I’d like to go for more fundamental stuff.
This is the 2nd post in the From Imperative to Functional Programming focus series.Other posts include:
- From Imperative to Functional Programming using Arrow
- From Imperative to Functional Programming, an approach (this post)
- From Imperative to Functional Programming: a grouping issue (and how to solve it)
- From Imperative to Functional Programming: the Dijkstra algorithm
On HackerRank, there’s this problem:
Consider a staircase of size 4:
# ## ### ####Observe that its base and height are both equal to n, and the image is drawn using
#symbols and spaces. The last line is not preceded by any spaces.Write a program that prints a staircase of size n.
An easy solution imperative-style to the problem is the following:
fun staircase(n: Int): Unit {
for (i: Int in 0 until n) {
for (j: Int in 0 until n) {
if (i + j < n - 1) print(" ")
else print("#")
if (j == n - 1) println()
}
}
}The main issue of this solution is its testability.
While in theory, it could be tested by changing the where System.out writes to, it would be cumbersome (to say the least).
Plus, if multiple tests make the same changes, they cannot be run in parallel.
As FP states, side-effects are bad.
And writing to the standard out is one mighty side-effect.
Pushing side-effects to the edge
Let’s move the writing part to the edge of the code by making the staircase() function return a String -
and print the result:
fun staircase(n: Int): String {
val builder = StringBuilder()
for (i: Int in 0 until n) {
for (j: Int in 0 until n) {
if (i + j < n - 1) builder.append(" ")
else builder.append("#")
if (j == n - 1) builder.append(System.lineSeparator())
}
}
return builder.toString()
}This is the first (and IMHO, the main step) that addresses the testability issue.
Removing loops
To go further down the FP path, loops need to be migrated to recursivity.
Let’s migrate the inner loop first:
fun staircase(n: Int): String {
val builder = StringBuilder()
for (i: Int in 0 until n) {
row(i, 0, n, builder)
}
return builder.toString()
}
private fun row(i: Int, j: Int, n: Int, builder: StringBuilder) {
builder.append(if (i + j < n - 1) " " else "#")
if (j < n - 1) row(i, j+ 1, n, builder)
else builder.append(System.lineSeparator())
}Now, to the outer loop:
fun staircase(n: Int): String {
val builder = StringBuilder()
column(0, n, builder)
return builder.toString()
}
private fun column(i: Int, n: Int, builder: StringBuilder) {
if (i < n) {
row(i, 0, n, builder)
column(i + 1, n, builder)
}
}
private fun row(i: Int, j: Int, n: Int, builder: StringBuilder) {
builder.append(if (i + j < n - 1) " " else "#")
if (j < n - 1) row(i, j+ 1, n, builder)
else builder.append(System.lineSeparator())
}Optimizing a bit
In Kotlin, the tailrec modifier allows to optimize the generated bytecode of recursive functions, by writing bytecode that is imperative.
The only requirement is that the recursive call must be the last call in the function.
Let’s invert the if/else condition in the row() function:
private tailrec fun row(i: Int, j: Int, n: Int, builder: StringBuilder) {
builder.append(if (i + j < n - 1) " " else "#")
if (j >= n - 1) builder.append(System.lineSeparator())
else row(i, j+ 1, n, builder)
}Likewise, the tailrec can be applied as-is to the column() function.
Removing state
The last issue is val builder = StringBuilder().
State is not FP-compatible.
Besides, the column() and row() functions do not return, and are not pure functions.
Let’s migrate the existing code to pure functions. Since it’s a bit complex, we will do that in multiple steps.
The first step is to explicitly return the StringBuilder, while keeping the accumulator (i.e. the builder argument):
fun staircase(n: Int): String {
return column(0, n, StringBuilder()).toString()
}
private fun column(i: Int, n: Int, builder: StringBuilder): StringBuilder {
if (i < n) {
row(i, 0, n, builder)
return column(i + 1, n, builder)
}
return builder
}The next step is to change the type to an immutable one - String instead of StringBuilder:
fun staircase(n: Int): String {
return column(0, n, "")
}
private fun column(i: Int, n: Int, string: String): String {
if (i < n) {
val builder = StringBuilder(string)
row(i, 0, n, builder)
return column(i + 1, n, builder.toString())
}
return string
}Now, let’s use the same technique on the row() function.
First, introduce a return type:
private fun column(i: Int, n: Int, string: String): String {
if (i < n) {
val builder = StringBuilder(string)
val row = row(i, 0, n, builder).toString()
return column(i + 1, n, row)
}
return string
}
private tailrec fun row(i: Int, j: Int, n: Int, builder: StringBuilder): StringBuilder {
builder.append(if (i + j < n - 1) " " else "#")
return if (j >= n - 1) builder.append(System.lineSeparator())
else row(i, j+ 1, n, builder)
}And finally, let’s change the data type as above:
private fun column(i: Int, n: Int, string: String): String {
if (i < n) {
val row = row(i, 0, n, string)
return column(i + 1, n, row)
}
return string
}
private tailrec fun row(i: Int, j: Int, n: Int, string: String): String {
val line = if (i + j < n - 1) "$string " else "$string#"
return if (j >= n - 1) line + System.lineSeparator()
else row(i, j+ 1, n, line)
}Nitpicking
In the above code, there are still two declared variables, row and line.
If one wants to go the whole nine yards, they need to be removed.
To achieve that, it’s easy to introduce another (pure) function:
private tailrec fun column(i: Int, n: Int, string: String): String =
if (i >= n) string
else column(i + 1, n, row(i, 0, n, string))
}
private tailrec fun row(i: Int, j: Int, n: Int, string: String): String =
if (j >= n - 1) line(i, j, n, string) + System.lineSeparator()
else row(i, j+ 1, n, line(i, j, n, string))
}
private fun line(i: Int, j: Int, n: Int, string: String) =
if (i + j < n - 1) "$string "
else "$string#"Bonus: some Clojure love
As I recently try to learn Clojure, here’s the equivalent Clojure code:
(defn line [i, j, n, string]
(if (< (+ i j) (- n 1))
(str string " ")
(str string "#")))
(defn row [i, j, n, string]
(if (>= j (- n 1))
(str (line i j n string) (System/lineSeparator))
(row i (+ j 1) n (line i j n string))))
(defn column [i, n, string]
(if (>= i n)
string
(column (+ i 1) n (row i 0 n string))))
(defn staircase [n]
(column 0 n ""))Conclusion
As for OOP, migrating to FP for the sake of it can make the code harder to read and maintain. IMHO, just pushing the console-write calls outside the main function would be enough. It of course depends on you (and your team’s) familiarity and experience with FP.