7. Functional Data Structures

Written by Massimo Carli

In Chapter 6, “Immutability & Recursion”, you learned all about immutability and how to use it in Kotlin. You learned:

• How using immutable objects helps solve concurrency problems.
• The cost you have to pay in terms of code simplicity.
• How to implement recursive functions and use the tailrec keyword to improve performance.

Immutability and recursion are fundamental skills you need to understand and implement immutable data structures and, in particular, persistence collections. In this chapter, you’ll learn:

• What an immutable data structure is.
• What it means for a data structure to be persistent.
• How to implement an immutable and persistent list as a classic example of immutable and persistent data structures.
• What pattern matching is and what you can actually achieve in Kotlin.
• What the main functions for a collection are and how to implement them in Kotlin.

As always, you’ll learn all this by solving some interesting exercises and challenges.

Immutable data structure

In the “Immutability and Kotlin collections” section in Chapter 6, “Immutability & Recursion”, you saw that the List<T> implementation you usually get in Kotlin isn’t an actual immutable collection, but something called a read-only collection. This means builder functions like listOf<T>() return objects you see through the List<T> interface, but they aren’t actually immutable. They still have mutators, but they just implement them by throwing exceptions when invoked.

As the name says, an immutable data structure is a data structure that can’t change after it’s created. However, you can still add or remove values in a sense. What you get from an immutable data structure after adding or removing an element is another data structure with the element added or removed. This might look like a waste of memory on the Java Virtual Machine with performance consequences because of the garbage collector. This isn’t always true.

Persistent singly linked list

The persistent singly linked list is a classic example of a functional data structure. You’ll find it often in functional programming tutorials because of its simplicity and because its implementation is a very good exercise of the typical functions a collection provides. Before diving into the code, it’s useful to have a visual representation that explains how to handle immutable data structures.

Imagine you have to build a singly linked list which is, of course, initially empty like in Figure 7.1:

You usually represent an empty list with the Nil value, but you could call it Zero, Empty or even Null. It’s important to note how the empty list Nil doesn’t depend on the type of values the list should contain. All the empty lists are the same.

You can then try to add an element, for instance, an Int, getting what’s shown in Figure 7.2:

This new representation of a list is very interesting because it’s somehow different from what you would’ve normally implemented using a classic object-oriented approach.

To prove this, add the following code in ObjectOrientedList.kt in the material for this chapter:

data class Node<T>( // 1
  val value: T,
  val next: Node<T>? = null
)

fun main() {
  val emptyList: Node<*>? = null // 2
  val singleValueList = Node(1) // 3
}

In this code, you define:

1. Node<T> as an immutable class with a property for value and one for the optional next element in the list of type Node<T>?.
2. emptyList as a constant of type Node<*> initialized with null.
3. singleValueList as a simple Node<Int>.

This is different from what you have in Figure 7.2 because there’s no explicit relation between what you have in singleValueList and emptyList. Also, emptyList is just a null value that doesn’t give meaning to the empty list object.

Of course, you can make the relation with emptyList explicit, modifying the previous code like this:

fun main() {
  val emptyList: Node<*>? = null
  val singleValueList = Node(1, emptyList as Node<Int>) // HERE
}

Here, you pass emptyList as a second parameter of the Node<T> primary constructor, and this requires you to do an explicit cast with as. IntelliJ isn’t super happy, as you see in Figure 7.3:

The following change would fix this warning, but again, it would just be another way of creating a simple Node<T>, and you’d lose the relation with emptyList:

fun main() {
  val singleValueList = Node(1, null)
}

To better understand how to implement the persistent singly linked list, look at Figure 7.4, illustrating the list you get by adding a second element:

Again, you might still have the references to the previous emptyList and singleValueList, but now you can find a pattern in how you build the list. In this case, the object-oriented code gives you a hint. Just add the following definition to the bottom of main:

val twoValuesList = Node(2, Node(1, null))

This is quite normal code, but it gives you an idea; it helps you see every list as a collection with the following characteristics:

1. It can be empty.
2. It can contain a value in the head with an optional list as the tail. These are represented as value and next respectively within Node.
3. In the last case, the tail can be empty.

This leads you to the following definition of FList<T>. Write it in FList.kt:

sealed class FList<out T> // 1
object Nil : FList<Nothing>() // 2
internal data class FCons<T>(
  val head: T,
  val tail: FList<T> = Nil
) : FList<T>() // 3

With this code, you define:

1. The sealed class FList<T>, which allows you to define a limited set of implementations that Kotlin forces you to define in the same file or package.
2. Nil as an object that represents the empty list. Because the empty list is the same for every type T, you can represent it as FList<Nothing>. This works because Nothing is a subtype of every other type and because FList<T> is covariant. You define the covariance of FList<T> using the out keyword. If you need a reminder on covariance, take a peek at Chapter 4, “Expression Evaluation, Laziness & More About Functions”.
3. FCons<T> as the second way to represent FList<T>: a head with another FList<T> as tail. Note how Nil is the default tail.

Note: The name Cons comes from the word “Constructor”. For this reason, one of the names for FList<T> is ConsList<T>.

FList<T> builders

In Kotlin, you can create different collection implementations using some builder methods. For instance, you create a read-only list of Int with:

val readOnlyList = listOf(1,2,3)

You create a mutable map with:

val mutableMap = mutableMapOf(1 to "One", 2 to "Two")

What builder function would you create for FList<T>? Open Builders.kt and write the following code:

fun <T> fListOf(vararg items: T): FList<T> { // 1
  val tail = items.sliceArray(1 until items.size) // 2
  return if (items.isEmpty()) Nil else FCons(items[0], fListOf(*tail)) // 3
}

This code allows you to create FList<T> using the following syntax:

fun main() {
  // ...
  val flist = fListOf(1, 2, 3)
}

In the previous code:

1. You define fListOf as a builder function using a vararg parameter for values of type T. It’s important to note how the return type is FList<T>.
2. The type for the vararg parameter is actually an Array, so in this case, items has the type Array<T>. You then use sliceArray for getting another array containing everything but the first element. If the initial array is empty or contains just one element, tail will also be the empty Array<T>.
3. If items is empty, you return Nil. Otherwise, you return FCons<T> where head is the first element, and tail is the FList<T> you get, invoking fListOf recursively on the sliced array.

Note: Note the use of the spread operator *, which allows you to use the values in an array as if they were a list of multiple vararg input parameters.

Safer FList<T> builders

Now, add the following code to main in the same FList.kt file:

fun main() {
  // ...
  val emptyList = fListOf() // ERROR
}

In this case, you have an error because you’re not providing the specific value for the type parameter T. An easy fix would be to provide what’s missing, like this:

fun main() {
  // ...
  val emptyList = fListOf<Int>()
}

But you know the empty list Nil is the same for every type, so the Int information should be obsolete. In this case, you have two different options:

1. Use Nil directly.
2. Use fListOf() as a parameter of another function, taking advantage of the type inference the Kotlin compiler provides.

Add this code to main as an example:

fun main() {
  val emptyList = Nil // 1
  val singleElementFList = FCons(2, fListOf()) // 2
}

In this code:

1. You use Nil directly.
2. You use fListOf when Kotlin is already expecting FList<Int> because of the FCons<T> you use for singleElementFList.

In the second point, there’s a problem, though. singleElementFList’s type is FCons<T> and not FList<T>. How can you prevent the direct use of Nil and FCons<T>, forcing all the clients to use them through a reference of type FList<T>?

You already solved a similar problem in Exercise 6.1 in Chapter 6, “Immutability & Recursion”. Comment out all the code in Builders.kt, open FList.kt and replace the FList<T> definition with the following:

sealed class FList<out T> {

  companion object { // 1
    @JvmStatic
    fun <T> of(vararg items: T): FList<T> { // 2
      val tail = items.sliceArray(1 until items.size)
      return if (items.isEmpty()) {
        empty()
      } else {
        FCons(items[0], of(*tail))
      }
    }

    @JvmStatic
    fun <T> empty(): FList<T> = Nil // 3
  }
}

internal object Nil : FList<Nothing>() // 4
internal data class FCons<T>(
  val head: T,
  val tail: FList<T> = Nil
) : FList<T>() // 5

In this code, you:

1. Use a companion object to define of and empty.
2. Implement of as the replacement for the previous fListOf. This allows you to use FList.of() syntax. The body is very similar to the fListOf you saw earlier. You replaced fListOf with of and Nil with the invocation of empty.
3. Define empty as a builder for the empty list Nil. It’s important to see how the return type is FList<T>. This simplifies the use of empty() in the following examples.
4. Create Nil as an internal object.
5. Define FCons<T> as an internal data class.

To try this code, open Main.kt and add:

fun main() {
  val emptyList = FList.empty<Int>() // 1
  val singleElementList = FList.of(1) // 2
  val singleElementList2 = FCons(1, emptyList) // 3
  val twoElementsList = FList.of(1, 2) // 4
}

In this code, you:

1. Create emptyList using FList.empty<Int>(), which still needs a type to help the compiler with type inference.
2. Use FList.of to create singleElementList with one element.
3. Create another FList<Int> with a single element using FCons<T> passing emptyList as a second parameter.
4. Use FList.of with two Int values to properly create an FList<Int> with two elements.

Declaring Nil and FCons<T> as internal has the advantage of hiding the actual implementations in code in different modules and, as you’ll see very soon, this might cause some problems. To understand what, it’s very useful to introduce the concept of pattern matching.

Pattern matching

A simple exercise can help you understand what pattern matching is and how it can be helpful. Suppose you want to implement size as a function that returns the number of elements in a given FList<T>. Open Accessor.kt and write the following code:

// DOESN'T COMPILE IN ANOTHER MODULE
fun <T> FList<T>.size(): Int = when (this) { // 1
  is Nil -> 0 // 2
  is FCons<T> -> 1 + tail.size() // 3
}

Because Nil and FCons<T> are internal, the previous code wouldn’t compile if implemented in a different module. However, you should note a few interesting things. Here, you:

1. Define the size extension function, which should return the number of elements in FList<T>. The result value is the evaluation of a when expression on this.
2. Return 0 if the current FList<T> is Nil, which is the empty FList<T>.
3. If the current FList<T> isn’t Nil, it means it has a head and tail. size is then the size of the tail + 1.

As said, this code wouldn’t compile if written in a different module because Nil and FCons<T> are internal classes. This doesn’t allow the use of the is keyword to test if a reference of type FList<T> is actually Nil or FCons<T>. In the latter case, you’d also need a way to get the reference to head and tail. You need something very similar to what, in languages like Swift or Scala, is called pattern matching. Something that would make this pseudo-code compile is:

when(list){
 Nil -> {}
 (head, tail) -> {}  
}

Unfortunately, that syntax doesn’t work yet with Kotlin, and it probably never will.

Note: Kotlin provides very limited pattern matching. For instance, if you release the constraint to have Nil and FCons<T> internal, you can make the previous code for size compile and, for FCons<T>, the tail property would be available as a consequence of the smart casting.

However, you can still do something to achieve a similar result. Open FList.kt and add the following code:

fun <T, S> FList<T>.match( // 1
  whenNil: () -> S, // 2
  whenCons: (head: T, tail: FList<T>) -> S // 3
) = when (this) {
  is Nil -> whenNil() // 4
  is FCons<T> -> whenCons(head, tail) // 5
}

In this code, you:

1. Define the match higher-order function as an extension of FList<T>. This function has two type parameters: T and S. T is the type for FList<T>. S is the type of result of the expression you want to evaluate if Flist<T> is Nil or FCons<T>.

2. Declare the first parameter whenNil as the lambda you want to evaluate if the FList<T> receiver is Nil. The lambda whenNil evaluates in a value of type S.

3. Define the second parameter, whenCons, as the lambda you want to evaluate if the FList<T> receiver is FCons<T>. Again, the lambda whenCons evaluates to a value of type S. Here, it’s important to note how whenCons accepts head and tail as input parameters.

4. Check if the receiver FList<T> is Nil, retuning the evaluation of whenNil.

5. Use the smart casting Kotlin provides to extract head and tail if the receiver value is FCons<T> and use them as input parameters for whenCons.

Because you define match in FList.kt, is Nil and is FCons<T> are available. Now, return to Accessor.kt, and replace the previous implementation of size with the following:

fun <T> FList<T>.size(): Int = match( 
  whenNil = { 0 }, // 1
  whenCons = { head, tail -> 1 + tail.size() } // 2
)

Here, you implement size, returning the result of the match function evaluating:

1. { 0 } if FList<T> is Nil.
2. {1 + tail.size()} if the receiver is FCons<T>.

To test the size function, just add the following code to the same file and run:

fun main() {
  println(FList.empty<Int>().size())
  println(FList.of(1).size())
  println(FList.of(1, 2, 3).size())
}

You’ll get the following output:

0
1
3

Exercise 7.1: Implement the extension function isEmpty(), which returns true if FList<T> is empty and false otherwise.

Try to answer these questions without the support of IntelliJ and check your solutions in Appendix G or the challenge project.

Note: The match function allows you to make the selection of the different states more explicit. FList<T> can be Nil or FCons<T>. You’ll use it many times in the rest of the chapter, but you could do the same directly using Nil and FCons<T> and leveraging Kotlin’s smart cast. Remember, you can use Nil and FCons<T> only in this module because of their internal visibility.

Other FList<T> accessors

You can use the match function you created earlier in the implementation of most of the functions you’ll see in the following paragraphs. Another simple function is the one returning Flist<T>’s head. Open Accessor.kt and add the following code:

fun <T> FList<T>.head(): T? = match( 
  whenNil = { null },  // 1
  whenCons = { head, _ -> head } // 2
)

In this case, you use match, returning:

1. null if the receiver is Nil.
2. head if the receiver is FCons<T>.

Again, you can easily test this by adding the following code to main in the same file:

fun main() {
  // ...
  println(FList.empty<Int>().head())
  println(FList.of(1).head())
  println(FList.of(1, 2, 3).head())
}

Run it, and check that you get the following output:

null
1
1

Exercise 7.2: Implement the extension function tail(), which returns the tail of a given FList<T>.

Iteration

Iterating over a collection is one of the most important features a data structure provides. How would you allow clients to iterate over the elements in FList<T>? The List<T> interface provides the forEach higher-order function. Open Iteration.kt and add the following code:

fun main() {
  listOf(1, 2, 3).forEach {
    println(it)
  }
}

Of course, running this code, you’ll get:

1
2
3

To implement the same forEach for your FList<T>, add the following code to the same file:

fun <T> FList<T>.forEach(fn: (T) -> Unit): Unit = match( // 1
    whenNil = {}, // 2
    whenCons = { head, tail -> // 3
      fn(head)
      tail.forEach(fn)
    }
)

Here, you define forEach:

1. With the lambda function fn as an input parameter. The lambda fn receives the current element of type T as input.
2. If the receiver is Nil, you do nothing.
3. If the receiver isn’t Nil, you invoke fn(head) and then recursively invoke forEach on the tail.

Run the following code:

fun main() {
  // ...
  FList.of(1, 2, 3).forEach {
    println(it)
  }
}

And you’ll get:

1
2
3

Exercise 7.3: Kotlin provides forEachIndexed for the Iterable<T> interface, which accepts as input a lambda of type (Int, T) -> Unit. The first Int parameter is the index of the item T in the collection. To test forEachIndexed, run the code:

listOf("a", "b", "c").forEachIndexed { index, item ->
 println("$index $item")
}

Getting the following output:

0 a
1 b
2 c

Can you implement the same for FList<T>?

Exercise 7.4: Another option to implement forEachIndexed is to make FList<T> an Iterable<T>. How would you do that? To make all the code coexist in the same codebase, call the Iterable<T> version IFList<T> with INil and ICons<T>.

Mutators

You just implemented some interesting functions to access elements in FList<T> or iterate over them. Now, it’s time to do something even more interesting that will allow you to actually add or remove elements and update the immutable singly linked list.

Inserting

In this chapter’s introduction, you saw, with some illustrations, how to add elements at the head of FList<T>. Later, in Exercise 7.5, you’ll implement addHead. Implementing append to add an element at the end of FList<T> is a little more challenging because it implies copying the initial list to a new one. Open Mutator.kt and add the following code:

fun <T> FList<T>.append(newItem: T): FList<T> = match( // 1
    whenNil = { FList.of(newItem) }, // 2
    whenCons = { head, tail ->
      FCons(head, tail.append(newItem)) // 3
    }
)

In this code, you:

1. Define append as an extension function of FList<T> with a single input parameter newItem of type T. You still use match.
2. Create a new FList<T> if the current value is Nil, with the value to append as the only element. This will be the tail of the new FList<T> you’re building.
3. Create a new FCons<T> when the current reference is FCons<T>, using head as the initial value and the list you get by appending newItem to tail.

To test the previous code, run:

fun main() {
  val initialList = FList.of(1, 2)
  val addedList = initialList.append(3)
  initialList.forEach {
    print("$it ")
  }
  println()
  addedList.forEach {
    print("$it ")
  }
}

You’ll get:

1 2
1 2 3

To help visualize what’s happening, think of it like this:

(1, (2, ())).append(3) // 1
(1, (2, ()).append(3)) // 2
(1, (2, ().append(3))) // 3
(1, (2, (3, ()))) // 4

Here:

1. You start invoking append(3) on an FList<Int> of 2 elements. Note how the last tail is Nil, represented by () above.
2. The first element is still 1, and the tail is the one you get, invoking append(3) on the previous tail.
3. Again, you invoke append(3) on the tail, which is Nil. This creates an FList<Int> with the only element 3.
4. The result is a new FList<Int> of 3 elements.

Exercise 7.5: Implement addHead, which adds a new element at the head of an existing FList<T>.

Filtering

In the previous chapters, you met the filter function that lets you select elements using some predicate. How would you implement the filter function for FList<T>? In Filter.kt, add the following code:

typealias Predicate<T> = (T) -> Boolean // 1

fun <T> FList<T>.filter(predicate: Predicate<T>): FList<T> = match(
  whenNil = { FList.empty() }, // 2
  whenCons = { head, tail ->
    if (predicate(head)) {
      FCons(head, tail.filter(predicate)) // 3
    } else {
      tail.filter(predicate) // 4
    }
  }
)

Here, you:

1. Define Predicate<T>, which you met in previous chapters.
2. Implement filter using the match function. When the receiver is Nil, you return the empty list using FList.empty(). You could also return Nil directly here.
3. Evaluate the predicate on head when the receiver isn’t empty. If it evaluates to true, you return FList<T> using the same head and what you get invoking filter on the tail.
4. Return what you get invoking filter on the tail if the predicate doesn’t evaluate to true on the head.

To test the previous code, run:

fun main() {
  FList.of(1, 2, 3, 4, 5, 6, 7, 8, 9)
    .filter { it % 3 == 0 }
    .forEach { println(it) }
}

This filters the values that are multiples of 3 in FList<Int>. In this case, the output is:

3
6
9

Exercise 7.6: Kotlin defines the take function on Iterable<T> that allows you to keep a given number of elements. For instance, running the following code:

 fun main() {
   listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
     .take(3)
     .forEach { print("$it ") }

You’d get:

1 2 3

Can you implement the same take function for FList<T>?

Exercise 7.7: Kotlin defines the takeLast function on Iterable<T> that allows you to keep a given number of elements at the end of the collection. For instance, running the following code:

fun main() {
  listOf(1, 2, 3, 4, 5, 6, 7, 8, 9, 10)
    .takeLast(3)
    .forEach { print("$it ") }

You’d get:

8 9 10

Can you implement the same takeLast function for FList<T>?

Why FList<T> is a persistent data structure

So far, you’ve met the descriptors immutable, functional and persistent for data structures, and it’s important to quickly emphasize what they are:

• Immutable data structure: This data structure can’t change after it’s been created. This means you can’t replace a value in a specific position with another or remove another element. When performing this kind of operation, you need to get another immutable data structure, as you’ve seen for other immutable objects in Chapter 6, “Immutability & Recursion”.
• Functional data structure: This is a data structure you can interact with using only pure functions. For instance, you get a new FList<T> filtering the data of another one using a predicate you represent using a pure function. As you learned in Chapter 3, “Functional Programming Concepts”, a pure function doesn’t have any side effects and is represented using a referentially transparent expression. In the following chapters, you’ll see many other functions like map, flatMap and others.
• Persistent data structure: This data structure always preserves the previous version of itself when it’s modified. They can be considered immutable, as updates aren’t in place. The FList<T> you implemented in this chapter is persistent. You see this when you add a new value. The existing object is still there, and it just becomes the tail of the new one.

Challenges

In this chapter, you had a lot of fun implementing some of the classic functions you find in collections for the singly linked list FList<T>. You also had the chance to use the recursion skills you learned in Chapter 6, “Immutability & Recursion”. Why not implement some more functions?

Challenge 7.1: First and last

Kotlin provides the functions first and last as extension functions of List<T>, providing, if available, the first and last elements. Can you implement the same for FList<T>?

Challenge 7.2: First and last with predicate

Kotlin provides an overload of first for Iterable<T> that provides the first element that evaluates a given Predicate<T> as true. It also provides an overload of last for List<T> that provides the last element that evaluates a given Predicate<T> as true. Can you implement firstWhen and lastWhen for FList<T> with the same behavior?

Challenge 7.3: Get at index

Implement the function get that returns the element at a given position i in FList<T>. For instance, with this code:

fun main() {
  println(FList.of(1,2,3,4,5).get(2))
}

You’d get:

3

Because 3 is the element at index 2. Consider 0 the index of the first element in FList<T>.

Key points

• An immutable data structure is a data structure that can’t change after it’s been created.
• A functional data structure is a data structure you can interact with using only pure functions.
• A persistent data structure is a data structure that always preserves the previous version of itself when it’s modified.
• Kotlin doesn’t have pattern matching, but you can achieve something similar using the smart cast feature.
• FList<T> is the implementation of a singly linked list and is a very common example of a functional, immutable and persistent data structure.

Where to go from here?

Congratulations! In this chapter, you had a lot of fun implementing the FList<T> functional data structure. You had the chance to apply what you learned in Chapter 6, “Immutability & Recursion”, for implementation of the most common higher-order functions like filter, forEach, take and many others. It’s crucial to say that these are just the first, and many others will come in the following chapters. In Chapter 9, “Data Types”, you’ll get to add more functions for FList<T>. For now, it’s time to dive deep into the concept of composition. See you there!