An immutable collection cannot be changed after it is created. Operations that would mutate an ordinary collection instead return another collection, leaving the original available. That sounds inconvenient for undo and redo, but it means earlier states remain intact rather than needing to be reconstructed. section 3.1 section 2.0
The strongest benefit is a stable fact: if a collection has particular contents now, no later operation can make that observation false. In a mutable compiler representation, changing the data could invalidate a cached fact without updating the cache. Immutability removes that kind of error. It also often lets threads share a collection without locks, because none of them can change its contents. section 2.1.1 section 2.1.4
Branch a stack without copying it
Start with an empty stack, push 10, then make two versions by pushing 20 and 30 onto the stack containing 10. The results are [20, 10] and [30, 10]; the earlier [10] remains unchanged. Both new stacks can refer to the same tail. This reuse is persistence: immutable versions share internal state instead of each copying the entire collection. section 2.2 section 2.1.6
var s1 = ImStack<int>.Empty;
var s2 = s1.Push(10);
var s3 = s2.Push(20);
var s4 = s2.Push(30); #1
var s5 = s4.Pop();
var s6 = s5.Pop();
Console.WriteLine(s1.Bracket());
Console.WriteLine(s2.Bracket());
Console.WriteLine(s3.Bracket());
Console.WriteLine(s4.Bracket());
Console.WriteLine(s5.Bracket());
Console.WriteLine(s6.Bracket());
The stack example keeps each version in a separate variable, then pops one branch. Compare the printed results to see which versions survive unchanged. section 2.2
Design the operations before choosing the representation. An immutable stack needs an empty value, Push, Peek, Pop, and enumeration; Push and Pop return stacks. A linked-list implementation makes a pushed item point to the previous stack. Empty-stack behavior needs care: peeking or popping it is invalid, and an empty value should not permit malformed tails. section 2.2 section 1.2
Immutability does not guarantee every operation is cheap. Reversing a linked list builds a new list in O(n) time and extra memory. A well-designed persistent deque uses trees to keep most operations O(1) on average and worst-case leaf changes O(log n) in time and extra memory. A working immutable structure can still share too little to be space-efficient; for production C#, standard immutable collections are usually preferable to a homemade stack. section 1.2.2 section 3.10 section 2.2
