3 * COPYRIGHT (c
) 1996 by AT
&T Research
. See COPYRIGHT file for details
.
5 * Abstract
signature of an applicative
-style finite
maps (dictionaries
)
6 * structure over ordered monomorphic keys
.
12 structure Key
: ORD_KEY
19 val isEmpty
: 'a map
-> bool
20 (* Return
true if and only
if the map is empty
*)
22 val singleton
: (Key
.ord_key
* 'a
) -> 'a map
23 (* return the specified singleton map
*)
25 val insert
: 'a map
* Key
.ord_key
* 'a
-> 'a map
26 val insert
' : ((Key
.ord_key
* 'a
) * 'a map
) -> 'a map
29 val find
: 'a map
* Key
.ord_key
-> 'a option
30 (* Look for an item
, return NONE
if the item doesn
't exist
*)
32 val inDomain
: ('a map
* Key
.ord_key
) -> bool
33 (* return
true, if the key is
in the domain
of the map
*)
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
.
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
) *)
44 val numItems
: 'a map
-> int
45 (* Return the number
of items
in the map
*)
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
. *)
51 val listKeys
: 'a map
-> Key
.ord_key list
52 (* return an ordered list
of the keys
in the map
. *)
54 val collate
: ('a
* 'a
-> order
) -> ('a map
* 'a map
) -> order
55 (* given an ordering on the map
's range
, return an ordering
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
.
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
.
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
.
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
. *)
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
.
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
.
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
.
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
.
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