[m-dev.] for review: change interface of random__permutation

[Fergus Henderson]

This change addresses my review comments on the diff
that Zoltan committed.

I didn't bother adding the `..' function that we talked
about; for now I've just added a similar function
(called `range') to the test cases that need it.

If I don't hear any objections, then I will commit this
change sometime soon.

----------

Estimated hours taken: 1.5

library/random.m:
	Change random__permutation so that it takes
	as its first argument a list(T) rather than an int N,
	and returns a permutation of that list rather than
	a permutation of the integers 0 .. N-1.

tests/tabling/expand*.m:
	Change to reflect the new interface to random__permutation.

NEWS:
	Document the random__permutation predicate.

Workspace: /d-drive/home/hg/fjh/mercury
Index: NEWS
===================================================================
RCS file: /home/mercury1/repository/mercury/NEWS,v
retrieving revision 1.160
diff -u -d -r1.160 NEWS
--- NEWS	2000/01/25 04:09:36	1.160
+++ NEWS	2000/02/09 05:32:36
@@ -1,7 +1,8 @@
-
 NEWS since Mercury release 0.9:
 -------------------------------
 
+Changes to the Mercury language:
+
 * We've added support for record syntax, so that fields of
   constructors can be conveniently extracted and updated
   without writing lots of trivial access predicates.
@@ -12,10 +13,16 @@
   that appeared in the release of the day in early January 2000.
   `Value =^ field' is now the syntax for DCG field selection,
   rather than `Value := ^ field'.
+
+Changes to the standard library:
  
 * Functions `int:^/2' and `integer:^/2' have been removed.
   Use `int__xor/2' and `integer__xor/2' instead.
   The operator `^' is now used for record syntax.
+
+* There's a new predicate `random__permutation', for
+  computing a random permutation of a list.
+
 
 NEWS for Mercury release 0.9.1:
 -------------------------------
Index: library/random.m
===================================================================
RCS file: /home/mercury1/repository/mercury/library/random.m,v
retrieving revision 1.17
diff -u -d -r1.17 random.m
--- library/random.m	2000/01/03 05:22:34	1.17
+++ library/random.m	2000/02/09 05:24:39
@@ -43,10 +43,10 @@
 :- pred random__randmax(int, random__supply, random__supply).
 :- mode random__randmax(out, mdi, muo) is det.
 
-	% random__permutation(Num, List, RS0, RS): binds List to a
-	% random permutation of the numbers in the range 0 .. Num - 1,
+	% random__permutation(List0, List, RS0, RS):
+	% binds List to a random permutation of List0,
 	% and binds RS to the new state of the random number supply.
-:- pred random__permutation(int, list(int), random__supply, random__supply).
+:- pred random__permutation(list(T), list(T), random__supply, random__supply).
 :- mode random__permutation(in, out, mdi, muo) is det.
 
 %---------------------------------------------------------------------------%
@@ -91,33 +91,32 @@
 
 	% The random permutation is implemented via a "sampling without
 	% replacement" method. In init_record, we build up a map in which
-	% every integer in the range 0 .. Num - 1 is mapped to itself. The
-	% sampling stage iterates from Num - 1 down to 0. The invariant being
-	% maintained is that at iteration I, the numbers in the image of
-	% the part of the map indexed by 0 .. I-1 are the numbers that have
+	% every integer in the range 0 .. Length - 1 is mapped to the
+	% corresponding element in the list.  The sampling stage
+	% iterates from Length - 1 down to 0. The invariant being
+	% maintained is that at iteration I, the elements in the image of
+	% the part of the map indexed by 0 .. I-1 are the elements that have
 	% not been selected yet. At each iteration, perform_sampling generates
-	% a random number Index in the range 0 .. I-1, adds the number that
+	% a random number Index in the range 0 .. I-1, adds the element that
 	% Index is mapped to, Next, to the permutation, and then ensures that
 	% Next is not generated again by swapping it with the image of I-1.
 
-random__permutation(Num, List, RS0, RS) :-
-	map__init(Empty),
-	init_record(Num, Empty, Samples0),
-	perform_sampling(Num, Samples0, [], List, RS0, RS).
+random__permutation(List0, List, RS0, RS) :-
+	map__init(Samples0),
+	init_record(List0, 0, Samples0, Len, Samples),
+	perform_sampling(Len, Samples, [], List, RS0, RS).
 
-:- pred init_record(int::in, map(int, int)::in, map(int, int)::out) is det.
+:- pred init_record(list(T)::in, int::in, map(int, T)::in, 
+		int::out, map(int, T)::out) is det.
 
-init_record(N, Record0, Record) :-
-	( N =< 0 ->
-		Record = Record0
-	;
-		N1 = N - 1,
-		map__det_insert(Record0, N1, N1, Record1),
-		init_record(N1, Record1, Record)
-	).
+init_record([], N, Record, N, Record).
+init_record([X|Xs], N0, Record0, N, Record) :-
+	map__det_insert(Record0, N0, X, Record1),
+	N1 = N0 + 1,
+	init_record(Xs, N1, Record1, N, Record).
 
-:- pred perform_sampling(int::in, map(int, int)::in,
-	list(int)::in, list(int)::out,
+:- pred perform_sampling(int::in, map(int, T)::in,
+	list(T)::in, list(T)::out,
 	random__supply::mdi, random__supply::muo) is det.
 
 perform_sampling(I, Record0, Order0, Order, RS0, RS) :-
Index: tests/tabling/expand.m
===================================================================
RCS file: /home/mercury1/repository/tests/tabling/expand.m,v
retrieving revision 1.1
diff -u -d -r1.1 expand.m
--- tests/tabling/expand.m	2000/01/03 08:53:11	1.1
+++ tests/tabling/expand.m	2000/02/09 05:26:56
@@ -14,7 +14,7 @@
 
 main -->
 	{ random__init(0, RS0) },
-	{ random__permutation(1024, Perm, RS0, RS1) },
+	{ random__permutation(range(0, 1023), Perm, RS0, RS1) },
 	{ choose_signs_and_enter(Perm, Solns, RS1, _RS) },
 	( { test_tables(Solns, yes) } ->
 		io__write_string("Test successful.\n")
@@ -22,6 +22,14 @@
 		io__write_string("Test unsuccessful.\n")
 	).
 	% io__report_tabling_stats.
+
+:- func range(int, int) = list(int).
+range(Min, Max) =
+	(if Min > Max then
+		[]
+	else
+		[Min | range(Min + 1, Max)]
+	).
 
 :- pred choose_signs_and_enter(list(int)::in, assoc_list(int)::out,
 	random__supply::mdi, random__supply::muo) is det.
Index: tests/tabling/expand_float.m
===================================================================
RCS file: /home/mercury1/repository/tests/tabling/expand_float.m,v
retrieving revision 1.1
diff -u -d -r1.1 expand_float.m
--- tests/tabling/expand_float.m	2000/01/03 08:53:12	1.1
+++ tests/tabling/expand_float.m	2000/02/09 05:27:07
@@ -14,7 +14,7 @@
 
 main -->
 	{ random__init(0, RS0) },
-	{ random__permutation(1024, Perm, RS0, RS1) },
+	{ random__permutation(range(0, 1023), Perm, RS0, RS1) },
 	{ choose_signs_and_enter(Perm, Solns, RS1, _RS) },
 	( { test_tables(Solns, yes) } ->
 		io__write_string("Test successful.\n")
@@ -22,6 +22,14 @@
 		io__write_string("Test unsuccessful.\n")
 	).
 	% io__report_tabling_stats.
+
+:- func range(int, int) = list(int).
+range(Min, Max) =
+	(if Min > Max then
+		[]
+	else
+		[Min | range(Min + 1, Max)]
+	).
 
 :- pred choose_signs_and_enter(list(int)::in, assoc_list(float)::out,
 	random__supply::mdi, random__supply::muo) is det.
Index: tests/tabling/expand_poly.m
===================================================================
RCS file: /home/mercury1/repository/tests/tabling/expand_poly.m,v
retrieving revision 1.1
diff -u -d -r1.1 expand_poly.m
--- tests/tabling/expand_poly.m	2000/01/03 08:53:12	1.1
+++ tests/tabling/expand_poly.m	2000/02/09 05:27:14
@@ -18,7 +18,7 @@
 
 main -->
 	{ random__init(0, RS0) },
-	{ random__permutation(1024, Perm, RS0, RS1) },
+	{ random__permutation(range(0, 1023), Perm, RS0, RS1) },
 	{ choose_signs_and_enter(Perm, 42, Solns1, RS1, RS2) },
 	( { test_tables(Solns1, yes) } ->
 		io__write_string("First test successful.\n")
@@ -44,6 +44,14 @@
 		io__write_string("Fourth test unsuccessful.\n")
 	).
 	% io__report_tabling_stats.
+
+:- func range(int, int) = list(int).
+range(Min, Max) =
+	(if Min > Max then
+		[]
+	else
+		[Min | range(Min + 1, Max)]
+	).
 
 :- pred choose_signs_and_enter(list(int)::in, T::in, list(record(int, T))::out,
 	random__supply::mdi, random__supply::muo) is det.

-- 
Fergus Henderson <fjh at cs.mu.oz.au>  |  "I have always known that the pursuit
WWW: <http://www.cs.mu.oz.au/~fjh>  |  of excellence is a lethal habit"
PGP: finger fjh at 128.250.37.3        |     -- the last words of T. S. Garp.
--------------------------------------------------------------------------
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
--------------------------------------------------------------------------