1(* Redblackmap -- applicative maps as Red-black trees *) 2signature Redblackmap = 3sig 4type ('key, 'a) dict 5 6exception NotFound 7 8val mkDict : ('key * 'key -> order) -> ('key, 'a) dict 9val insert : ('key, 'a) dict * 'key * 'a -> ('key, 'a) dict 10val find : ('key, 'a) dict * 'key -> 'a 11val peek : ('key, 'a) dict * 'key -> 'a option 12val remove : ('key, 'a) dict * 'key -> ('key, 'a) dict * 'a 13val numItems : ('key, 'a) dict -> int 14val listItems : ('key, 'a) dict -> ('key * 'a) list 15val app : ('key * 'a -> unit) -> ('key,'a) dict -> unit 16val revapp : ('key * 'a -> unit) -> ('key,'a) dict -> unit 17val foldr : ('key * 'a * 'b -> 'b)-> 'b -> ('key,'a) dict -> 'b 18val foldl : ('key * 'a * 'b -> 'b) -> 'b -> ('key,'a) dict -> 'b 19val map : ('key * 'a -> 'b) -> ('key,'a) dict -> ('key, 'b) dict 20val transform : ('a -> 'b) -> ('key,'a) dict -> ('key, 'b) dict 21end 22 23(* 24 [('key, 'a) dict] is the type of applicative maps from domain type 25 'key to range type 'a, or equivalently, applicative dictionaries 26 with keys of type 'key and values of type 'a. They are implemented 27 as Okasaki-style red-black trees. 28 29 [mkDict ordr] returns a new, empty map whose keys have ordering 30 ordr. 31 32 [insert(m, i, v)] extends (or modifies) map m to map i to v. 33 34 [find (m, k)] returns v if m maps k to v; otherwise raises NotFound. 35 36 [peek(m, k)] returns SOME v if m maps k to v; otherwise returns NONE. 37 38 [remove(m, k)] removes k from the domain of m and returns the 39 modified map and the element v corresponding to k. Raises NotFound 40 if k is not in the domain of m. 41 42 [numItems m] returns the number of entries in m (that is, the size 43 of the domain of m). 44 45 [listItems m] returns a list of the entries (k, v) of keys k and 46 the corresponding values v in m, in order of increasing key values. 47 48 [app f m] applies function f to the entries (k, v) in m, in 49 increasing order of k (according to the ordering ordr used to 50 create the map or dictionary). 51 52 [revapp f m] applies function f to the entries (k, v) in m, in 53 decreasing order of k. 54 55 [foldl f e m] applies the folding function f to the entries (k, v) 56 in m, in increasing order of k. 57 58 [foldr f e m] applies the folding function f to the entries (k, v) 59 in m, in decreasing order of k. 60 61 [map f m] returns a new map whose entries have form (k, f(k,v)), 62 where (k, v) is an entry in m. 63 64 [transform f m] returns a new map whose entries have form (k, f v), 65 where (k, v) is an entry in m. 66*) 67