@@ 47,6 47,9 @@ functor PersistentHashMapFn (Key : HASH_
T.alter (m, h, fn eopt => SOME (addToEntry (h, k, v) eopt))
end
+ fun singleton (k, v) =
+ insert (T.empty, k, v)
+
fun remove (m, k) =
let val h = Key.hashVal k
in
@@ 76,6 79,41 @@ functor PersistentHashMapFn (Key : HASH_
| SOME (_, v) => SOME v
end
+ fun alter (m : 'a hash_map, k : hash_key, f : 'a option -> 'a option) =
+ let val h = Key.hashVal k
+ in
+ case T.find (m, h) of
+ NONE =>
+ (case f NONE of
+ NONE => m
+ | SOME v => T.insert (m, h, ONE (k, v)))
+ | SOME (ONE (k', v')) =>
+ (if Key.sameKey (k', k)
+ then case f (SOME v') of
+ NONE => T.remove (m, h)
+ | SOME v => T.insert (m, h, ONE (k, v))
+ else case f NONE of
+ NONE => m
+ | SOME v => T.insert (m, h, MANY [(k', v'), (k, v)]))
+ | SOME (MANY values) =>
+ (case List.foldr (fn ((k', v'), (acc, found)) =>
+ if Key.sameKey (k', k)
+ then case f (SOME v') of
+ NONE => (acc, true)
+ | SOME v => ((k, v) :: acc, true)
+ else ((k', v') :: acc, found))
+ ([], false)
+ values of
+ ([], true) => T.remove (m, h)
+ | ([value], true) => T.insert (m, h, ONE value)
+ | (values, true) => T.insert (m, h, MANY values)
+ | (values, false) =>
+ (case f NONE of
+ NONE => m
+ | SOME v => T.insert (m, h, MANY ((k, v) :: values)))
+ )
+ end
+
fun lookup (m, k) =
case find (m, k) of
NONE => raise Subscript
@@ 122,7 160,32 @@ functor PersistentHashMapFn (Key : HASH_
f (k, v, acc)) acc values)
acc m
+ fun map f m =
+ foldli (fn (k, v, acc) => insert (acc, k, f v)) T.empty m
+
+ fun mapi f m =
+ foldli (fn (k, v, acc) => insert (acc, k, f (k, v))) T.empty m
+
+ fun filter f m =
+ foldli (fn (k, v, acc) => if f v
+ then insert (acc, k, v)
+ else acc)
+ T.empty m
+
+ fun filteri f m =
+ foldli (fn (k, v, acc) => if f (k, v)
+ then insert (acc, k, v)
+ else acc)
+ T.empty m
+
fun enumerate m =
foldri (fn (k, v, acc) => (k, v) :: acc) [] m
-
+
+ fun listKeys m =
+ foldri (fn (k, v, acc) => k :: acc) [] m
+
+ val inDomain = contains
+ val listItemsi = enumerate
+
end
+
@@ 25,17 25,13 @@ signature PERSISTENT_HASH_MAP = sig
(** Test whether a hash map is empty *)
val isEmpty : 'a hash_map -> bool
+ (** Create a singleton map *)
+ val singleton : hash_key * 'a -> 'a hash_map
+
(** Insert a key-value pair, returning a new hash map. If the key
is already present, its value will be updated in the new map *)
val insert : 'a hash_map * hash_key * 'a -> 'a hash_map
- (** Return the hash map with the given key removed. If the key is
- not present, the returned hash map will be unchanged *)
- val remove : 'a hash_map * hash_key -> 'a hash_map
-
- (** Test whether the hash map contains the given key *)
- val contains : 'a hash_map * hash_key -> bool
-
(** Look for a key and return its corresponding value, or NONE if
the key is not present in the hash map *)
val find : 'a hash_map * hash_key -> 'a option
@@ 43,7 39,30 @@ signature PERSISTENT_HASH_MAP = sig
(** Look for a key and return its corresponding value, raising
Subscript if the key is not present in the hash map *)
val lookup : 'a hash_map * hash_key -> 'a
-
+
+ (** Test whether the hash map contains the given key *)
+ val contains : 'a hash_map * hash_key -> bool
+
+ (** Return the hash map with the given key removed. If the key is
+ not present, the returned hash map will be unchanged *)
+ val remove : 'a hash_map * hash_key -> 'a hash_map
+
+ (** Alter a key-value pair in the hash map, returning a new hash
+ map. The function argument should map from the previous value
+ associated with the key, or NONE if it was absent before, to
+ the new value, or NONE if it is to be removed. (This is called
+ alter rather than modify to avoid confusion with the array
+ modify functions, which do something rather different) *)
+ val alter : 'a hash_map * hash_key * ('a option -> 'a option) -> 'a hash_map
+
+ (** Create a new hash map by applying the given map function to
+ the values in this hash map *)
+ val map : ('a -> 'b) -> 'a hash_map -> 'b hash_map
+
+ (** Create a new hash map by applying the given map function to
+ the key-value pairs in this hash map *)
+ val mapi : (hash_key * 'a -> 'b) -> 'a hash_map -> 'b hash_map
+
(** Fold over all the values in the hash map, in sort order *)
val foldl : ('a * 'b -> 'b) -> 'b -> 'a hash_map -> 'b
@@ 59,6 78,25 @@ signature PERSISTENT_HASH_MAP = sig
(** Return a list of all key-value pairs in the hash map, in sort order *)
val enumerate : 'a hash_map -> (hash_key * 'a) list
+ (** Return a list of all keys in the hash map, in sort order *)
+ val listKeys : 'a hash_map -> hash_key list
+
+ (** Return a hash map derived from this one, in which the elements
+ that do not satisfy the given predicate have been removed *)
+ val filter : ('a -> bool) -> 'a hash_map -> 'a hash_map
+
+ (** Return a hash map derived from this one, in which the elements
+ that do not satisfy the given predicate have been removed *)
+ val filteri : (hash_key * 'a -> bool) -> 'a hash_map -> 'a hash_map
+
+
(*!!! + tabulate, union/intersection etc *)
+
+ (** SML/NJ ORD_MAP compatibility name for "contains" *)
+ val inDomain : 'a hash_map * hash_key -> bool
+
+ (** SML/NJ ORD_MAP compatibility name for "enumerate" *)
+ val listItemsi : 'a hash_map -> (hash_key * 'a) list
+
end