alice
library
manual.

Alice Project

The RefMap structure


________ Synopsis ____________________________________________________

    signature REF_MAP
    structure RefMap : REF_MAP
  

The RefMap structure provides polymorphic hash tables using references as keys. The content of a reference is not relevant, only the identity of the reference is taken into account. References hence can safely be updated without rendering the table inconsistent.

Note that imperative maps are not thread-safe. Explicit locking has to be used if they need to be accessed concurrently. Also note that the behaviour of iterator functionals is unspecified if the passed argument function tries to modify the map.

See also: IMP_MAP, IMP_SET, HASHABLE, ORDERED


________ Import ______________________________________________________

    import signature REF_MAP from "x-alice:/lib/data/REF_MAP-sig"
    import structure RefMap from "x-alice:/lib/data/RefMap"

________ Interface ___________________________________________________

    signature REF_MAP =
    sig
	eqtype ('a,'b) map
	type ('a,'b) t = ('a,'b) map

	exception Unknown
	exception Collision

	val map :            unit -> ('a,'b) map
	val clone :          ('a,'b) map -> ('a,'b) map
	val fromList :       ('a ref * 'b) list -> ('a,'b) map
	val fromVector :     ('a ref * 'b) vector -> ('a,'b) map
	val toList :         ('a,'b) map -> ('a ref * 'b) list
	val toVector :       ('a,'b) map -> ('a ref * 'b) vector

	val insert :         ('a,'b) map * 'a ref * 'b -> unit
	val insertDisjoint : ('a,'b) map * 'a ref * 'b -> unit
	val insertWith :     ('b * 'b -> 'b) -> ('a,'b) map * 'a ref * 'b -> unit
	val insertWithi :    ('a ref * 'b * 'b -> 'b) -> ('a,'b) map * 'a ref * 'b -> unit

	val remove :         ('a,'b) map * 'a ref -> unit
	val removeExistent : ('a,'b) map * 'a ref -> unit		(* Unknown *)
	val removeWith :     ('a ref -> unit) -> ('a,'b) map * 'a ref -> unit
	val removeAll :      ('a,'b) map -> unit

	val union :          ('a,'b) map * ('a,'b) map -> unit
	val unionDisjoint :  ('a,'b) map * ('a,'b) map -> unit		(* Collision *)
	val unionWith :      ('b * 'b -> 'b) -> ('a,'b) map * ('a,'b) map -> unit
	val unionWithi :     ('a ref * 'b * 'b -> 'b) -> ('a,'b) map * ('a,'b) map -> unit

	val intersect :      ('a,'b) map * ('a,'b) map -> unit
	val intersectWith :  ('b * 'b -> 'b) -> ('a,'b) map * ('a,'b) map -> unit
	val intersectWithi : ('a ref * 'b * 'b -> 'b) -> ('a,'b) map * ('a,'b) map -> unit

	val difference :     ('a,'b) map * ('a,'b) map -> unit

	val size :           ('a,'b) map -> int
	val isEmpty :        ('a,'b) map -> bool

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

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

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

	val appi :           ('a ref * 'b -> unit) -> ('a,'b) map -> unit
	val modifyi :        ('a ref * 'b -> 'b) -> ('a,'b) map -> unit
	val foldi :          ('a ref * 'b * 'c -> 'c) -> 'c -> ('a,'b) map -> 'c
	val alli :           ('a ref * 'b -> bool) -> ('a,'b) map -> bool
	val existsi :        ('a ref * 'b -> bool) -> ('a,'b) map -> bool
	val findi :          ('a ref * 'b -> bool) -> ('a,'b) map -> ('a ref * 'b) option
	val filteri :        ('a ref * 'b -> bool) -> ('a,'b) map -> unit
    end
  

________ Description _________________________________________________

eqtype ('a,'b) map
type ('a,'b) t = ('a,'b) map

The type of finite maps from references of 'a to values of type 'b. Only maps created by the same function application are equal. Like ref and array, the map type always admits equality, independently from its arguments.

exception Unknown

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

exception Collision

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

map ()

Creates an empty map.

clone m

Creates a copy of the map m.

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.

toVector m

Returns the vector of key/value pairs from map m. Equivalent to Vector.fromList(toList m).

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

Extends the map m with the entry k->x. In the first form, if m already contains k, then the corresponding entry gets replaced by k->x. In the second form, Collision 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)

Removes the entry corresponding to key k from the map m. In the first form, if k is not contained in m, then the map is left unchanged. In the second form, Unknown will be raised. In the third form, f is applied to k before the map is modified. The following equivalences hold:

      remove         = removeWith ignore
      removeExistent = removeWith (fn k => raise Unknown k)
removeAll m

Removes all entries from the map m.

union (m1, m2)
unionDisjoint (m1, m2)
unionWith f (m1, m2)
unionWithi f (m1, m2)

Inserts all entries from map m2 into map m1. In the first form, if m1 and m2 contain entries k->x1 and k->x2, respectively, then the entry in m1 will get replaced by k->x2. In the second form, Collision will be raised. In the third form, the entry will get replaced by k->f(x1,x2). In the forth form, k 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)

Removes all entries k->x1 from map m1 for which k is not in the domain of m2. In the first form, if m2 contains a corresponding entry k->x2, respectively, then the entry in m1 will get replaced by k->x2. In the second form, the entry will get replaced by k->f(x1,x2). In the third form, k is additionally passed to f. The following equivalences hold:

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

Removes all entries k->x1 from map m1 for which k 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 an empty map, false otherwise. Equivalent to size m = 0.

member (m, k)

Returns true if the map m contains the key 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, NONE otherwise. In the second form, returns x unwrapped, or raises Unknown 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.

equal f (m1, m2)

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

submap f (m1, m2)

Returns true if m1 contains an entry k->x1 for every entry k->x2 in m2, such that 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. The following equivalences hold:

      app  f m = appi (f o #2) m
      appi f m = List.app f (toList m)
modify f m
modifyi f m

In the second form, modifies the map by replacing each entry k->x by k->f(k, x). In the first form, only x is passed to f. The following equivalences hold:

      modify  f m = modifyi (f o #2) m
      modifyi f m = List.app (fn (k, x) => insert(k, f (k, x))) (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. 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. 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. 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. 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 removes all entries from the map for which f(k, x) delivered false. In the first form, only x is passed to f. The following equivalences hold:

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


last modified 2007/Mar/30 17:10