Sorted sets

SortedSet[T] stores unique values ordered by the element’s IOrderedKey capability. Its selected ordering witness is part of the complete static set type, while the set value keeps its ordinary runtime layout. See Witness-indexed types for the language feature behind this guarantee. It is useful when membership and deterministic iteration both matter. MutSortedSet[T] provides mutable updates with immutable snapshot support.

Create and update an immutable set

The empty constructor needs an expected element type:

func main() -> Unit do
  set : SortedSet[Int] = SortedSet.empty();
  set = set.add(3);
  set = set.add(1);
  set = set.add(2);
  set = set.add(2);

  Debug.trace(set.contains(2));
  Debug.trace(set.contains(9));
  Debug.trace(set.length());
end

add and remove return new immutable sets. Adding a value that is already present keeps the set unchanged. Earlier values remain valid and unchanged. contains reports whether a value is present; length returns the element count.

Deterministic iteration

foreach yields values in element order:

func print_values(set : SortedSet[Int]) -> Unit do
  foreach value in set do
    Console.println(value.to_string());
  end;
end

Ordering is supplied by the selected IOrderedKey for T provider. Primitive ordered elements obtain that provider through Prelude associations. Custom element types need an appropriate extension.

Mutable sets and snapshots

func main() -> Unit do
  original : SortedSet[Int] = SortedSet.empty();
  original = original.add(1);

  mutable = original.to_mut();
  mutable.add(2);
  mutable.add(2);

  snapshot = mutable.to_immut();

  mutable.add(3);
  Debug.trace(original);
  Debug.trace(snapshot);
  Debug.trace(mutable.contains(1));
end

Mutable add updates in place and returns whether the value was newly added. Mutable remove returns whether a value was present. to_immut() creates a stable snapshot; later mutable updates cannot change it. to_mut() creates a mutable view that may initially share persistent structure while preserving value semantics.

Capability-rich types

The set type carries the element-ordering extension as part of its complete type. The standard structural providers for immutable sets compare, hash, debug, and iterate elements in ordered-element semantics when the element type supports the required capabilities.

Next: JSON.