chapter two

2 Immutable stacks and queues

 

This chapter covers

  • The compelling benefits and small costs of immutable data structures
  • Implementing stacks and queues
  • Exploring ways to build an undo-redo stack
  • Analyzing time and space complexity
  • Implementing the Hughes list

We started with a gentle introduction to review the basics; we’ll expand upon the immutable list in Chapter 1 to build some different kinds of lists to illustrate a few diverse concepts. We’ll build an immutable stack by making marginal improvements to our linked list. Once we have immutable stacks we can build an immutable queue, which will show how worst-case performance and amortized-case performance can be very different. We’ll explore how immutable data structures enable undo-redo logic, and how you can build a mutable interface on top of an immutable data structure. Finally, we’ll look at the Hughes list, a bizarre stack implementation which at first glance appears to contain no actual data, and has very different performance characteristics than our run-of-the-mill stack.

In each section we’ll first define the problem we’re attempting to solve with the data structure, create an interface, make some attempts at implementation, and finish up with an informal performance analysis.

Before we get into any of that though, I should say what compelling benefits changed how I approached programming; I strongly prefer immutable data structures over their mutable counterparts.

2.1 Why immutability?

2.1.1 Correctness

2.1.2 Historical preservation

2.1.3 Security: TOCTOU me about it

2.1.4 Safer multithreading

2.1.5 Memoization for time performance

2.1.6 Persistence for space performance

2.1.7 The functional programming attitude

2.2 An immutable stack

2.2.1 A covariant immutable stack

2.3 A queue, a queue, an immutable queue

2.4 Mutable wrappers

2.5 Undo and redo

2.5.1 Create an army of clones

2.5.2 Use a different data structure and the command pattern

2.5.3 Undo and redo with mutable-over-immutable data structures

2.6 The Hughes List: build it for cheap, pay for it later

2.6.1 Reverse redux

2.6.2 Currying and partial application

2.6.3 Implementing the Hughes list

2.6.4 Complexity of the Hughes list

2.6.5 Where is the data in this data structure?

2.6.6 A couple more performance considerations

2.6.7 Reverse a linked list

2.7 Summary