8 Functional data structures

So far, I’ve talked mostly about higher-level functional programming concepts, and we spent quite a while examining the benefits of programming without mutable state. The problem is that programs tend to have many moving parts. While discussing purity in chapter 5, I said one of the options is to have only the main component with mutable state. All other components are pure and calculate a series of changes that should be performed on the main component, but without actually changing anything. Then the main component can perform those changes on itself.

This approach creates a clear separation between the pure parts of the program and those that deal with the mutable state. The problem is that it’s often not easy to design software like this, because you need to pay attention to the order in which the calculated changes to the state should be applied. If you don’t do that properly, you may encounter data races similar to those you have when working with mutable state in a concurrent environment.

8.1 Immutable linked lists

8.1.1 Adding elements to and removing them from the start of a list

8.1.2 Adding elements to and removing them from the end of a list

8.1.3 Adding elements to and removing them from the middle of a list

8.1.4 Memory management

8.2 Immutable vector-like data structures

8.2.1 Element lookup in bitmapped vector tries

8.2.2 Appending elements to bitmapped vector tries

8.2.3 Updating elements in bitmapped vector tries

8.2.4 Removing elements from the end of the bitmapped vector trie

8.2.5 Other operations and the overall efficiency of bitmapped vector tries

Summary