Chapter 2: Immutable stacks and queues

Introduction

This chapter introduces a progression from immutable linked lists to stacks, queues, undo-redo systems, mutable wrappers, and Hughes lists while comparing their performance characteristics.

• Chapter data-structure progression: Describe the chapter's planned progression from the immutable linked list to immutable stacks and queues, undo-redo logic, mutable interfaces over immutable structures, and the Hughes list.
  Why it matters: This roadmap connects the chapter's structures as variations on immutable lists with different capabilities and trade-offs.
• Implementation and analysis approach: Describe the recurring approach promised for the chapter: define each data-structure problem, create an interface, try implementations, and finish with an informal time-and-space performance analysis.
  Why it matters: Knowing this recurring pattern helps you follow why the chapter presents several implementations rather than only a final design.
• Immutable-structure preference: State that the author strongly prefers immutable data structures over mutable counterparts because the chapter will first explain their compelling benefits and small costs.
  Why it matters: The preference for immutability is the perspective motivating the chapter's designs and examples.

Key terms: immutable linked list, immutable stack, immutable queue, undo-redo, mutable interface, Hughes list, interface, implementation, time complexity, space complexity

2.1 Why immutability?

This brief introduction poses the question of why immutable data structures are often preferable to otherwise equivalent mutable ones.

• Preference for immutability: State the section's central question: why one might prefer an immutable data structure over an otherwise equivalent mutable one, despite immutability seeming like fewer features.
  Why it matters: The rest of the section develops reasons that immutability can be more valuable than mutability.

Key terms: mutable, immutable data structures

2.1.1 Correctness

This subsection explains that immutability preserves previously deduced facts, preventing stale-state bugs and making code easier to test, debug, and maintain.

• Correctness through stable facts: Explain why facts deduced about an immutable object remain true over time, and contrast this with how mutation can make cached facts out of date. Describe how favoring immutable data structures can eliminate an entire class of correctness bugs.
  Why it matters: If a data structure cannot change, reasoning and cached conclusions about it do not silently become invalid later.

Key terms: immutable data structures, immutable object, mutated data structure, cached fact, out-of-date fact, Roslyn

2.1.2 Historical preservation

This subsection shows how immutability preserves trustworthy past states and histories.

• Historical preservation through immutability: Explain how immutable data structures allow an application to retain and reason about its past, using a ledger or source-control history as an example.
  Why it matters: Preserved history makes prior states trustworthy and available for rollback or later inspection.

Key terms: immutability, ledger, historical record, source-control systems, rollback

2.1.3 Security

This subsection shows how mutable inputs enable a time-of-check/time-of-use security attack and why immutability is a useful defense-in-depth mitigation.

• TOCTOU privilege escalation: Explain how a time-of-check/time-of-use (TOCTOU) attack can use mutation of a shared object to obtain access to a resource that was not authorized.
  Why it matters: A value that was safe when checked may become dangerous before trusted code actually uses it.
• Immutability as security mitigation: Describe why making objects immutable by default mitigates this TOCTOU attack: low-trust code cannot alter an object in flight after high-trust code has validated it. State that immutability is one defense-in-depth measure, especially when there is no reason to mutate the data structure.
  Why it matters: Immutability closes the particular gap between checking data and using the same data later.

Key terms: mutable data, TOCTOU, time of check/time of use, high-trust code, low-trust code, ResourceName, immutable, mutable, defense in depth, in flight

2.1.4 Safer multithreading

This subsection explains why immutable objects make shared data safer in multithreaded code.

• Lock-free immutable sharing: Explain how immutability can allow an object to be shared across threads without locks. State that, because no thread can mutate the shared object, its contents remain the same regardless of thread scheduling.
  Why it matters: Immutable shared state removes a major source of races in multithreaded programs.

Key terms: shared mutable state, races, immutable objects, locks, thread scheduling

2.1.5 Memoization for time performance

This subsection explains why memoizing expensive computations on immutable data structures can trade memory for faster repeated queries.

• Memoization on immutable data: Explain why a fact computed about an immutable data structure remains valid forever, and how memoization caches function arguments and results to avoid repeating an expensive computation. State that this optimization trades additional memory use for less execution time when the same computation is needed again.
  Why it matters: Because immutable data does not change, cached answers about it can be safely reused instead of recomputed.

Key terms: immutability, memoization, cache, function arguments, results

2.1.6 Persistence for space performance

This section explains why immutable data structures can use less memory than mutable ones when both old and changed versions must coexist, through persistence and internal-state reuse.

• Persistence and structural reuse: Explain why an immutable data structure can retain both an original and changed version without doubling memory, and define persistence as efficiently reusing internal state to save space.
  Why it matters: Persistence makes immutable versions practical when a program needs to keep earlier and later states at the same time.
• Coexisting historical versions: Describe the distinction between changing a mutable array when only one version is needed and retaining both the changed and unchanged versions in memory.
  Why it matters: Many useful operations need an earlier state and a later state simultaneously, so the cost of preserving versions matters.

Key terms: persistent, immutable data structures, internal state, mutable data structure, array, changed version, unchanged version

2.1.7 The functional programming attitude

This subsection frames immutable data structures within the functional programming mindset and argues for pragmatically mixing functional and imperative styles in languages such as C#.

• Functional programming and immutability: Explain why immutable data structures are often called purely functional, relating them to programs built from functions that take and return values without mutation or other side effects.
  Why it matters: This connection explains the programming attitude behind the immutable structures developed in the chapter.
• Pragmatic mixed programming styles: Describe the section's pragmatic position that C# can mix functional and imperative programming as needed, while a functional mindset can judiciously reduce complexity in object-oriented programs. Distinguish this position from both an absolute claim that all state must be immutable and the criticism that real-world models naturally require mutable state.
  Why it matters: The book uses immutability as a useful tool within ordinary object-oriented programming, not as an all-or-nothing requirement.

Key terms: immutable data structures, purely functional, functional programming, mutations, side effects, imperative programming, line-of-business languages, C#, functional mindset, object-oriented programming

2.2 An immutable stack

This section designs and implements an immutable stack ADT as a persistent linked structure, then analyzes its behavior and performance.

• Immutable stack ADT design: Describe the operations required by the immutable stack abstract data type, including creation, Push, Peek, Pop, IsEmpty, and sequence use. Explain that immutable Push and Pop return new stack objects rather than changing an existing stack.
  Why it matters: Starting from the operations and their effects lets clients depend on a useful abstraction before choosing its implementation.
• Empty and nonempty stack classes: Explain how the implementation represents an empty stack as a singleton object and a nonempty stack as an item plus a tail stack. Describe why this null-object design avoids null references and places empty and nonempty behavior in separate implementations of the same interface.
  Why it matters: A real empty-stack object eliminates a common null error while making the recursive linked representation safe and explicit.
• Persistent tail sharing: Explain persistence in the stack example: pushing creates a new head that points to the old stack, so earlier stacks remain unchanged and stacks with the same tail share existing nodes. Distinguish this structural sharing from memoizing identical Push results.
  Why it matters: Structural sharing is what lets immutable versions coexist without copying an entire stack for every update.
• Stack complexity characteristics: State the asymptotic costs of this linked immutable stack: Push, Peek, Pop, and IsEmpty are O(1); enumerating n items takes O(n) time and O(1) extra memory apart from the enumerator; and one n-item stack requires O(n) objects, with shared tails reducing storage across versions.
  Why it matters: These costs show why a linked immutable stack is efficient for top-of-stack operations and versioned histories but not for traversing every item.

Key terms: abstract data type, ADT, immutable stack, Push, Peek, Pop, null object pattern, singleton, empty stack, nonempty stack

2.3 A covariant immutable stack

This section shows why mutable generic collections cannot safely be covariant and how an immutable stack can gain covariance by moving Push out of its interface.

• Covariance safety constraints: Explain generic covariance as allowing a value such as an IEnumerable<Giraffe> to be used where an IEnumerable<Animal> is expected, and describe C#'s safety restrictions on covariant interfaces.
  Why it matters: Covariance lets a more specific immutable collection be used through a more general type without breaking type safety.
• Mutable list type failure: Trace why a hypothetical covariant IList<T> would violate type safety: an IList<Tiger> could be viewed as an IList<Animal>, receive a Giraffe through Add, and later yield that Giraffe as though it were a Tiger.
  Why it matters: The failure case shows exactly why mutation, rather than inheritance itself, prevents safe covariance.
• Covariant stack extension method: Describe how IImStack<T> becomes covariant by removing Push(T) from the interface and supplying Push as an extension method, so the interface exposes only safe output uses of T while call sites remain unchanged.
  Why it matters: This technique preserves the convenient Push API while allowing immutable stacks of specific types to be used as stacks of more general types.

Key terms: generic covariance, covariant interface, output positions, reference type, IEnumerable<T>, IList<T>, Add, IList<Tiger>, IList<Animal>, Tiger

2.4 A queue, a queue, an immutable queue

This section implements a persistent immutable FIFO queue with two immutable stacks and analyzes its ordinary, worst-case, and claimed amortized costs.

• FIFO queue behavior: Distinguish a queue from a stack by stating that a queue dequeues the least recently enqueued item, and describe its immutable operations such as Enqueue, Dequeue, Peek, and IsEmpty.
  Why it matters: The FIFO requirement determines why a queue cannot use the same simple one-ended strategy as a stack.
• Two-stack queue representation: Describe how an immutable queue uses an enqueue stack for newly enqueued items and a dequeue stack for items ready to be removed, including the invariant that every nonempty queue has a nonempty dequeue stack.
  Why it matters: Two stacks make cheap operations at opposite logical ends possible while preserving old queue versions.
• Transfer during dequeue: Trace the special cases of Enqueue and Dequeue: enqueuing into an empty queue places the item on the dequeue stack; when dequeuing exhausts that stack while the enqueue stack is nonempty, reverse the enqueue stack to form the new dequeue stack; and return the singleton Empty queue when both become empty.
  Why it matters: These cases preserve FIFO order and ensure the queue representation continues to satisfy its invariant.
• Queue performance tradeoffs: Explain that IsEmpty, Peek, and Enqueue are constant time and memory, while a Dequeue that reverses an n-item enqueue stack is worst-case O(n) time and space; describe the section's argument for constant amortized dequeue cost and its warning that this averaging argument is later identified as flawed.
  Why it matters: Amortized cheapness does not prevent an individual dequeue from causing a noticeable, unpredictable delay.

Key terms: queue, Enqueue, Dequeue, Peek, IsEmpty, least recently enqueued, enqueue stack, dequeue stack, invariant, persistent

2.5 Mutable wrappers

This section shows how a mutable wrapper can provide convenient updates while retaining immutable snapshots of an underlying data structure.

• Mutable-over-immutable wrapper: Describe how a mutable class can wrap an immutable data structure by keeping a private reference to it, forwarding public operations to the immutable object, and replacing that reference with each resulting updated immutable object.
  Why it matters: This pattern gives code a convenient mutable-looking interface without making the underlying data structure mutable.
• Freezing immutable snapshots: Explain how accepting an initial immutable object and providing a Freeze method lets the wrapper act as a mutable builder while returning the current immutable object as a snapshot at any time.
  Why it matters: You can build conveniently through one mutable reference while preserving an immutable value whenever you need one.

Key terms: mutable wrapper, immutable data structure, private field, underlying immutable object, initial immutable object, Freeze method, immutable snapshot, mutable builder

2.6 Undo and redo

This introduction frames undo-redo for a mutable queue as a nontrivial problem and previews alternative approaches before presenting the preferred mutable-over-immutable solution.

• Queue undo difficulty: Explain why undoing an enqueue in a mutable queue cannot generally be implemented by simply dequeuing an item. State that dequeue removes the front item, which need not be the item most recently enqueued, except in the special case where the queue had been empty.
  Why it matters: Undo must restore the prior program state, not merely perform an operation that sometimes appears to reverse the last action.
• Undo-redo solution landscape: Describe the three approaches positioned by this introduction: cloning states as a bad option, using a different data structure with the command pattern as a typical option, and the author's preferred mutable-over-immutable approach. State only that the later subsections develop these options, not implementation details absent from this introduction.
  Why it matters: The alternatives provide a framework for comparing ways an application can retain or recover earlier states.

Key terms: undo-redo logic, mutable queue, enqueue, dequeue, peek, mutable-over-immutable wrapper, command pattern

2.6.1 Create an army of clones

This subsection presents clone-based undo/redo for a mutable queue and explains why its time and space costs make it impractical.

• Clone-based undo-redo workflow: Describe the clone-based approach to undo and redo for a mutable queue, including the working queue, undo stack, redo stack, and how each operation changes them.
  Why it matters: This establishes a straightforward baseline solution that later undo-redo designs improve upon.
• Cloning scalability costs: Explain why cloning the mutable queue for every operation does not scale, relating an O(n) clone to slower operations and O(n²) total memory for a queue of size n with its undo history.
  Why it matters: Recognizing the copying costs explains why practical undo-redo systems need a different representation.

Key terms: working queue, undo stack, redo stack, clone operation, O(n) time, O(n) extra space, O(n²)

2.6.2 Use a different data structure and the command pattern

This subsection implements undo and redo over mutable state by using a deque plus stacks of inverse commands, then explains why this command-based approach becomes complex.

• Mutable deque for queue operations: Describe why a mutable deque is used instead of a mutable queue for this undo-redo design, including the cheap operations available at both ends.
  Why it matters: A deque makes it possible to remove and restore queue items at the appropriate ends without requiring its implementation details here.
• Command-based undo-redo mechanism: Trace how the working deque, undo stack, and redo stack cooperate to perform enqueue, dequeue, undo, and redo operations. Explain that each user operation records an inverse command, clears redo history when a new operation occurs, and transfers an appropriate opposite command between history stacks during undo or redo.
  Why it matters: This is the standard mutable-state pattern for reconstructing prior actions without storing an immutable version of the whole state.
• Command pattern complexity: Explain why undo-redo logic over mutable program state is complicated: every undoable action needs command objects for both undoing and redoing it, and every mutable structure in program state must support reversal of each mutation.
  Why it matters: This limitation motivates the following mutable-over-immutable approach, which aims to simplify undo and redo.

Key terms: deque, EnqueueLeft, DequeueLeft, EnqueueRight, DequeueRight, working deque, undo stack, redo stack, command, command pattern

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

This section shows how a reusable mutable undo-redo helper can add cheap history navigation to immutable wrappers, while analyzing the persistence benefits and repeated worst-case costs of an immutable queue.

• Reusable undo-redo helper: Describe how an UndoRedo<T> helper centralizes the mutable undo and redo stack logic so it can be reused with wrappers around different immutable types. Explain that a mutable-over-immutable wrapper mainly forwards operations to its current immutable value while the helper manages historical states.
  Why it matters: Centralizing history management lets immutable data structures gain undo and redo without implementing separate command objects for every operation.
• Constant-time history overhead: Explain the time and direct stack-space overhead of UndoRedo<T>: its methods and properties use O(1) stack operations, while its undo and redo stack nodes consume O(n) additional memory for n stored history entries.
  Why it matters: This distinguishes the modest bookkeeping cost of history stacks from the cost of retaining the immutable versions themselves.
• Persistence-based version sharing: Explain why retaining many immutable queue versions does not duplicate every queue: persistence lets successive versions share most of their state, so each newly saved queue adds only O(1) extra memory on average.
  Why it matters: Structural sharing makes version-based undo practical even when the history contains many immutable queue objects.
• Redo and repeated dequeue costs: Distinguish redo from repeating an operation after undo: redoing a previously computed expensive dequeue is O(1) because it restores a saved immutable version, but undoing and performing that dequeue anew can repeatedly reverse the enqueue stack and repeat the O(n) cost. Describe the suggested responses: accept the case when it is not practical, use a data structure with a better worst case, or memoize Reverse by trading memory for time.
  Why it matters: Persistence makes redo exceptionally cheap, but it does not automatically protect an application from repeatedly triggering an expensive immutable-queue operation.

Key terms: UndoRedo<T>, mutable-over-immutable wrapper, undo stack, redo stack, immutable type, O(1), O(n), stack nodes, persistence, immutable queue

2.7 The Hughes list: Build it cheap, pay for it later

Introduces the Hughes list as a John Hughes–invented difference list whose cheap pushes at either end trade off against expensive top access and removal.

• Hughes list tradeoff: Describe the Hughes list's inverted stack-performance tradeoff: pushing at either end is cheap, whereas peeking at or popping the top is expensive.
  Why it matters: This unusual cost profile explains why a Hughes list is useful for cheap construction but requires payment when its contents are accessed.
• Difference list naming: State that the Hughes list was invented by Swedish computer scientist John Hughes and is also called a d list or difference list.
  Why it matters: Recognizing the alternate names helps connect this structure to discussions and implementations that use different terminology.

Key terms: Hughes list, pushing, peeking, popping, time complexity, John Hughes, d list, difference list

2.7.1 Reverse redux

This subsection refactors stack reversal around ReverseOnto, derives concatenation and tail append from it, and explains their linear costs.

• ReverseOnto semantics: Explain that ReverseOnto reverses one stack and pushes its items onto a supplied tail stack, equivalently concatenating the reverse of the left stack with an unreversed right stack. State that Reverse is the special case of ReverseOnto whose tail is empty.
  Why it matters: ReverseOnto is the primitive that makes the later stack operations easy to define.
• Derived stack operations: Describe how Concatenate preserves the left stack's original order by reversing the left stack and then reversing it onto the right stack. Explain that Append adds an item at the tail end by concatenating a one-item stack.
  Why it matters: These definitions show how operations at the inconvenient end of an immutable stack can be built from reversal.
• Linear costs and empty optimization: State that ReverseOnto takes O(n) time and memory for n items in the left stack, so Reverse, Concatenate, and Append are also O(n). Describe the Concatenate optimization: when the right stack is empty, it returns the left stack directly and avoids reversing that left stack twice.
  Why it matters: The special case avoids needless work, while the general linear cost motivates the Hughes list that follows.

Key terms: ReverseOnto, Reverse, tail, stack, Concatenate, Append, one-item stack, O(n), right stack, left stack

2.7.2 Currying and partial application

This subsection introduces currying and partial application in C#, including the idea that a curried function can retain a bound value for later use.

• Currying transformation: Explain currying as transforming a function with multiple arguments into a sequence of functions that each take one argument. Describe that a curried two-argument function takes its first argument and returns another function that accepts the second argument.
  Why it matters: Currying is the functional technique that makes it possible to create functions incrementally and is used in the Hughes list implementation.
• Partial application: Distinguish partial application from currying. Explain that partial application binds one argument of a function to a particular value, producing a new function that needs the remaining argument or arguments.
  Why it matters: Partial application lets code specialize a general operation, such as turning an adder into an add-4 function, without supplying every argument yet.
• Bound-value storage intuition: Describe the subsection's analogy that a curried function can be viewed as storing its bound value: passing n returns a function that adds n, and calling that returned function with 0 retrieves n.
  Why it matters: This storage analogy prepares the reader to see how functions can represent data in the Hughes list.

Key terms: currying, curried function, higher-order function, partial application, bound, left argument, bound value, curried, adder, add4

2.7.3 Implementing the Hughes list

This section implements a Hughes list as a delegate that represents deferred stack concatenation and derives its basic list operations from function composition.

• Hughes list functional representation: Explain that a Hughes list stores a function from an immutable stack to an immutable stack, rather than storing its elements directly. Describe how calling that function with a stack produces the represented list concatenated onto that argument stack.
  Why it matters: This representation is what lets the Hughes list postpone concatenation work instead of performing it immediately.
• Deferred concatenation tradeoff: Describe why constructing a Hughes-list function can make an otherwise expensive operation cheap at construction time, while deferring the actual concatenation cost until the list contents are requested. State that this is not free work but postponed work.
  Why it matters: The central benefit and cost of the Hughes list is shifting work from building a sequence to consuming it.
• Empty-list identity invariant: Explain that the empty Hughes list is represented by the identity function, because concatenating an empty list onto an argument stack returns that argument unchanged. Describe why all empty Hughes lists must use the same delegate so emptiness can be tested by delegate reference equality.
  Why it matters: A single shared empty representation makes the empty case recognizable and preserves the intended emptiness test.
• Composed Hughes-list operations: Trace how concatenating two nonempty Hughes lists composes their delegates as stack => hl1.c(hl2.c(stack)), so the first list precedes the second and both precede the supplied stack. Describe how a singleton uses Push on its argument stack, and how conversion to a normal stack enables Peek, Pop, and enumeration.
  Why it matters: Function composition supplies the actual implementation pattern for concatenation and the other Hughes-list operations.

Key terms: Hughes list, Concat, delegate, partial application, immutable stack, concatenation, function construction, deferred work, identity function, empty Hughes list

2.7.4 Complexity of the Hughes list

This section analyzes the Hughes list’s constant-time construction operations and linear-time costs when its deferred delegate is evaluated.

• Constant-time list construction: Explain why Make, IsEmpty, FromStack, both Concatenate operations, Single, Push, and Append are O(1) for a Hughes list. State that they only compare references or construct delegates, so their immediate cost does not depend on list size.
  Why it matters: Hughes lists are useful because large lists can be assembled cheaply before anyone needs to read them.
• Deferred access costs: Describe why Peek, Pop, and enumeration cost O(n) in the size of the represented Hughes list. Explain that these operations call ToStack, which evaluates the stored delegate, and that delegate evaluation is linear in the represented list size.
  Why it matters: The cheap construction of a Hughes list trades immediate work for work paid later when the list is converted or read.
• Concatenated delegate analysis: Trace why a delegate for the concatenation of Hughes lists hl1 and hl2 has cost O(n1+n2). State the assumptions that hl2.c costs O(n2) and hl1.c costs O(n1) independently of its input stack size, then relate n1+n2 to the size of the concatenated represented list.
  Why it matters: This argument shows that repeated deferred concatenations preserve a predictable linear cost when the final list is evaluated.

Key terms: Hughes list, Make, IsEmpty, FromStack, Concatenate, Single, Peek, Pop, enumeration, ToStack

2.7.5 Where is the data in this data structure?

This subsection reveals that a Hughes list’s delegate reference hides a closure-based binary graph whose traversal builds the resulting stack.

• Closure-based Hughes list representation: Explain where a Hughes list stores its data despite exposing only a single delegate reference. Describe how compiler-generated closure objects capture the values and Hughes-list references needed by the delegate.
  Why it matters: The apparent one-delegate representation makes sense only once you see the closure objects hidden behind the lambdas.
• Concatenation closure graph: Describe how a concatenation operation creates a closure resembling a binary-tree node. State that its captured hl1 and hl2 references act as left and right children, so a Hughes list is secretly a binary graph.
  Why it matters: Seeing concatenation as graph construction explains how the structure defers work instead of eagerly copying list contents.
• ToStack graph traversal: Trace what happens when ToStack is called on a Hughes list. Explain that the empty stack is passed to the top delegate, traversal goes to the right first to push the bottom value, and recursive traversal then passes the growing stack through left delegates to push successive elements.
  Why it matters: This traversal explains how deferred Hughes-list operations finally produce an ordinary stack in the expected element order.

Key terms: Hughes list, delegate, closure class, lambda body, captured values, concatenation, hl1, hl2, binary graph, left child

2.7.6 A couple more performance considerations

This section evaluates Hughes-list performance beyond ordinary time and memory complexity, explaining its stack-depth risk, why Pop remains linear, and when its deferred construction is worthwhile.

• Call-stack depth limitation: Explain why calling ToStack on a Hughes list built from n Push and Append operations consumes O(n) call-stack space, and why this can cause a stack-overflow exception even for lists of only a few thousand items in .NET.
  Why it matters: A data structure can have acceptable running time and heap use yet still fail because the fixed-size call stack is exhausted.
• Deferred Pop trade-offs: Describe why making Hughes-list Pop deferred and O(1) would shift cost and information elsewhere: ToStack would take O(n) in the total number of pushes and pops, and IsEmpty would need to call ToStack rather than use a reference comparison.
  Why it matters: This shows why an apparently faster operation can worsen the performance or simplicity of other essential operations.
• Hughes-list accumulation use cases: State that Hughes lists are best for accumulating a list through Push, Append, and Concatenate when the whole list does not need to be iterated until construction is finished, because those construction operations must remain sublinear.
  Why it matters: Choosing the structure for deferred list construction captures its strengths without relying on it for workloads dominated by popping or immediate traversal.

Key terms: stack depth, call stack, ToStack, stack-overflow exception, Hughes list, Pop, IsEmpty, reference comparison, deferred Pop, HList<int>.Empty

2.7.7 Reverse a linked list

Shows that a Hughes list can represent reversing a stack in constant time by deferring the actual reversal until conversion back to a stack.

• Deferred Hughes-list reversal: Explain how a Hughes-list factory modified from FromStack uses ReverseOnto so that its delegate appends the reverse of one stack onto another. State that constructing this representation takes O(1) time, while calling ToStack performs the deferred work in O(n) time.
  Why it matters: This illustrates how a deferred functional representation can make list reversal appear constant-time without eliminating the eventual linear work.

Key terms: Hughes list, ReverseOnto, FromStack, ToStack, delegate

2.8 Summary

This summary recaps why immutable data structures are safer and can be efficient, how they simplify undo-redo, and how Hughes lists defer costs with trade-offs.