0299b00a7d3a — Chris Cannam tip 5 months ago
Add alter, and tweak naming to make for slightly easier compatibility with SML/NJ map
2 files changed, 110 insertions(+), 9 deletions(-)

M persistent-hash-map-fn.sml
M persistent-hash-map.sig
M persistent-hash-map-fn.sml +64 -1
@@ 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
+

          
M persistent-hash-map.sig +46 -8
@@ 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