Making prolog predicates deterministic : <p>I've written a predicate, <code>shuffle/3</code>, 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.</p>

<p>For example:</p>

<pre><code>?- 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.
</code></pre>

<p>Here's the code I've come up with to implement it:</p>

<pre><code>shuffle([], [], []).
shuffle([H|R], [H|Left], Right) :- shuffle(R, Right, Left).
shuffle([H|R], Left, [H|Right]) :- shuffle(R, Right, Left).
</code></pre>

<p>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: <code>shuffle([1, 2, 3, 4], [1, 2], [3, 4])</code>.</p>

<p>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?</p>

<p>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?</p>
