Why does Prolog find to many solutions when filtering a list?

Question

I have written a predicate which filters a list of all numbers below 6, but prolog finds more than one solution.

The predicate looks like this:

sift([], []).
sift([H | T], [H | Res]):- H > 6,
    sift(T, Res).
sift([_ | T], Res):-
    sift(T, Res).

I am asking it this: ?- sift([1, 7, 2, 13], X).

Which results in:

X = [7, 13]
X = [7]
X = [13]
X = []

I only expected X = [7, 13], so why does Prolog find all these extra answers?

Answer 1

Backtracking.

When you type sift([1,10], X)., Prolog is able to pattern match both sift([H | T], [H | Res]) and sift([_ | T], Res). This means that Prolog leaves a choicepoint, choosing one option and then coming back to other other predicate later.

Prolog matches the first predicate, sift([7, 2, 13], [H | Res]), further calling sift([2, 13], Res).

However, it also matches the second predicate, sift([_ | [2, 13]], Res) and will back-track to this later, skipping 7.

We can fix this by only skipping the element if we want to filter it out.

sift([], []).
sift([H | T], [H | Res]) :-
    H >= 6,
    sift(T, Res).
sift([H | T], Res) :-
    H < 6,
    sift(T, Res).

This gives:

?- sift([1, 7, 2, 13], X).
X = [7, 13] ;
false.

An alternative is to use a Prolog if:

sift2([], []).
sift2([H | T], [H2 | T2]) :-
    H >= 6 ->
    (H2 = H,
    sift2(T, T2)
    ); sift2(T, [H2 | T2]).

This predicate says 'take a list and a potential answer. If the first element is equal to or greater than six, the first element of the list and the answer should match, and the filtered tail should match the tail of the answer. Otherwise, the tail of the list needs to be able to produce the whole answer'.

This avoids backtracking and will stop searching for a solution after the first.

?- sift2([1, 7, 2, 13], X).
X = [7, 13].

Take a look at both predicates with trace. turned on for a further description.