12 A short introduction to functional data structures

In chapter 11, you saw how to create immutable objects. Particularly, section 11.1 showed the pitfalls of state mutation when concurrency is involved. These pitfalls become even more evident when dealing with collections. Because it takes longer to process a large collection than to update a single object, there are greater chances of a race conditions occurring (we saw an example of this in section 1.1.3).

Now that you know about immutable objects, let’s look at some of the principles behind the design of immutable data structures. Note that the terms functional data structures and immutable data structures are used interchangeably in the literature.¹ You’ll see that the principles are the same: after all, objects are just ad hoc data structures.

If you commit to only working with immutable data, all data structures should also be immutable. For example, you should never add an element to a list by changing its structure, but rather create a new list with the desired changes.

This may initially cause you to raise your eyebrows: “To add an item to a list, I need to copy all existing elements into a new list along with the extra item? How inefficient is that?”

12.1 The classic functional linked list

12.1.1 Common list operations

12.1.2 Modifying an immutable list

12.1.3 Destructuring any IEnumerable

12.2 Binary trees

12.2.1 Common tree operations

12.2.2 Structure sharing

12.3 In conclusion

Exercises

Summary