Prolog Does the order of recursion matter?

When you optimize anything, make sure to measure first! (most of us tend to forget this....)

When you optimize Prolog, look out for the following:

• Tail recursion tends to do better (so there goes your "before or after series of statements" question);
• Avoid creating choice points you don't need (this depends on the Prolog implementation)
• Use an optimal algorithm (as in, don't traverse a list twice if you don't have to).

A solution that is "optimized" for a more or less standard Prolog implementation will look maybe a bit different. I will name it list_uniq (in analogy to the command-line uniq tool):

list_uniq([], []). % Base case
list_uniq([H|T], U) :-
    list_uniq_1(T, H, U). % Helper predicate

list_uniq_1([], X, [X]).
list_uniq_1([H|T], X, U) :-
    (   H == X
    ->  list_uniq_1(T, X, U)
    ;   [X|U1] = U,
        list_uniq_1(T, H, U1)
    ).

It is different from the reduce0/2 by @CapelliC because it uses lagging to avoid the inherent non-determinism of [X|Xs] and [X,X|Xs] in the first argument.

Now to the claim that it is "optimized":

• It traverses the list exactly once (no need for reversing)
• It it tail-recursive
• It does not create and discard choice points

You will get the same 12 inferences as @CapelliC, and if you then use a somewhat longer list, you will start to see differences:

?- length(As, 100000), maplist(=(a), As),
   length(Bs, 100000), maplist(=(b), Bs),
   length(Cs, 100000), maplist(=(c), Cs),
   append([As, Bs, Cs, As, Cs, Bs], L),
   time(list_uniq(L, U)).
% 600,006 inferences, 0.057 CPU in 0.057 seconds (100% CPU, 10499893 Lips)
As = [a, a, a, a, a, a, a, a, a|...],
Bs = [b, b, b, b, b, b, b, b, b|...],
Cs = [c, c, c, c, c, c, c, c, c|...],
L = [a, a, a, a, a, a, a, a, a|...],
U = [a, b, c, a, c, b].

The same query with reduce0, reduce1, reduce2 from @CapelliC's answer:

% reduce0(L, U)
% 600,001 inferences, 0.125 CPU in 0.125 seconds (100% CPU, 4813955 Lips)
% reduce1(L, U)
% 1,200,012 inferences, 0.393 CPU in 0.394 seconds (100% CPU, 3050034 Lips)
% reduce2(L, U)
% 2,400,004 inferences, 0.859 CPU in 0.861 seconds (100% CPU, 2792792 Lips)

So, creating and discarding choice points with cuts (!) has a price, too.

However, list_uniq/2, as it stands, can be wrong for queries where the first argument is not ground:

?- list_uniq([a,B], [a,b]).
B = b. % OK

?- list_uniq([a,A], [a]).
false. % WRONG!

reduce0/2 and reduce1/2 can be wrong, too:

?- reduce0([a,B], [a,b]).
false.

?- reduce1([a,B], [a,b]).
false.

As for reduce2/2, I am not sure about this one:

?- reduce2([a,A], [a,a]).
A = a.

Instead, using the definition of if_/3 from this answer:

list_uniq_d([], []). % Base case
list_uniq_d([H|T], U) :-
    list_uniq_d_1(T, H, U). % Helper predicate

list_uniq_d_1([], X, [X]).
list_uniq_d_1([H|T], X, U) :-
    if_(H = X,
        list_uniq_d_1(T, H, U),
        (   [X|U1] = U,
            list_uniq_d_1(T, H, U1)
        )
    ).

With it:

?- list_uniq_d([a,a,a,b], U).
U = [a, b].

?- list_uniq_d([a,a,a,b,b], U).
U = [a, b].

?- list_uniq_d([a,A], U).
A = a,
U = [a] ;
U = [a, A],
dif(A, a).

?- list_uniq_d([a,A], [a]).
A = a ;
false. % Dangling choice point

?- list_uniq_d([a,A], [a,a]).
false.

?- list_uniq_d([a,B], [a,b]).
B = b.

?- list_uniq_d([a,A], [a,a]).
false.

It takes longer, but the predicate seems to be correct. With the same query as used for the other timings:

% 3,000,007 inferences, 1.140 CPU in 1.141 seconds (100% CPU, 2631644 Lips)