src/smlnj-lib/ord-map-sig.sml

   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
   9 signature ORD_MAP =
  10   sig
  11
  12     structure Key : ORD_KEY
  13
  14     type 'a map
  15
  16     val empty : 'a map
  17         (* The empty map *)
  18
  19     val isEmpty : 'a map -> bool
  20         (* Return true if and only if the map is empty *)
  21
  22     val singleton : (Key.ord_key * 'a) -> 'a map
  23         (* return the specified singleton map *)
  24
  25     val insert  : 'a map * Key.ord_key * 'a -> 'a map
  26     val insert' : ((Key.ord_key * 'a) * 'a map) -> 'a map
  27         (* Insert an item. *)
  28
  29     val find : 'a map * Key.ord_key -> 'a option
  30         (* Look for an item, return NONE if the item doesn't exist *)
  31
  32     val inDomain : ('a map * Key.ord_key) -> bool
  33         (* return true, if the key is in the domain of the map *)
  34
  35     val remove : 'a map * Key.ord_key -> 'a map * 'a
  36         (* Remove an item, returning new map and value removed.
  37          * Raises LibBase.NotFound if not found.
  38          *)
  39
  40     val first : 'a map -> 'a option
  41     val firsti : 'a map -> (Key.ord_key * 'a) option
  42         (* return the first item in the map (or NONE if it is empty) *)
  43
  44     val numItems : 'a map ->  int
  45         (* Return the number of items in the map *)
  46
  47     val listItems  : 'a map -> 'a list
  48     val listItemsi : 'a map -> (Key.ord_key * 'a) list
  49         (* Return an ordered list of the items (and their keys) in the map. *)
  50
  51     val listKeys : 'a map -> Key.ord_key list
  52         (* return an ordered list of the keys in the map. *)
  53
  54     val collate : ('a * 'a -> order) -> ('a map * 'a map) -> order
  55         (* given an ordering on the map's range, return an ordering
  56          * on the map.
  57          *)
  58
  59     val unionWith  : ('a * 'a -> 'a) -> ('a map * 'a map) -> 'a map
  60     val unionWithi : (Key.ord_key * 'a * 'a -> 'a) -> ('a map * 'a map) -> 'a map
  61         (* return a map whose domain is the union of the domains of the two input
  62          * maps, using the supplied function to define the map on elements that
  63          * are in both domains.
  64          *)
  65
  66     val intersectWith  : ('a * 'b -> 'c) -> ('a map * 'b map) -> 'c map
  67     val intersectWithi : (Key.ord_key * 'a * 'b -> 'c) -> ('a map * 'b map) -> 'c map
  68         (* return a map whose domain is the intersection of the domains of the
  69          * two input maps, using the supplied function to define the range.
  70          *)
  71
  72     val mergeWith : ('a option * 'b option -> 'c option)
  73           -> ('a map * 'b map) -> 'c map
  74     val mergeWithi : (Key.ord_key * 'a option * 'b option -> 'c option)
  75           -> ('a map * 'b map) -> 'c map
  76         (* merge two maps using the given function to control the merge. For
  77          * each key k in the union of the two maps domains, the function
  78          * is applied to the image of the key under the map.  If the function
  79          * returns SOME y, then (k, y) is added to the resulting map.
  80          *)
  81
  82     val app  : ('a -> unit) -> 'a map -> unit
  83     val appi : ((Key.ord_key * 'a) -> unit) -> 'a map -> unit
  84         (* Apply a function to the entries of the map in map order. *)
  85
  86     val map  : ('a -> 'b) -> 'a map -> 'b map
  87     val mapi : (Key.ord_key * 'a -> 'b) -> 'a map -> 'b map
  88         (* Create a new map by applying a map function to the
  89          * name/value pairs in the map.
  90          *)
  91
  92     val foldl  : ('a * 'b -> 'b) -> 'b -> 'a map -> 'b
  93     val foldli : (Key.ord_key * 'a * 'b -> 'b) -> 'b -> 'a map -> 'b
  94         (* Apply a folding function to the entries of the map
  95          * in increasing map order.
  96          *)
  97
  98     val foldr  : ('a * 'b -> 'b) -> 'b -> 'a map -> 'b
  99     val foldri : (Key.ord_key * 'a * 'b -> 'b) -> 'b -> 'a map -> 'b
 100         (* Apply a folding function to the entries of the map
 101          * in decreasing map order.
 102          *)
 103
 104     val filter  : ('a -> bool) -> 'a map -> 'a map
 105     val filteri : (Key.ord_key * 'a -> bool) -> 'a map -> 'a map
 106         (* Filter out those elements of the map that do not satisfy the
 107          * predicate.  The filtering is done in increasing map order.
 108          *)
 109
 110     val mapPartial  : ('a -> 'b option) -> 'a map -> 'b map
 111     val mapPartiali : (Key.ord_key * 'a -> 'b option) -> 'a map -> 'b map
 112         (* map a partial function over the elements of a map in increasing
 113          * map order.
 114          *)
 115
 116   end (* ORD_MAP *)