Example 11: Random Shuffle

Overview

The main structure of the program will be a) read lines, b) random permutate lines, c) write lines. We can already define the main program, without executing it:

main :-
    read_lines(L),
    random_permutation(L, R),
    write_lines(R).

Random

A simple method to produce a random permutation in Prolog, is to first extend the given list by a uniform random number, and then keysort and strip the list again. Dogelog Player provides uniform random numbers in the interval [0,1) via library(util/math), and a native implementation of keysort is found in library(compat).

Each time pressing the instrumentation button will give a different result:

:- ensure_loaded(library(compat)).
:- ensure_loaded(library(util/math)).

random_permutation(L, R) :-
    add_key(L, H),
    keysort(H, J),
    remove_key(J, R).

add_key([], []).
add_key([X|L], [Y-X|R]) :- random(Y), add_key(L, R).

remove_key([], []).
remove_key([_-X|L], [X|R]) :- remove_key(L, R).

?- random_permutation([1,2,3,4,5], X).

Input

For input we rely on the Prolog term reading, whereas we use the Prolog term end_of_file as a marker that the list has been completely entered. We can explore reading directly in a notebook, by adding the input after the reading query. Because we read Prolog terms, we have to terminate each input by a period. Feel free to edit the input and see what happens:

read_lines(L) :- read(X), read_lines(X, L).

read_lines(end_of_file, []) :- !.
read_lines(X, [X|L]) :- read(Y), read_lines(Y, L).

?- read_lines(L).
foo.
bar.
baz.
end_of_file.

Output

For output we simple flesh out some Prolog terms in a tail recursive loop. One might be tempted to use higher order programming here and some maplist, but Dogelog Player doesn't provide call/n for performance and didactical reasons, so we have to do it more explicitly. The can explore writing directly in a notebook, since it shows the output after the writing query:

write_lines([]).
write_lines([X|L]) :- write(X), nl, write_lines(L).

?- write_lines([foo,bar,baz]).

Result

We can now run the main program already sketched in the first paragraph. We will provide a small list of Turing award winners that were inclined with artificial intelligence. The notebook allows combining reading and writing. Again each time pressing the instrumention button will give a different result. Feel also free to edit the input and see what happens:

?- main.
'Marvin Minsky'.
'John McCarthy'.
'Herbert A. Simon'.
'Allen Newell'.
end_of_file.