Concatenation joins two sequences end to end, preserving their order. The operation is easy to specify but not always cheap to perform. For immutable sequences, the central question is whether joining must copy items now, can defer that work, or can reuse a structure that supports a faster join. section 3.7 section 2.7.3
An immutable stack provides a straightforward baseline: reverse the left stack, then push its items onto the right stack in their original order. The result takes O(n) time and extra memory in the size of the left stack. An empty right stack is a useful special case: return the left stack without copying it. section 2.7.1
Listing 2.13 ReverseOnto and friends
static class Extensions
{
public static IImStack<T> ReverseOnto<T>(
this IImStack<T> stack, IImStack<T> tail)
{
var result = tail;
for (; !stack.IsEmpty; stack = stack.Pop())
result = result.Push(stack.Peek());
return result;
}
public static IImStack<T> Reverse<T>(
this IImStack<T> stack) =>
stack.ReverseOnto(ImStack<T>.Empty);
public static IImStack<T> Concatenate<T>(
this IImStack<T> xs, IImStack<T> ys) =>
ys.IsEmpty ? xs : xs.Reverse().ReverseOnto(ys);
public static IImStack<T> Append<T>(
this IImStack<T> stack, T item) =>
stack.Concatenate(ImStack<T>.Empty.Push(item));
}
The C# implementation makes the two reversals—and the empty-right shortcut—visible in one small method. section 2.7.1
A Hughes list changes *when* concatenation happens. It stores a delegate that accepts a tail stack; joining two Hughes lists constructs a new delegate that applies the right list’s function before the left list’s. Thus building a concatenation costs O(1), regardless of list size. Reading the contents calls the delegates and pays the O(n) construction cost then. The captured references form a binary graph: cheap concatenation here is deferred work, not work eliminated. section 2.7.4 section 2.7.5
private static HList<T> Concatenate(HList<T> hl1, HList<T> hl2) =>
hl1.IsEmpty ? hl2 : Make(stack => hl1.c(hl2.c(stack)));
The expression `hl1.c(hl2.c(stack))` shows how function composition preserves left-to-right item order while postponing stack construction. section 2.7.3
A finger-tree deque takes a different route to cheap concatenation. A simple loop could push every item of the right deque onto the left, taking linear time. Instead, the deque retains its outer buffers and joins its smaller middle deques recursively. To make the join possible, the middle accepts mini-deques of either two or three items rather than only three. A helper repacks the boundary items into those permitted sizes before the recursive join. section 3.7
Listing 3.7 Implementing concatenation of multiple-item deques
public sealed class Deque<T> : IDeque<T>
{
[…]
public IDeque<T> Concatenate(IDeque<T> items) =>
right is Deque<T> r ?
new Deque<T>(
left,
middle.PushRightMany(right.TwosAndThrees(r.left))
.Concatenate(r.middle),
r.right) :
this.PushRightMany(items);
}
static class Extensions
{
public static IDeque<T> PushRightMany<T>(
this IDeque<T> deque, IEnumerable<T> items) =>
items.Aggregate(deque, (d, item) => d.PushRight(item));
}
The multiple-item case repacks the touching boundaries, pushes the resulting minis into the left middle, and concatenates that middle with the right middle. section 3.7
Empty deques remain an identity: concatenating one returns the other. A single-item case becomes a push. For two multiple-item deques, recursion descends through at most O(log n) levels, giving concatenation O(log n) worst-case time and extra space. Allowing two-item minis keeps tree depth logarithmic; pushes and pops remain O(1) amortized, with O(log n) worst cases. section 3.7 section 3.8
The same operation appears outside list implementations. `SelectMany` obtains a sequence for each input item and concatenates the results into one sequence. String concatenation has a separate trap: repeatedly appending to an immutable string copies earlier content and can make a build O(n²); `StringBuilder` avoids that repeated copying in the string-building examples. section 11.4 section 1.2.1 section 9.3.4
