Sorted maps

SortedMap[K, V] stores entries ordered by the key’s IOrderedKey capability. 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: JSON.