[m-rev.] diff: more support for semidet folds with (mostly-)unique accumulators

[Julien Fischer]

Branches: main

Add semidet modes with (mostly-)unique accumulators for many of the fold-style
predicates in the standard library that didn't already have such modes.

library/bimap.m:
library/cord.m:
library/list.m:
library/map.m:
library/tree234.m:
 	As above.

NEWS:
 	Announce the above additions.

Index: NEWS
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/NEWS,v
retrieving revision 1.545
diff -u -r1.545 NEWS
--- NEWS	18 Nov 2010 07:38:59 -0000	1.545
+++ NEWS	22 Nov 2010 04:48:03 -0000
@@ -53,6 +53,17 @@
  * We have added the predicates version_array.foldl2/6, version_array.foldr/4,
    and version_array.foldr2/6 to the standard library.

+* We have added semidet modes with unique and mostly-unique accumulators for
+  the following predicates:
+	bimap.foldl2/6
+	bimap.foldl3/8
+	cord.foldl_pred/4
+  	cord.map_foldl/5
+	list.map_corresponding_foldl2/8
+	list.map_corresponding_foldl3/10
+	list.map_corresponding3_foldl/7
+	map.foldl3/8
+
  Changes to the Mercury compiler:

  * Support for building and linking against frameworks on Mac OS X has
Index: library/bimap.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/bimap.m,v
retrieving revision 1.29
diff -u -r1.29 bimap.m
--- library/bimap.m	31 Jul 2008 06:34:40 -0000	1.29
+++ library/bimap.m	22 Nov 2010 04:48:03 -0000
@@ -264,12 +264,18 @@
  :- pred bimap.foldl2(pred(K, V, A, A, B, B), bimap(K, V), A, A, B, B).
  :- mode bimap.foldl2(pred(in, in, in, out, in, out) is det,
      in, in, out, in, out) is det.
-:- mode bimap.foldl2(pred(in, in, in, out, in, out) is semidet,
-    in, in, out, in, out) is semidet.
+:- mode bimap.foldl2(pred(in, in, in, out, mdi, muo) is det,
+    in, in, out, mdi, muo) is det.
  :- mode bimap.foldl2(pred(in, in, in, out, di, uo) is det,
      in, in, out, di, uo) is det.
  :- mode bimap.foldl2(pred(in, in, di, uo, di, uo) is det,
      in, di, uo, di, uo) is det.
+:- mode bimap.foldl2(pred(in, in, in, out, in, out) is semidet,
+    in, in, out, in, out) is semidet.
+:- mode bimap.foldl2(pred(in, in, in, out, mdi, muo) is semidet,
+    in, in, out, mdi, muo) is semidet.
+:- mode bimap.foldl2(pred(in, in, in, out, di, uo) is semidet,
+    in, in, out, di, uo) is semidet.

      % Perform a traversal of the bimap, applying an accumulator predicate
      % with three accumulators for each key-value pair. (Although no more
@@ -280,14 +286,20 @@
      A, A, B, B, C, C).
  :- mode bimap.foldl3(pred(in, in, in, out, in, out, in, out) is det,
      in, in, out, in, out, in, out) is det.
-:- mode bimap.foldl3(pred(in, in, in, out, in, out, in, out) is semidet,
-    in, in, out, in, out, in, out) is semidet.
+:- mode bimap.foldl3(pred(in, in, in, out, in, out, mdi, muo) is det,
+    in, in, out, in, out, mdi, muo) is det.
  :- mode bimap.foldl3(pred(in, in, in, out, in, out, di, uo) is det,
      in, in, out, in, out, di, uo) is det.
  :- mode bimap.foldl3(pred(in, in, in, out, di, uo, di, uo) is det,
      in, in, out, di, uo, di, uo) is det.
  :- mode bimap.foldl3(pred(in, in, di, uo, di, uo, di, uo) is det,
      in, di, uo, di, uo, di, uo) is det.
+:- mode bimap.foldl3(pred(in, in, in, out, in, out, in, out) is semidet,
+    in, in, out, in, out, in, out) is semidet.
+:- mode bimap.foldl3(pred(in, in, in, out, in, out, mdi, muo) is semidet,
+    in, in, out, in, out, mdi, muo) is semidet.
+:- mode bimap.foldl3(pred(in, in, in, out, in, out, di, uo) is semidet,
+    in, in, out, in, out, di, uo) is semidet.

      % Extract a the forward map from the bimap, the map from key to value.
      %
Index: library/cord.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/cord.m,v
retrieving revision 1.16
diff -u -r1.16 cord.m
--- library/cord.m	20 Aug 2010 02:38:17 -0000	1.16
+++ library/cord.m	22 Nov 2010 04:48:03 -0000
@@ -158,26 +158,52 @@
  :- func foldl(func(T, U) = U, cord(T), U) = U.
  :- pred foldl_pred(pred(T, U, U), cord(T), U, U).
  :- mode foldl_pred(in(pred(in, in, out) is det), in, in, out) is det.
+:- mode foldl_pred(in(pred(in, mdi, muo) is det), in, mdi, muo) is det.
  :- mode foldl_pred(in(pred(in, di, uo) is det), in, di, uo) is det.
+:- mode foldl_pred(in(pred(in, in, out) is semidet), in, in, out) is semidet.
+:- mode foldl_pred(in(pred(in, mdi, muo) is semidet), in, mdi, muo) is semidet.
+:- mode foldl_pred(in(pred(in, di, uo) is semidet), in, di, uo) is semidet.

      % foldr(F, C, A) = list.foldr(F, list(C), A).
      %
  :- func foldr(func(T, U) = U, cord(T), U) = U.
-:- pred foldr_pred(pred(T, U, U)::in(pred(in, in, out) is det), cord(T)::in,
-    U::in, U::out) is det.
+:- pred foldr_pred(pred(T, U, U), cord(T), U, U).
+:- mode foldr_pred(in(pred(in, in, out) is det), in, in, out) is det.
+:- mode foldr_pred(in(pred(in, mdi, muo) is det), in, mdi, muo) is det.
+:- mode foldr_pred(in(pred(in, di, uo) is det), in, di, uo) is det.
+:- mode foldr_pred(in(pred(in, in, out) is semidet), in, in, out) is semidet.
+:- mode foldr_pred(in(pred(in, mdi, muo) is semidet), in, mdi, muo) is semidet.
+:- mode foldr_pred(in(pred(in, di, uo) is semidet), in, di, uo) is semidet.

      % map_foldl(P, CA, CB, !Acc):
      %
      % This predicate calls P on each element of the input cord, working
      % left to right. Each call to P transforms an element of the input cord
      % to the corresponding element of the output cord, and updates the
-    % accumulator(s).
+    % accumulator.
+    %
+:- pred map_foldl(pred(A, B, C, C), cord(A), cord(B), C, C).
+:- mode map_foldl(in(pred(in, out, in, out) is det), in, out, in, out)
+    is det.
+:- mode map_foldl(in(pred(in, out, mdi, muo) is det), in, out, mdi, muo)
+    is det.
+:- mode map_foldl(in(pred(in, out, di, uo) is det), in, out, di, uo)
+    is det.
+:- mode map_foldl(in(pred(in, out, in, out) is semidet), in, out, in, out)
+    is semidet.
+:- mode map_foldl(in(pred(in, out, mdi, muo) is semidet), in, out, mdi, muo)
+    is semidet.
+:- mode map_foldl(in(pred(in, out, di, uo) is semidet), in, out, di, uo)
+    is semidet.
+
+    % As above, but with two accumulators.
      %
-:- pred map_foldl(pred(A, B, C, C)::in(pred(in, out, in, out) is det),
-    cord(A)::in, cord(B)::out, C::in, C::out) is det.
  :- pred map_foldl2(pred(A, B, C, C, D, D)::
      in(pred(in, out, in, out, in, out) is det),
      cord(A)::in, cord(B)::out, C::in, C::out, D::in, D::out) is det.
+
+    % As above, but with three accumulators.
+    %
  :- pred map_foldl3(pred(A, B, C, C, D, D, E, E)::
      in(pred(in, out, in, out, in, out, in, out) is det),
      cord(A)::in, cord(B)::out, C::in, C::out, D::in, D::out, E::in, E::out)
@@ -601,7 +627,14 @@

  :- pred foldl_node_pred(pred(T, U, U), cord_node(T), U, U).
  :- mode foldl_node_pred(in(pred(in, in, out) is det), in, in, out) is det.
+:- mode foldl_node_pred(in(pred(in, mdi, muo) is det), in, mdi, muo) is det.
  :- mode foldl_node_pred(in(pred(in, di, uo) is det), in, di, uo) is det.
+:- mode foldl_node_pred(in(pred(in, in, out) is semidet), in, in, out)
+    is semidet.
+:- mode foldl_node_pred(in(pred(in, mdi, muo) is semidet), in, mdi, muo)
+    is semidet.
+:- mode foldl_node_pred(in(pred(in, di, uo) is semidet), in, di, uo)
+    is semidet.

  foldl_node_pred(P, unit_node(X), !Acc) :-
      P(X, !Acc).
@@ -627,8 +660,16 @@
  foldr_pred(P, nonempty_cord(N), !Acc) :-
      foldr_node_pred(P, N, !Acc).

-:- pred foldr_node_pred(pred(T, U, U)::in(pred(in, in, out) is det),
-    cord_node(T)::in, U::in, U::out) is det.
+:- pred foldr_node_pred(pred(T, U, U), cord_node(T), U, U).
+:- mode foldr_node_pred(in(pred(in, in, out) is det), in, in, out) is det.
+:- mode foldr_node_pred(in(pred(in, mdi, muo) is det), in, mdi, muo) is det.
+:- mode foldr_node_pred(in(pred(in, di, uo) is det), in, di, uo) is det.
+:- mode foldr_node_pred(in(pred(in, in, out) is semidet), in, in, out)
+    is semidet.
+:- mode foldr_node_pred(in(pred(in, mdi, muo) is semidet), in, mdi, muo)
+    is semidet.
+:- mode foldr_node_pred(in(pred(in, di, uo) is semidet), in, di, uo)
+    is semidet.

  foldr_node_pred(P, unit_node(X), !Acc) :-
      P(X, !Acc).
@@ -644,8 +685,19 @@
  map_foldl(P, nonempty_cord(NX), nonempty_cord(NY), !A) :-
      map_foldl_node(P, NX, NY, !A).

-:- pred map_foldl_node(pred(A, B, C, C)::in(pred(in, out, in, out) is det),
-    cord_node(A)::in, cord_node(B)::out, C::in, C::out) is det.
+:- pred map_foldl_node(pred(A, B, C, C), cord_node(A), cord_node(B), C, C).
+:- mode map_foldl_node(in(pred(in, out, in, out) is det), in, out, in, out)
+    is det.
+:- mode map_foldl_node(in(pred(in, out, mdi, muo) is det), in, out, mdi, muo)
+    is det.
+:- mode map_foldl_node(in(pred(in, out, di, uo) is det), in, out, di, uo)
+    is det.
+:- mode map_foldl_node(in(pred(in, out, in, out) is semidet), in, out,
+    in, out) is semidet.
+:- mode map_foldl_node(in(pred(in, out, mdi, muo) is semidet), in, out,
+    mdi, muo) is semidet.
+:- mode map_foldl_node(in(pred(in, out, di, uo) is semidet), in, out,
+    di, uo) is semidet.

  map_foldl_node(P, unit_node(X), unit_node(Y), !A) :-
      P(X, Y, !A).
Index: library/list.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/list.m,v
retrieving revision 1.199
diff -u -r1.199 list.m
--- library/list.m	13 Nov 2010 16:49:26 -0000	1.199
+++ library/list.m	22 Nov 2010 04:48:03 -0000
@@ -685,11 +685,23 @@
  :- pred list.map_corresponding_foldl2(pred(A, B, C, D, D, E, E),
      list(A), list(B), list(C), D, D, E, E).
  :- mode list.map_corresponding_foldl2(
-    pred(in, in, out, in, out, in, out) is det, in, in, out, in, out, in, out)
-    is det.
+    pred(in, in, out, in, out, in, out) is det, in, in, out, in, out,
+    in, out) is det.
  :- mode list.map_corresponding_foldl2(
-    pred(in, in, out, in, out, di, uo) is det, in, in, out, in, out, di, uo)
-    is det.
+    pred(in, in, out, in, out, mdi, muo) is det, in, in, out, in, out,
+    mdi, muo) is det.
+:- mode list.map_corresponding_foldl2(
+    pred(in, in, out, in, out, di, uo) is det, in, in, out, in, out,
+    di, uo) is det.
+:- mode list.map_corresponding_foldl2(
+    pred(in, in, out, in, out, in, out) is semidet, in, in, out, in, out,
+    in, out) is semidet.
+:- mode list.map_corresponding_foldl2(
+    pred(in, in, out, in, out, mdi, muo) is semidet, in, in, out, in, out,
+    mdi, muo) is semidet.
+:- mode list.map_corresponding_foldl2(
+    pred(in, in, out, in, out, di, uo) is semidet, in, in, out, in, out,
+    di, uo) is semidet.

      % Like list.map_corresponding_foldl/6 except that it has three
      % accumulators.
@@ -700,8 +712,20 @@
      pred(in, in, out, in, out, in, out, in, out) is det, in, in, out, in, out,
      in, out, in, out) is det.
  :- mode list.map_corresponding_foldl3(
+    pred(in, in, out, in, out, in, out, mdi, muo) is det, in, in, out, in, out,
+    in, out, mdi, muo) is det.
+:- mode list.map_corresponding_foldl3(
      pred(in, in, out, in, out, in, out, di, uo) is det, in, in, out, in, out,
      in, out, di, uo) is det.
+:- mode list.map_corresponding_foldl3(
+    pred(in, in, out, in, out, in, out, in, out) is semidet, in, in, out,
+    in, out, in, out, in, out) is semidet.
+:- mode list.map_corresponding_foldl3(
+    pred(in, in, out, in, out, in, out, mdi, muo) is semidet, in, in, out,
+    in, out, in, out, mdi, muo) is semidet.
+:- mode list.map_corresponding_foldl3(
+    pred(in, in, out, in, out, in, out, di, uo) is semidet, in, in, out,
+    in, out, in, out, di, uo) is semidet.

      % list.map_corresponding3_foldl/7 is like list.map_corresponding3 except
      % that it has an accumulator threaded through it.
@@ -710,8 +734,19 @@
      list(A), list(B), list(C), list(D), E, E).
  :- mode list.map_corresponding3_foldl(pred(in, in, in, out, in, out) is det,
      in, in, in, out, in, out) is det.
+:- mode list.map_corresponding3_foldl(pred(in, in, in, out, mdi, muo) is det,
+    in, in, in, out, mdi, muo) is det.
  :- mode list.map_corresponding3_foldl(pred(in, in, in, out, di, uo) is det,
      in, in, in, out, di, uo) is det.
+:- mode list.map_corresponding3_foldl(
+    pred(in, in, in, out, in, out) is semidet,
+    in, in, in, out, in, out) is semidet.
+:- mode list.map_corresponding3_foldl(
+    pred(in, in, in, out, mdi, muo) is semidet,
+    in, in, in, out, mdi, muo) is semidet.
+:- mode list.map_corresponding3_foldl(
+    pred(in, in, in, out, di, uo) is semidet,
+    in, in, in, out, di, uo) is semidet.

      % list.foldl(Pred, List, Start, End) calls Pred with each
      % element of List (working left-to-right) and an accumulator
@@ -797,8 +832,8 @@
      in, in, out, in, out, in, out) is det.
  :- mode list.foldl3(pred(in, in, out, in, out, mdi, muo) is det,
      in, in, out, in, out, mdi, muo) is det.
-:- mode list.foldl3(pred(in, in, out, in, out, in, out) is cc_multi,
-    in, in, out, in, out, in, out) is cc_multi.
+:- mode list.foldl3(pred(in, in, out, in, out, di, uo) is det,
+    in, in, out, in, out, di, uo) is det.
  :- mode list.foldl3(pred(in, in, out, in, out, in, out) is semidet,
      in, in, out, in, out, in, out) is semidet.
  :- mode list.foldl3(pred(in, in, out, in, out, mdi, muo) is semidet,
@@ -809,8 +844,8 @@
      in, in, out, in, out, in, out) is nondet.
  :- mode list.foldl3(pred(in, in, out, in, out, mdi, muo) is nondet,
      in, in, out, in, out, mdi, muo) is nondet.
-:- mode list.foldl3(pred(in, in, out, in, out, di, uo) is det,
-    in, in, out, in, out, di, uo) is det.
+:- mode list.foldl3(pred(in, in, out, in, out, in, out) is cc_multi,
+    in, in, out, in, out, in, out) is cc_multi.
  :- mode list.foldl3(pred(in, in, out, in, out, di, uo) is cc_multi,
      in, in, out, in, out, di, uo) is cc_multi.

Index: library/map.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/map.m,v
retrieving revision 1.120
diff -u -r1.120 map.m
--- library/map.m	28 Jul 2010 02:10:09 -0000	1.120
+++ library/map.m	22 Nov 2010 04:48:03 -0000
@@ -349,19 +349,26 @@
  :- pred map.foldl3(pred(K, V, A, A, B, B, C, C), map(K, V), A, A, B, B, C, C).
  :- mode map.foldl3(pred(in, in, in, out, in, out, in, out) is det,
      in, in, out, in, out, in, out) is det.
-:- mode map.foldl3(pred(in, in, in, out, in, out, in, out) is semidet,
-    in, in, out, in, out, in, out) is semidet.
+:- mode map.foldl3(pred(in, in, in, out, in, out, mdi, muo) is det,
+    in, in, out, in, out, mdi, muo) is det.
  :- mode map.foldl3(pred(in, in, in, out, in, out, di, uo) is det,
      in, in, out, in, out, di, uo) is det.
  :- mode map.foldl3(pred(in, in, in, out, di, uo, di, uo) is det,
      in, in, out, di, uo, di, uo) is det.
  :- mode map.foldl3(pred(in, in, di, uo, di, uo, di, uo) is det,
      in, di, uo, di, uo, di, uo) is det.
+:- mode map.foldl3(pred(in, in, in, out, in, out, in, out) is semidet,
+    in, in, out, in, out, in, out) is semidet.
+:- mode map.foldl3(pred(in, in, in, out, in, out, mdi, muo) is semidet,
+    in, in, out, in, out, mdi, muo) is semidet.
+:- mode map.foldl3(pred(in, in, in, out, in, out, di, uo) is semidet,
+    in, in, out, in, out, di, uo) is semidet.

      % Perform an inorder traversal of the map, applying an accumulator
      % predicate with four accumulators for each key-value pair.
      % (Although no more expressive than map.foldl, this is often
      % a more convenient format, and a little more efficient).
+    %
  :- pred map.foldl4(pred(K, V, A, A, B, B, C, C, D, D), map(K, V),
      A, A, B, B, C, C, D, D).
  :- mode map.foldl4(pred(in, in, in, out, in, out, in, out, in, out) is det,
Index: library/tree234.m
===================================================================
RCS file: /home/mercury/mercury1/repository/mercury/library/tree234.m,v
retrieving revision 1.69
diff -u -r1.69 tree234.m
--- library/tree234.m	28 Jul 2010 02:10:09 -0000	1.69
+++ library/tree234.m	22 Nov 2010 04:48:03 -0000
@@ -171,14 +171,20 @@
  	A, A, B, B, C, C).
  :- mode tree234.foldl3(pred(in, in, in, out, in, out, in, out) is det,
      in, in, out, in, out, in, out) is det.
-:- mode tree234.foldl3(pred(in, in, in, out, in, out, in, out) is semidet,
-    in, in, out, in, out, in, out) is semidet.
+:- mode tree234.foldl3(pred(in, in, in, out, in, out, mdi, muo) is det,
+    in, in, out, in, out, mdi, muo) is det.
  :- mode tree234.foldl3(pred(in, in, in, out, in, out, di, uo) is det,
      in, in, out, in, out, di, uo) is det.
  :- mode tree234.foldl3(pred(in, in, in, out, di, uo, di, uo) is det,
      in, in, out, di, uo, di, uo) is det.
  :- mode tree234.foldl3(pred(in, in, di, uo, di, uo, di, uo) is det,
      in, di, uo, di, uo, di, uo) is det.
+:- mode tree234.foldl3(pred(in, in, in, out, in, out, in, out) is semidet,
+    in, in, out, in, out, in, out) is semidet.
+:- mode tree234.foldl3(pred(in, in, in, out, in, out, mdi, muo) is semidet,
+    in, in, out, in, out, mdi, muo) is semidet.
+:- mode tree234.foldl3(pred(in, in, in, out, in, out, di, uo) is semidet,
+    in, in, out, in, out, di, uo) is semidet.

  :- pred tree234.foldl4(pred(K, V, A, A, B, B, C, C, D, D), tree234(K, V),
  	A, A, B, B, C, C, D, D).

--------------------------------------------------------------------------
mercury-reviews mailing list
Post messages to:       mercury-reviews at csse.unimelb.edu.au
Administrative Queries: owner-mercury-reviews at csse.unimelb.edu.au
Subscriptions:          mercury-reviews-request at csse.unimelb.edu.au
--------------------------------------------------------------------------