<p>Here's a straightforward way you can do it and <strong>preserve <a href="/questions/tagged/logical-purity" class="post-tag" title="show questions tagged &#39;logical-purity&#39;" rel="tag">logical-purity</a>!</strong></p>

<pre><code>not_all_equal([E|Es]) :-
   some_dif(Es, E).

some_dif([X|Xs], E) :-
   (  dif(X, E)
   ;  X = E, some_dif(Xs, E)
   ).
</code></pre>

<p>Here are some sample queries using SWI-Prolog 7.7.2. </p>

<p>First, the most general query:</p>

<pre><code>?- not_all_equal(Es).
   dif(_A,_B), Es = [_A,_B|_C]
;  dif(_A,_B), Es = [_A,_A,_B|_C]
;  dif(_A,_B), Es = [_A,_A,_A,_B|_C]
;  dif(_A,_B), Es = [_A,_A,_A,_A,_B|_C]
;  dif(_A,_B), Es = [_A,_A,_A,_A,_A,_B|_C]
...
</code></pre>

<p>Next, the query the OP gave in the question:</p>

<pre><code>?- not_all_equal([A,B,C]), A=a, B=b.
   A = a, B = b
;  false.                          % &lt;- the toplevel hints at non-determinism
</code></pre>

<p>Last, let's put the subgoal <code>A=a, B=b</code> upfront:</p>

<pre><code>?- A=a, B=b, not_all_equal([A,B,C]).
   A = a, B = b
;  false.                          % &lt;- (non-deterministic, like above)
</code></pre>

<p>Good, but ideally the last query should have succeeded deterministically!</p>

<hr>

<h3>Enter <code><a href="http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/swi/" rel="nofollow noreferrer">library</a>(<a href="http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/swi/reif.pl" rel="nofollow noreferrer">reif</a>)</code></h3>

<p><a href="https://sicstus.sics.se/sicstus/docs/latest4/html/sicstus.html/Indexing.html" rel="nofollow noreferrer">First argument indexing</a> 
takes the principal functor of the first predicate argument (plus a few simple built-in tests) into account to improve the determinism of sufficiently instantiated goals.</p>

<p>This, by itself, does <em>not</em> cover <code>dif/2</code> satisfactorily.</p>

<p>What can we do? Work with
<a href="https://stackoverflow.com/q/13664870/4609915">reified term equality/inequality</a>&mdash;effectively <a href="https://arxiv.org/abs/1607.01590" rel="nofollow noreferrer">indexing <code>dif/2</code></a>!</p>

<pre><code>some_dif([X|Xs], E) :-                     % some_dif([X|Xs], E) :-
   if_(dif(X,E), true,                     %    (  dif(X,E), true
       (X = E, some_dif(Xs,E))             %    ;  X = E, some_dif(Xs,E)
      ).                                   %    ).
</code></pre>

<p>Notice the similarities of the new and the old implementation!</p>

<p>Above, the goal <code>X = E</code> is redundant on the left-hand side. Let's remove it! </p>

<pre><code>some_dif([X|Xs], E) :-
   if_(dif(X,E), true, some_dif(Xs,E)).
</code></pre>

<p><em>Sweet!</em> But, alas, we're not quite done (yet)!</p>

<pre>
?- not_all_equal(Xs).
<b>DOES NOT TERMINATE</b>
</pre>

<p><em>What's going on?</em></p>

<p>It turns out that the implementation of <code>dif/3</code> prevents us from getting a nice answer sequence for the most general query. To do so&mdash;without using additional goals forcing fair enumeration&mdash;we need a tweaked implementation of <code>dif/3</code>, which I call <code>diffirst/3</code>:</p>

<pre><code>diffirst(X, Y, T) :-
   (  X == Y -&gt; T = false
   ;  X \= Y -&gt; T = true
   ;  T = true,  dif(X, Y)
   ;  T = false, X = Y
   ).
</code></pre>

<p>Let's use <code>diffirst/3</code> instead of <code>dif/3</code> in the definition of predicate <code>some_dif/2</code>:</p>

<pre><code>some_dif([X|Xs], E) :-
   if_(diffirst(X,E), true, some_dif(Xs,E)).
</code></pre>

<p>So, at long last, here are above queries with the new <code>some_dif/2</code>:</p>

<pre><code>?- not_all_equal(Es).                     % query #1
   dif(_A,_B), Es = [_A,_B|_C]
;  dif(_A,_B), Es = [_A,_A,_B|_C]
;  dif(_A,_B), Es = [_A,_A,_A,_B|_C]
...

?- not_all_equal([A,B,C]), A=a, B=b.      % query #2
   A = a, B = b
;  false.

?- A=a, B=b, not_all_equal([A,B,C]).      % query #3
A = a, B = b.
</code></pre>

<p>Query #1 does not terminate, but has the same nice compact answer sequence. <strong>Good!</strong></p>

<p>Query #2 is still non-determinstic. Okay. To me this is as good as it gets.</p>

<p>Query #3 has become deterministic: <strong>Better now!</strong></p>

<hr>

<p><strong>The bottom line:</strong></p>

<ol>
<li>Use <code>library(reif)</code> to tame excess non-determinism while preserving logical purity!</li>
<li><code>diffirst/3</code> should find its way into <code>library(reif)</code> :)</li>
</ol>

<hr>

<hr>

<hr>

<p><strong>EDIT:</strong> more general using a <a href="/questions/tagged/meta-predicate" class="post-tag" title="show questions tagged &#39;meta-predicate&#39;" rel="tag">meta-predicate</a> (suggested by a comment; thx!)</p>

<p>Let's generalize <code>some_dif/2</code> like so:</p>

<pre><code>:- meta_predicate some(2,?).
some(P_2, [X|Xs]) :-
   if_(call(P_2,X), true, some(P_2,Xs)).
</code></pre>

<p><code>some/2</code> can be used with reified predicates other than <code>diffirst/3</code>.</p>

<p>Here an update to <code>not_all_equal/1</code> which now uses <code>some/2</code> instead of <code>some_dif/2</code>:</p>

<pre><code>not_all_equal([X|Xs]) :-
   some(diffirst(X), Xs).
</code></pre>

<p>Above sample queries still give the same answers, so I won't show these here.</p>
How to implement a not_all_equal/1 predicate
<p>How would one implement a <code>not_all_equal/1</code> predicate, which succeeds if the given list contains at least 2 different elements and fails otherwise?</p>

<p>Here is my attempt (a not very pure one):</p>

<pre><code>not_all_equal(L) :-
    (   member(H1, L), member(H2, L), H1 \= H2 -&gt; true
    ;   list_to_set(L, S),
        not_all_equal_(S)
    ).

not_all_equal_([H|T]) :-
    (   member(H1, T), dif(H, H1)
    ;   not_all_equal_(T)
    ).
</code></pre>

<p>This however does not always have the best behaviour:</p>

<pre><code>?- not_all_equal([A,B,C]), A = a, B = b.
A = a,
B = b ;
A = a,
B = b,
dif(a, C) ;
A = a,
B = b,
dif(b, C) ;
false.
</code></pre>

<p>In this example, only the first answer should come out, the two other ones are superfluous.</p>