A delegate is a type-safe reference to a compatible method or function. Its signature describes what can be called, while its value can capture a computation for later execution. section 2.7.3
A Hughes list uses a delegate as its entire representation: instead of storing items, it stores a function that concatenates a future stack. Construction stays cheap, while the deferred work is paid when the list is materialized. section 2.7.3
The delegate-based design has distinctive consequences:
- A nested Concat delegate replaces the clumsy Func<IImStack<T>, IImStack<T>> type and makes the field and constructor readable. section 2.7.3
- Lambdas such as stack => stack.Push(item) construct delegates that capture the operation without immediately executing it. section 2.7.3
- Calling the delegate with an empty stack materializes the result, allowing Peek, Pop, and enumeration to operate on an ordinary immutable stack. section 2.7.3
- The representation makes Push, Append, Concatenate, and IsEmpty O(1), but materialization can consume O(n) call-stack space and overflow for sufficiently large lists. section 2.7.6
A delegate as deferred storage
Func<int, int, int> adder = (x, y) => x + y; Func<int, Func<int, int>> curried = x => y => adder(x, y); Func<int, int> storage = curried(123); storage(0) produces 123. The delegate stores the bound computation until invocation. section 2.7.3
Listing 2.14 The Hughes list
struct HList<T> : IEnumerable<T>
{
delegate IImStack<T> Concat(IImStack<T> stack);
private readonly Concat c;
private HList(Concat c) => this.c = c;
private static HList<T> Make(Concat c) => new HList<T>(c);
public static HList<T> Empty { get; } = Make(stack => stack);
public bool IsEmpty => ReferenceEquals(c, Empty.c);
public static HList<T> FromStack(IImStack<T> fromStack) =>
fromStack.IsEmpty ?
Empty :
Make(stack => fromStack.Concatenate(stack));
public IImStack<T> ToStack() => c(ImStack<T>.Empty);
public T Peek() => ToStack().Peek();
public HList<T> Pop() => FromStack(ToStack().Pop());
private static HList<T> Concatenate(HList<T> hl1, HList<T> hl2) =>
hl1.IsEmpty ? hl2 : Make(stack => hl1.c(hl2.c(stack)));
public static HList<T> Single(T item) =>
Make(stack => stack.Push(item));
public HList<T> Push(T item) => Concatenate(Single(item), this);
public HList<T> Append(T item) => Concatenate(this, Single(item));
public HList<T> Concatenate(HList<T> hl) => Concatenate(this, hl);
public IEnumerator<T> GetEnumerator() => ToStack().GetEnumerator();
IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}
Inspect the complete Hughes-list implementation, including the delegate type, deferred concatenation, materialization, and enumeration. section 2.7.3
