[m-rev.] For post-commit review: add more library predicates

[Julien Fischer]

Add some more library predicates.

library/hash_table.m:
     Add fold2/6 and fold3/8.

library/rbtree.m:
     Add foldl2_values/6.

library/assoc_list.m:
     Add the predicate svremove/4, which is like remove/4 but with the
     arguments in an order more conducive to the use of state variable
     notation.  Eventually, we should deprecate the current remove/4
     and re-order its arguments so they match those of the identically
     named predicates for other types that implement the map ADT.

     Do not module qualify clause heads.

NEWS:
      Announce the above.

Julien.

diff --git a/NEWS b/NEWS
index 48df372..ab3b0ea 100644
--- a/NEWS
+++ b/NEWS
@@ -362,9 +362,19 @@ Changes to the Mercury standard library:
     - mktime/1
     - ctime/1

-* The following predicate has been added to the rbtree module:
+* The following predicates have been added to the rbtree module:

     - foldl_values/4
+   - foldl2_values/6
+
+* The following predicates have been added to the hash_table module:
+
+   - fold2/6
+   - fold3/8
+
+* We have added the predicate svremove/4 to the assoc_list module.
+  This like the remove/4 predicate but with its arguments are in
+  an order more conducive to the use of state variable notation.

  Changes to the Mercury compiler:

diff --git a/library/assoc_list.m b/library/assoc_list.m
index 60458d0..008e3e2 100644
--- a/library/assoc_list.m
+++ b/library/assoc_list.m
@@ -76,6 +76,12 @@
  :- pred remove(assoc_list(K, V)::in, K::in, V::out, assoc_list(K, V)::out)
      is semidet.

+    % As above, but with an argument ordering that is more conducive to
+    % the use of state variable notation.
+    %
+:- pred svremove(K::in, V::out, assoc_list(K, V)::in, assoc_list(K, V)::out)
+    is semidet.
+
  :- func map_keys_only(func(K) = L, assoc_list(K, V)) = assoc_list(L, V).
  :- pred map_keys_only(pred(K, L), assoc_list(K, V), assoc_list(L, V)).
  :- mode map_keys_only(pred(in, out) is det, in, out) is det.
@@ -212,17 +218,17 @@

  %---------------------------------------------------------------------------%

-assoc_list.reverse_members(AL1) = AL2 :-
+reverse_members(AL1) = AL2 :-
      assoc_list.reverse_members(AL1, AL2).

-assoc_list.reverse_members([], []).
-assoc_list.reverse_members([K - V | KVs], [V - K | VKs]) :-
+reverse_members([], []).
+reverse_members([K - V | KVs], [V - K | VKs]) :-
      assoc_list.reverse_members(KVs, VKs).

-assoc_list.from_corresponding_lists(Ks, Vs) = AL :-
+from_corresponding_lists(Ks, Vs) = AL :-
      assoc_list.from_corresponding_lists(Ks, Vs, AL).

-assoc_list.from_corresponding_lists(Ks, Vs, KVs) :-
+from_corresponding_lists(Ks, Vs, KVs) :-
      ( if assoc_list.from_corresponding_2(Ks, Vs, KVsPrime) then
          KVs = KVsPrime
      else
@@ -244,29 +250,29 @@ assoc_list.from_corresponding_lists(Ks, Vs, KVs) :-
  :- pred assoc_list.from_corresponding_2(list(K)::in, list(V)::in,
      assoc_list(K,V)::out) is semidet.

-assoc_list.from_corresponding_2([], [], []).
-assoc_list.from_corresponding_2([A | As], [B | Bs], [A - B | ABs]) :-
+from_corresponding_2([], [], []).
+from_corresponding_2([A | As], [B | Bs], [A - B | ABs]) :-
      assoc_list.from_corresponding_2(As, Bs, ABs).

-assoc_list.keys(AL) = Ks :-
+keys(AL) = Ks :-
      assoc_list.keys(AL, Ks).

-assoc_list.keys([], []).
-assoc_list.keys([K - _ | KVs], [K | Ks]) :-
+keys([], []).
+keys([K - _ | KVs], [K | Ks]) :-
      assoc_list.keys(KVs, Ks).

-assoc_list.values(AL) = Vs :-
+values(AL) = Vs :-
      assoc_list.values(AL, Vs).

-assoc_list.values([], []).
-assoc_list.values([_ - V | KVs], [V | Vs]) :-
+values([], []).
+values([_ - V | KVs], [V | Vs]) :-
      assoc_list.values(KVs, Vs).

-assoc_list.keys_and_values([], [], []).
-assoc_list.keys_and_values([K - V | KVs], [K | Ks], [V | Vs]) :-
+keys_and_values([], [], []).
+keys_and_values([K - V | KVs], [K | Ks], [V | Vs]) :-
      assoc_list.keys_and_values(KVs, Ks, Vs).

-assoc_list.search([K - V | KVs], Key, Value) :-
+search([K - V | KVs], Key, Value) :-
      ( if K = Key then
          Value = V
      else
@@ -283,7 +289,7 @@ AL ^ det_elem(K) = V :-
          report_lookup_error("assoc_list.det_elem: key not found", K)
      ).

-assoc_list.remove([K - V | KVs], Key, Value, Filtered) :-
+remove([K - V | KVs], Key, Value, Filtered) :-
      ( if K = Key then
          Value = V,
          Filtered = KVs
@@ -292,38 +298,41 @@ assoc_list.remove([K - V | KVs], Key, Value, Filtered) :-
          Filtered = [K - V | FilteredTail]
      ).

-assoc_list.map_keys_only(_P, [], []).
-assoc_list.map_keys_only(P, [K0 - V | KVs0], [K - V | KVs]) :-
+svremove(Key, Value, !AL) :-
+    assoc_list.remove(!.AL, Key, Value, !:AL).
+
+map_keys_only(_P, [], []).
+map_keys_only(P, [K0 - V | KVs0], [K - V | KVs]) :-
      P(K0, K),
      assoc_list.map_keys_only(P, KVs0, KVs).

-assoc_list.map_keys_only(_F, []) = [].
-assoc_list.map_keys_only(F, [K0 - V | KVs0]) = [K - V | KVs] :-
+map_keys_only(_F, []) = [].
+map_keys_only(F, [K0 - V | KVs0]) = [K - V | KVs] :-
      K = F(K0),
      KVs = assoc_list.map_keys_only(F, KVs0).

-assoc_list.map_values_only(_P, [], []).
-assoc_list.map_values_only(P, [K - V0 | KVs0], [K - V | KVs]) :-
+map_values_only(_P, [], []).
+map_values_only(P, [K - V0 | KVs0], [K - V | KVs]) :-
      P(V0, V),
      assoc_list.map_values_only(P, KVs0, KVs).

-assoc_list.map_values_only(_F, []) = [].
-assoc_list.map_values_only(F, [K - V0 | KVs0]) = [K - V | KVs] :-
+map_values_only(_F, []) = [].
+map_values_only(F, [K - V0 | KVs0]) = [K - V | KVs] :-
      V = F(V0),
      KVs = assoc_list.map_values_only(F, KVs0).

-assoc_list.map_values(_P, [], []).
-assoc_list.map_values(P, [K - V0 | KVs0], [K - V | KVs]) :-
+map_values(_P, [], []).
+map_values(P, [K - V0 | KVs0], [K - V | KVs]) :-
      P(K, V0, V),
      assoc_list.map_values(P, KVs0, KVs).

-assoc_list.map_values(_F, []) = [].
-assoc_list.map_values(F, [K - V0 | KVs0]) = [K - V | KVs] :-
+map_values(_F, []) = [].
+map_values(F, [K - V0 | KVs0]) = [K - V | KVs] :-
      V = F(K, V0),
      KVs = assoc_list.map_values(F, KVs0).

-assoc_list.filter(_, [],  []).
-assoc_list.filter(P, [HK - HV | T], True) :-
+filter(_, [],  []).
+filter(P, [HK - HV | T], True) :-
      ( if P(HK) then
          assoc_list.filter(P, T, TrueTail),
          True = [HK - HV | TrueTail]
@@ -331,11 +340,11 @@ assoc_list.filter(P, [HK - HV | T], True) :-
          assoc_list.filter(P, T, True)
      ).

-assoc_list.filter(P, List) = Trues :-
+filter(P, List) = Trues :-
      assoc_list.filter(P, List, Trues).

-assoc_list.negated_filter(_, [],  []).
-assoc_list.negated_filter(P, [HK - HV | T], False) :-
+negated_filter(_, [],  []).
+negated_filter(P, [HK - HV | T], False) :-
      ( if P(HK) then
          assoc_list.negated_filter(P, T, False)
      else
@@ -343,11 +352,11 @@ assoc_list.negated_filter(P, [HK - HV | T], False) :-
          False = [HK - HV | FalseTail]
      ).

-assoc_list.negated_filter(P, List) = Falses :-
+negated_filter(P, List) = Falses :-
      assoc_list.negated_filter(P, List, Falses).

-assoc_list.filter(_, [],  [], []).
-assoc_list.filter(P, [HK - HV | T], True, False) :-
+filter(_, [],  [], []).
+filter(P, [HK - HV | T], True, False) :-
      ( if P(HK) then
          assoc_list.filter(P, T, TrueTail, False),
          True = [HK - HV | TrueTail]
@@ -356,13 +365,13 @@ assoc_list.filter(P, [HK - HV | T], True, False) :-
          False = [HK - HV | FalseTail]
      ).

-assoc_list.merge(As, Bs) = ABs :-
+merge(As, Bs) = ABs :-
      assoc_list.merge(As, Bs, ABs).

-assoc_list.merge([], [], []).
-assoc_list.merge([A | As], [], [A | As]).
-assoc_list.merge([], [B | Bs], [B | Bs]).
-assoc_list.merge([A | As], [B | Bs], Cs) :-
+merge([], [], []).
+merge([A | As], [], [A | As]).
+merge([], [B | Bs], [B | Bs]).
+merge([A | As], [B | Bs], Cs) :-
      ( if
          A = AK - _AV,
          B = BK - _BV,
@@ -376,26 +385,26 @@ assoc_list.merge([A | As], [B | Bs], Cs) :-
          Cs = [A | Cs0]
      ).

-assoc_list.foldl_keys(_, [], !Acc).
-assoc_list.foldl_keys(P, [KV | KVs], !Acc) :-
+foldl_keys(_, [], !Acc).
+foldl_keys(P, [KV | KVs], !Acc) :-
      KV = K - _V,
      P(K, !Acc),
      assoc_list.foldl_keys(P, KVs, !Acc).

-assoc_list.foldl_values(_, [], !Acc).
-assoc_list.foldl_values(P, [KV | KVs], !Acc) :-
+foldl_values(_, [], !Acc).
+foldl_values(P, [KV | KVs], !Acc) :-
      KV = _K - V,
      P(V, !Acc),
      assoc_list.foldl_values(P, KVs, !Acc).

-assoc_list.foldl2_values(_, [], !Acc1, !Acc2).
-assoc_list.foldl2_values(P, [KV | KVs], !Acc1, !Acc2) :-
+foldl2_values(_, [], !Acc1, !Acc2).
+foldl2_values(P, [KV | KVs], !Acc1, !Acc2) :-
      KV = _K - V,
      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) :-
+foldl3_values(_, [], !Acc1, !Acc2, !Acc3).
+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).
diff --git a/library/hash_table.m b/library/hash_table.m
index 1e8e5c0..1791d9a 100644
--- a/library/hash_table.m
+++ b/library/hash_table.m
@@ -215,7 +215,7 @@

      % Fold a predicate over the key-value bindings in a hash table.
      %
-:- pred fold(pred(K, V, T, T), hash_table(K, V), T, T).
+:- pred fold(pred(K, V, A, A), hash_table(K, V), A, A).
  :- mode fold(in(pred(in, in, in, out) is det), hash_table_ui,
      in, out) is det.
  :- mode fold(in(pred(in, in, mdi, muo) is det), hash_table_ui,
@@ -229,6 +229,35 @@
  :- mode fold(in(pred(in, in, di, uo) is semidet), hash_table_ui,
      di, uo) is semidet.

+:- pred fold2(pred(K, V, A, A, B, B), hash_table(K, V), A, A, B, B).
+:- mode fold2(in(pred(in, in, in, out, in, out) is det), hash_table_ui,
+    in, out, in, out) is det.
+:- mode fold2(in(pred(in, in, in, out, mdi, muo) is det), hash_table_ui,
+    in, out, mdi, muo) is det.
+:- mode fold2(in(pred(in, in, in, out, di, uo) is det), hash_table_ui,
+    in, out, di, uo) is det.
+:- mode fold2(in(pred(in, in, in, out, in, out) is semidet), hash_table_ui,
+    in, out, in, out) is semidet.
+:- mode fold2(in(pred(in, in, in, out, mdi, muo) is semidet), hash_table_ui,
+    in, out, mdi, muo) is semidet.
+:- mode fold2(in(pred(in, in, in, out, di, uo) is semidet), hash_table_ui,
+    in, out, di, uo) is semidet.
+
+:- pred fold3(pred(K, V, A, A, B, B, C, C), hash_table(K, V), A, A, B, B,
+    C, C).
+:- mode fold3(in(pred(in, in, in, out, in, out, in, out) is det),
+    hash_table_ui, in, out, in, out, in, out) is det.
+:- mode fold3(in(pred(in, in, in, out, in, out, mdi, muo) is det),
+    hash_table_ui, in, out, in, out, mdi, muo) is det.
+:- mode fold3(in(pred(in, in, in, out, in, out, di, uo) is det),
+    hash_table_ui, in, out, in, out, di, uo) is det.
+:- mode fold3(in(pred(in, in, in, out, in, out, in, out) is semidet),
+    hash_table_ui, in, out, in, out, in, out) is semidet.
+:- mode fold3(in(pred(in, in, in, out, in, out, mdi, muo) is semidet),
+    hash_table_ui, in, out, in, out, mdi, muo) is semidet.
+:- mode fold3(in(pred(in, in, in, out, in, out, di, uo) is semidet),
+    hash_table_ui, in, out, in, out, di, uo) is semidet.
+
  %---------------------------------------------------------------------------%
  %---------------------------------------------------------------------------%

@@ -758,7 +787,7 @@ fold_f(F, List, A0, A) :-
  fold(P, HT, !A) :-
      foldl(fold_p(P), HT ^ buckets, !A).

-:- pred fold_p(pred(K, V, T, T), hash_table_alist(K, V), T, T).
+:- pred fold_p(pred(K, V, A, A), hash_table_alist(K, V), A, A).
  :- mode fold_p(pred(in, in, in, out) is det, in, in, out) is det.
  :- mode fold_p(pred(in, in, mdi, muo) is det, in, mdi, muo) is det.
  :- mode fold_p(pred(in, in, di, uo) is det, in, di, uo) is det.
@@ -779,5 +808,68 @@ fold_p(P, List, !A) :-
      ).

  %---------------------------------------------------------------------------%
+
+fold2(P, HT, !A, !B) :-
+    foldl2(fold2_p(P), HT ^ buckets, !A, !B).
+
+:- pred fold2_p(pred(K, V, A, A, B, B), hash_table_alist(K, V), A, A, B, B).
+:- mode fold2_p(pred(in, in, in, out, in, out) is det, in, in, out,
+    in, out) is det.
+:- mode fold2_p(pred(in, in, in, out, mdi, muo) is det, in, in, out,
+    mdi, muo) is det.
+:- mode fold2_p(pred(in, in, in, out, di, uo) is det, in, in, out,
+    di, uo) is det.
+:- mode fold2_p(pred(in, in, in, out, in, out) is semidet, in, in, out,
+    in, out) is semidet.
+:- mode fold2_p(pred(in, in, in, out, mdi, muo) is semidet, in,in, out,
+    mdi, muo) is semidet.
+:- mode fold2_p(pred(in, in, in, out, di, uo) is semidet, in, in, out,
+    di, uo) is semidet.
+
+fold2_p(P, List, !A, !B) :-
+    (
+        List = ht_nil
+    ;
+        List = ht_single(K, V),
+        P(K, V, !A, !B)
+    ;
+        List = ht_cons(K, V, KVs),
+        P(K, V, !A, !B),
+        fold2_p(P, KVs, !A, !B)
+    ).
+
+%---------------------------------------------------------------------------%
+
+fold3(P, HT, !A, !B, !C) :-
+    foldl3(fold3_p(P), HT ^ buckets, !A, !B, !C).
+
+:- pred fold3_p(pred(K, V, A, A, B, B, C, C), hash_table_alist(K, V),
+    A, A, B, B, C, C).
+:- mode fold3_p(pred(in, in, in, out, in, out, in, out) is det, in,
+    in, out, in, out, in, out) is det.
+:- mode fold3_p(pred(in, in, in, out, in, out, mdi, muo) is det, in,
+    in, out, in, out, mdi, muo) is det.
+:- mode fold3_p(pred(in, in, in, out, in, out, di, uo) is det, in,
+    in, out, in, out, di, uo) is det.
+:- mode fold3_p(pred(in, in, in, out, in, out, in, out) is semidet, in,
+    in, out, in, out, in, out) is semidet.
+:- mode fold3_p(pred(in, in, in, out, in, out, mdi, muo) is semidet, in,
+    in, out, in, out, mdi, muo) is semidet.
+:- mode fold3_p(pred(in, in, in, out, in, out, di, uo) is semidet, in,
+    in, out, in, out, di, uo) is semidet.
+
+fold3_p(P, List, !A, !B, !C) :-
+    (
+        List = ht_nil
+    ;
+        List = ht_single(K, V),
+        P(K, V, !A, !B, !C)
+    ;
+        List = ht_cons(K, V, KVs),
+        P(K, V, !A, !B, !C),
+        fold3_p(P, KVs, !A, !B, !C)
+    ).
+
+%---------------------------------------------------------------------------%
  :- end_module hash_table.
  %---------------------------------------------------------------------------%
diff --git a/library/rbtree.m b/library/rbtree.m
index bfc9bc5..eb2b554 100644
--- a/library/rbtree.m
+++ b/library/rbtree.m
@@ -230,6 +230,20 @@
  :- mode foldl_values(pred(in, mdi, muo) is semidet, in, mdi, muo) is semidet.
  :- mode foldl_values(pred(in, di, uo) is semidet, in, di, uo) is semidet.

+:- pred foldl2_values(pred(V, A, A, B, B), rbtree(K, V), A, A, B, B).
+:- mode foldl2_values(pred(in, in, out, in, out) is det, in, in, out,
+    in, out) is det.
+:- mode foldl2_values(pred(in, in, out, mdi, muo) is det, in, in, out,
+    mdi, muo) is det.
+:- mode foldl2_values(pred(in, in, out, di, uo) is det, in, in, out,
+    di, uo) is det.
+:- mode foldl2_values(pred(in, in, out, in, out) is semidet, in, in, out,
+    in, out) is semidet.
+:- mode foldl2_values(pred(in, in, out, mdi, muo) is semidet, in, in, out,
+    mdi, muo) is semidet.
+:- mode foldl2_values(pred(in, in, out, di, uo) is semidet, in, in, out,
+    di, uo) is semidet.
+
  :- func map_values(func(K, V) = W, rbtree(K, V)) = rbtree(K, W).
  :- pred map_values(pred(K, V, W), rbtree(K, V), rbtree(K, W)).
  :- mode map_values(pred(in, in, out) is det, in, out) is det.
@@ -1113,6 +1127,18 @@ foldl_values(Pred, black(_K, V, Left, Right), !Acc) :-

  %---------------------------------------------------------------------------%

+foldl2_values(_Pred, empty, !Acc1, !Acc2).
+foldl2_values(Pred, red(_K, V, Left, Right), !Acc1, !Acc2) :-
+    rbtree.foldl2_values(Pred, Left, !Acc1, !Acc2),
+    Pred(V, !Acc1, !Acc2),
+    rbtree.foldl2_values(Pred, Right, !Acc1, !Acc2).
+foldl2_values(Pred, black(_K, V, Left, Right), !Acc1, !Acc2) :-
+    rbtree.foldl2_values(Pred, Left, !Acc1, !Acc2),
+    Pred(V, !Acc1, !Acc2),
+    rbtree.foldl2_values(Pred, Right, !Acc1, !Acc2).
+
+%---------------------------------------------------------------------------%
+
  map_values(F, T1) = T2 :-
      P = ( pred(X::in, Y::in, Z::out) is det :- Z = F(X, Y) ),
      rbtree.map_values(P, T1, T2).