[m-rev.] for review: Add map.merge/4

[Paul Bone]

Branches: master

Add map.merge/4

This version of map.merge takes an additional parameter allowing the callee
to specify how conflicting key-value pairs should be handled.  This is
useful when the values for a given key need to be merged in some way.

merge's parameter order looks like: merge(ResulveFunc, MapA, MapB, Map).
The current implementation runs in linear time with respect to its first
argument, this is different from the existing merge/3 predicate.  Before
committing this I'd like to determine which argument order is preferred and
if it is worthwhile changing the argument order of merge/4 (this
contribution) to conform with the established order or somehow transitioning
to a new argument order.  Another option is using a different name for this
slightly different predicate (this may be good regardless of the argument
order discussion).

Thanks.

library/map.m:
    As above.

NEWS:
    List the new predicate and function.
---
 NEWS          |  4 ++--
 library/map.m | 34 ++++++++++++++++++++++++++++++++--
 2 files changed, 34 insertions(+), 4 deletions(-)

diff --git a/NEWS b/NEWS
index 496c14e..22e90ff 100644
--- a/NEWS
+++ b/NEWS
@@ -15,8 +15,8 @@ Changes to the Mercury standard library:
 * We have added the following predicates to the array and version_array
   modules: is_empty/1, all_true/2 and all_false/2.
 
-* We have added the following functions to the map module: det_min_key/1
-  and det_max_key/1.
+* We have added the following functions to the map module: det_min_key/1,
+  det_max_key/1 and merge/3.  We have also added the predicate merge/4.
 
 * We have added the following predicates to the list module: foldr2/6 and
   foldr3/8.
diff --git a/library/map.m b/library/map.m
index ebeecf5..3a52617 100644
--- a/library/map.m
+++ b/library/map.m
@@ -299,8 +299,19 @@
     % in the second map, so for efficiency, you want to put the bigger map
     % first and the smaller map second.
     %
-:- func map.merge(map(K, V), map(K, V)) = map(K, V).
-:- pred map.merge(map(K, V)::in, map(K, V)::in, map(K, V)::out) is det.
+:- func merge(map(K, V), map(K, V)) = map(K, V).
+:- pred merge(map(K, V)::in, map(K, V)::in, map(K, V)::out) is det.
+
+    % Merge two maps resolving disjoint keys.
+    %
+    % If a value is present in both maps then the higher
+    % order value is used to resolve the conflict.  The implementation takes
+    % time proportional to the size of MapA.  So for efficiency you want to
+    % put the smaller map first and the larger one second.
+    %
+:- func merge(func(K, V, V) = V, map(K, V), map(K, V)) = map(K, V).
+:- pred merge((func(K, V, V) = V)::in, map(K, V)::in,
+    map(K, V)::in, map(K, V)::out) is det.
 
     % For map.overlay(MapA, MapB, Map), if MapA and MapB both contain the
     % same key, then Map will map that key to the value from MapB.
@@ -1142,6 +1153,25 @@ map.merge(MA, MB, M) :-
 
 %-----------------------------------------------------------------------------%
 
+merge(Resolve, MA, MB) = Map :-
+    merge(Resolve, MA, MB, Map).
+
+merge(Resolve, MA, MB, Map) :-
+    map.foldl(merge_item(Resolve), MA, MB, Map).
+
+:- pred merge_item((func(K, V, V) = V)::in, K::in, V::in,
+    map(K, V)::in, map(K, V)::out) is det.
+
+merge_item(Resolve, KA, VA, !Map) :-
+    ( map.search(!.Map, KA, VB) ->
+        V = Resolve(KA, VA, VB),
+        map.det_update(KA, V, !Map)
+    ;
+        map.det_insert(KA, VA, !Map)
+    ).
+
+%-----------------------------------------------------------------------------%
+
 map.old_merge(M1, M2) = M3 :-
     map.old_merge(M1, M2, M3).
 
-- 
1.8.5.1