Почему Пролог находит много решений при фильтрации списка?

Question

Я написал предикат, который фильтрует список всех чисел ниже 6, но пролог находит более одного решения.

Предикат выглядит так:

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

Я спрашиваю это так: ?- sift([1, 7, 2, 13], X).

Что приводит к:

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

Iожидаемый X = [7, 13], так почему же Пролог находит все эти дополнительные ответы?

Answer 1

Backtracking.

Когда вы набираете sift([1,10], X)., Prolog может сопоставлять паттерны как sift([H | T], [H | Res]), так и sift([_ | T], Res). Это означает, что Пролог оставляет точку выбора , выбирая одну опцию и затем возвращаясь к другому другому предикату.

Пролог соответствует первому предикату sift([7, 2, 13], [H | Res]), далее вызывая sift([1, 13], Res).

Однако, он также соответствует второму предикату, sift([_ | [2, 13]], Res) и вернется к этому позже, пропустив 7.

Мы можем исправить это, пропустив элемент, только если мы хотим отфильтроватьit out.

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

Это дает:

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

Альтернативой является использование Пролога , если :

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

Этот предикатговорит «возьми список и потенциальный ответ. Если первый элемент равен или больше шести, первый элемент списка и ответ должны совпадать, а отфильтрованный хвост должен совпадать с хвостом ответа. В противном случае хвост списка должен быть в состоянии дать полный ответ ».

Это позволяет избежать обратного отслеживания и прекратит поиск решения после первого.

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

Посмотрите на оба предиката с включенным trace. для дальнейшего описания.