Suppose you need to assemble an immutable list from many smaller lists, appending at either end before you read the result. Ordinary stack concatenation can cost O(n) each time. A Hughes list—also called a difference list—makes Push, Append, and Concatenate O(1) by postponing the work. The bargain reverses familiar expectations: looking at or removing the first item is expensive. section 2.7 section 2.7.4
The C# representation is a struct whose only field is a delegate from an immutable stack to an immutable stack. Think of that delegate as an instruction to prepend the represented items to whatever stack it receives. Empty returns its argument unchanged; Single pushes one item. ToStack supplies an empty stack and obtains the list’s contents. Peek, Pop, and enumeration therefore materialize a stack first. section 2.7.3
private static HList<T> Concatenate(HList<T> hl1, HList<T> hl2) =>
hl1.IsEmpty ? hl2 : Make(stack => hl1.c(hl2.c(stack)));
Concatenation constructs a delegate rather than traversing either list. When called, it runs the right delegate first, then passes that result to the left delegate, preserving list order. section 2.7.3
That small implementation produces an unusual cost profile:
- Push, Append, Concatenate, and IsEmpty take O(1): they construct delegates or compare references, regardless of list size. section 2.7.4
- ToStack performs the postponed work; Peek, Pop, and enumeration call it. Materializing a list takes O(n) in the represented items. section 2.7.3 section 2.7.4
- A list assembled through n pushes and appends uses O(n) call-stack space when materialized. In .NET, even a few thousand elements can cause stack overflow. section 2.7.6
Build first, inspect later
Starting with an immutable stack containing 4, 3, 2, construct a Hughes list, push 5, append 1, concatenate the original Hughes list, then append 0. Reading it produces [5,4,3,2,1,4,3,2,0]. The construction composes operations; reading executes them. section 2.7.5
Figure 2.3 A Hughes list is secretly a binary graph. Delegates created from lambda bodies have automatically created closure classes with fields hl1 and hl2 that refer to the left and right lists being concatenated.
The apparent absence of stored data is a closure trick. A concatenation lambda captures references to its left and right lists, much like a binary-tree node; other closures capture items or stacks. The delegate graph is the hidden data structure. section 2.7.5
Why not defer Pop too? Then conversion would depend on the total number of pushes and pops, even if few items remained. Worse, IsEmpty could no longer rely on comparing its delegate with Empty’s: a deferred push followed by a pop would represent an empty list without using the Empty delegate. This structure is best when assembly dominates and inspection can wait. section 2.7.6
public static HList<T> Reverse(IImStack<T> fromStack) =>
fromStack.IsEmpty ?
Empty :
Make(stack => fromStack.ReverseOnto(stack));
The same technique can represent a reversed stack by capturing a call to ReverseOnto. Creating that representation takes O(1); converting it to a stack still takes O(n). Deferred work is not eliminated work. section 2.7.7
