[m-rev.] diff: updates to random modules
Mark Brown
mark at mercurylang.org
Fri Sep 6 17:38:25 AEST 2019
Hi all,
This addresses the discussion on the users list.
Mark
-------------- next part --------------
commit 3a83702562de5341e4ab4d7ff6786e89a21061b6
Author: Mark Brown <mark at mercurylang.org>
Date: Fri Sep 6 15:40:26 2019 +1000
Changes per the discussion on the users list.
library/random.m:
Add predicates shuffle_list/{4,5} and shuffle_array/{4,5}.
library/random.m:
library/random.sfc*.m:
Improve comments.
tests/hard_coded/Mmakefile:
tests/hard_coded/random_shuffle*.{m,exp}:
Test the new predicates.
diff --git a/library/random.m b/library/random.m
index 3b9873f..98322ca 100644
--- a/library/random.m
+++ b/library/random.m
@@ -95,6 +95,7 @@
:- include_module sfc32.
:- include_module sfc64.
+:- import_module array.
:- import_module io.
:- import_module list.
@@ -181,6 +182,16 @@
:- pred normal_floats(float::out, float::out, R::in, R::out) is det
<= random(R).
+ % Generate a random permutation of a list.
+ %
+:- pred shuffle_list(list(T)::in, list(T)::out, R::in, R::out) is det
+ <= random(R).
+
+ % Generate a random permutation of an array.
+ %
+:- pred shuffle_array(array(T)::array_di, array(T)::array_uo, R::in, R::out)
+ is det <= random(R).
+
%---------------------------------------------------------------------------%
% Interface to unique random number generators. Callers need to
@@ -270,7 +281,7 @@
%
% Generate two pseudo-random floats from a normal (i.e., Gaussian)
% distribution with mean 0.0 and standard deviation 1.0, using the
- % Nox-Muller method.
+ % Box-Muller method.
%
% We generate two at a time for efficiency; they are independent of
% each other.
@@ -278,6 +289,16 @@
:- pred normal_floats(P::in, float::out, float::out, S::di, S::uo) is det
<= urandom(P, S).
+ % Generate a random permutation of a list.
+ %
+:- pred shuffle_list(P::in, list(T)::in, list(T)::out, S::di, S::uo) is det
+ <= urandom(P, S).
+
+ % Generate a random permutation of an array.
+ %
+:- pred shuffle_array(P::in, array(T)::array_di, array(T)::array_uo,
+ S::di, S::uo) is det <= urandom(P, S).
+
%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%
@@ -381,6 +402,10 @@
%
% Creates a supply of random numbers RS using the specified Seed.
%
+ % This predicate has been declared obsolete because all of the
+ % interface from here on is deprecated. All code using this part
+ % of the interface will need to be updated.
+ %
:- pragma obsolete(init/2).
:- pred init(int::in, supply::uo) is det.
@@ -447,7 +472,6 @@
:- implementation.
-:- import_module array.
:- import_module float.
:- import_module int.
:- import_module math.
@@ -511,6 +535,30 @@ normal_floats(U, V, !R) :-
normal_floats(U, V, !R)
).
+shuffle_list(L0, L, !R) :-
+ A0 = array(L0),
+ shuffle_array(A0, A, !R),
+ L = array.to_list(A).
+
+shuffle_array(A0, A, !R) :-
+ Lo = array.min(A0),
+ Hi = array.max(A0),
+ Sz = array.size(A0),
+ shuffle_2(Lo, Lo, Hi, Sz, A0, A, !R).
+
+:- pred shuffle_2(int::in, int::in, int::in, int::in,
+ array(T)::array_di, array(T)::array_uo, R::in, R::out) is det
+ <= random(R).
+
+shuffle_2(I, Lo, Hi, Sz, !A, !R) :-
+ ( if I > Hi then
+ true
+ else
+ uniform_int_in_range(Lo, Sz, J, !R),
+ swap_elems(I, J, !A),
+ shuffle_2(I + 1, Lo, Hi, Sz, !A, !R)
+ ).
+
%---------------------------------------------------------------------------%
uniform_int_in_range(P, Start, Range0, N, !S) :-
@@ -567,6 +615,30 @@ normal_floats(P, U, V, !S) :-
normal_floats(P, U, V, !S)
).
+shuffle_list(P, L0, L, !S) :-
+ A0 = array(L0),
+ shuffle_array(P, A0, A, !S),
+ L = array.to_list(A).
+
+shuffle_array(P, A0, A, !S) :-
+ Lo = array.min(A0),
+ Hi = array.max(A0),
+ Sz = array.size(A0),
+ shuffle_2(P, Lo, Lo, Hi, Sz, A0, A, !S).
+
+:- pred shuffle_2(P::in, int::in, int::in, int::in, int::in,
+ array(T)::array_di, array(T)::array_uo, S::di, S::uo) is det
+ <= urandom(P, S).
+
+shuffle_2(P, I, Lo, Hi, Sz, !A, !S) :-
+ ( if I > Hi then
+ true
+ else
+ uniform_int_in_range(P, Lo, Sz, J, !S),
+ swap_elems(I, J, !A),
+ shuffle_2(P, I + 1, Lo, Hi, Sz, !A, !S)
+ ).
+
%---------------------------------------------------------------------------%
:- pred uniform_to_normal(float::in, float::in, float::out, float::out)
@@ -580,6 +652,15 @@ uniform_to_normal(X, Y, U, V) :-
U = X * Fac,
V = Y * Fac.
+:- pred swap_elems(int::in, int::in, array(T)::array_di, array(T)::array_uo)
+ is det.
+
+swap_elems(I, J, !A) :-
+ array.lookup(!.A, I, XI),
+ array.lookup(!.A, J, XJ),
+ array.unsafe_set(I, XJ, !A),
+ array.unsafe_set(J, XI, !A).
+
%---------------------------------------------------------------------------%
%---------------------------------------------------------------------------%
diff --git a/library/random.sfc16.m b/library/random.sfc16.m
index 9bee6f1..84a2d27 100644
--- a/library/random.sfc16.m
+++ b/library/random.sfc16.m
@@ -31,7 +31,8 @@
:- instance random(random).
- % Initialise a 16-bit SFC generator with the default seed.
+ % Initialise a 16-bit SFC generator with the default seed. The
+ % resulting generator produces the same sequence every time.
%
:- func init = random.
diff --git a/library/random.sfc32.m b/library/random.sfc32.m
index 7ca3803..0875992 100644
--- a/library/random.sfc32.m
+++ b/library/random.sfc32.m
@@ -36,7 +36,8 @@
:- instance urandom(params, ustate).
:- instance urandom_dup(ustate).
- % Initialise a 32-bit SFC generator with the default seed.
+ % Initialise a 32-bit SFC generator with the default seed. The
+ % resulting generator produces the same sequence every time.
%
:- pred init(params::out, ustate::uo) is det.
diff --git a/library/random.sfc64.m b/library/random.sfc64.m
index 97d86e7..53bffe0 100644
--- a/library/random.sfc64.m
+++ b/library/random.sfc64.m
@@ -33,7 +33,8 @@
:- instance urandom(params, ustate).
:- instance urandom_dup(ustate).
- % Initialise a 64-bit SFC generator with the default seed.
+ % Initialise a 64-bit SFC generator with the default seed. The
+ % resulting generator produces the same sequence every time.
%
:- pred init(params::out, ustate::uo) is det.
diff --git a/tests/hard_coded/Mmakefile b/tests/hard_coded/Mmakefile
index fd909b3..f6447b0 100644
--- a/tests/hard_coded/Mmakefile
+++ b/tests/hard_coded/Mmakefile
@@ -499,7 +499,9 @@ ifeq "$(filter erlang%,$(GRADE))" ""
RANDOM_PROGS = \
random1 \
random2 \
- random3
+ random3 \
+ random_shuffle \
+ random_shuffle2
else
RANDOM_PROGS =
endif
diff --git a/tests/hard_coded/random_shuffle.exp b/tests/hard_coded/random_shuffle.exp
new file mode 100644
index 0000000..61bb69a
--- /dev/null
+++ b/tests/hard_coded/random_shuffle.exp
@@ -0,0 +1,10 @@
+Passed.
+Passed.
+Passed.
+Passed.
+Passed.
+Passed.
+Passed.
+Passed.
+Passed.
+Passed.
diff --git a/tests/hard_coded/random_shuffle.m b/tests/hard_coded/random_shuffle.m
new file mode 100644
index 0000000..60db582
--- /dev/null
+++ b/tests/hard_coded/random_shuffle.m
@@ -0,0 +1,40 @@
+%---------------------------------------------------------------------------%
+% vim: ts=4 sw=4 sts=4 et ft=mercury
+%---------------------------------------------------------------------------%
+
+:- module random_shuffle.
+:- interface.
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+:- implementation.
+
+:- import_module int.
+:- import_module list.
+:- import_module random.
+:- import_module random.sfc32.
+
+main(!IO) :-
+ List = 1 `..` 100,
+ sfc32.init(P, S),
+ make_io_urandom(P, S, M, !IO),
+ test(M, List, 10, !IO).
+
+:- pred test(M::in, list(int)::in, int::in, io::di, io::uo) is det
+ <= urandom(M, io).
+
+test(M, List, Count, !IO) :-
+ ( if Count > 0 then
+ shuffle_list(M, List, Shuffled, !IO),
+ sort_and_remove_dups(Shuffled, Sorted),
+ ( if Sorted = List then
+ io.write_string("Passed.\n", !IO)
+ else
+ io.write_string("Failed!\n", !IO)
+ ),
+ test(M, List, Count - 1, !IO)
+ else
+ true
+ ).
+
diff --git a/tests/hard_coded/random_shuffle2.exp b/tests/hard_coded/random_shuffle2.exp
new file mode 100644
index 0000000..61bb69a
--- /dev/null
+++ b/tests/hard_coded/random_shuffle2.exp
@@ -0,0 +1,10 @@
+Passed.
+Passed.
+Passed.
+Passed.
+Passed.
+Passed.
+Passed.
+Passed.
+Passed.
+Passed.
diff --git a/tests/hard_coded/random_shuffle2.m b/tests/hard_coded/random_shuffle2.m
new file mode 100644
index 0000000..4ff09da
--- /dev/null
+++ b/tests/hard_coded/random_shuffle2.m
@@ -0,0 +1,39 @@
+%---------------------------------------------------------------------------%
+% vim: ts=4 sw=4 sts=4 et ft=mercury
+%---------------------------------------------------------------------------%
+
+:- module random_shuffle2.
+:- interface.
+:- import_module io.
+
+:- pred main(io::di, io::uo) is det.
+
+:- implementation.
+
+:- import_module int.
+:- import_module list.
+:- import_module random.
+:- import_module random.sfc16.
+
+main(!IO) :-
+ List = 1 `..` 100,
+ R = sfc16.init,
+ test(List, 10, R, _, !IO).
+
+:- pred test(list(int)::in, int::in, R::in, R::out, io::di, io::uo) is det
+ <= random(R).
+
+test(List, Count, !R, !IO) :-
+ ( if Count > 0 then
+ shuffle_list(List, Shuffled, !R),
+ sort_and_remove_dups(Shuffled, Sorted),
+ ( if Sorted = List then
+ io.write_string("Passed.\n", !IO)
+ else
+ io.write_string("Failed!\n", !IO)
+ ),
+ test(List, Count - 1, !R, !IO)
+ else
+ true
+ ).
+
More information about the reviews
mailing list