[m-rev.] diff: standard library additions

[Julien Fischer]

Branches: master

-------------------


Add some more standard library procedures.

library/bimap.m:
 	Add a predicate for testing semantic equality of bimaps.

library/assoc_list.m:
 	Add fold_values with two or three accumulator arguments.

library/int.m:
 	Add fold_{up,down} with three accumulator arguments.

library/map.m:
library/tree234.m;
 	Add foldl_values with two or three accumulator arguments.

NEWS:
 	Announce the above additions.

 	Reformat the existing changes to the pqueue module slightly

Julien.

diff --git a/NEWS b/NEWS
index 496c14e..79bc885 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 predicates and functions to the map module:
+  det_min_key/1, det_max_key/1, foldl2_values/6 and foldl3_values/8.

  * We have added the following predicates to the list module: foldr2/6 and
    foldr3/8.
@@ -24,14 +24,18 @@ Changes to the Mercury standard library:
  * We have added the following predicates to the bag module: foldl/4 and
    foldl2/6.

-* We have added the following predicate to the assoc_list module:
-  foldl2_values/6.
+* We have added the following predicates to the assoc_list module:
+  foldl2_values/6 and foldl3_values/8.

-* We have added the following predicates to the pqueue module:
-  is_empty/1, peek/3, peek_key/2, peek_value/2, det_peek/3 and merge/3.
-  We have also added the following functions to the pqueue module:
+* We have added the following predicates and functions to the pqueue module:
+  is_empty/1, peek/3, peek_key/2, peek_value/2, det_peek/3, merge/3,
    det_peek_key/1 and det_peek_value/1.

+* We have added the predicate bimap.equal/2.
+
+* We have added the following predicates to the int module: fold_up3/9 and
+  fold_down3/9.
+
  Changes to the extras distribution:

  * We've added a library that provides support for accessing the function
diff --git a/library/assoc_list.m b/library/assoc_list.m
index 63d0e40..7c9813a 100644
--- a/library/assoc_list.m
+++ b/library/assoc_list.m
@@ -199,6 +199,27 @@
      in, out, in, out) is multi.
  :- mode assoc_list.foldl2_values(pred(in, in, out, in, out) is nondet, in,
      in, out, in, out) is nondet.
+ 
+    % As above, but with three accumulators.
+    %
+:- pred assoc_list.foldl3_values(pred(V, A, A, B, B, C, C), assoc_list(K, V),
+    A, A, B, B, C, C).
+:- mode assoc_list.foldl3_values(pred(in, in, out, in, out, in, out) is det,
+    in, in, out, in, out, in, out) is det.
+:- mode assoc_list.foldl3_values(pred(in, in, out, in, out, mdi, muo) is det,
+    in, in, out, in, out, mdi, muo) is det.
+:- mode assoc_list.foldl3_values(pred(in, in, out, in, out, di, uo) is det,
+    in, in, out, in, out, di, uo) is det.
+:- mode assoc_list.foldl3_values(pred(in, in, out, in, out, in, out) is semidet,
+    in, in, out, in, out, in, out) is semidet.
+:- mode assoc_list.foldl3_values(pred(in, in, out, in, out, mdi, muo) is semidet,
+    in, in, out, in, out, mdi, muo) is semidet.
+:- mode assoc_list.foldl3_values(pred(in, in, out, in, out, di, uo) is semidet,
+    in, in, out, in, out, di, uo) is semidet.
+:- mode assoc_list.foldl3_values(pred(in, in, out, in, out, in, out) is multi,
+    in, in, out, in, out, in, out) is multi.
+:- mode assoc_list.foldl3_values(pred(in, in, out, in, out, in, out) is nondet,
+    in, in, out, in, out, in, out) is nondet.

  %-----------------------------------------------------------------------------%
  %-----------------------------------------------------------------------------%
@@ -392,6 +413,12 @@ assoc_list.foldl2_values(P, [KV | KVs], !Acc1, !Acc2) :-
      P(V, !Acc1, !Acc2),
      assoc_list.foldl2_values(P, KVs, !Acc1, !Acc2).

+assoc_list.foldl3_values(_, [], !Acc1, !Acc2, !Acc3).
+assoc_list.foldl3_values(P, [KV | KVs], !Acc1, !Acc2, !Acc3) :-
+    KV = _K - V,
+    P(V, !Acc1, !Acc2, !Acc3),
+    assoc_list.foldl3_values(P, KVs, !Acc1, !Acc2, !Acc3).
+
  %-----------------------------------------------------------------------------%
  :- end_module assoc_list.
  %-----------------------------------------------------------------------------%
diff --git a/library/bimap.m b/library/bimap.m
index 4fd8a5b..c52b203 100644
--- a/library/bimap.m
+++ b/library/bimap.m
@@ -46,6 +46,15 @@
      %
  :- pred bimap.is_empty(bimap(K, V)::in) is semidet.

+    % True if both bimaps have the same set of key-value pairs, regardless of
+    % how the bimaps were constructed.
+    %
+    % Unifying bimaps does not work as one might expect because the internal
+    % structures of two bimaps that contain the same set of key-value pairs
+    % may be different.
+    %
+:- pred bimap.equal(bimap(K, V)::in, bimap(K, V)::in) is semidet.
+
      % Search the bimap. The first mode searches for a value given a key
      % and the second mode searches for a key given a value.
      %
@@ -358,6 +367,11 @@ bimap.singleton(K, V) = B:-
  bimap.is_empty(bimap(Forward, _)) :-
      map.is_empty(Forward). % by inference == map.is_empty(Reverse).

+bimap.equal(BMA, BMB) :-
+    BMA = bimap(ForwardA, _ReverseA),
+    BMB = bimap(ForwardB, _ReverseB),
+    map.equal(ForwardA, ForwardB).
+
  bimap.search(bimap(Forward, Reverse), K, V) :-
      map.search(Forward, K, V),
      map.search(Reverse, V, K).
diff --git a/library/int.m b/library/int.m
index 2530b70..3a86657 100644
--- a/library/int.m
+++ b/library/int.m
@@ -349,6 +349,60 @@
      in, out, in, out) is nondet.
  :- mode int.fold_down2(pred(in, in, out, mdi, muo) is nondet, in, in,
      in, out, mdi, muo) is nondet.
+ 
+    % fold_up3(F, Low, High, !Acc1, Acc2, !Acc3) <=>
+    %   list.foldl3(F, Low .. High, !Acc1, !Acc2, !Acc3)
+    %
+    % NOTE: fold_up3/9 is undefined if High = int.max_int.
+    %
+:- pred int.fold_up3(pred(int, T, T, U, U, V, V), int, int, T, T, U, U, V, V).
+:- mode int.fold_up3(pred(in, in, out, in, out, in, out) is det,
+    in, in, in, out, in, out, in, out) is det.
+:- mode int.fold_up3(pred(in, in, out, in, out, mdi, muo) is det,
+    in, in, in, out, in, out, mdi, muo) is det.
+:- mode int.fold_up3(pred(in, in, out, in, out, di, uo) is det,
+    in, in, in, out, in, out, di, uo) is det.
+:- mode int.fold_up3(pred(in, in, out, di, uo, di, uo) is det,
+    in, in, in, out, di, uo, di, uo) is det.
+:- mode int.fold_up3(pred(in, in, out, in, out, array_di, array_uo) is det,
+    in, in, in, out, in, out, array_di, array_uo) is det.
+:- mode int.fold_up3(pred(in, in, out, in, out, in, out) is semidet,
+    in, in, in, out, in, out, in, out) is semidet.
+:- mode int.fold_up3(pred(in, in, out, in, out, mdi, muo) is semidet,
+    in, in, in, out, in, out, mdi, muo) is semidet.
+:- mode int.fold_up3(pred(in, in, out, in, out, di, uo) is semidet,
+    in, in, in, out, in, out, di, uo) is semidet.
+:- mode int.fold_up3(pred(in, in, out, in, out, in, out) is nondet,
+    in, in, in, out, in, out, in, out) is nondet.
+:- mode int.fold_up3(pred(in, in, out, in, out, mdi, muo) is nondet,
+    in, in, in, out, in, out, mdi, muo) is nondet.
+ 
+    % fold_up3(F, Low, High, !Acc1, Acc2, !Acc3) <=>
+    %   list.foldr3(F, Low .. High, !Acc1, !Acc2, !Acc3)
+    %
+    % NOTE: fold_down3/9 is undefined if Low = int.min_int.
+    %
+:- pred int.fold_down3(pred(int, T, T, U, U, V, V), int, int, T, T, U, U, V, V).
+:- mode int.fold_down3(pred(in, in, out, in, out, in, out) is det,
+    in, in, in, out, in, out, in, out) is det.
+:- mode int.fold_down3(pred(in, in, out, in, out, mdi, muo) is det,
+    in, in, in, out, in, out, mdi, muo) is det.
+:- mode int.fold_down3(pred(in, in, out, in, out, di, uo) is det,
+    in, in, in, out, in, out, di, uo) is det.
+:- mode int.fold_down3(pred(in, in, out, di, uo, di, uo) is det,
+    in, in, in, out, di, uo, di, uo) is det.
+:- mode int.fold_down3(pred(in, in, out, in, out, array_di, array_uo) is det,
+    in, in, in, out, in, out, array_di, array_uo) is det.
+:- mode int.fold_down3(pred(in, in, out, in, out, in, out) is semidet,
+    in, in, in, out, in, out, in, out) is semidet.
+:- mode int.fold_down3(pred(in, in, out, in, out, mdi, muo) is semidet,
+    in, in, in, out, in, out, mdi, muo) is semidet.
+:- mode int.fold_down3(pred(in, in, out, in, out, di, uo) is semidet,
+    in, in, in, out, in, out, di, uo) is semidet.
+:- mode int.fold_down3(pred(in, in, out, in, out, in, out) is nondet,
+    in, in, in, out, in, out, in, out) is nondet.
+:- mode int.fold_down3(pred(in, in, out, in, out, mdi, muo) is nondet,
+    in, in, in, out, in, out, mdi, muo) is nondet.

      % nondet_int_in_range(Lo, Hi, I):
      %
@@ -831,6 +885,12 @@ int.fold_up2(P, Lo, Hi, !A, !B) :-
        else  true
      ).

+int.fold_up3(P, Lo, Hi, !A, !B, !C) :-
+    ( if    Lo =< Hi
+      then  P(Lo, !A, !B, !C), int.fold_up3(P, Lo + 1, Hi, !A, !B, !C)
+      else  true
+    ).
+
  %-----------------------------------------------------------------------------%

  int.fold_down(P, Lo, Hi, !A) :-
@@ -848,6 +908,14 @@ int.fold_down2(P, Lo, Hi, !A, !B) :-
        else  true
      ).

+int.fold_down3(P, Lo, Hi, !A, !B, !C) :-
+    ( if    Lo =< Hi
+      then  P(Hi, !A, !B, !C), int.fold_down3(P, Lo, Hi - 1, !A, !B, !C)
+      else  true
+    ).
+
+%-----------------------------------------------------------------------------%
+
  nondet_int_in_range(Lo, Hi, I) :-
      % Leave a choice point only if there is at least one solution
      % to find on backtracking.
diff --git a/library/map.m b/library/map.m
index 24d225c..3bd416e 100644
--- a/library/map.m
+++ b/library/map.m
@@ -456,6 +456,51 @@
  :- mode map.foldl_values(pred(in, mdi, muo) is cc_multi, in, mdi, muo)
      is cc_multi.

+    % As above, but with two accumulators.
+    %
+:- pred map.foldl2_values(pred(V, A, A, B, B), map(K, V), A, A, B, B).
+:- mode map.foldl2_values(pred(in, in, out, in, out) is det, in,
+    in, out, in, out) is det.
+:- mode map.foldl2_values(pred(in, in, out, mdi, muo) is det, in,
+    in, out, mdi, muo) is det.
+:- mode map.foldl2_values(pred(in, in, out, di, uo) is det, in,
+    in, out, di, uo) is det.
+:- mode map.foldl2_values(pred(in, in, out, in, out) is semidet, in,
+    in, out, in, out) is semidet.
+:- mode map.foldl2_values(pred(in, in, out, mdi, muo) is semidet, in,
+    in, out, mdi, muo) is semidet.
+:- mode map.foldl2_values(pred(in, in, out, di, uo) is semidet, in,
+    in, out, di, uo) is semidet.
+:- mode map.foldl2_values(pred(in, in, out, in, out) is cc_multi, in,
+    in, out, in, out) is cc_multi.
+:- mode map.foldl2_values(pred(in, in, out, mdi, muo) is cc_multi, in,
+    in, out, mdi, muo) is cc_multi.
+:- mode map.foldl2_values(pred(in, in, out, di, uo) is cc_multi, in,
+    in, out, di, uo) is cc_multi.
+
+    % As above, but with three accumulators.
+    %
+:- pred map.foldl3_values(pred(V, A, A, B, B, C, C), map(K, V),
+    A, A, B, B, C, C).
+:- mode map.foldl3_values(pred(in, in, out, in, out, in, out) is det, in,
+    in, out, in, out, in, out) is det.
+:- mode map.foldl3_values(pred(in, in, out, in, out, mdi, muo) is det, in,
+    in, out, in, out, mdi, muo) is det.
+:- mode map.foldl3_values(pred(in, in, out, in, out, di, uo) is det, in,
+    in, out, in, out, di, uo) is det.
+:- mode map.foldl3_values(pred(in, in, out, in, out, in, out) is semidet, in,
+    in, out, in, out, in, out) is semidet.
+:- mode map.foldl3_values(pred(in, in, out, in, out, mdi, muo) is semidet, in,
+    in, out, in, out, mdi, muo) is semidet.
+:- mode map.foldl3_values(pred(in, in, out, in, out, di, uo) is semidet, in,
+    in, out, in, out, di, uo) is semidet.
+:- mode map.foldl3_values(pred(in, in, out, in, out, in, out) is cc_multi, in,
+    in, out, in, out, in, out) is cc_multi.
+:- mode map.foldl3_values(pred(in, in, out, in, out, mdi, muo) is cc_multi, in,
+    in, out, in, out, mdi, muo) is cc_multi.
+:- mode map.foldl3_values(pred(in, in, out, in, out, di, uo) is cc_multi, in,
+    in, out, in, out, di, uo) is cc_multi.
+
  :- func map.foldr(func(K, V, A) = A, map(K, V), A) = A.
  :- pred map.foldr(pred(K, V, A, A), map(K, V), A, A).
  :- mode map.foldr(pred(in, in, in, out) is det, in, in, out) is det.
@@ -1263,6 +1308,12 @@ map.foldl4(Pred, Map, !A, !B, !C, !D) :-
  map.foldl_values(Pred, Map, !A) :-
      tree234.foldl_values(Pred, Map, !A).

+map.foldl2_values(Pred, Map, !A, !B) :-
+    tree234.foldl2_values(Pred, Map, !A, !B).
+
+map.foldl3_values(Pred, Map, !A, !B, !C) :-
+    tree234.foldl3_values(Pred, Map, !A, !B, !C).
+
  map.foldr(F, M, A) = B :-
      P = (pred(W::in, X::in, Y::in, Z::out) is det :- Z = F(W, X, Y) ),
      map.foldr(P, M, A, B).
diff --git a/library/tree234.m b/library/tree234.m
index 7aa6efd..01422fc 100644
--- a/library/tree234.m
+++ b/library/tree234.m
@@ -300,6 +300,47 @@
  :- mode tree234.foldl_values(pred(in, mdi, muo) is cc_multi, in, mdi, muo)
      is cc_multi.

+:- pred tree234.foldl2_values(pred(V, A, A, B, B), tree234(K, V), A, A, B, B).
+:- mode tree234.foldl2_values(pred(in, in, out, in, out) is det, in,
+    in, out, in, out) is det.
+:- mode tree234.foldl2_values(pred(in, in, out, mdi, muo) is det, in,
+    in, out, mdi, muo) is det.
+:- mode tree234.foldl2_values(pred(in, in, out, di, uo) is det, in,
+    in, out, di, uo) is det.
+:- mode tree234.foldl2_values(pred(in, in, out, in, out) is semidet, in,
+    in, out, in, out) is semidet.
+:- mode tree234.foldl2_values(pred(in, in, out, mdi, muo) is semidet, in,
+    in, out, mdi, muo) is semidet.
+:- mode tree234.foldl2_values(pred(in, in, out, di, uo) is semidet, in,
+    in, out, di, uo) is semidet.
+:- mode tree234.foldl2_values(pred(in, in, out, in, out) is cc_multi, in,
+    in, out, in, out) is cc_multi.
+:- mode tree234.foldl2_values(pred(in, in, out, mdi, muo) is cc_multi, in,
+    in, out, mdi, muo) is cc_multi.
+:- mode tree234.foldl2_values(pred(in, in, out, di, uo) is cc_multi, in,
+    in, out, di, uo) is cc_multi.
+
+:- pred tree234.foldl3_values(pred(V, A, A, B, B, C, C), tree234(K, V),
+    A, A, B, B, C, C).
+:- mode tree234.foldl3_values(pred(in, in, out, in, out, in, out) is det,
+    in, in, out, in, out, in, out) is det.
+:- mode tree234.foldl3_values(pred(in, in, out, in, out, mdi, muo) is det,
+    in, in, out, in, out, mdi, muo) is det.
+:- mode tree234.foldl3_values(pred(in, in, out, in, out, di, uo) is det,
+    in, in, out, in, out, di, uo) is det.
+:- mode tree234.foldl3_values(pred(in, in, out, in, out, in, out) is semidet,
+    in, in, out, in, out, in, out) is semidet.
+:- mode tree234.foldl3_values(pred(in, in, out, in, out, mdi, muo) is semidet,
+    in, in, out, in, out, mdi, muo) is semidet.
+:- mode tree234.foldl3_values(pred(in, in, out, in, out, di, uo) is semidet,
+    in, in, out, in, out, di, uo) is semidet.
+:- mode tree234.foldl3_values(pred(in, in, out, in, out, in, out) is cc_multi,
+    in, in, out, in, out, in, out) is cc_multi.
+:- mode tree234.foldl3_values(pred(in, in, out, in, out, mdi, muo) is cc_multi,
+    in, in, out, in, out, mdi, muo) is cc_multi.
+:- mode tree234.foldl3_values(pred(in, in, out, in, out, di, uo) is cc_multi,
+    in, in, out, in, out, di, uo) is cc_multi.
+
  :- func tree234.foldr(func(K, V, A) = A, tree234(K, V), A) = A.

  :- pred tree234.foldr(pred(K, V, A, A), tree234(K, V), A, A).
@@ -3831,6 +3872,48 @@ tree234.foldl_values(Pred, four(_K0, V0, _K1, V1, _K2, V2, T0, T1, T2, T3),
      Pred(V2, !A),
      tree234.foldl_values(Pred, T3, !A).

+tree234.foldl2_values(_Pred, empty, !A, !B).
+tree234.foldl2_values(Pred, two(_K, V, T0, T1), !A, !B) :-
+    tree234.foldl2_values(Pred, T0, !A, !B),
+    Pred(V, !A, !B),
+    tree234.foldl2_values(Pred, T1, !A, !B).
+tree234.foldl2_values(Pred, three(_K0, V0, _K1, V1, T0, T1, T2), !A, !B) :-
+    tree234.foldl2_values(Pred, T0, !A, !B),
+    Pred(V0, !A, !B),
+    tree234.foldl2_values(Pred, T1, !A, !B),
+    Pred(V1, !A, !B),
+    tree234.foldl2_values(Pred, T2, !A, !B).
+tree234.foldl2_values(Pred, four(_K0, V0, _K1, V1, _K2, V2, T0, T1, T2, T3),
+        !A, !B) :-
+    tree234.foldl2_values(Pred, T0, !A, !B),
+    Pred(V0, !A, !B),
+    tree234.foldl2_values(Pred, T1, !A, !B),
+    Pred(V1, !A, !B),
+    tree234.foldl2_values(Pred, T2, !A, !B),
+    Pred(V2, !A, !B),
+    tree234.foldl2_values(Pred, T3, !A, !B).
+
+tree234.foldl3_values(_Pred, empty, !A, !B, !C).
+tree234.foldl3_values(Pred, two(_K, V, T0, T1), !A, !B, !C) :-
+    tree234.foldl3_values(Pred, T0, !A, !B, !C),
+    Pred(V, !A, !B, !C),
+    tree234.foldl3_values(Pred, T1, !A, !B, !C).
+tree234.foldl3_values(Pred, three(_K0, V0, _K1, V1, T0, T1, T2), !A, !B, !C) :-
+    tree234.foldl3_values(Pred, T0, !A, !B, !C),
+    Pred(V0, !A, !B, !C),
+    tree234.foldl3_values(Pred, T1, !A, !B, !C),
+    Pred(V1, !A, !B, !C),
+    tree234.foldl3_values(Pred, T2, !A, !B, !C).
+tree234.foldl3_values(Pred, four(_K0, V0, _K1, V1, _K2, V2, T0, T1, T2, T3),
+        !A, !B, !C) :-
+    tree234.foldl3_values(Pred, T0, !A, !B, !C),
+    Pred(V0, !A, !B, !C),
+    tree234.foldl3_values(Pred, T1, !A, !B, !C),
+    Pred(V1, !A, !B, !C),
+    tree234.foldl3_values(Pred, T2, !A, !B, !C),
+    Pred(V2, !A, !B, !C),
+    tree234.foldl3_values(Pred, T3, !A, !B, !C).
+
  %------------------------------------------------------------------------------%

  tree234.foldr(F, T, A) = B :-