Multi tool use

Making prolog predicates deterministic

I've written a predicate, shuffle/3, which generates "shuffles" of two lists. When the second and third argument are instantiated, the first argument becomes a list which has all the elements of both Left and Right, in the same order that they appear in Left and Right.

shuffle/3

For example:

?- shuffle(X, [1, 2], [3, 4]).
X = [1, 3, 2, 4] ;
X = [1, 3, 4, 2] ;
X = [1, 2, 3, 4] ;
X = [3, 4, 1, 2] ;
X = [3, 1, 2, 4] ;
X = [3, 1, 4, 2] ;
false.


Here's the code I've come up with to implement it:

shuffle(, , ).
shuffle([H|R], [H|Left], Right) :- shuffle(R, Right, Left).
shuffle([H|R], Left, [H|Right]) :- shuffle(R, Right, Left).


This works well, and even generates reasonable results for "the most general query", but it fails to be deterministic for any query, even one where all arguments are fully instantiated: shuffle([1, 2, 3, 4], [1, 2], [3, 4]).

shuffle([1, 2, 3, 4], [1, 2], [3, 4])

My real question is: is there anything I can do, while maintaining purity (so, no cuts), which makes this predicate deterministic when all arguments are fully instantiated?

And while I'm here, I'm new to Prolog, I wonder if anyone has advice on why I would care about determinism. Is it important for real prolog programs?

once/1

shuffle/3

shuffle(-Out, +Left, +Right)

1 Answer
1

No, there is no way to make this predicate deterministic while still maintaining pure code. To see this, consider:

?- shuffle([1, 1], [1], [1]).
true
; true.


There are two answers to this. Why? The best is not to use a debugger to understand this, but rather to use a generalized query:

?- shuffle([X1, X2], [Y1], [Y2]).
X1 = Y1, X2 = Y2
; X1 = Y2, X2 = Y1.


So here you can see the "true" connection between the arguments! And now our specific query is an instance of this more general query. Thus, no way to remove the two answers.

However, you might use cut in a pure way, provided it is guarded such that the result will always be pure. Like testing ground(shuffe(Xs, Ys, Zs)) but all of this is quite ad hoc.

ground(shuffe(Xs, Ys, Zs))

On second thought, there might be a pure, determinate answer, but only if the answers to shuffle([X1, X2], [Y1], [Y2]). are changed somehow. The answer actually should be:

shuffle([X1, X2], [Y1], [Y2]).

?- shuffledet([X1, X2], [Y1], [Y2]).
X1 = X2, X2 = Y1, Y1 = Y2 % all equal
; dif(X1, X2), X1 = Y1, X2 = Y2
; dif(X1, X2), X1 = Y2, X2 = Y1.


So that might be a possibility... I will had put a 500 bounty on this ASAP, but no response.

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.