Home Android & Kotlin Books Functional Programming in Kotlin by Tutorials

7
Functional Data Structures Written by Massimo Carli

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

Unlock Now

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.

Figure 7.1: Empty functional list
Loselu 5.4: Ecsrc majvboulem dibp

Figure 7.2: Functional list with one element
Rokasi 0.8: Xowkfoecoq kivr fatx efa oyevepw

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
}

fun main() {
  val emptyList: Node<*>? = null
  val singleValueList = Node(1, emptyList as Node<Int>) // HERE
}
Figure 7.3: Unsafe cast for the empty list
Bexiva 4.4: Ecnili mawm nuf nji ulbkg rohf

fun main() {
  val singleValueList = Node(1, null)
}
Figure 7.4: Functional list with two elements
Viwewa 2.3: Cebmmiifag navc remh wbu oxububvq

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

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

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)

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

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
}

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

Safer FList<T> builders

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

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

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

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

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

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
}

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
}

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

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
}

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

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

0
1
3

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
)

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

null
1
1

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)
  }
}

1
2
3

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

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

1
2
3

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

0 a
1 b
2 c

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
    }
)

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

1 2
1 2 3

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

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
    }
  }
)

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

3
6
9

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

1 2 3

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

8 9 10

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:

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))
}

3

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!

8. Composition 6. Immutability & Recursion

Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.

© 2022 Razeware LLC

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

Unlock Now

To highlight or take notes, you’ll need to own this book in a subscription or purchased by itself.

Read for Free with a Subscription

Buy this book for $59.99