1(* Redblackmap -- applicative maps as Red-black trees *) 2signature Redblackmap = 3sig 4 type ('key, 'a) dict 5 6 exception NotFound 7 8 val mkDict : ('key * 'key -> order) -> ('key, 'a) dict 9 val fromList : ('key * 'key -> order) -> ('key * 'a) list -> ('key, 'a) dict 10 val update : ('key, 'a) dict * 'key * ('a option -> 'a) -> ('key, 'a) dict 11 val insert : ('key, 'a) dict * 'key * 'a -> ('key, 'a) dict 12 val insertList : ('key, 'a) dict * ('key * 'a) list -> ('key, 'a) dict 13 val findKey : ('key, 'a) dict * 'key -> 'key * 'a 14 val find : ('key, 'a) dict * 'key -> 'a 15 val peek : ('key, 'a) dict * 'key -> 'a option 16 val remove : ('key, 'a) dict * 'key -> ('key, 'a) dict * 'a 17 val numItems : ('key, 'a) dict -> int 18 val listItems : ('key, 'a) dict -> ('key * 'a) list 19 val isEmpty : ('key, 'a) dict -> bool 20 val app : ('key * 'a -> unit) -> ('key,'a) dict -> unit 21 val revapp : ('key * 'a -> unit) -> ('key,'a) dict -> unit 22 val foldr : ('key * 'a * 'b -> 'b)-> 'b -> ('key,'a) dict -> 'b 23 val foldl : ('key * 'a * 'b -> 'b) -> 'b -> ('key,'a) dict -> 'b 24 val map : ('key * 'a -> 'b) -> ('key,'a) dict -> ('key, 'b) dict 25 val transform : ('a -> 'b) -> ('key,'a) dict -> ('key, 'b) dict 26end 27 28(* 29 [('key, 'a) dict] is the type of applicative maps from domain type 30 'key to range type 'a, or equivalently, applicative dictionaries 31 with keys of type 'key and values of type 'a. They are implemented 32 as Okasaki-style red-black trees. 33 34 [mkDict ordr] returns a new, empty map whose keys have ordering 35 ordr. 36 37 [fromList ordr xs] returns a map that contains the (index, value) 38 pairs in xs, whose keys have ordering ordr. It is equivalent to 39 insertList (mkDict ordr, xs). 40 41 [update(m, i, f)] extends m to map i to (f NONE) if i is not 42 already mapped, or to (f (SOME v)) if i is already mapped to v. 43 44 [insert(m, i, v)] extends (or modifies) map m to map i to v. 45 46 [insertList(m, xs)] extends (or modifies) map m with the (index, 47 value) pairs in xs. (It is equivalent to foldl (fn ((i, v), m) => 48 insert (m, i, v)) m xs.) Note that later list entries will 49 overwrite earlier entries for the same index. 50 51 [findKey (m, k)] returns (k, v) if m maps k to v; 52 otherwise, raises NotFound. The returned key is the last one EQUAL in 53 the order to k that was used to extend or modify the map. 54 55 [find (m, k)] returns v if m maps k to v; otherwise raises NotFound. 56 57 [peek(m, k)] returns SOME v if m maps k to v; otherwise returns NONE. 58 59 [remove(m, k)] removes k from the domain of m and returns the 60 modified map and the element v corresponding to k. Raises NotFound 61 if k is not in the domain of m. 62 63 [numItems m] returns the number of entries in m (that is, the size 64 of the domain of m). 65 66 [listItems m] returns a list of the entries (k, v) of keys k and 67 the corresponding values v in m, in order of increasing key values. 68 69 [isEmpty m] returns true if the map m is empty, and false otherwise. 70 71 [app f m] applies function f to the entries (k, v) in m, in 72 increasing order of k (according to the ordering ordr used to 73 create the map or dictionary). 74 75 [revapp f m] applies function f to the entries (k, v) in m, in 76 decreasing order of k. 77 78 [foldl f e m] applies the folding function f to the entries (k, v) 79 in m, in increasing order of k. 80 81 [foldr f e m] applies the folding function f to the entries (k, v) 82 in m, in decreasing order of k. 83 84 [map f m] returns a new map whose entries have form (k, f(k,v)), 85 where (k, v) is an entry in m. 86 87 [transform f m] returns a new map whose entries have form (k, f v), 88 where (k, v) is an entry in m. 89*) 90