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. Base includes it.

A map’s representation depends on the canonical Ord instance used to build it. The compiler therefore classifies Ord (and Hash) as representation-affecting in store::coherence::is_representation_affecting. Map identity does not currently encode that instance, so programs exchanging a map across an assembly boundary must agree on its canonical ordering.

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(1, map_insert(1, "a", map_empty))

Some(a)

`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_lookup(2, map_from_list([(1, "a"), (2, "b")]))

Some(b)

`map_member`

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

True when key is present in the map.

map_member(2, map_from_list([(1, "a"), (2, "b")]))

true

`map_size`

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

The number of entries.

map_size(map_from_list([(1, "a"), (2, "b")]))

`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_min(map_from_list([(2, "b"), (1, "a")]))

Some((1, a))

`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_delete(1, map_from_list([(1, "a"), (2, "b")])))

[(2, b)]

`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_to_list(map_from_list([(2, "b"), (1, "a")]))

[(1, a), (2, b)]

`map_keys`

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

The keys in ascending order.

map_keys(map_from_list([(2, "b"), (1, "a")]))

[1, 2]

`map_values`

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

The values in ascending key order.

map_values(map_from_list([(1, "a"), (2, "b")]))

[a, b]

`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_to_list(map_from_list([(2, "b"), (1, "a")]))

[(1, a), (2, b)]

`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.

map_values(map_map_values(\(v) -> v + 1, map_from_list([(1, 10), (2, 20)])))

[11, 21]

Keyboard shortcuts

Prism