Sorted maps

SortedMap[K, V] stores entries ordered by the key’s IOrderedKey capability. Its selected ordering witness is part of the complete static map type, while the map value keeps its ordinary runtime layout. See Witness-indexed types for the language feature behind this guarantee. It is useful when lookup and deterministic iteration both matter. MutSortedMap[K, V] provides mutable updates with immutable snapshot support.

Create and update an immutable map

The empty constructor needs an expected key and value type:

func main() -> Unit do
  map : SortedMap[Int, String] = SortedMap.empty();
  map = map.set(3, "three");
  map = map.set(1, "one");
  map = map.set(2, "two");

  Debug.trace(map.get(2));
  Debug.trace(map.has(9));
end

set and remove return new immutable maps. Earlier values remain valid and unchanged. get returns Option[V]; has reports whether a key is present; length returns the entry count.

Deterministic iteration

foreach yields (key, value) tuples in key order:

func print_entries(map : SortedMap[Int, String]) -> Unit do
  foreach (key, value) in map do
    Console.println(key.to_string() ++ ": " ++ value);
  end;
end

Ordering is supplied by the selected IOrderedKey for K provider. Primitive ordered keys obtain that provider through Prelude associations. Custom key types need an appropriate extension.

Mutable maps and snapshots

func main() -> Unit do
  original : SortedMap[Int, String] = SortedMap.empty();
  original = original.set(1, "one");

  mutable = original.to_mut();
  mutable.set(2, "two");
  snapshot = mutable.to_immut();

  mutable.set(1, "ONE");
  Debug.trace(original);
  Debug.trace(snapshot);
  Debug.trace(mutable.get(1));
end

Mutable set updates in place and returns Unit. Mutable remove returns whether a key 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 map type carries the key-ordering extension as part of its complete type. The standard structural providers for immutable maps compare, hash, debug, and iterate entries in ordered-entry semantics when their key and value types support the required capabilities.

Next: Sorted sets.