[m-dev.] For review: iteration support added to std_util.m

[Ralph Becket]

There's definitely room for some debate on argument ordering and how many
indices etc. etc. are necessary/correct/appropriate.

Bear in mind that sequence quantification will make most of this stuff 
redundant.

Ralph



Estimated hours taken: 2

Added funcs and preds to support common iteration schemes.

library/std_util.m
	Added the following:
	iterate/5		- fairly general indexed iteration
	iterate_dcg//4
	over_range/4		- iteration indexed by ascending integer
range
	over_range_dcg//3
	iterate_until/3		- unindexed iteration until some condition
	iterate_until_dcg//1

Index: std_util.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/std_util.m,v
retrieving revision 1.217
diff -u -r1.217 std_util.m
--- std_util.m	2001/01/09 23:30:18	1.217
+++ std_util.m	2001/01/11 16:57:42
@@ -566,6 +566,60 @@
 	%
 :- pred deconstruct(T::in, string::out, int::out, list(univ)::out) is det.
 
+%
----------------------------------------------------------------------------
%
+
+	% iterate(I, ContP, Succ, Fn, X) computes
+	%
+	% 	Fn(Succ^n(I), ...Fn(Succ(I), Fn(I, X))...)
+	%
+	% where Succ^n(I) denotes the Succ(Succ(...(i)...)) (n times)
+	% and n is the least integer such that ContP(Succ^(n+1)(I))
+	% fails.
+	%
+:- func iterate(I, pred(I), func(I) = I, func(I, T) = T, T) = T.
+:- mode iterate(in, pred(in) is semidet, func(in) = out is det,
+		func(in, in) = out is det, in) = out is det.
+
+	% iterate_dcg(I, ContP, Succ, P, X0, X) is a DCG version
+	% of iterate/5.
+	%
+:- pred iterate_dcg(I, pred(I), func(I) = I, pred(I, T, T), T, T).
+:- mode iterate_dcg(in, pred(in) is semidet, func(in) = out is det,
+		pred(in, in, out) is det, in, out) is det.
+:- mode iterate_dcg(in, pred(in) is semidet, func(in) = out is det,
+		pred(in, di, uo) is det, di, uo) is det.
+
+	% A version of iterate/5 specialised for ascending integer
+	% sequences.
+	%
+:- func over_range(int, int, func(int, T) = T, T) = T.
+
+	% A DCG version of over_range/4.
+	%
+:- pred over_range_dcg(int, int, pred(int, T, T), T, T).
+:- mode over_range_dcg(in, in, pred(in, in, out) is det, in, out) is det.
+:- mode over_range_dcg(in, in, pred(in, di, uo) is det, di, uo) is det.
+
+	% iterate_until(DoneP, Fn, X) computes
+	%
+	% 	Fn^n(X)
+	%
+	% where n is the least integer such that DoneP(Fn^n(X))
+	% succeeds.
+	%
+:- func iterate_until(pred(T), func(T) = T, T) = T.
+:- mode iterate_until(pred(in) is semidet, func(in) = out is det, in) = out
+		is det.
+
+	% A DCG version of iterate_until/3; the key difference here is
+	% that the predicate argument must return yes if further
+	% iteration is to take place and no otherwise.
+	%
+:- pred iterate_until_dcg(pred(bool, T, T), T, T).
+:- mode iterate_until_dcg(pred(out, in, out) is det, in, out) is det.
+:- mode iterate_until_dcg(pred(out, di, uo) is det, di, uo) is det.
+
+
 :- implementation.
 :- interface.
 
@@ -3968,3 +4022,46 @@
 aggregate(P, F, Acc0) = Acc :-
 	aggregate(P, (pred(X::in, A0::in, A::out) is det :- A = F(X, A0)),
 		Acc0, Acc).
+
+%
----------------------------------------------------------------------------
%
+
+iterate(I, ContP, Succ, Fn, X) =
+	( if ContP(I) then
+		iterate(Succ(I), ContP, Succ, Fn, Fn(I, X))
+	  else
+	  	X
+	).
+
+%
----------------------------------------------------------------------------
%
+
+iterate_dcg(I, ContP, Succ, P) -->
+	( if { ContP(I) } then
+		P(I),
+		iterate_dcg(Succ(I), ContP, Succ, P)
+	  else
+	  	[]
+	).
+
+%
----------------------------------------------------------------------------
%
+
+over_range(Lo, Hi, Fn, X) =
+	iterate(Lo, >=(Hi), plus(1), Fn, X).
+
+%
----------------------------------------------------------------------------
%
+
+over_range_dcg(Lo, Hi, P) -->
+	iterate_dcg(Lo, >=(Hi), plus(1), P).
+
+%
----------------------------------------------------------------------------
%
+
+iterate_until(DoneP, Fn, X) =
+	( if DoneP(X) then X else iterate_until(DoneP, Fn, Fn(X)) ).
+
+%
----------------------------------------------------------------------------
%
+
+iterate_until_dcg(P) -->
+	P(Cont),
+	( if { Cont = yes } then [] else iterate_until_dcg(P) ).
+
+%
----------------------------------------------------------------------------
%
+%
----------------------------------------------------------------------------
%

--
Ralph Becket      |      MSR Cambridge      |      rbeck at microsoft.com 
--------------------------------------------------------------------------
mercury-developers mailing list
Post messages to:       mercury-developers at cs.mu.oz.au
Administrative Queries: owner-mercury-developers at cs.mu.oz.au
Subscriptions:          mercury-developers-request at cs.mu.oz.au
--------------------------------------------------------------------------