The `ORD_MAP` signature

The `ORD_MAP` signature defines an interface to finite maps over ordered keys. The SML/NJ Library provides a number of different implementations of this interface. Functors are provided for constructing maps for user-defined key types; in addition, a number of instances for specific types are also provided.

## Synopsis

``````signature ORD_MAP

structure AtomMap : ORD_MAP where type Key.ord_key = Atom.atom
structure AtomBinaryMap : ORD_MAP where type Key.ord_key = Atom.atom
structure AtomRedBlackMap : ORD_MAP where type Key.ord_key = Atom.atom
structure IntBinaryMap : ORD_MAP where type Key.ord_key = int
structure IntListMap : ORD_MAP where type Key.ord_key = int
structure IntRedBlackMap : ORD_MAP where type Key.ord_key = int
structure WordRedBlackMap : ORD_MAP where type Key.ord_key = word``````

## Interface

``````structure Key : ORD_KEY

type 'a map

val empty : 'a map

val isEmpty : 'a map -> bool

val singleton : (Key.ord_key * 'a) -> 'a map

val insert  : 'a map * Key.ord_key * 'a -> 'a map
val insert' : ((Key.ord_key * 'a) * 'a map) -> 'a map

val insertWith  : ('a * 'a -> 'a) -> 'a map * Key.ord_key * 'a -> 'a map
val insertWithi : (Key.ord_key * 'a * 'a -> 'a) -> 'a map * Key.ord_key * 'a -> 'a map

val find : 'a map * Key.ord_key -> 'a option

val lookup : 'a map * Key.ord_key -> 'a

val inDomain : ('a map * Key.ord_key) -> bool

val remove : 'a map * Key.ord_key -> 'a map * 'a

val first : 'a map -> 'a option
val firsti : 'a map -> (Key.ord_key * 'a) option

val numItems : 'a map ->  int

val listItems  : 'a map -> 'a list
val listItemsi : 'a map -> (Key.ord_key * 'a) list

val listKeys : 'a map -> Key.ord_key list

val collate : ('a * 'a -> order) -> ('a map * 'a map) -> order

val unionWith  : ('a * 'a -> 'a) -> ('a map * 'a map) -> 'a map
val unionWithi : (Key.ord_key * 'a * 'a -> 'a) -> ('a map * 'a map) -> 'a map

val intersectWith  : ('a * 'b -> 'c) -> ('a map * 'b map) -> 'c map
val intersectWithi : (Key.ord_key * 'a * 'b -> 'c) -> ('a map * 'b map) -> 'c map

val mergeWith : ('a option * 'b option -> 'c option)
-> ('a map * 'b map) -> 'c map
val mergeWithi : (Key.ord_key * 'a option * 'b option -> 'c option)
-> ('a map * 'b map) -> 'c map

val app  : ('a -> unit) -> 'a map -> unit
val appi : ((Key.ord_key * 'a) -> unit) -> 'a map -> unit

val map  : ('a -> 'b) -> 'a map -> 'b map
val mapi : (Key.ord_key * 'a -> 'b) -> 'a map -> 'b map

val foldl  : ('a * 'b -> 'b) -> 'b -> 'a map -> 'b
val foldli : (Key.ord_key * 'a * 'b -> 'b) -> 'b -> 'a map -> 'b
val foldr  : ('a * 'b -> 'b) -> 'b -> 'a map -> 'b
val foldri : (Key.ord_key * 'a * 'b -> 'b) -> 'b -> 'a map -> 'b

val filter  : ('a -> bool) -> 'a map -> 'a map
val filteri : (Key.ord_key * 'a -> bool) -> 'a map -> 'a map

val mapPartial  : ('a -> 'b option) -> 'a map -> 'b map
val mapPartiali : (Key.ord_key * 'a -> 'b option) -> 'a map -> 'b map

val exists : ('a -> bool) -> 'a map -> bool
val existsi : (Key.ord_key * 'a -> bool) -> 'a map -> bool
val all : ('a -> bool) -> 'a map -> bool
val alli : (Key.ord_key * 'a -> bool) -> 'a map -> bool``````

## Description

`structure Key : ORD_KEY`

This substructure defines the type of keys used to index the maps and the comparison function used to order them.

`type 'a map`

A finite map from `Key.ord_key` values to `'b` values.

`val empty : 'a map`

The empty map.

`val isEmpty : 'a map -> bool`

`isEmpty m` returns true if, and only if, `m` is empty.

`val singleton : (Key.ord_key * 'a) -> 'a map`

`singleton (key, v)` creates the singleton map that maps `key` to `v`.

`val insert : 'a map * Key.ord_key * 'a -> 'a map`

`insert (m, key, v)` adds the mapping from `key` to `v` to `m`. This mapping overrides any previous mapping from `key`.

`val insert' : ((Key.ord_key * 'a) * 'a map) -> 'a map`

`insert' ((key, v), map)` adds the mapping from `key` to `v` to `m`. This mapping overrides any previous mapping from `key`.

`val insertWith : ('a * 'a -> 'a) -> 'a map * Key.ord_key * 'a -> 'a map`

`insertWith comb (m, key, v)` adds the mapping from `key` to `value` to `m`, where `value = comb(v', v)`, if `m` already contained a mapping from `key` to `v'`; otherwise, `value = v`.

`val insertWithi : (Key.ord_key * 'a * 'a -> 'a) -> 'a map * Key.ord_key * 'a -> 'a map`

`insertWithi comb (m, key, v)` adds the mapping from `key` to `value` to `m`, where `value = comb(key, v', v)`, if `m` already contained a mapping from `key` to `v'`; otherwise, `value = v`.

`val find : 'a map * Key.ord_key -> 'a option`

`find (m, key)` returns `SOME v`, if `m` maps `key` to `v` and `NONE` otherwise.

`val lookup : 'a map * Key.ord_key -> 'a`

`lookup (m, key)` returns `v`, if `m` maps `key` to `v`; otherwise it raises the exception `NotFound`.

`val inDomain : ('a map * Key.ord_key) -> bool`

`inDomain (m, key)` returns `true` if `key` is in the domain of `m`.

`val remove : 'a map * Key.ord_key -> 'a map * 'a`

`remove (m, key)` returns the pair `(m', v)`, if `m` maps `key` to `v` and where `m'` is `m` with `key` removed from its domain. If `key` is not in the domain of `m`, then it raises the exception `NotFound`.

`val first : 'a map -> 'a option`

`first m` returns `SOME item` when `item` is the value associated with the first (or smallest) key in the domain of the map `m`. It returns `NONE` when the map is empty.

`val firsti : 'a map -> (Key.ord_key * 'a) option`

`first m` returns `SOME(key, item)` when `key` is the first (or smallest) key in the domain of the map `m` and `key` maps to `item`. It returns `NONE` when the map is empty.

`val numItems : 'a map -> int`

`numItems m` returns the size of `m`'s domain.

`val listItems : 'a map -> 'a list`

`listItems m` returns a list of the values in the range of `m`. Note that this list will contain duplicates when multiple keys in `m`'s domain map to the same value.

`val listItemsi : 'a map -> (Key.ord_key * 'a) list`

`listItemsi m` returns a list of the key-value pairs in `m`.

`val listKeys : 'a map -> Key.ord_key list`

`listKeys m` returns a list of the keys in the domain of `m`.

`val collate : ('a * 'a -> order) -> ('a map * 'a map) -> order`

`collate cmpV (m1, m2)` returns the order of the two maps, where `cmpV` is used to compare the values in the domain.

`val unionWith : ('a * 'a -> 'a) -> ('a map * 'a map) -> 'a map`

`unionWith comb (m1, m2)` returns the union of the two maps, using the function `comb` to combine values when there is a collision of keys. More formally, this expression returns the map

$\begin{array}{l} \{ (k, \mathtt{m1}(k)) \;|\;k \in \mathbf{dom}(\mathtt{m1}) \setminus \mathbf{dom}(\mathtt{m2}) \} \cup \\ \{ (k, \mathtt{m2}(k)) \;|\;k \in \mathbf{dom}(\mathtt{m2}) \setminus \mathbf{dom}(\mathtt{m1}) \} \cup \\ \{ (k, \mathtt{comb}(\mathtt{m1}(k), \mathtt{m2}(k)) \;|\;k \in \mathbf{dom}(\mathtt{m1}) \cap \mathbf{dom}(\mathtt{m2}) \} \end{array}$

For example, we could implement a multiset of keys by mapping keys to their multiplicity. Then, the union of two multisets could be defined by

``fun union (ms1, ms2) = unionWith Int.+ (ms1, ms2)``
`val unionWithi : (Key.ord_key * 'a * 'a -> 'a) -> ('a map * 'a map) -> 'a map`

`unionWithi comb (m1, m2)` returns the union of the two maps, using the function `comb` to combine values when there is a collision of keys. More formally, this expression returns the map

$\begin{array}{l} \{ (k, \mathtt{m1}(k)) \;|\;k \in \mathbf{dom}(\mathtt{m1}) \setminus \mathbf{dom}(\mathtt{m2}) \} \cup \\ \{ (k, \mathtt{m2}(k)) \;|\;k \in \mathbf{dom}(\mathtt{m2}) \setminus \mathbf{dom}(\mathtt{m1}) \} \cup \\ \{ (k, \mathtt{comb}(k, \mathtt{m1}(k), \mathtt{m2}(k)) \;|\;k \in \mathbf{dom}(\mathtt{m1}) \cap \mathbf{dom}(\mathtt{m2}) \} \end{array}$
`val intersectWith : ('a * 'b -> 'c) -> ('a map * 'b map) -> 'c map`

`intersectWith comb (m1, m2)` returns the intersection of the two maps, where the values in the range are a computed by applying the function `comb` to the values from the two maps. More formally, this expression returns the map

$\{ (k, \mathtt{comb}(\mathtt{m1}(k), \mathtt{m2}(k)) \;|\;k \in \mathbf{dom}(\mathtt{m1}) \cap \mathbf{dom}(\mathtt{m2}) \}$
`val intersectWithi : (Key.ord_key * 'a * 'b -> 'c) -> ('a map * 'b map) -> 'c map`

`intersectWithi comb (m1, m2)` returns the intersection of the two maps, where the values in the range are a computed by applying the function `comb` to the kay and the values from the two maps. More formally, this expression returns the map

$\{ (k, \mathtt{comb}(k, \mathtt{m1}(k), \mathtt{m2}(k)) \;|\;k \in \mathbf{dom}(\mathtt{m1}) \cap \mathbf{dom}(\mathtt{m2}) \}$
`val mergeWith : ('a option * 'b option -> 'c option) -> ('a map * 'b map) -> 'c map`

`mergeWith comb (m1, m2)` merges the two maps using the function `comb` as a decision procedure for adding elements to the new map. For each key $\mathtt{key} \in \mathbf{dom}(\mathtt{m1}) \cup \mathbf{dom}(\mathtt{m2})$, we evaluate `comb(optV1, optV2)`, where `optV1` is `SOME v` if $(\mathtt{key}, \mathtt{v}) \in \mathtt{m1}$ and is `NONE` if latexmath:[\mathtt{key} \not\in \mathbf{dom}(\mathtt{m1}); likewise for `optV2`. If `comb(optV1, optV2)` returns `SOME v'`, then we add `(key, v')` to the result.

The `mergeWith` function is a generalization of the `unionWith` and `intersectionWith` functions.

`val mergeWithi : (Key.ord_key * 'a option * 'b option -> 'c option) -> ('a map * 'b map) -> 'c map`

`mergeWithi comb (m1, m2)` merges the two maps using the function `comb` as a decision procedure for adding elements to the new map. The difference between this function and `mergeWith` is that the `comb` function takes the `key` value in addition to the optional values from the range.

`val app : ('a -> unit) -> 'a map -> unit`

`app f m` applies the function `f` to the values in the range of `m`.

`val appi : ((Key.ord_key * 'a) -> unit) -> 'a map -> unit`

`appi f map` applies the function `f` to the key-value pairs that define `m`.

`val map : ('a -> 'b) -> 'a map -> 'b map`

`map f m` creates a new finite map `m'` by applying the function `f` to the values in the range of `m`. Thus, if $(\mathtt{key}, \mathtt{v}) \in \mathtt{m}$, then `(key, f v)` will be in `m'`.

`val mapi : (Key.ord_key * 'a -> 'b) -> 'a map -> 'b map`

`mapi f m` creates a new finite map `m'` by applying the function `f` to the key-value pairs of `m`. Thus, if $(\mathtt{key}, \mathtt{v}) \in \mathtt{m}$, then `(key, f(key, v))` will be in `m'`.

`val foldl : ('a * 'b -> 'b) -> 'b -> 'a map -> 'b`

`foldl fl init m` folds the function `f` over the range of `m` using `init` as the initial value. Items are processed in increasing order of their key values.

`val foldli : (Key.ord_key * 'a * 'b -> 'b) -> 'b -> 'a map -> 'b`

`foldli f init m` folds the function `f` over the key-value pairs in `m` using `init` as the initial value. Items are processed in increasing order of their key values.

`val foldr : ('a * 'b -> 'b) -> 'b -> 'a map -> 'b`

`foldr fl init m` folds the function `f` over the range of `m` using `init` as the initial value. Items are processed in decreasing order of their key values.

`val foldri : (Key.ord_key * 'a * 'b -> 'b) -> 'b -> 'a map -> 'b`

`foldri f init m` folds the function `f` over the key-value pairs in `m` using `init` as the initial value. Items are processed in decreasing order of their key values.

`val filter : ('a -> bool) -> 'a map -> 'a map`

`filter pred m` filters out those items `(key, v)` from `m`, such that `pred v` returns `false`. More formally, this expression returns the map $\{ (\mathtt{key}, \mathtt{v})\;|\;\mathtt{key} \in \mathbf{dom}(\mathtt{m}) \wedge \mathtt{pred}(\mathtt{v}) \}$.

`val filteri : (Key.ord_key * 'a -> bool) -> 'a map -> 'a map`

`filteri pred m` filters out those items `(key, v)` from `m`, such that `pred(key, v)` returns `false`. More formally, this expression returns the map $\{ (\mathtt{key}, \mathtt{v})\;|\;\mathtt{key} \in \mathbf{dom}(\mathtt{m}) \wedge \mathtt{pred}(\mathtt{key}, \mathtt{v}) \}$.

`val mapPartial : ('a -> 'b option) -> 'a map -> 'b map`

`mapPartial f m` maps the partial function `f` over the items of `m`. More formally, this expression returns the map

$\{ (k, v') \;|\; (k, v) \in \mathtt{m} \wedge \mathtt{f}(v) = \mathtt{SOME}(v') \}$
`val mapPartiali : (Key.ord_key * 'a -> 'b option) -> 'a map -> 'b map`

`mapPartiali f m` maps the partial function `f` over the items of `m`. More formally, this expression returns the map

$\{ (k, v') \;|\; (k, v) \in \mathtt{m} \wedge \mathtt{f}(k, v) = \mathtt{SOME}(v') \}$
`val exists : ('a -> bool) -> 'a map -> bool`

`exists pred m` returns `true` if, and only if, there exists an item $(\mathtt{key}, \mathtt{v}) \in \mathtt{m}$, such that `pred v` returns `true`.

`val existsi : (Key.ord_key * 'a -> bool) -> 'a map -> bool`

`exists pred m` returns `true` if, and only if, there exists an item $(\mathtt{key}, \mathtt{v}) \in \mathtt{m}$, such that `pred(key, v)` returns `true`.

`val all : ('a -> bool) -> 'a map -> bool`

`all pred m` returns `true` if, and only if, `pred v` returns `true` for all items $(\mathtt{key}, \mathtt{v}) \in \mathtt{m}$.

`val alli : (Key.ord_key * 'a -> bool) -> 'a map -> bool`

`all pred m` returns `true` if, and only if, `pred(key, v)` returns `true` for all items $(\mathtt{key}, \mathtt{v}) \in \mathtt{m}$.

## Instances

`structure AtomMap`

This structure is an alias for `AtomRedBlackMap`.

`structure AtomBinaryMap`

Maps over atoms implemented using balanced binary trees. Note that it is recommended that one use the `AtomMap` structure as it provides better performance.

`structure AtomRedBlackMap`

Maps over atoms implemented using red-black trees.

`structure IntBinaryMap`

Maps over ints implemented using balanced binary trees. Note that it is recommended that one use the `IntRedBlackMap` structure as it provides better performance.

`structure IntListMap`

Maps over words implemented using sorted lists. This implementation is fast for small sets, but does not scale well to large sizes.

`structure IntRedBlackMap`

Maps over ints implemented using red-black binary trees.

`structure WordRedBlackMap`

Maps over words implemented using red-black binary trees.