Summary
We looked at lists, the basic data structures used for functional programming. We had a detailed look at how list algorithms work in the immutable, side-effect-free functional world.
We saw the notion of a persistent data structure wherein the original version of the data structure is never mutated. Instead, we created a new structure, reflecting the change. We saw many cases of node insertion and removal for both lists and binary trees.
All of this copying could be thought of as too expensive. However, as we saw, we shared as many nodes as possible with the original data structure. We need to copy nodes only when we need to preserve the original version.
We implemented lists in Scala with the view of studying persistence and sharing. We implemented some functional list algorithms to better understand the fundamental concepts at play. In the rest of the book, we will use Scala's immutable lists.
Hope you have enjoyed the journey so far. Let's continue the fun ride and look at binary...
