Part 1 Extending the basics
In this part, we’ll look at some unusual twists on common data structures and algorithms that are useful for solving a variety of problems.
What possible use is a stack or a queue whose contents are unchanging? A data structure that can’t change is surprisingly useful because the more things change, the more they’re not the same. We’ll look at immutable stacks and queues in chapter 2 and explore the bizarre Hughes list, which seems to contain no data and has fast concatenation but slow popping—opposite of the performance we’d expect.
What if we have to add and remove items at both ends of a list? It’s not clear how to implement this efficiently. In chapter 3, we’ll see how finger trees solve this problem elegantly and push the limits of a generic type system in doing so.
Immutable data structures enable the use of memoization strategies for enormous compression of time and space. There’s no more vivid (or fun) illustration of this than Gosper’s HashLife algorithm. This algorithm can compute trillions of generations of a cellular automaton in seconds as long as the cellular grid computed is larger than one that would fit in all the available memory in the world. We’ll explore the meaning of Life in chapter 4.