Рекурсия в прологе, привязка к переменной

Question

У меня есть рекурсивное предложение, которое принимает 2 списка, при каждом вызове рекурсии я удаляю один элемент из списка и связываю этот новый список (с удаленным элементом) с новой переменной.

Это сделано правильно, если я напишу эту переменную. Но когда у меня есть модель, она возвращает обратно, делая последнюю привязку (список, который мне нужен) к этой переменной, отмененной предыдущей привязкой.

Я попытался воспроизвести ситуацию в этом небольшом фрагменте кода:

test([],Test,Result).
test([H|T],Test,Result):-
    member(H,Test),
    delete(Test,H,Test1),
    write(Test1),
    write('\n'),
    test(T,Test1,Test1).
test([H|T],Test,Test1):-
    test(T,Test,Test1). 

?- test([1,2,3],[5,2,4,6,1],R).

Я понимаю, что результат должен быть в заголовке предложения следующим образом:

test([H|T],Test,Test1)....

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

Какие-нибудь подсказки, как справиться с этим?

Кроме того, я довольно новичок в прологе, просто прочитал несколько уроков в Интернете и выполнил простые упражнения

Answer 1

filter([], []).

filter([Head|Tail], [Head|Result]) :-
    sometest(Head),
    filter(Tail, Result).

filter([Head|Tail], Result) :-
    \+ sometest(Head),
    filter(Tail, Result).

Теперь, чтобы увидеть, как это работает, попробуйте выполнить вызов trace/0 перед запуском предиката filter/2, который детализирует выполнение (по крайней мере, на swi pl):

Рассмотрим этот предикат sometest/1:

sometest(N) :- N mod 2 =:= 0.

Теперь давайте запустим режим трассировки:

?- trace.
true.

А теперь давайте назовем ваш предикат:

[trace] ?- filter([1, 2, 3], R).
   Call: (6) filter([1, 2, 3], _G522) ? creep
   Call: (7) sometest(1) ? creep
   Call: (8) 1 mod 2=:=0 ? creep
   Fail: (8) 1 mod 2=:=0 ? creep
   Fail: (7) sometest(1) ? creep
   Redo: (6) filter([1, 2, 3], _G522) ? creep
   Call: (7) sometest(1) ? creep
   Call: (8) 1 mod 2=:=0 ? creep
   Fail: (8) 1 mod 2=:=0 ? creep
   Fail: (7) sometest(1) ? creep
   Call: (7) filter([2, 3], _G522) ? creep
   Call: (8) sometest(2) ? creep
   Call: (9) 2 mod 2=:=0 ? creep
   Exit: (9) 2 mod 2=:=0 ? creep
   Exit: (8) sometest(2) ? creep
   Call: (8) filter([3], _G597) ? creep
   Call: (9) sometest(3) ? creep
   Call: (10) 3 mod 2=:=0 ? creep
   Fail: (10) 3 mod 2=:=0 ? creep
   Fail: (9) sometest(3) ? creep
   Redo: (8) filter([3], _G597) ? creep
   Call: (9) sometest(3) ? creep
   Call: (10) 3 mod 2=:=0 ? creep
   Fail: (10) 3 mod 2=:=0 ? creep
   Fail: (9) sometest(3) ? creep
   Call: (9) filter([], _G597) ? creep
   Exit: (9) filter([], []) ? creep
   Exit: (8) filter([3], []) ? creep
   Exit: (7) filter([2, 3], [2]) ? creep
   Exit: (6) filter([1, 2, 3], [2]) ? creep
R = [2] ;
false.

Если вы потратите время, чтобы понять, что здесь делает пролог, это в основном так: вы бежите, пока не находите предикат истинным (базовый случай, здесь, filter([], [])), а затем строите свой список в обратном направлении.в зависимости от того, какой путь вы выбрали, чтобы достичь этого случая.Здесь это означает, что если sometest было правдой, вы добавляете Head в Result, если нет, то нет.

Обратите внимание, что вам нужно использовать \+ condition (что означает, что условие не можетво втором пункте, как я, или используйте cut в первом, как указано ниже, в противном случае соответствующий Head все равно будет проходить через второе предложение во время возврата:

filter([], []).

filter([Head|Tail], [Head|Result]) :-
    sometest(Head),
    !,
    filter(Tail, Result).

filter([Head|Tail], Result) :-
    filter(Tail, Result).

Теперь, если вы используетеswi-pl, обратите внимание, что вы можете напрямую использовать include/3 для достижения того, что вы хотите (это, безусловно, присутствует и в других реализациях под этим или другим именем):

?- include(sometest, [1, 2, 3, 4, 5], R).
R = [2, 4].

Надеюсь, это помогло.