Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

Data.IntMap

Persistent integer-keyed map: a big-endian patricia trie over 64-bit keys.

Keys are I64, the fixed-width signed integer, because a radix trie branches by testing one bit of a machine word. Int is arbitrary-precision and has no highest set bit, so a trie cannot branch on it and no 64-bit branch word can order it; Data.Map serves Int keys through comparison chains. Convert with to_i64 at the boundary, which wraps to the low 64 bits exactly as it does everywhere else.

The branch word of a key is its two’s-complement bit pattern with the sign bit flipped. That transform is a bijection, and it turns signed key order into unsigned branch-word order, so branching is a plain bit test with no sign special case and an in-order walk yields ascending keys, negatives first.

A branch node carries the prefix its keys agree on, the single-bit mask of the position where they split, and the subtrees whose branch bit is zero and one. Every branch keeps two non-empty children, so a node’s mask is exactly the highest bit on which two of its keys differ and a key set determines the tree uniquely. Iteration order therefore depends on the key set alone and never on insertion order, and the stronger statement holds too: maps built from the same bindings in different orders are structurally equal, so intmap_to_list, intmap_fold, and the derived Eq and Show all agree across orders.

Opt-in: not in Base.

Types

IntMap

type IntMap(v)
  = IMEmpty
  | IMLeaf(I64, v)
  | IMBranch(U64, U64, IntMap(v), IntMap(v))
  deriving (Eq, Show)

A map from I64 keys to values of type v.

IMEmpty is the empty map, IMLeaf(key, value) a single binding, and IMBranch(prefix, mask, zeros, ones) a split: every key below it agrees with prefix above the single set bit of mask, zeros holds those whose branch bit is clear and ones those whose branch bit is set. Both subtrees of a branch are non-empty.

Functions and Values

intmap_empty

intmap_empty : forall a. Data.IntMap.IntMap(a)

The empty map.

intmap_is_empty(intmap_empty)

true

intmap_singleton

intmap_singleton : forall a. (I64, a) -> Data.IntMap.IntMap(a)

The map binding key to value and nothing else.

intmap_to_list(intmap_singleton(7i64, "a"))

[(7, a)]

intmap_insert

intmap_insert : forall a. (I64, a, Data.IntMap.IntMap(a)) -> Data.IntMap.IntMap(a)

Insert key with value, overwriting any existing binding.

intmap_lookup(1i64, intmap_insert(1i64, "a", intmap_empty))

Some(a)

intmap_insert_with

intmap_insert_with : forall e0 a. ((a, a) -> a ! {e0}, I64, a, Data.IntMap.IntMap(a)) -> Data.IntMap.IntMap(a) ! {e0}

Insert key with value, combining a clash as f(new, old).

intmap_to_list(
  intmap_insert_with(\(a, b) -> a + b, 1i64, 10, intmap_singleton(1i64, 5)),
)

[(1, 15)]

intmap_lookup

intmap_lookup : forall a. (I64, Data.IntMap.IntMap(a)) -> Option(a)

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

intmap_lookup(2i64, intmap_from_list([(1i64, "a"), (2i64, "b")]))

Some(b)

intmap_member

intmap_member : forall a. (I64, Data.IntMap.IntMap(a)) -> Bool

True when key is bound.

intmap_member(2i64, intmap_from_list([(1i64, "a"), (2i64, "b")]))

true

intmap_delete

intmap_delete : forall a. (I64, Data.IntMap.IntMap(a)) -> Data.IntMap.IntMap(a)

Remove key (a no-op when absent).

intmap_to_list(intmap_delete(1i64, intmap_from_list([(1i64, "a"), (2i64, "b")])))

[(2, b)]

intmap_size

intmap_size : forall a. (Data.IntMap.IntMap(a)) -> Int

The number of bindings.

intmap_size(intmap_from_list([(1i64, "a"), (2i64, "b")]))

2

intmap_is_empty

intmap_is_empty : forall a. (Data.IntMap.IntMap(a)) -> Bool

True when the map has no bindings.

intmap_is_empty(intmap_empty)

true

intmap_union

intmap_union : forall a. (Data.IntMap.IntMap(a), Data.IntMap.IntMap(a)) -> Data.IntMap.IntMap(a)

The union of two maps, keeping the left value where a key is in both.

intmap_to_list(
  intmap_union(
    intmap_from_list([(1i64, "a"), (2i64, "b")]),
    intmap_from_list([(2i64, "z"), (3i64, "c")]),
  ),
)

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

intmap_union_with

intmap_union_with : forall e0 a. ((a, a) -> a ! {e0}, Data.IntMap.IntMap(a), Data.IntMap.IntMap(a)) -> Data.IntMap.IntMap(a) ! {e0}

The union of two maps, combining a key present in both as f(left, right).

The two branch nodes are walked together: the shallower one is descended into until the masks meet, so the merge costs the shape of the two tries rather than a re-insertion of every binding.

intmap_to_list(
  intmap_union_with(
    \(a, b) -> a + b,
    intmap_from_list([(1i64, 10), (2i64, 20)]),
    intmap_from_list([(2i64, 2), (3i64, 3)]),
  ),
)

[(1, 10), (2, 22), (3, 3)]

intmap_intersection

intmap_intersection : forall a b. (Data.IntMap.IntMap(a), Data.IntMap.IntMap(b)) -> Data.IntMap.IntMap(a)

The bindings of t1 whose key is also in t2, with t1’s values.

intmap_to_list(
  intmap_intersection(
    intmap_from_list([(1i64, "a"), (2i64, "b"), (3i64, "c")]),
    intmap_from_list([(2i64, "z"), (3i64, "y"), (4i64, "x")]),
  ),
)

[(2, b), (3, c)]

intmap_difference

intmap_difference : forall a b. (Data.IntMap.IntMap(a), Data.IntMap.IntMap(b)) -> Data.IntMap.IntMap(a)

The bindings of t1 whose key is not in t2.

intmap_to_list(
  intmap_difference(
    intmap_from_list([(1i64, "a"), (2i64, "b"), (3i64, "c")]),
    intmap_from_list([(2i64, "z"), (3i64, "y")]),
  ),
)

[(1, a)]

intmap_filter

intmap_filter : forall e0 a. ((I64, a) -> Bool ! {e0}, Data.IntMap.IntMap(a)) -> Data.IntMap.IntMap(a) ! {e0}

The bindings satisfying keep(key, value).

A surviving branch still splits on the highest bit two of its remaining keys differ on, because a branch whose child empties collapses, so filtering lands on the same tree the survivors would have built from scratch.

intmap_to_list(
  intmap_filter(
    \(_k, v) -> v > 1,
    intmap_from_list([(1i64, 1), (2i64, 2), (3i64, 3)]),
  ),
)

[(2, 2), (3, 3)]

intmap_map_values

intmap_map_values : forall e0 a b. ((a) -> b ! {e0}, Data.IntMap.IntMap(a)) -> Data.IntMap.IntMap(b) ! {e0}

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

intmap_values(
  intmap_map_values(\(v) -> v + 1, intmap_from_list([(1i64, 10), (2i64, 20)])),
)

[11, 21]

intmap_fold

intmap_fold : forall e0 a b. ((a, I64, b) -> a ! {e0}, a, Data.IntMap.IntMap(b)) -> a ! {e0}

Fold f(acc, key, value) over the bindings in ascending key order.

The zero subtree of a branch holds the smaller branch words and branch-word order is key order, so a left-to-right walk is ascending with no sign case.

intmap_fold(\(acc, k, _v) -> acc + k, 0i64, intmap_from_list([(1i64, "a"), (2i64, "b")]))

3

intmap_to_list

intmap_to_list : forall a. (Data.IntMap.IntMap(a)) -> List((I64, a))

The (key, value) pairs in ascending key order, negative keys first.

intmap_to_list(intmap_from_list([(2i64, "b"), (0i64, "z"), (1i64, "a")]))

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

intmap_keys

intmap_keys : forall a. (Data.IntMap.IntMap(a)) -> List(I64)

The keys in ascending order.

intmap_keys(intmap_from_list([(2i64, "b"), (1i64, "a")]))

[1, 2]

intmap_values

intmap_values : forall a. (Data.IntMap.IntMap(a)) -> List(a)

The values in ascending key order.

intmap_values(intmap_from_list([(1i64, "a"), (2i64, "b")]))

[a, b]

intmap_from_list

intmap_from_list : forall a. (List((I64, a))) -> Data.IntMap.IntMap(a)

Build a map from (key, value) pairs; a later pair overwrites an earlier one with the same key. The result depends only on the surviving bindings, so any ordering of the same list of distinct keys builds the identical tree.

intmap_to_list(intmap_from_list([(2i64, "b"), (1i64, "a")]))

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