[m-rev.] for review: add predicate versions of int.fold_up/down

[Julien Fischer]

On Sat, 27 Mar 2004, Ralph Becket wrote:

> Julien Fischer, Friday, 26 March 2004:
> >
> > Estimated hours taken: 1
> > Branches: main
> >
> > Add predicate versions of int.fold_up and int.fold_down.
> >
> > XXX We should probably consider swapping the order of
> > the arguments in the function versions so they correspond
> > to the predicate versions more closely.
> >
> > library/int.m:
> > 	Add the predicates int.fold_up/5 and int.fold_down/5.
>
> While you're at it, could you also add int.fold_up2/7 and
> int.fold_down2/7 (the fold2 variants are useful enough to warrant
> inclusion in the library):
>
Done.

> > Index: library/int.m
> > ===================================================================
> > RCS file: /home/mercury1/repository/mercury/library/int.m,v
> > retrieving revision 1.98
> > diff -u -r1.98 int.m
> > --- library/int.m	2 Feb 2004 03:53:07 -0000	1.98
> > +++ library/int.m	26 Mar 2004 00:34:35 -0000
> > @@ -233,15 +233,31 @@
> >  :- func int__bits_per_int = int.
> >  :- pred int__bits_per_int(int::out) is det.
> >
> > +	% fold_up(F, Low, High, !Acc) <=> list.foldl(F, Low `..` High, !Acc)
> > +	%
> > +	% NOTE: fold_up/5 is undefined if High = int.max_int.
> > +	%
> > +:- pred int__fold_up(pred(int, T, T), int, int, T, T).
> > +:- mode int__fold_up(pred(in, in, out) is det, in, in, in, out) is det.
> > +:- mode int__fold_up(pred(in, di, uo) is det, in, in, di, uo) is det.
>
> The list.fold[lr] predicates have more comprehensive mode coverage:
>
> :- pred list__foldl(pred(X, Y, Y), list(X), Y, Y).
> :- mode list__foldl(pred(in, di, uo) is det, in, di, uo) is det.
> :- mode list__foldl(pred(in, in, out) is det, in, in, out) is det.
> :- mode list__foldl(pred(in, in, out) is semidet, in, in, out) is semidet.
> :- mode list__foldl(pred(in, in, out) is nondet, in, in, out) is nondet.
> :- mode list__foldl(pred(in, di, uo) is cc_multi, in, di, uo) is cc_multi.
> :- mode list__foldl(pred(in, in, out) is cc_multi, in, in, out) is cc_multi.
>
> It's probably a good idea to do the same thing here.
>
I've added some more modes based on those for foldl.


> > @@ -674,10 +690,22 @@
> >
> >  %-----------------------------------------------------------------------------%
> >
> > +int__fold_up(F, Lo, Hi, !A) :-
> > +	( if	Lo =< Hi
> > +	  then	F(Lo, !A), int__fold_up(F, Lo + 1, Hi, !A)
> > +	  else	true
> > +	).
> > +
>
> I would have used `P' rather than `F' for the closure name.
>
Good point.  I've changed it to `P'.

I've also swapped the argument order of the function versions
and augmented the test case somewhat.

Revised diff follows:

Estimated hours taken: 2
Branches: main

Add the predicates int.fold_up, int.fold_down, int.fold_up2
and int.fold_down/2.

Swap the order of the arguments of the functions int.fold_up
and int.fold_down.

library/int.m:
	Add the predicates int.fold_up/5, int.fold_down/5,
	int.fold_up2/7 and int.fold_down2/7.
	Swap the order of the arguments if int.fold_up/4 and
	int.fold_down/4.

tests/hard_coded/int_fold_up_down.m:
tests/hard_coded/int_fold_up_down.exp:
	Test the new predicates.

NEWS:
	Mention the new predicates.


Index: NEWS
===================================================================
RCS file: /home/mercury1/repository/mercury/NEWS,v
retrieving revision 1.330
diff -u -r1.330 NEWS
--- NEWS	19 Mar 2004 14:33:36 -0000	1.330
+++ NEWS	27 Mar 2004 12:08:29 -0000
@@ -91,8 +91,10 @@

 Changes to the Mercury standard library:

-* We've added two new functions, fold_up/4 and fold_down/4, to int.m.
-  These functions support iteration over contiguous integer ranges.
+* We've add some new predicates and functions to int.m.
+  int.fold_up/4, int.fold_down/4, int.fold_up/5, int.fold_down/5,
+  int.fold_up2/7 and int.fold_down2/7 support iteration over
+  contiguous integer ranges.

 * We've added a new library module, `array2d', for two-dimensional arrays.

Index: library/int.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/int.m,v
retrieving revision 1.98
diff -u -r1.98 int.m
--- library/int.m	2 Feb 2004 03:53:07 -0000	1.98
+++ library/int.m	29 Mar 2004 04:10:10 -0000
@@ -233,17 +233,83 @@
 :- func int__bits_per_int = int.
 :- pred int__bits_per_int(int::out) is det.

-	% fold_up(F, Acc, Low, High) = list.foldl(F, Low `..` High, Acc)
+	% fold_up(F, Low, High, !Acc) <=> list.foldl(F, Low `..` High, !Acc)
 	%
-	% NOTE: fold_up/4 is undefined if High = int__max_int.
+	% NOTE: fold_up/5 is undefined if High = int.max_int.
 	%
-:- func int__fold_up(func(int, T) = T, T, int, int) = T.
+:- pred int__fold_up(pred(int, T, T), int, int, T, T).
+:- mode int__fold_up(pred(in, in, out) is det, in, in, in, out) is det.
+:- mode int__fold_up(pred(in, di, uo) is det, in, in, di, uo) is det.
+:- mode int__fold_up(pred(in, in, out) is semidet, in, in, in, out)
+	is semidet.
+:- mode int__fold_up(pred(in, in, out) is nondet, in, in, in, out)
+	is nondet.
+:- mode int__fold_up(pred(in, di, uo) is cc_multi, in, in, di, uo)
+	is cc_multi.
+:- mode int__fold_up(pred(in, in, out) is cc_multi, in, in, in, out)
+	is cc_multi.

-	% fold_down(F, Acc, Low, High) = list.foldr(F, Low `..` High, Acc)
+	% fold_up(F, Low, High, Acc) <=> list.foldl(F, Low `..` High, Acc)
 	%
-	% NOTE: fold_down/4 is undefined if Low = int__min_int.
+	% NOTE: fold_up/4 is undefined if High = int.max_int.
 	%
-:- func int__fold_down(func(int, T) = T, T, int, int) = T.
+:- func int__fold_up(func(int, T) = T, int, int, T) = T.
+
+	% fold_down(F, Low, High, !Acc) <=> list.foldr(F, Low `..` High, !Acc)
+	%
+	% NOTE: fold_down/5 is undefined if Low int.min_int.
+	%
+:- pred int__fold_down(pred(int, T, T), int, int, T, T).
+:- mode int__fold_down(pred(in, in, out) is det, in, in, in, out) is det.
+:- mode int__fold_down(pred(in, di, uo) is det, in, in, di, uo) is det.
+:- mode int__fold_down(pred(in, in, out) is semidet, in, in, in, out)
+	is semidet.
+:- mode int__fold_down(pred(in, in, out) is nondet, in, in, in, out)
+	is nondet.
+:- mode int__fold_down(pred(in, di, uo) is cc_multi, in, in, di, uo)
+	is cc_multi.
+:- mode int__fold_down(pred(in, in, out) is cc_multi, in, in, in, out)
+	is cc_multi.
+
+	% fold_down(F, Low, High, Acc) <=> list.foldr(F, Low `..` High, Acc)
+	%
+	% NOTE: fold_down/4 is undefined if Low = int.min_int.
+	%
+:- func int__fold_down(func(int, T) = T, int, int, T) = T.
+
+	% fold_up2(F, Low, High, !Acc1, Acc2) <=>
+	% 	list.foldl2(F, Low `..` High, !Acc1, !Acc2)
+	%
+	% NOTE: fold_up2/7 is undefined if High = int.max_int.
+	%
+:- pred int__fold_up2(pred(int, T, T, U, U), int, int, T, T, U, U).
+:- mode int__fold_up2(pred(in, in, out, in, out) is det, in, in, in, out,
+	in, out) is det.
+:- mode int__fold_up2(pred(in, in, out, in, out) is semidet, in, in,
+	in, out, in, out) is semidet.
+:- mode int__fold_up2(pred(in, in, out, in, out) is nondet, in, in,
+	in, out, in, out) is nondet.
+:- mode int__fold_up2(pred(in, in, out, di, uo) is det, in, in, in, out,
+	di, uo) is det.
+:- mode int__fold_up2(pred(in, di, uo, di, uo) is det, in, in, di, uo,
+	di, uo) is det.
+
+	% fold_down2(F, Low, High, !Acc1, !Acc2) <=>
+	% 	list.foldr2(F, Low `..` High, !Acc1, Acc2).
+	%
+	% NOTE: fold_down2/7 is undefined if Low = int.min_int.
+	%
+:- pred int__fold_down2(pred(int, T, T, U, U), int, int, T, T, U, U).
+:- mode int__fold_down2(pred(in, in, out, in, out) is det, in, in, in, out,
+	in, out) is det.
+:- mode int__fold_down2(pred(in, in, out, in, out) is semidet, in, in,
+	in, out, in, out) is semidet.
+:- mode int__fold_down2(pred(in, in, out, in, out) is nondet, in, in,
+	in, out, in, out) is nondet.
+:- mode int__fold_down2(pred(in, in, out, di, uo) is det, in, in, in, out,
+	di, uo) is det.
+:- mode int__fold_down2(pred(in, di, uo, di, uo) is det, in, in, di, uo,
+	di, uo) is det.

 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
@@ -674,13 +740,37 @@

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

-int__fold_up(F, A, Lo, Hi) =
-	( if Lo =< Hi then int__fold_up(F, F(Lo, A), Lo + 1, Hi) else A ).
+int__fold_up(P, Lo, Hi, !A) :-
+	( if	Lo =< Hi
+	  then	P(Lo, !A), int__fold_up(P, Lo + 1, Hi, !A)
+	  else	true
+	).
+
+int__fold_up(F, Lo, Hi, A) =
+	( if Lo =< Hi then int__fold_up(F, Lo + 1, Hi, F(Lo, A)) else A ).
+
+int__fold_up2(P, Lo, Hi, !A, !B) :-
+	( if	Lo =< Hi
+	  then	P(Lo, !A, !B), int__fold_up2(P, Lo + 1, Hi, !A, !B)
+	  else	true
+	).

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

-int__fold_down(F, A, Lo, Hi) =
-	( if Lo =< Hi then int__fold_down(F, F(Hi, A), Lo, Hi - 1) else A ).
+int__fold_down(P, Lo, Hi, !A) :-
+	( if 	Lo =< Hi
+	  then	P(Hi, !A), int__fold_down(P, Lo, Hi - 1, !A)
+	  else	true
+	).
+
+int__fold_down(F, Lo, Hi, A) =
+	( if Lo =< Hi then int__fold_down(F, Lo, Hi - 1, F(Hi, A)) else A ).
+
+int__fold_down2(P, Lo, Hi, !A, !B) :-
+	( if	Lo =< Hi
+	  then	P(Hi, !A, !B), int__fold_down2(P, Lo, Hi - 1, !A, !B)
+	  else	true
+	).

 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
Index: tests/hard_coded/int_fold_up_down.exp
===================================================================
RCS file: /home/mercury1/repository/tests/hard_coded/int_fold_up_down.exp,v
retrieving revision 1.1
diff -u -r1.1 int_fold_up_down.exp
--- tests/hard_coded/int_fold_up_down.exp	27 Jan 2004 03:26:38 -0000	1.1
+++ tests/hard_coded/int_fold_up_down.exp	29 Mar 2004 05:16:16 -0000
@@ -1,2 +1,45 @@
 (5(4(3(2(1)))))
 (1(2(3(4(5)))))
+(5(4(3(2(1)))))
+(1(2(3(4(5)))))
+(5(4(3(2(1)))))(5(4(3(2(1)))))
+(1(2(3(4(5)))))(1(2(3(4(5)))))
+12345
+54321
+(5-1(4-1(3-1(2-1(1-1)))))
+(5-1(4-1(3-1(2-1(1-2)))))
+(5-1(4-1(3-1(2-2(1-1)))))
+(5-1(4-1(3-1(2-2(1-2)))))
+(5-1(4-1(3-2(2-1(1-1)))))
+(5-1(4-1(3-2(2-1(1-2)))))
+(5-1(4-1(3-2(2-2(1-1)))))
+(5-1(4-1(3-2(2-2(1-2)))))
+(5-1(4-2(3-1(2-1(1-1)))))
+(5-1(4-2(3-1(2-1(1-2)))))
+(5-1(4-2(3-1(2-2(1-1)))))
+(5-1(4-2(3-1(2-2(1-2)))))
+(5-1(4-2(3-2(2-1(1-1)))))
+(5-1(4-2(3-2(2-1(1-2)))))
+(5-1(4-2(3-2(2-2(1-1)))))
+(5-1(4-2(3-2(2-2(1-2)))))
+(5-2(4-1(3-1(2-1(1-1)))))
+(5-2(4-1(3-1(2-1(1-2)))))
+(5-2(4-1(3-1(2-2(1-1)))))
+(5-2(4-1(3-1(2-2(1-2)))))
+(5-2(4-1(3-2(2-1(1-1)))))
+(5-2(4-1(3-2(2-1(1-2)))))
+(5-2(4-1(3-2(2-2(1-1)))))
+(5-2(4-1(3-2(2-2(1-2)))))
+(5-2(4-2(3-1(2-1(1-1)))))
+(5-2(4-2(3-1(2-1(1-2)))))
+(5-2(4-2(3-1(2-2(1-1)))))
+(5-2(4-2(3-1(2-2(1-2)))))
+(5-2(4-2(3-2(2-1(1-1)))))
+(5-2(4-2(3-2(2-1(1-2)))))
+(5-2(4-2(3-2(2-2(1-1)))))
+(5-2(4-2(3-2(2-2(1-2)))))
+
+(5(4(3(2(1)))))
+int.fold_up/5 failed
+(1(2(3(4(5)))))
+int.fold_down/5 failed
Index: tests/hard_coded/int_fold_up_down.m
===================================================================
RCS file: /home/mercury1/repository/tests/hard_coded/int_fold_up_down.m,v
retrieving revision 1.1
diff -u -r1.1 int_fold_up_down.m
--- tests/hard_coded/int_fold_up_down.m	27 Jan 2004 03:26:38 -0000	1.1
+++ tests/hard_coded/int_fold_up_down.m	29 Mar 2004 05:16:06 -0000
@@ -12,27 +12,110 @@

 :- import_module io.

 :- pred main(io :: di, io :: uo) is det.

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

 :- implementation.

-:- import_module int, string, list.
+:- import_module int, string, list, std_util.

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

 main(!IO) :-
-    io.write_string(int.fold_up(f, "", 1, 5)   ++ "\n", !IO),
-    io.write_string(int.fold_down(f, "", 1, 5) ++ "\n", !IO).
-
+
+    io.write_string(int.fold_up(f, 1, 5, "")   ++ "\n", !IO),
+    io.write_string(int.fold_down(f, 1, 5, "") ++ "\n", !IO),
+
+    int.fold_up(p, 1, 5, "", FoldUpRes),
+    io.write_string(FoldUpRes ++ "\n", !IO),
+    int.fold_down(p, 1, 5, "", FoldDownRes),
+    io.write_string(FoldDownRes ++ "\n", !IO),
+
+    int.fold_up2(p2, 1, 5, "", FoldUp2Acc1, "", FoldUp2Acc2),
+    io.write_string(FoldUp2Acc1 ++ FoldUp2Acc2 ++ "\n", !IO),
+    int.fold_down2(p2, 1, 5, "", FoldDown2Acc1, "", FoldDown2Acc2),
+    io.write_string(FoldDown2Acc1 ++ FoldDown2Acc2 ++ "\n", !IO),
+
+    int.fold_up(io.write_int, 1, 5, !IO),
+    io.nl(!IO),
+    int.fold_down(io.write_int, 1, 5, !IO),
+    io.nl(!IO),
+
+        % This should produce some solutions.
+    UpNondetPred = (pred(Res::out) is nondet :-
+        int.fold_up(p_nondet, 1, 5, "", Res)
+    ),
+    std_util.solutions(UpNondetPred, NondetSolnsUp),
+    io.write_list(NondetSolnsUp, "\n", io.write_string, !IO),
+    io.nl(!IO),
+
+        % This will produce no solutions.
+    DownNondetPred = (pred(Res::out) is nondet :-
+        int.fold_down(p_nondet, 1, 6, "", Res)
+    ),
+    std_util.solutions(DownNondetPred, NondetSolnsDown),
+    io.write_list(NondetSolnsDown, "\n", io.write_string, !IO),
+    io.nl(!IO),
+
+        % This should succeed.
+    ( if    int.fold_up(p_semi, 1, 5, "", SemidetUpResS)
+      then  io.write_string(SemidetUpResS ++ "\n", !IO)
+      else  io.write_string("int.fold_up/5 failed\n", !IO)
+    ),
+
+        % This should fail.
+    ( if    int.fold_up(p_semi, 1, 6, "", SemidetUpResF)
+      then  io.write_string(SemidetUpResF ++ "\n", !IO)
+      else  io.write_string("int.fold_up/5 failed\n", !IO)
+    ),
+
+        % This should succeed.
+    ( if    int.fold_down(p_semi, 1, 5, "", SemidetDownResS)
+      then  io.write_string(SemidetDownResS ++ "\n", !IO)
+      else  io.write_string("int.fold_down/5 failed\n", !IO)
+    ),
+
+        % This should fail.
+    ( if    int.fold_down(p_semi, 1, 6, "", SemidetDownResF)
+      then  io.write_string(SemidetDownResF ++ "\n", !IO)
+      else  io.write_string("int.fold_down/5 failed\n", !IO)
+    ).

 :- func f(int, string) = string.

 f(X, S) = string.format("(%d%s)", [i(X), s(S)]).
+
+:- pred p(int::in, string::in, string::out) is det.
+
+p(X, S, string.format("(%d%s)", [i(X), s(S)])).
+
+:- pred p2(int::in, string::in, string::out, string::in, string::out) is det.
+
+p2(X, S, string.format("(%d%s)", [i(X), s(S)]), T,
+        string.format("(%d%s)", [i(X), s(T)])).
+
+:- pred p_nondet(int::in, string::in, string::out) is nondet.
+
+p_nondet(1, S, string.format("(1-1%s)", [s(S)])).
+p_nondet(1, S, string.format("(1-2%s)", [s(S)])).
+p_nondet(2, S, string.format("(2-1%s)", [s(S)])).
+p_nondet(2, S, string.format("(2-2%s)", [s(S)])).
+p_nondet(3, S, string.format("(3-1%s)", [s(S)])).
+p_nondet(3, S, string.format("(3-2%s)", [s(S)])).
+p_nondet(4, S, string.format("(4-1%s)", [s(S)])).
+p_nondet(4, S, string.format("(4-2%s)", [s(S)])).
+p_nondet(5, S, string.format("(5-1%s)", [s(S)])).
+p_nondet(5, S, string.format("(5-2%s)", [s(S)])).
+
+:- pred p_semi(int::in, string::in, string::out) is semidet.
+
+p_semi(1, S, string.format("(1%s)", [s(S)])).
+p_semi(2, S, string.format("(2%s)", [s(S)])).
+p_semi(3, S, string.format("(3%s)", [s(S)])).
+p_semi(4, S, string.format("(4%s)", [s(S)])).
+p_semi(5, S, string.format("(5%s)", [s(S)])).

 %-----------------------------------------------------------------------------%
 %-----------------------------------------------------------------------------%
--------------------------------------------------------------------------
mercury-reviews mailing list
post:  mercury-reviews at cs.mu.oz.au
administrative address: owner-mercury-reviews at cs.mu.oz.au
unsubscribe: Address: mercury-reviews-request at cs.mu.oz.au Message: unsubscribe
subscribe:   Address: mercury-reviews-request at cs.mu.oz.au Message: subscribe
--------------------------------------------------------------------------