3 Functional data structures

We said in chapter 1 that functional programs don’t update variables or modify mutable data structures. The emphasis on keeping variables immutable raises pressing questions: what sort of data structures can we use in functional programming, how do we define them in Kotlin, and how do we operate on them?

This chapter teaches the concept of functional data structures by writing our own implementations of a singly linked list and a tree. We also learn about the related processing technique of matching and get lots of practice writing and generalizing pure functions.

This chapter has many exercises to help with this last point—writing and generalizing pure functions. Some of these exercises may be challenging. Always try your best to solve them by yourself, although you can find helpful tips and pointers at the back of the book in appendix A. If you really get stuck or would like to confirm that your answers are correct, see appendix B for complete solutions. Try to use this resource only when you absolutely must! All the source code for the samples and exercises is also available in our GitHub repository (https://github.com/fpinkotlin/fpinkotlin).

3.1 Defining functional data structures

3.2 Working with functional data structures

3.2.1 The “when” construct for matching by type

3.2.2 The when construct as an alternative to if-else logic

3.2.3 Pattern matching and how it differs from Kotlin matching

3.3 Data sharing in functional data structures

3.3.1 The efficiency of data sharing

3.4 Recursion over lists and generalizing to HOFs

3.4.1 More functions for working with lists

3.4.2 Lists in the Kotlin standard library

3.4.3 Inefficiency of assembling list functions from simpler components