Immutable collections

Links

• Immutable Collections
• F# Collections
• Record Nondestructive Mutation

Definition

An immutable collection is a collection of instances that

• preserves its structure all the time: no addition or removal of elements, no change of order
• disallows element-level assignments

While still offering APIs to perform mutations: Add, Remove, ...

The immutable collections are designed with two goals in mind:

• reuse as much memory as possible, to avoid copying, and to reduce pressure on the garbage collector
• support the same operations offered by mutable collections with competitive time complexities

Immutable Stacks

var s1 = ImmutableStack<int>.Empty; // call push, s1 remains unchanged, and it returns a reference to the resulting immutable stack which contains the element 1. var s2 = s1.Push(1); // call push, s2 remains unchanged, and it returns a reference to the resulting immutable stack which contains no element. var s3 = s2.Pop();