Learning Functional Data Structures and Algorithms

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 ...