Suppose an update must leave both the old and new versions available. With a mutable array, that can mean copying the entire array before changing one element. An immutable structure can instead reuse unchanged internal state. A structure that does this efficiently is called persistent: an update creates a new version without rebuilding everything that stayed the same. section 2.1.6
Branching stacks
Start with an immutable stack containing 10. Push 20 onto it to make one stack, then push 30 onto the original to make another. Both new stacks retain the same tail containing 10; neither changes the original. Push and Pop take O(1) time, and the shared tail needs only one node. This is sharing, not memoization: separately pushing 10 onto an empty stack can still allocate separate nodes. section 2.2
Listing 2.2 Implementing the immutable stack
class ImStack<T> : IImStack<T>
{
private class EmptyStack : IImStack<T> #1
{
public EmptyStack() { }
public IImStack<T> Push(T item) => new ImStack<T>(item, this); #2
public T Peek() => throw new InvalidOperationException();
public IImStack<T> Pop() => throw new InvalidOperationException();
public bool IsEmpty => true;
public IEnumerator<T> GetEnumerator()
{
yield break;
}
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator(); #3
}
public static IImStack<T> Empty { get; } = new EmptyStack(); #4
private readonly T item;
private readonly IImStack<T> tail;
private ImStack(T item, IImStack<T> tail) #5
{
this.item = item;
this.tail = tail;
}
public IImStack<T> Push(T item) => new ImStack<T>(item, this);
public T Peek() => item;
public IImStack<T> Pop() => tail;
public bool IsEmpty => false;
public IEnumerator<T> GetEnumerator()
{
for (IImStack<T> s = this; !s.IsEmpty; s = s.Pop())
yield return s.Peek();
}
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
In Push, the new node receives this as its tail. That reference is the mechanism that preserves and shares the previous stack. section 2.2
Immutability alone does not guarantee useful persistence. A naïve immutable deque stores a left item, a middle deque, and a right item, but pushing or popping rebuilds the middle recursively. Its versions are preserved, yet each update allocates O(n) nodes and takes linear time. The question is not merely whether an operation returns a new value; it is how much of the old value the result can reuse. section 3.2
A more effective deque groups items into small chunks at its ends and stores larger nested chunks in the middle. When an end chunk has room, an update replaces that chunk while reusing the middle and opposite end. Most pushes and pops therefore change only a small part of the structure. The resulting tree has O(log n) depth; rare worst-case pushes and pops cost O(log n) in time and extra memory, while most operations cost O(1) on average. section 3.3.2 section 3.10
Listing 3.5 The deque of minis
public sealed class Deque<T> : IDeque<T>
{ […]
private readonly IMini left;
private readonly IDeque<IMini> middle; #1
private readonly IMini right;
private Deque(IMini left, IDeque<IMini> middle, IMini right)
{
this.left = left;
this.middle = middle;
this.right = right;
}
public IDeque<T> PushLeft(T value) =>
left.Size < 4 ?
new Deque<T>(left.PushLeft(value), middle, right) :
new Deque<T>(
new Two(value, left.Left()),
middle.PushLeft(left.PopLeft()), #2
right);
public IDeque<T> PushRight(T value) =>
right.Size < 4 ?
new Deque<T>(left, middle, right.PushRight(value)) :
new Deque<T>(
left,
middle.PushRight(right.PopRight()), #3
new Two(right.Right(), value));
public IDeque<T> PopLeft()
{
if (left.Size > 1)
return new Deque<T>(left.PopLeft(), middle, right);
if (!middle.IsEmpty)
return new Deque<T>(middle.Left(), middle.PopLeft(), right);
if (right.Size > 1)
return new Deque<T>(
new One(right.Left()), middle, right.PopLeft());
return new SingleDeque(right.Left());
}
public IDeque<T> PopRight()
{
if (right.Size > 1)
return new Deque<T>(left, middle, right.PopRight());
if (!middle.IsEmpty)
return new Deque<T>(left, middle.PopRight(), middle.Right());
if (left.Size > 1)
return new Deque<T>(
left.PopRight(), middle, new One(left.Right()));
return new SingleDeque(left.Right());
}
public T Left() => left.Left();
public T Right() => right.Right();
public bool IsEmpty => false;
public IEnumerator<T> GetEnumerator()
{
foreach (var item in left)
yield return item;
foreach (var mini in middle)
foreach(var item in mini)
yield return item;
foreach (var item in right)
yield return item;
}
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
Compare the two PushLeft branches: one reuses middle directly; the full-end case pushes a chunk into it. section 3.3.2
Keeping versions makes undo and redo straightforward: store previous immutable states on stacks and switch which state is current. Shared queue state keeps the average additional storage per saved version small, and redoing an already computed expensive operation can take O(1). There is a caveat: undoing an expensive dequeue and then performing that dequeue again can repeat the expense, so a simple amortized-cost argument may fail across branches. section 2.6.3
