alice
library
manual.

Alice Project

The MAP signature


________ Synopsis ____________________________________________________

    signature MAP
    functor MkRedBlackMap (Key : ORDERED) :> MAP where type key = Key.t
  

The MAP signature provides a functional interface to finite maps. The MkRedBlackMap functor provides an implementation of this interface based on red-black trees.

See also: IMP_MAP, SET, ORDERED


________ Import ______________________________________________________

    import signature MAP from "x-alice:/lib/data/MAP-sig"
    import functor MkRedBlackMap from "x-alice:/lib/data/MkRedBlackMap"

________ Interface ___________________________________________________

    signature MAP =
    sig
	type key
	type 'a map
	type 'a t = 'a map

	exception Unknown of key
	exception Collision of key

	val empty :          'a map
	val singleton :      key * 'a -> 'a map
	val fromList :       (key * 'a) list -> 'a map
	val fromVector :     (key * 'a) vector -> 'a map
	val toList :         'a map -> (key * 'a) list
	val toVector :       'a map -> (key * 'a) vector

	val insert :         'a map * key * 'a -> 'a map
	val insertDisjoint : 'a map * key * 'a -> 'a map
	val insertWith :     ('a * 'a -> 'a) -> 'a map * key * 'a -> 'a map
	val insertWithi :    (key * 'a * 'a -> 'a) -> 'a map * key * 'a -> 'a map

	val remove :         'a map * key -> 'a map
	val removeExistent : 'a map * key -> 'a map
	val removeWith :     (key -> unit) -> 'a map * key -> 'a map

	val union :          'a map * 'a map -> 'a map
	val unionDisjoint :  'a map * 'a map -> 'a map
	val unionWith :      ('a * 'a -> 'a) -> 'a map * 'a map -> 'a map
	val unionWithi :     (key * 'a * 'a -> 'a) -> 'a map * 'a map -> 'a map

	val intersect :      'a map * 'a map -> 'a map
	val intersectWith :  ('a * 'a -> 'a) -> 'a map * 'a map -> 'a map
	val intersectWithi : (key * 'a * 'a -> 'a) -> 'a map * 'a map -> 'a map

	val difference :     'a map * 'a map -> 'a map

	val size :           'a map -> int
	val isEmpty :        'a map -> bool

	val member :         'a map * key -> bool
	val lookup :         'a map * key -> 'a option
	val lookupExistent : 'a map * key -> 'a
	val choose :         'a map -> 'a option
	val choosei :        'a map -> (key * 'a) option

	val equal :          ('a * 'a -> bool) -> 'a map * 'a map -> bool
	val submap :         ('a * 'a -> bool) -> 'a map * 'a map -> bool
	val disjoint :       'a map * 'a map -> bool

	val app :            ('a -> unit) -> 'a map -> unit
	val map :            ('a -> 'b) -> 'a map -> 'b map
	val mapPartial :     ('a -> 'b option) -> 'a map -> 'b map
	val fold :           ('a * 'b -> 'b) -> 'b -> 'a map -> 'b
	val all :            ('a -> bool) -> 'a map -> bool
	val exists :         ('a -> bool) -> 'a map -> bool
	val find :           ('a -> bool) -> 'a map -> 'a option
	val filter :         ('a -> bool) -> 'a map -> 'a map
	val partition :      ('a -> bool) -> 'a map -> 'a map * 'a map

	val appi :           (key * 'a -> unit) -> 'a map -> unit
	val mapi :           (key * 'a -> 'b) -> 'a map -> 'b map
	val mapPartiali :    (key * 'a -> 'b option) -> 'a map -> 'b map
	val foldi :          (key * 'a * 'b -> 'b) -> 'b -> 'a map -> 'b
	val alli :           (key * 'a -> bool) -> 'a map -> bool
	val existsi :        (key * 'a -> bool) -> 'a map -> bool
	val findi :          (key * 'a -> bool) -> 'a map -> (key * 'a) option
	val filteri :        (key * 'a -> bool) -> 'a map -> 'a map
	val partitioni :     (key * 'a -> bool) -> 'a map -> 'a map * 'a map
    end
  

________ Description _________________________________________________

type key

The type of keys.

type 'a map
type 'a t = 'a map

The type of finite maps from keys of type key to values of type 'a.

exception Unknown of key

Indicates that a key could not be found in the map.

exception Collision of key

Indicates an attempt to add a key that already is in the map when using functions that disallow replacement.

empty

The empty map.

singleton (k, x)

The map only containing the single entry k->x.

fromList l

Constructs a map from a list of key/value pairs. Raises Collision k is a key in the list that is followed by at least one other key equal to k.

fromVector v

Constructs a map from a vector of key/value pairs. Raises Collision k if k is a key in the vector that is followed by at least one other entry with a key equal to k. Equivalent to fromList(Vector.toList v).

toList m

Returns the list of key/value pairs from map m. For red-black maps, the pairs are delivered in increasing key order.

toVector m

Returns the vector of key/value pairs from map m. For red-black maps, the pairs are delivered in increasing key order. Equivalent to Vector.fromList(toList m).

insert (m, k, x)
insertDisjoint (m, k, x)
insertWith f (m, k, x)
insertWithi f (m, k, x)

Returns the map m extended with the entry k->x. In the first form, if m already contains a key k' equal to k, then the corresponding entry gets replaced by k->x. In the second form, Collision k' will be raised. In the third form, the entry is replaced by k->f(x', x), where x' is the value k' maps to. In the forth form, k' is additionally passed to f. The following equivalences hold:

      insert         = insertWith #2
      insertDisjoint = insertWithi (fn (k,_,_) => raise Collision k)
      insertWith f   = insertWithi (fn (_,x,y) => f(x, y))
remove (m, k)
removeExistent (m, k)
removeWith f (m, k)

Returns the map m with the entry corresponding to key k removed. In the first form, if no key equal to k is contained in m, then the map is returned unchanged. In the second form, Unknown k will be raised. In the third form, f is applied to k before the map is returned unchanged. The following equivalences hold:

      remove         = removeWith ignore
      removeExistent = removeWith (fn k => raise Unknown k)
union (m1, m2)
unionDisjoint (m1, m2)
unionWith f (m1, m2)
unionWithi f (m1, m2)

Returns the union of maps m1 and m1. In the first form, if m1 and m2 contain entries k1->x1 and k2->x2 with equal keys k1 and k2, respectively, then the resulting map will contain k2->x2. In the second form, Collision k2 will be raised. In the third form, the resulting map will contain k2->f(x1,x2). In the forth form, k2 is additionally passed to f. The following equivalences hold:

      union         = unionWith #2
      unionDisjoint = unionWithi (fn (k,_,_) => raise Collision k)
      unionWith f   = unionWithi (fn (_,x,y) => f(x, y))
intersect (m1, m2)
intersectWith f (m1, m2)
intersectWithi f (m1, m2)

Returns the intersection of maps m1 and m1, i.e. a map whose domain is the intersection of the domains of the two maps. In the first form, if m1 and m2 contain entries k1->x1 and k2->x2 with equal keys k1 and k2, respectively, then the resulting map will contain k2->x2. In the second form, the resulting map will contain k2->f(x1,x2). In the third form, k2 is additionally passed to f. The following equivalences hold:

      intersect         = intersectWith #2
      intersectWith f   = intersectWithi (fn (_,x,y) => f(x, y))
difference (m1, m2)

Returns the difference of maps m1 and m1, i.e. a map that contains only those entries k1->x1 from m1 for which no key k2 equal to k1 is in the domain of m2.

size m

Returns the cardinality of the map m, i.e. the number of entries it contains.

isEmpty m

Returns true if m is the empty map, false otherwise. Equivalent to size m = 0.

member (m, k)

Returns true if the map m contains a key equal to k, false otherwise.

lookup (m, k)
lookupExistent (m, k)

In the first form, returns SOME x if the map m contains an entry k'->x, where key k' is equal to k, NONE otherwise. In the second form, returns x unwrapped, or raises Unknown k if no such entry exists.

choose m
choosei m

In the first form, returns SOME x, such that k->x is an entry of the map m. In the second form, returns SOME(k,x). Returns NONE if m is the empty map. For red-black maps, k will be the smallest key in the map.

equal f (m1, m2)

Returns true if m1 and m2 are maps with equal entries, false otherwise. Two entries k1->x1 and k2->x2 are considered equal if Key.equal(k1, k2) andalso f(x1, x2) evaluates to true.

submap f (m1, m2)

Returns true if m1 contains an entry k1->x1 for every entry k2->x2 in m2, such that Key.equal(k1, k2) andalso f(x1, x2) evaluates to true.

disjoint (m1, m2)

Returns true if m1 and m2 are maps with disjoint domains, false otherwise.

app f m
appi f m

In the second form, applies f to each entry in the map m. In the first form, applies f to the value in the entry only. For red-black trees, this happens in increasing order. The following equivalences hold:

      app  f m = appi (f o #2) m
      appi f m = List.app f (toList m)
map f m
mapi f m

In the second form, returns the map which contains the entries resulting from applying f to each entry in map m. In the first form, only x is passed to f. For red-black trees, the mapping is applied in increasing order. The following equivalences hold:

      map  f m = mapi (f o #2) m
      mapi f m = fromList (List.map f (toList m))
mapPartial f m
mapPartiali f m

In the second form, applies f to each entry in map m and returns the map of defined results. In the first form, only x is passed to f. For red-black trees, the function is applied in increasing order. The following equivalences hold:

      mapPartial  f m = mapPartiali (f o #2) m
      mapPartiali f m = fromList (List.mapPartial f (toList m))
fold f a m
foldi f a m

In the second form, sequentially applies f to the triple of each map entry's key and value and the result of the previous application, starting with initial value a. In the first form, only an entry's value and the previous result are passed to f. For red-black trees, folding is performed in increasing order. The following equivalences hold:

      fold  f a m = fold (fn (_,x,y) => f (x,y)) a m
      foldi f a m = List.foldl f a (toList m)
all f m
alli f m

In the second form, applies f to each entry (k, x) of map ms until f(k, x) delivers false. Returns false if such an entry exists, true otherwise. In the first form, only x is passed to f. For red-black trees, f is applied in increasing order. The following equivalences hold:

      all  f m = alli (f o #2) m
      alli f m = List.all f (toList m)
exists f m
existsi f m

In the second form, applies f to each entry (k, x) of map ms until f(k, x) delivers true. Returns true if such an entry exists, false otherwise. In the first form, only x is passed to f. For red-black trees, f is applied in increasing order. The following equivalences hold:

      exists  f m = existsi (f o #2) m
      existsi f m = List.exists f (toList m)
find f m
findi f m

In the second form, applies f to each entry (k, x) of map m until f(k, x) delivers true. Returns SOME(k, x) if such an entry exists, NONE otherwise. In the first form, only x is passed to f, and on success SOME x is returned. For red-black trees, f is applied in increasing order. The following equivalences hold:

      find  f m = Option.map #2 (findi (f o #2) m)
      findi f m = List.find f (toList m)
filter f m
filteri f m

In the second form, applies f to each entry (k, x) of map m and returns the map containing those entries for which f(k, x) delivered true. In the first form, only x is passed to f. For red-black trees, f is applied in increasing order. The following equivalences hold:

      filter  f m = filteri (f o #2) m
      filteri f m = fromList (List.filter f (toList m))
partition f m
partitioni f m

In the second form, applies f to each entry (k, x) of map m and returns the pair (m1, m2) of maps where m1 contains all entries for which f(k, x) delivered true, and m2 all entries for which it delivered false. In the first form, only x is passed to f. For red-black trees, f is applied in increasing order. The following equivalences hold:

      partition  f m = partitioni (f o #2) m
      partitioni f m = Pair.map (fromList, fromList) (List.partition f (toList m))


last modified 2007/Mar/30 17:10