Data.Map

Persistent ordered map: an AVL-balanced binary search tree over keys.

The Map(k, v) type and its Tip/Bin constructors are wired in; this module is the operation surface. The prelude opens it.

Reserved (a later release): a map’s identity will carry the content hash of the canonical Ord instance it was built with, so a map that crosses an assembly boundary commits to the ordering it was ordered by. Two programs that canonicalize different Ord(k) cannot then silently exchange a Map(k, v) built under one and walked under the other. The classes whose instance choice affects a container’s representation live in one place on the compiler side (store::coherence::is_representation_affecting, Ord and Hash); this note is the container-side half of that reservation, so the two cannot drift.

Functions and Values

map_empty

map_empty : forall a b c. Map(a, b, c)

The empty map.

map_height

map_height : forall a b c. (Map(a, b, c)) -> Int

Helper: the cached height of the tree (0 for the empty map).

map_node

map_node : forall a b c. (a, b, Map(a, b, c), Map(a, b, c)) -> Map(a, b, c)

Helper: build a Bin node, computing its height from its children.

map_bf

map_bf : forall a b c. (Map(a, b, c)) -> Int

Helper: the balance factor of a node (left height minus right height).

map_rot_right

map_rot_right : forall a b c. (Map(a, b, c)) -> Map(a, b, c)

Helper: a single right AVL rotation.

map_rot_left

map_rot_left : forall a b c. (Map(a, b, c)) -> Map(a, b, c)

Helper: a single left AVL rotation.

map_balance

map_balance : forall a b c. (Map(a, b, c)) -> Map(a, b, c)

Helper: rebalance a node after an insert or delete unbalanced it.

map_insert

map_insert : forall a b c. (b, c, Map(b, c, a)) -> Map(b, c, a)

Insert key with value, overwriting any existing binding, and rebalance.

map_lookup

map_lookup : forall a b c. (b, Map(b, c, a)) -> Option(c)

The value bound to key as Some, or None when absent.

map_member

map_member : forall a b c. (b, Map(b, c, a)) -> Bool

True when key is present in the map.

map_size

map_size : forall a b c. (Map(a, b, c)) -> Int

The number of entries.

map_min

map_min : forall a b c. (Map(a, b, c)) -> Option((a, b))

The smallest key and its value as Some, or None when empty.

map_delete

map_delete : forall a b c. (b, Map(b, c, a)) -> Map(b, c, a)

Remove key (a no-op if absent), rebalancing the tree.

map_to_list

map_to_list : forall a b c. (Map(a, b, c)) -> List((a, b))

The (key, value) pairs in ascending key order.

map_keys

map_keys : forall a b c. (Map(a, b, c)) -> List(a)

The keys in ascending order.

map_values

map_values : forall a b c. (Map(a, b, c)) -> List(b)

The values in ascending key order.

map_from_list

map_from_list : forall a b c. (List((b, c))) -> Map(b, c, a)

Build a map from (key, value) pairs; a later pair overwrites an earlier one with the same key.

map_map_values

map_map_values : forall e0 a b c d e. ((e) -> d ! {e0}, Map(a, e, b)) -> Map(a, d, c) ! {e0}

Apply f to every value, keeping keys and tree structure.