1signature Binarymap = 2sig 3 4(* Binarymap -- applicative maps as balanced ordered binary trees *) 5(* From SML/NJ lib 0.2, copyright 1993 by AT&T Bell Laboratories *) 6(* Original implementation due to Stephen Adams, Southampton, UK *) 7 8type ('key, 'a) dict 9 10exception NotFound 11 12val mkDict : ('key * 'key -> order) -> ('key, 'a) dict 13val insert : ('key, 'a) dict * 'key * 'a -> ('key, 'a) dict 14val find : ('key, 'a) dict * 'key -> 'a 15val peek : ('key, 'a) dict * 'key -> 'a option 16val remove : ('key, 'a) dict * 'key -> ('key, 'a) dict * 'a 17val numItems : ('key, 'a) dict -> int 18val listItems : ('key, 'a) dict -> ('key * 'a) list 19val app : ('key * 'a -> unit) -> ('key,'a) dict -> unit 20val revapp : ('key * 'a -> unit) -> ('key,'a) dict -> unit 21val foldr : ('key * 'a * 'b -> 'b)-> 'b -> ('key,'a) dict -> 'b 22val foldl : ('key * 'a * 'b -> 'b) -> 'b -> ('key,'a) dict -> 'b 23val map : ('key * 'a -> 'b) -> ('key,'a) dict -> ('key, 'b) dict 24val transform : ('a -> 'b) -> ('key,'a) dict -> ('key, 'b) dict 25 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 ordered balanced binary trees. 33 34 [mkDict ordr] returns a new, empty map whose keys have ordering 35 ordr. 36 37 [insert(m, i, v)] extends (or modifies) map m to map i to v. 38 39 [find (m, k)] returns v if m maps k to v; otherwise raises NotFound. 40 41 [peek(m, k)] returns SOME v if m maps k to v; otherwise returns NONE. 42 43 [remove(m, k)] removes k from the domain of m and returns the 44 modified map and the element v corresponding to k. Raises NotFound 45 if k is not in the domain of m. 46 47 [numItems m] returns the number of entries in m (that is, the size 48 of the domain of m). 49 50 [listItems m] returns a list of the entries (k, v) of keys k and 51 the corresponding values v in m, in order of increasing key values. 52 53 [app f m] applies function f to the entries (k, v) in m, in 54 increasing order of k (according to the ordering ordr used to 55 create the map or dictionary). 56 57 [revapp f m] applies function f to the entries (k, v) in m, in 58 decreasing order of k. 59 60 [foldl f e m] applies the folding function f to the entries (k, v) 61 in m, in increasing order of k. 62 63 [foldr f e m] applies the folding function f to the entries (k, v) 64 in m, in decreasing order of k. 65 66 [map f m] returns a new map whose entries have form (k, f(k,v)), 67 where (k, v) is an entry in m. 68 69 [transform f m] returns a new map whose entries have form (k, f v), 70 where (k, v) is an entry in m. 71*) 72