Home My Page Projects Code Snippets Project Openings SML/NJ
Summary Activity Forums Tracker Lists Tasks Docs Surveys News SCM Files

SCM Repository

[smlnj] Annotation of /smlnj-lib/branches/rt-transition/Util/ord-map-sig.sml
ViewVC logotype

Annotation of /smlnj-lib/branches/rt-transition/Util/ord-map-sig.sml

Parent Directory Parent Directory | Revision Log Revision Log


Revision 4070 - (view) (download)

1 : monnier 2 (* ord-map-sig.sml
2 :     *
3 : jhr 4070 * COPYRIGHT (c) 2012 The Fellowship of SML/NJ (http://www.smlnj.org)
4 :     * All rights reserved.
5 :     *
6 : monnier 2 * COPYRIGHT (c) 1996 by AT&T Research. See COPYRIGHT file for details.
7 :     *
8 :     * Abstract signature of an applicative-style finite maps (dictionaries)
9 :     * structure over ordered monomorphic keys.
10 :     *)
11 :    
12 :     signature ORD_MAP =
13 :     sig
14 :    
15 :     structure Key : ORD_KEY
16 : jhr 4070 (* the map's domain and its comparison function *)
17 : monnier 2
18 :     type 'a map
19 :    
20 :     val empty : 'a map
21 :     (* The empty map *)
22 :    
23 : monnier 289 val isEmpty : 'a map -> bool
24 :     (* Return true if and only if the map is empty *)
25 :    
26 : monnier 411 val singleton : (Key.ord_key * 'a) -> 'a map
27 :     (* return the specified singleton map *)
28 :    
29 : monnier 29 val insert : 'a map * Key.ord_key * 'a -> 'a map
30 :     val insert' : ((Key.ord_key * 'a) * 'a map) -> 'a map
31 :     (* Insert an item. *)
32 : monnier 2
33 :     val find : 'a map * Key.ord_key -> 'a option
34 :     (* Look for an item, return NONE if the item doesn't exist *)
35 :    
36 : jhr 2274 val lookup : 'a map * Key.ord_key -> 'a
37 :     (* look for an item, raise the NotFound exception if it doesn't exist *)
38 :    
39 : monnier 411 val inDomain : ('a map * Key.ord_key) -> bool
40 :     (* return true, if the key is in the domain of the map *)
41 :    
42 : monnier 2 val remove : 'a map * Key.ord_key -> 'a map * 'a
43 :     (* Remove an item, returning new map and value removed.
44 :     * Raises LibBase.NotFound if not found.
45 :     *)
46 :    
47 : monnier 289 val first : 'a map -> 'a option
48 :     val firsti : 'a map -> (Key.ord_key * 'a) option
49 :     (* return the first item in the map (or NONE if it is empty) *)
50 :    
51 : monnier 2 val numItems : 'a map -> int
52 :     (* Return the number of items in the map *)
53 :    
54 :     val listItems : 'a map -> 'a list
55 :     val listItemsi : 'a map -> (Key.ord_key * 'a) list
56 : monnier 411 (* Return an ordered list of the items (and their keys) in the map. *)
57 : monnier 2
58 : monnier 411 val listKeys : 'a map -> Key.ord_key list
59 :     (* return an ordered list of the keys in the map. *)
60 :    
61 : monnier 2 val collate : ('a * 'a -> order) -> ('a map * 'a map) -> order
62 :     (* given an ordering on the map's range, return an ordering
63 :     * on the map.
64 :     *)
65 :    
66 :     val unionWith : ('a * 'a -> 'a) -> ('a map * 'a map) -> 'a map
67 :     val unionWithi : (Key.ord_key * 'a * 'a -> 'a) -> ('a map * 'a map) -> 'a map
68 :     (* return a map whose domain is the union of the domains of the two input
69 :     * maps, using the supplied function to define the map on elements that
70 :     * are in both domains.
71 :     *)
72 :    
73 :     val intersectWith : ('a * 'b -> 'c) -> ('a map * 'b map) -> 'c map
74 :     val intersectWithi : (Key.ord_key * 'a * 'b -> 'c) -> ('a map * 'b map) -> 'c map
75 :     (* return a map whose domain is the intersection of the domains of the
76 :     * two input maps, using the supplied function to define the range.
77 :     *)
78 :    
79 : jhr 1193 val mergeWith : ('a option * 'b option -> 'c option)
80 :     -> ('a map * 'b map) -> 'c map
81 :     val mergeWithi : (Key.ord_key * 'a option * 'b option -> 'c option)
82 :     -> ('a map * 'b map) -> 'c map
83 :     (* merge two maps using the given function to control the merge. For
84 :     * each key k in the union of the two maps domains, the function
85 :     * is applied to the image of the key under the map. If the function
86 :     * returns SOME y, then (k, y) is added to the resulting map.
87 :     *)
88 :    
89 : monnier 2 val app : ('a -> unit) -> 'a map -> unit
90 :     val appi : ((Key.ord_key * 'a) -> unit) -> 'a map -> unit
91 :     (* Apply a function to the entries of the map in map order. *)
92 :    
93 :     val map : ('a -> 'b) -> 'a map -> 'b map
94 :     val mapi : (Key.ord_key * 'a -> 'b) -> 'a map -> 'b map
95 :     (* Create a new map by applying a map function to the
96 :     * name/value pairs in the map.
97 :     *)
98 :    
99 :     val foldl : ('a * 'b -> 'b) -> 'b -> 'a map -> 'b
100 :     val foldli : (Key.ord_key * 'a * 'b -> 'b) -> 'b -> 'a map -> 'b
101 :     (* Apply a folding function to the entries of the map
102 :     * in increasing map order.
103 :     *)
104 :    
105 :     val foldr : ('a * 'b -> 'b) -> 'b -> 'a map -> 'b
106 :     val foldri : (Key.ord_key * 'a * 'b -> 'b) -> 'b -> 'a map -> 'b
107 :     (* Apply a folding function to the entries of the map
108 :     * in decreasing map order.
109 :     *)
110 :    
111 :     val filter : ('a -> bool) -> 'a map -> 'a map
112 :     val filteri : (Key.ord_key * 'a -> bool) -> 'a map -> 'a map
113 :     (* Filter out those elements of the map that do not satisfy the
114 :     * predicate. The filtering is done in increasing map order.
115 :     *)
116 :    
117 :     val mapPartial : ('a -> 'b option) -> 'a map -> 'b map
118 :     val mapPartiali : (Key.ord_key * 'a -> 'b option) -> 'a map -> 'b map
119 :     (* map a partial function over the elements of a map in increasing
120 :     * map order.
121 :     *)
122 :    
123 : jhr 4070 val exists : ('a -> bool) -> 'a map -> bool
124 :     val existsi : (Key.ord_key * 'a -> bool) -> 'a map -> bool
125 :     (* check the elements of a map with a predicate and return true if
126 :     * any element satisfies the predicate. Return false otherwise.
127 :     * Elements are checked in key order.
128 :     *)
129 :    
130 :     val all : ('a -> bool) -> 'a map -> bool
131 :     val alli : (Key.ord_key * 'a -> bool) -> 'a map -> bool
132 :     (* check the elements of a map with a predicate and return true if
133 :     * they all satisfy the predicate. Return false otherwise. Elements
134 :     * are checked in key order.
135 :     *)
136 :    
137 : monnier 2 end (* ORD_MAP *)

root@smlnj-gforge.cs.uchicago.edu
ViewVC Help
Powered by ViewVC 1.0.0