3 Functional data structures

 

This chapter covers:

  • Defining functional data structures using algebraic data types
  • Demonstrating how branching logic can be written in a single expression
  • Sharing data using functional data structures
  • Using list recursion and generalising to higher-order functions
  • Practice writing and generalizing pure functions
  • Implementing List and Tree data structures from first principals

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?

In this chapter, we’ll learn the concept of functional data structures by writing our own implementations of a singly linked list and tree. We will also learn about the related processing technique of matching, and get lots of practice writing and generalizing pure functions.

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 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 higher-order functions

3.4.1 More functions for working with lists

3.4.2 Lists in the Kotlin standard library

3.4.3 Inefficiency on assembling list functions from simpler components

3.5 Trees

3.6 Summary