In Chapter 5, “Higher-Order Functions”, you learned everything about one of the pillars of functional programming. Higher-order functions don’t just allow you to adopt a declarative approach for more readable code; they favor the use of pure functions with all the benefits and advantages you learned in Chapter 3, “Functional Programming Concepts”.
Immutability is another fundamental principle very common in functional programming. Using immutable objects allows you to implement robust code, reducing errors in different situations. For instance, think of what happens when you run your code in concurrent environments, where race conditions and deadlocks are the enemies. Immutability helps reduce that risk! You’ll see that creating immutable objects is relatively easy, but it comes at a cost you need to mitigate.
In this chapter, you’ll learn:
What immutability means in the context of the Kotlin language.
What read-only collections are and how Kotlin uses them to simulate immutability.
Why you’d want to pursue immutability.
What the cost of immutability is when running code in a Java Virtual Machine (JVM).
How immutability relates to functional programming.
What recursion is and how it helps in the use of immutable objects.
What tail recursion is and how it can optimize your code.
You’ll learn all this by writing code in Kotlin and having some fun with interesting exercises and challenges. Open up the chapter project to get started.
Immutability
Immutability is a relatively simple concept to understand: It basically describes the process of writing your code using immutable objects. An immutable object is an object whose state can’t be modified after it’s created. You describe immutable objects using immutable classes.
In Chapter 2, “Function Fundamentals”, you learned that the state of an object is the set of values of all its properties. Because of this, immutable classes describing immutable object instances don’t define mutators or expose any mutable internal state.
Before diving into the study and implementation of functional data structures in Chapter 7, it’s crucial to describe what immutability is and why it’s important.
Kotlin and immutability
In Effective Java, a popular book written by Joshua Bloch, “Item 15” states: “Classes should be immutable unless there’s a very good reason to make them mutable”. This is a rule of thumb, but most programming languages leave immutable class implementation to the developers, and each language has its own patterns. Kotlin is no different.
A simple immutable Kotlin class
For instance, Kotlin data classes can be mutable or immutable depending on if you define properties using var or val. In any case, Kotlin forces you to make this choice explicit.
Open Immutable.kt in this chapter’s material, and write the following code:
data class User(
val id: Int,
val username: String
)
User is an immutable class because you define each property using val and, as you’ll see later, because String and Int are also immutable.
Looking at the decompiled code, you get something like the following:
public final class User {
private final int id; // 1
@NotNull
private final String username; // 1
public final int getId() { // 2
return this.id;
}
@NotNull
public final String getUsername() { // 2
return this.username;
}
public User(int id, @NotNull String username) {
Intrinsics.checkNotNullParameter(username, "username");
super();
this.id = id;
this.username = username;
}
// ...
}
Note: You learned how to get the decompiled code in IntelliJ in Chapter 3, “Functional Programming Concepts” in the section “Referentially transparent expressions and Kotlin inline functions”.
Here, you see what’s related to immutability:
Each property has a private and final instance variable. private allows them to be visible only in the same class and final forces them to be initialized in the constructor without any chance of changing later.
You have getters for each property exposing the related local private instance variable. In this case, you see how the getters are also final to prevent overriding them in a User subclass. This last point is redundant because Kotlin classes can’t be extended by default, as you see in final class User. It’s also worth noting that there are no setters for the two properties.
Note: If you want to remove final from User in the generated code, you need to declare User as a normal open or abstract class in Kotlin. Remember that data classes can’t be open or abstract.
Using defensive copy
In Kotlin, using val for all the properties is necessary but not sufficient to make a data class immutable. With User, this works because id is an Int and username is a String, which are immutable classes. To prove that this isn’t enough to make the class fully immutable, add the following code to Immutable.kt:
data class WrongImmutableUser(
val id: Int,
val username: String,
val dob: java.util.Date = Date() // HERE
)
Here, you define all the properties using val, and the decompiled code translates them in private and final instance variables with only getters. However, WrongImmutableUser isn’t immutable because of the Date type. Just run the following code to prove it:
fun main() {
val w = WrongImmutableUser(1, "maxcarli") // 1
println(w) // 2
w.dob.time = 1000L // 3
println(w) // 4
}
Here, you:
Create an instance of WrongImmutableUser.
Print its initial value.
Access dob and change its state.
Print the state of WrongImmutableUser again.
Running the previous code, you’ll see how the state has actually changed:
WrongImmutableUser(id=1, username=maxcarli, dob=Tue Aug 31 00:11:33 BST 2021)
WrongImmutableUser(id=1, username=maxcarli, dob=Thu Jan 01 01:00:01 GMT 1970)
Note: The actual date you see in your output may differ. The Date default constructor uses the current time.
An option to avoid this modification is by using a defensive copy, which introduces complexity because it returns a copy of the mutable property using some verbose code like this:
data class WrongImmutableUser(
val id: Int,
val username: String,
val _dob: java.util.Date = Date() // 1
) {
val dob: Date // 2
get() = Date().apply { // 3
time = _dob.time
}
}
In this case, you:
Define _dob as a parameter for the actual date of birth property.
Declare dob as a read-only property of the same type Date.
Create a copy of _dob’s value every time the same property is accessed.
If you now run the same main you added earlier, you get the following output:
WrongImmutableUser(id=1, username=maxcarli, _dob=Tue Aug 31 00:24:44 BST 2021)
WrongImmutableUser(id=1, username=maxcarli, _dob=Tue Aug 31 00:24:44 BST 2021)
You tried to change the value of dob, but the state of WrongImmutableUser didn’t change. This is because you acted on a copy of Date. This makes the original WrongImmutableUser immutable, but the code isn’t the best, and you also need to document this behavior somewhere.
A simple mutable Kotlin class
To implement a mutable version of User, write the following code in the same Immutable.kt file:
data class MutableUser( // 1
val id: Int, // 2
var username: String // 3
)
This simple class has some important things to note:
The class MutableUser has a name giving information about the mutability. As you’ll see later, the same happens with Kotlin collections where MutableList<T> is the mutable version of List<T>.
You declare the id using val.
You need just one var property to make the whole class mutable.
Look at the decompiled code, and you now get something like this:
public final class MutableUser {
private final int id;
@NotNull
private String username; // 1
public final int getId() {
return this.id;
}
@NotNull
public final String getUsername() {
return this.username;
}
public final void setUsername(@NotNull String var1) { // 2
Intrinsics.checkNotNullParameter(var1, "<set-?>");
this.username = var1;
}
public MutableUser(int id, @NotNull String username) {
Intrinsics.checkNotNullParameter(username, "username");
super();
this.id = id;
this.username = username;
}
// ...
}
In this case, the properties you define using var:
Are translated into instance variables that aren’t final.
Have setter or mutator methods.
Now, you can run the following code without any compilation errors:
fun main() {
val mutableUser = MutableUser(8, "maxcarli")
println(mutableUser)
mutableUser.username = "massimo"
println(mutableUser)
}
Sometimes, people confuse the concept of immutability with the concept of constant. Of course, a way to make a class immutable is to have all its properties as constants, but:
Immutability refers to objects whose state can’t change after they’re created.
Constant refers to references or variables that can’t change their values once initialized.
Can’t change the value of constantUser, assigning the reference to a new MutableUser.
Can change the state of the object referenced by constantUser because of type MutableUser, which is mutable.
The same happens when you use a parameter of a function, like in the following code:
fun changeUsername(user: MutableUser) { // 1
user = MutableUser(2, "Alice") // ERROR // 2
user.username = "Alice" // 3
}
In this case, you:
Define changeUsername with a user parameter of type MutableUser.
Try to assign a different value to user. This doesn’t compile because function parameters are implicitly constant. If it were possible, you wouldn’t see the effect of the assignment outside the function. Kotlin, like Java, doesn’t have references like C++ does.
Can use user to change MutableUser‘s state because it’s mutable.
It’s interesting to look at the decompiled code:
public static final void changeUsername(@NotNull MutableUser user) {
Intrinsics.checkNotNullParameter(user, "user");
user.setUsername("Alice");
}
In this code, nothing’s preventing the reassignment of user, which is something happening at the Kotlin compiler level. Thank you, Kotlin!
Immutability and Kotlin collections
In the previous paragraphs, you created User as an example of an immutable class and MutableUser as its mutable companion. Kotlin uses the same naming convention for collections. When you refer to List<E>, you implicitly mean the immutable version of a list. If you need to modify the list, you need to refer to MutableList<E>.
It’s fundamental to understand how List<E> differs from MutableList<E>. Look at the source code, and you’ll find that List<E> is an interface in the kotlin.collections package containing some read-only operations, while MutableList<E> extends List<E>, adding mutator functions like add or remove.
Some of those are represented in the UML diagram in Figure 6.1:
Figure 6.1: List<E> and MutableList<E> relationship
To explore this more, open Collections.kt and write:
fun main() {
val immutableList = listOf(1, 2, 3, 4, 5) // 1
val asMutableList = immutableList as MutableList<Int> // 2
asMutableList.add(10) // 3
// immutableList.add(10) // DOESN'T COMPILE
}
In this code, you:
Create immutableList as an immutable List<Int> you get from listOf.
Define asMutableList, casting immutableList to MutableList<Int>. This doesn’t give any compilation errors. That’s because a List<T> can possibly be a MutableList<T>, so the Kotlin compiler can’t exclude that at compile time.
Invoke add on asMutableList.
Run the code, and you get:
Exception in thread "main" java.lang.UnsupportedOperationException
at java.util.AbstractList.add(AbstractList.java:148)
This doesn’t mean add doesn’t exist in the objects referenced by immutableList. It means the List<Int> implementation you get from listOf implements add in a way that it throws an UnsupportedOperationException when invoked. This isn’t the same as having a List<Int> implementation with no add function at all.
You get the immutability of the object provided by listOf by hiding add behind the List<E> interface and making the object safe by throwing an exception in the add implementation. The same is true for other mutators like remove. For this reason, collections like List<T> are called read-only collections.
Note: At the time of writing, there’s a proposal for a different implementation of mutable, immutable and persistence collections.
In Chapter 7, “Functional Data Structures”, you’ll learn what an immutable collection is through the implementation of FList and FTree.
Immutability advantages
So far, you’ve learned how to implement immutability in Kotlin, but you haven’t actually seen why you should pursue immutability. The main reasons are:
Simplicity
Consistency
Avoiding duplication
Thread safety
It’s useful to give some examples for each of those:
Simplicity
Immutable classes are usually easier to implement and, for sure, easier to think about. The reason for this is in the definition itself of an immutable object. If an object can’t change its state after it’s been created, it means you don’t have to implement mutators and logic to accept only values that are valid for the specific domain.
Consistency
Immutable objects are very good keys in a Map when mutable ones are dangerous. To prove that, add the following code to Consistency.kt:
data class MutableKey( // 1
var id: Int
)
fun main() {
val key1 = MutableKey(1) // 2
val key2 = MutableKey(2) // 2
val myMap = mutableMapOf( // 3
key1 to "First",
key2 to "Second"
)
println("Value for $key1 is ${myMap[key1]}") // 4
key1.id = 2 // 5
println("Value for $key1 is ${myMap[key1]} after key1 update") // 6
println("Value for $key2 is ${myMap[key2]}") // 6
println("The Map is $myMap") // 7
myMap.remove(key1).also { println("Removed $key1 from myMap") } // 8
myMap.remove(key2).also { println("Removed $key2 from myMap") } // 8
println("The Map after remove is $myMap") // 8
println("Value for $key1 is ${myMap[key1]} after key1 remove") // 9
println("Value for $key2 is ${myMap[key2]} after key2 remove") // 9
}
When you run main, you get the following output:
Value for Key(id=1) is First
Value for Key(id=2) is Second after key1 update
Value for Key(id=2) is Second
The Map is {Key(id=2)=First, Key(id=2)=Second}
Removed Key(id=2) from myMap
Removed Key(id=2) from myMap
The Map after remove is {Key(id=2)=First}
Value for Key(id=2) is null after key1 remove
Value for Key(id=2) is null after key2 remove
Following the points in the previous code, note how you:
Create MutableKey as a mutable data class with a simple Int property, id.
Initialize key1 and key2 using 1 and 2 as id, respectively.
Create myMap using key1 and key2 as the keys, and "First" and "Second" as the values, respectively.
Print the value for key1. As expected, you get the value First.
Mutate key1, assigning the value 2 to its id property. This is quite dangerous because you should already have a key for that id.
Print the values for key1 and key2, getting Second in both cases. This isn’t obvious because when changing the value of id for key1, you might expect that the related value First has overridden the existing value Second. This isn’t the case, but the situation is actually even worse.
Print myMap’s current state, which contains two equal keys with two different values. How can that be possible?
Try to remove the values for both key1 and key2, and then print myMap‘s state again. You might expect an empty Map, but this isn’t the case. The value for key1 is still there. Or, at least, that’s what you see in the output.
Access the values in the map for key1 and key2, getting null for both.
There’s definitely something wrong because of the mutability of Key. To prevent these things from happening, you should make Key immutable, which you can do by adding this to Consistency.kt:
data class Key(
val id: Int // HERE
)
Note: Key is immutable because Int is immutable and id cannot be reassigned.
Replace MutableKey with Key everywhere you’re using it. Using val for id means the following line doesn’t compile:
// ...
key1.id = 2
// ...
Comment out key1.id = 2 so your code compiles. Run the previous code using your new immutable keys, and you get the following output:
Value for Key(id=1) is First
Value for Key(id=1) is First after key1 update
Value for Key(id=2) is Second
The Map is {Key(id=1)=First, Key(id=2)=Second}
Removed Key(id=1) from myMap
Removed Key(id=2) from myMap
The Map after remove is {}
Value for Key(id=1) is null after key1 remove
Value for Key(id=2) is null after key2 remove
In this case, myMap:
Contains both the keys for different id values and you can’t change that by mutating the keys.
Is empty after removing the values for both key1 and key2.
This is actually the proof that every class should be immutable unless there’s a good reason to make it mutable. In this case, there isn’t a good reason to make Key mutable.
Avoid duplication
In the previous example, you created two different instances of Key with two different values for id. It’s interesting to see what happens if you create two different instances of the immutable version of Key for the same id. Run the following code after writing it in Reuse.kt:
fun main() {
val key1 = Key(1) // 1
val key2 = Key(1) // 1
val myMap = mutableMapOf<Key, String>()
myMap[key1] = "First" // 2
println("Value for $key1 is ${myMap[key1]}") // 3
println("The Map is $myMap") // 3
myMap[key2] = "Second" // 4
println("Value for $key2 is ${myMap[key2]}") // 5
println("The Map is $myMap") // 5
}
In this case, the output is:
Value for Key(id=1) is First
The Map is {Key(id=1)=First}
Value for Key(id=1) is Second
The Map is {Key(id=1)=Second}
Here, you:
Create two Key instances using the same value for id.
Insert a value, "First", in myMap using key1.
Print the value for key1 and the whole map, getting what you expect.
Insert a new value, "Second", in myMap using key2.
Print the value for key2, checking that the new value has overridden the old one.
The previous code proves key1 and key2 are effectively the same key, and creating new instances of them is redundant. Because Key is immutable, there’s no reason to create more instances for the same value of id. Reusing the same object also simplifies the job of the compilers that can implement and apply some low-level optimizations similar to the ones they apply to constants.
Note: Later, you’ll see some curious consequences of immutable instance reusability in the JVM when dealing with Java wrapper types like Integer, Long, etc.
Exercise 6.1: In this section, you learned it’s useful to avoid creating multiple instances of immutable classes because they represent the same value. Given the following immutable class Id:
class Id(val id: Int)
How would you change it to prevent any client from creating multiple instances of Id for the same id?
When you run this code:
fun main() {
val id1 = // Create Id for id = 1
val id2 = // Create Id for id = 1
val id3 = // Create Id for id = 2
val id4 = // Create Id for id = 2
println("${id1 === id2}")
println("${id1 === id2}")
println("${id1 === id3}")
println("${id3 === id4}")
}
You get:
true
true
false
true
Exercise 6.2: What happens if the Id class in Exercise 6.1 is a data class?
Thread safety
Immutable objects can be used safely by different threads without falling into an inconsistent state. Concurrent programming is difficult, and you always need to adopt synchronization strategies to avoid classic problems like race conditions or deadlock. Using immutable objects helps, but it’s not always enough.
A race condition happens when multiple threads access shared data, and the result depends on the order the operations happen. For instance, write this code in Safety.kt:
data class MutableCounter( // 1
var count: Int = 0
)
val counter = MutableCounter() // 2
val task = { // 3
randomDelay() // 4
counter.count++ // 3
randomDelay() // 4
if (counter.count == 2) { // 3
println("Completed")
}
}
fun main() { // 5
thread(block = task)
thread(block = task)
}
In this code, you:
Define MutableCounter as a simple mutable class, wrapping Int to use as a counter.
Initialize counter with an instance of MutableCounter.
Define a lambda that increments the value of count and prints a message if the counter value is 2.
Use randomDelay, found in Util.kt, which waits a random interval of time up to 100 milliseconds (ms).
Finally, create main, where you start two different threads running the same task on the same object counter.
Run main multiple times, and see how, sometimes, you get a single output like:
Completed
Other times, you get:
Completed
Completed
This is a typical example of a race condition, explained in Figure 6.2:
Figure 6.2: Race condition scenarios
Scenario 1: One thread accesses count and increments its value to 1. The same thread checks if the value is 2, printing nothing. Now, the other thread accesses count, increments it to 2 and executes the same test. The test is now successful and prints the Completed message.
Scenario 2: One thread accesses count and increments its value to 1. Before this thread reaches the test, the other one accesses count, incrementing the value to 2. Now, both threads execute the test, which is successful in both cases. It prints Completed and produces the double output.
You might argue that this happens because of randomDelay. This is true, but randomDelay simply simulates the scheduler’s behavior, which is the component responsible for assigning each thread in the runnable state the right to proceed. To be considered thread-safe, your code should work whatever the scheduler algorithm is and hence, whatever order of instructions the different threads run.
But how can immutability solve this specific problem? Well, immutability helps you avoid the race condition because it prevents you from updating the state of a shared object. To solve the counter problem, you need to approach it differently. Here, you’re basically assuming that you want to:
Run the task to increment the counter and check its value in a concurrent way.
Print the Completed message only once if the value of counter is 2.
In Chapter 17, “Sequence & Flow”, you’ll learn more about composition of suspendable functions. But a possible naive solution could be the following, which you can add in Safety.kt, making sure to comment out the existing main:
data class Counter( // 1
val count: Int = 0
)
fun incAndCheck(counter: Counter): Counter {
randomDelay()
val newCounter = Counter(counter.count + 1) // 2
randomDelay()
if (newCounter.count == 2) {
println("Completed")
}
return newCounter
}
fun main() {
val counter = Counter()
lateinit var counter1: Counter
val th1 = thread { // 3
counter1 = incAndCheck(counter)
}
th1.join() // 4
thread {
incAndCheck(counter1)
}
}
Concurrent programming isn’t easy because you need to use synchronization mechanisms to make your code work correctly with different scheduling algorithms. But don’t worry, the steps are outlined below.
Note: In Chapter 8, “Composition”, you’ll see how to solve this problem using the Kleisli category you learned in Chapter 3, “Functional Programming Concepts”.
In the previous code, you:
Create Counter as an immutable class.
Implement incAndCheck as a function receiving one Counter as input and returning another Counter as output. Here, it’s crucial to see how the Counter object you return is a new instance you create using counter.count + 1. Because of println, this isn’t a pure function.
Create th1 as a thread in main, where you start to execute incAndCheck.
Use join as the synchronization mechanism mentioned earlier. This allows you to make your code correct. With this, you’re asking the main thread to wait for the completion of th1. When it completes, you have the right value of counter1 to use for the run of the second thread.
You introduced synchronization to make the code correct at the cost of a lower throughput, which is the number of operations you can do in a period of time.
Note: In the case of more than two threads, the solution would be different, much more complex, and is outside the scope of this book.
Note: MapReduce is a possible alternative to manage the counter problem, but it would have the challenge of executing the println message when the counter reaches the value 2. As a possible trade-off, you might choose to display the message in the end, checking if the counter is greater than or equal to 2.
In conclusion, immutability helps you make your code more robust, but you still need a way to use it properly in different situations.
The price of immutability
As you’ve seen so far, immutability has some advantages, but nothing comes for free. Sometimes, using mutable objects instead makes the code easier to write. For instance, write the following code in ImmutabilityCost.kt:
fun mutableIncAndCheck(counter: MutableCounter) { // 1
randomDelay()
counter.count++ // 1
randomDelay()
if (counter.count == 2) {
println("Completed")
}
}
fun main() {
val counter = MutableCounter() // 2
val th1 = thread { // 3
mutableIncAndCheck(counter)
}
th1.join() // 4
thread { // 5
mutableIncAndCheck(counter)
}
}
In this case, you:
Define mutableIncAndCheck as a function that adds 1 to count of the MutableCounter you pass as a parameter and checks if the new value is 2.
Create a single instance of MutableCounter and assign it to counter.
Start a new thread, th1, invoking mutableIncAndCheck with counter.
Use join to wait for the completion of th1.
Start the second thread again, invoking mutableIncAndCheck with counter.
Run the previous code multiple times, and you’ll always get Completed once.
This code is simpler because you don’t have to do all the copies and pass them around.
Another option is creating a critical section, which is a block of code that only one thread can access at a time. Open CriticalSection.kt and write the following code:
@Synchronized // 1
fun syncedMutableIncAndCheck(counter: MutableCounter) {
randomDelay()
counter.count++
randomDelay()
if (counter.count == 2) {
println("Completed")
}
}
fun main() {
val counter = MutableCounter()
thread { // 2
syncedMutableIncAndCheck(counter)
}
thread { // 2
syncedMutableIncAndCheck(counter)
}
}
In this code, you:
Use @Synchronized to make the body of syncedMutableIncAndCheck a critical section. This means that only one thread at a time can access it.
Start two different threads executing syncedMutableIncAndCheck on the same MutableCounter object.
Because only one thread can execute syncedMutableIncAndCheck at a time, there’s no race condition on counter.
Immutability in JVM
At this point, a weird question might come to your mind. How can you change immutable objects? The example in the previous section gives you an answer. If you want to increment the count property of an immutable Counter object, you just create a new instance, like this:
val counter0 = Counter()
val counter1 = Counter(counter0.count + 1)
Is creating too many objects expensive? Of course, it is. Creating many objects forces the garbage collector (GC) to start minor and major collections, impacting the application’s performance. Fortunately, there are also ways to reduce the impact:
Reuse the same value.
Use a mutable companion.
You’ll learn more about these options below.
Note: Garbage collection is a process responsible for reclaiming the memory used by objects that are no longer active or used. Depending on the GC algorithm, this process might have some impact on CPU usage, removing the application’s resources with some visible effects. Minor and major collections are two different steps that a generational algorithm runs on young or old objects, respectively. GC is a very interesting topic, but outside the scope of this book.
Reuse the same value
Open BasicTypes.kt and write the following code:
fun main() {
val a: Int? = 1
val b: Int? = 1
println("Equals ${a == b}")
println("Same ${a === b}")
}
Note: In this code, you’re using Int?, which Kotlin, on JVM, maps to Integer. Compare this to Int, which Kotlin maps to the int primitive type and doesn’t have the concept of reference. This is because Integer can be null and int can’t. Because of this and the approaching introduction of value classes, the === operator for referential equality on basic types has been deprecated.
When you run it, you get:
Equals true
Same true
Because a and b are of type Int?, the compiler maps them to an instance of Integer. The instances should be different, and the referential equality should return false, but this isn’t happening. The reason for this outcome isn’t completely obvious. Replace the previous code with the following:
fun main() {
val a: Int? = 200
val b: Int? = 200
println("Equals ${a == b}")
println("Same ${a === b}")
}
Run the code, and you get:
Equals true
Same false
Hey, why is 1 === 1true while 200 === 200 is false? This is a design choice done for performance reasons. When you assign the literal 200 to a and b, the compiler automatically boxes the primitive value into an Integer.
If the value’s between -128 and 127, the JVM is smart enough to recycle the same values. If the literal is outside that interval, the JVM creates a new instance every time. This is because of the assumption that small values are more likely to be used multiple times in a program.
Use a mutable companion
Another option to have less impact on the GC is the creation of a mutable companion. A classic and very important example is the StringBuffer class as a mutable companion class for String. The String class is immutable, and StringBuffer is a classic thread-safe class encapsulating its state in a private instance variable kept safe using synchronized methods.
Note: StringBuilder exposes the same StringBuffer interface, removing the synchronization on the methods. This makes StringBuilder more efficient than StringBuffer, and it’s a good choice when thread safety is guaranteed in another way or not required.
Now you know all about immutability. You learned how to implement it in Kotlin and what the trade-offs are in terms of thread safety and performance. But what’s the relationship between immutability and functional programming? Is immutability somehow related to the declarative approach you use when writing higher-order functions? Is it actually possible to create applications using only immutable objects? Is the immutability real, or is it just an illusion?
Immutability and functional programming
So far, you’ve learned that two of the main concepts in functional programming are:
Pure functions
Higher-order functions
In Chapter 3, “Functional Programming Concepts”, you learned that a pure function doesn’t have any side effects. This means the function doesn’t mutate the state of any object external to the function itself. In Chapter 5, “Higher-Order Functions”, you learned how to write your code using a declarative approach and pure functions.
Open FPImmutability.kt, and add the following code:
fun main() {
var total = 0 // 1
val list = listOf(1, 5, 10, 12, 34, 55, 80, 23, 35, 12, 80)
for (i in 0 until list.size) {
if (list[i] % 5 == 0) {
total += list[i] // 2
}
}
println("Total: $total")
}
This is imperative code that allows you to calculate the sum of the values in a list that are multiples of 5. It is not only imperative, but it contains a lot of mutable variables in particular:
total for the result.
i as the index of the for to iterate over all the values in the list.
Run main, and you get:
Total: 265
Now, replace the previous code with the following:
fun main() {
val multipleOf5 = { value: Int -> value % 5 == 0 }
val total = listOf(1, 5, 10, 12, 34, 55, 80, 23, 35, 12, 80)
.filter(multipleOf5)
.sum()
println("Total: $total")
}
When you run this code, you get the same result:
Total: 265
In this case, you don’t have anything mutable. You don’t see any index to update for iterating over the list and no total to update with the elements that are multiples of 5 in the list. It’s crucial to understand that this is what you see, but it doesn’t mean it’s actually what’s happening. Control-Click on sum, and IntelliJ gets you to the following code:
@kotlin.jvm.JvmName("sumOfInt")
public fun Iterable<Int>.sum(): Int {
var sum: Int = 0
for (element in this) {
sum += element
}
return sum
}
This is how Kotlin implements sum on Iterable<T>. If you do the same on filter, you get this:
public inline fun <T> Iterable<T>.filter(predicate: (T) -> Boolean): List<T> {
return filterTo(ArrayList<T>(), predicate)
}
Selecting filterTo, you get here:
public inline fun <T, C : MutableCollection<in T>> Iterable<T>.filterTo(destination: C, predicate: (T) -> Boolean): C {
for (element in this) if (predicate(element)) destination.add(element)
return destination
}
This means that when you run the declarative code on List<T> with filter and sum, you’re actually running code with all the mutations you had in your first imperative implementation. The difference is that mutation is hidden in a well-tested and safe place, which is perfectly fine.
The declarative approach you have with functional programming favors the use of immutable objects, but it doesn’t completely prevent you from using mutable objects instead.
In fact, nothing prevents you from writing the following ugly implementation of the sum use case:
// DON'T DO THIS!!!
var total = 0
listOf(1, 5, 10, 12, 34, 55, 80, 23, 35, 12, 80)
.forEach {
if (it % 5 == 0) {
total += it
}
}
println("Total: $total")
Although the output is correct, here, you’re using the declarative function forEach to change the state of the external variable total. Please, don’t do that!
Immutability and recursion
Recursion happens when a function calls itself to accomplish a specific task. Usually, this happens until a specific condition, the terminal condition, is achieved. Recursion is a very useful technique to use when dealing with immutable objects. Suppose you want to calculate, again, the sum of all the multiples of 5 in a list. Open Recursion.kt and write the following code:
fun recAddMulti5(list: List<Int>): Int { // 1
fun loop(i: Int, sum: Int): Int = when { // 2
i == list.size -> sum // 3
list[i] % 5 == 0 -> loop(i + 1, sum + list[i]) // 4
else -> loop(i + 1, sum)
}
return loop(0, 0) // 5
}
fun main() {
val list = listOf(1, 5, 10, 12, 34, 55, 80, 23, 35, 12, 80)
println(recAddMulti5(list))
}
Run the code, and you get the same value you got in the previous examples:
265
In the previous code, you:
Define recAddMulti5 as the function that calculates the sum of the multiples of 5 in a list.
Implement loop as a recursive local function that receives, as input parameters, the index i of the current element and the partial sum. In the body, you evaluate different cases using a when expression.
Test the value of i. If the list is completed, the total sum is the value you get as input.
Check if the value at index i is a multiple of 5. If it is, you invoke loop again for the next index, adding the element at position i to the sum.
Invoke loop again for the next index with the same sum in all the other cases.
As you can see, there’s no apparent mutation here. This is because, during the execution, no variables are changing their values, but you implement a similar behavior, passing parameters to a recursive function. This might look expensive and prone to stack-overflow errors, but not all recursive functions are equal. Some recursive functions can be implemented using a loop with an evident performance improvement. It’s the case of tail-recursive functions.
Exercise 6.3: The Tower of Hanoi is a classic example of a recursive function. It is a famous game consisting of three rods and a set of n disks of different radii. At the beginning, all the disks are stacked on the first rod. You need to move all the disks from the first rod to the third, following some rules:
Figure 6a.2: Hanoi Towers
Only one disk may be moved at a time.
Each move consists of taking the top disk from one of the stacks and placing it on top of another stack or on an empty rod.
No disk may be placed on top of a disk that’s smaller than it.
Can you implement this in Kotlin?
Tailrec functions
In the previous paragraph, you learned how recursion helps you accomplish some tasks without any sort of mutation. Instead of changing the value of a variable in a cycle, you invoke a function, passing the new value as parameter.
To better explain this concept, add the following code to TailRec.kt:
fun imperativeFactorial(n: Int): Int {
var result = 1 // 1
for (value in 2..n) { // 2
result *= value // 3
}
return result // 4
}
fun main() {
println(imperativeFactorial(10))
}
This is the imperative implementation of the factorial of a number n. In this code, you:
Initialize result to 1.
Iterate over all the values from 2 to n.
Update current by multiplying it by value.
Return current.
Run this code, and you get:
3628800
Note: You represent the factorial of a positive integer value, n, with n!, which is the result of multiplying all the integer values between 1 and n. For instance, 3! = 3 * 2 * 1 = 6.
So far, so good. In the previous paragraph, you learned that you can remove mutation with recursion. Now, add the following code to the same file:
fun recursiveFactorial(n: Int): Int = when (n) { // 1
1 -> 1 // 2
else -> n * recursiveFactorial(n - 1) // 3
}
In this case, you:
Define recursiveFactorial and use the when expression, checking the different values of the input parameter n.
Return 1 as the result of 1!.
Return the multiplication of n with the recursiveFactorial(n-1) otherwise.
Run this code, and the output is, of course, the same:
fun main() {
println(recursiveFactorial(10))
}
3628800
The code is now shorter and more intuitive because it’s closer to the definition of factorial. Take a closer look, and note how you always get the result by multiplying the value of n by recursiveFactorial(n - 1). The following is a representation of what’s actually happening when you invoke recursiveFactorial(5):
In this case, note how the recursion is needed because, to return recursiveFactorial(n), the function needs to calculate recursiveFactorial(n - 1) first until it reaches the terminal condition, which is the result of recursiveFactorial(1).
Can you do better? In this case, yes! Add the following code to the same file:
fun tailRecFactorial(n: Int, fact: Int = 1): Int = when (n) { // 1
1 -> fact // 2
else -> tailRecFactorial(n - 1, n * fact) // 3
}
This looks similar to recursiveFactorial, but it’s actually very different. In this case, you:
Define tailRecFactorial with two input parameters. The first is the value n that you want to calculate the factorial of. The second is the current result, fact.
Return fact when you reach the value 1 for n.
Return the result of tailRecFactorial for n - 1, adding the factor of n in the second parameter if n isn’t 1.
Run this code, and the output is, of course, the same:
fun main() {
println(tailRecFactorial(10))
}
3628800
This time, repeat the previous exercise for recursiveFactorial(5), and you get the following sequence:
Note how you don’t actually need an invocation of recursiveFactorial(n - 1) to complete for it to return the value of recursiveFactorial(n). This is very important because it means that you could convert the recursion in a simple loop. This is an example of tail recursion. Tail recursion is a particular case of recursion, where the return value of a function is calculated as a call to itself and nothing else.
Look at the decompiled code, and you’ll see something like the following:
public static final int tailRecFactorial(int n, int fact) {
int var10000;
switch(n) {
case 1:
var10000 = fact;
break;
default:
var10000 = tailRecFactorial(n - 1, n * fact); // HERE
}
return var10000;
}
Kotlin isn’t smart enough to understand that a function is tail recursive, so you have to give it an hint. Just add the tailrec keyword like this:
tailrec fun tailRecFactorial(n: Int, fact: Int = 1): Int = when (n) { // HERE
1 -> fact
else -> tailRecFactorial(n - 1, n * fact)
}
The decompiled code now becomes:
public static final int tailRecFactorial(int n, int fact) {
while(true) { // HERE
switch(n) {
case 1:
return fact;
default:
int var10000 = n - 1;
fact = n * fact;
n = var10000;
}
}
}
The Kotlin compiler has replaced the recursion with a simple while loop, which has an important impact on performance.
Mastering recursion is an important skill when you deal with functional data structures, as you’ll see next in Chapter 7, “Functional Data Structures”.
Exercise 6.4: Tail-recursive functions usually provide better performance. Can you prove this using the chrono function in Util.kt?
/** Utility that measures the time for executing a lambda N times */
fun chrono(times: Int = 1, fn: () -> Unit): Long {
val start = System.nanoTime()
(1..times).forEach({ fn() })
return System.nanoTime() - start
}
Challenges
In this chapter, you learned a lot about immutability and recursion. You’ve already done some interesting exercises, but now it’s time for a couple more challenges.
Challenge 6.1: Immutability and recursion
In “Immutability and recursion”, you implemented recAddMulti5 as a recursive function. Is the loop internal function tail recursive?
Challenge 6.2: Tail-recursive Fibonacci
Fibonacci is one of the most famous sequences you can implement using recursion. Remember, the nth Fibonacci number is the sum of the two previous Fibonacci numbers, starting with 0, 1, 1.... Can you implement it as a tail-recursive function? Can you prove the tail-recursive function has better performance than the non-tail-recursive companion?
Key points
Immutable objects are objects whose state can’t be modified after they’re created.
Immutable classes describe immutable objects. They’re usually simpler because they don’t provide mutators.
Classes should be immutable unless there’s a very good reason to make them mutable.
Immutable objects can be used safely by different threads without putting them into an inconsistent state.
You can use immutable objects to make your code more robust, but they don’t solve all your problems.
Recursion is an important technique that allows you to handle mutation in a safe way.
Tail recursion is a particular case of recursion where the return value of a function is calculated as a call to itself and nothing else.
Where to go from here?
Congratulations! In this chapter, you learned a lot about immutability and recursion. These are very important concepts that you need to master to really understand functional data structures — the next chapter’s topic.
