1(* ord-map-sig.sml 2 * 3 * COPYRIGHT (c) 1996 by AT&T Research. See COPYRIGHT file for details. 4 * 5 * Abstract signature of an applicative-style finite maps (dictionaries) 6 * structure over ordered monomorphic keys. 7 * 8 * Extended by two functions "update" and "findSome" - Martin Erwig 9 *) 10 11signature ORD_MAP_UPD = 12 sig 13 14 type 'a map 15 16 val empty : 'a map 17 (* The empty map *) 18 19 val insert : 'a map * int * 'a -> 'a map 20 (* Insert an item. *) 21 22 val update : 'a map * int * ('a -> 'a) -> 'a map 23 (* Update an item by applying a function to the item already stored. 24 * Raises LibBase.NotFound if not found. 25 *) 26 27 val find : 'a map * int -> 'a option 28 (* Look for an item, return NONE if the item doesn't exist *) 29 30 val findSome : 'a map -> (int * 'a) option 31 (* Get an arbitrary item, return NONE if the map is empty *) 32 33 val remove : 'a map * int -> 'a map * 'a 34 (* Remove an item, returning new map and value removed. 35 * Raises LibBase.NotFound if not found. 36 *) 37 38 val numItems : 'a map -> int 39 (* Return the number of items in the map *) 40 41 val listItems : 'a map -> 'a list 42 val listItemsi : 'a map -> (int * 'a) list 43 (* Return an ordered list of the items (and their keys) in the map. 44 *) 45 46 val collate : ('a * 'a -> order) -> ('a map * 'a map) -> order 47 (* given an ordering on the map's range, return an ordering 48 * on the map. 49 *) 50 51 val unionWith : ('a * 'a -> 'a) -> ('a map * 'a map) -> 'a map 52 val unionWithi : (int * 'a * 'a -> 'a) -> ('a map * 'a map) -> 'a map 53 (* return a map whose domain is the union of the domains of the two input 54 * maps, using the supplied function to define the map on elements that 55 * are in both domains. 56 *) 57 58 val intersectWith : ('a * 'a -> 'b) -> ('a map * 'a map) -> 'b map 59 val intersectWithi : (int * 'a * 'a -> 'b) -> ('a map * 'a map) -> 'b map 60 (* return a map whose domain is the intersection of the domains of the 61 * two input maps, using the supplied function to define the range. 62 *) 63 64 val app : ('a -> unit) -> 'a map -> unit 65 val appi : ((int * 'a) -> unit) -> 'a map -> unit 66 (* Apply a function to the entries of the map in map order. *) 67 68 val map : ('a -> 'b) -> 'a map -> 'b map 69 val mapi : (int * 'a -> 'b) -> 'a map -> 'b map 70 (* Create a new map by applying a map function to the 71 * name/value pairs in the map. 72 *) 73 74 val foldl : ('a * 'b -> 'b) -> 'b -> 'a map -> 'b 75 val foldli : (int * 'a * 'b -> 'b) -> 'b -> 'a map -> 'b 76 (* Apply a folding function to the entries of the map 77 * in increasing map order. 78 *) 79 80 val foldr : ('a * 'b -> 'b) -> 'b -> 'a map -> 'b 81 val foldri : (int * 'a * 'b -> 'b) -> 'b -> 'a map -> 'b 82 (* Apply a folding function to the entries of the map 83 * in decreasing map order. 84 *) 85 86 val filter : ('a -> bool) -> 'a map -> 'a map 87 val filteri : (int * 'a -> bool) -> 'a map -> 'a map 88 (* Filter out those elements of the map that do not satisfy the 89 * predicate. The filtering is done in increasing map order. 90 *) 91 92 val mapPartial : ('a -> 'b option) -> 'a map -> 'b map 93 val mapPartiali : (int * 'a -> 'b option) -> 'a map -> 'b map 94 (* map a partial function over the elements of a map in increasing 95 * map order. 96 *) 97 98 end (* ORD_MAP *) 99