Как удалить все вхождения?

Question

Я пытаюсь понять, почему код 1 работает нормально, но код 2 выводит false:

remove(X,[],[]).
remove(X,[X|Y],Z):-remove(X,Y,Z). % [X|Y] is the input list
remove(X,[F|Y],[F|Z]):-remove(X,Y,Z). % code 1


remove(X,[],[]).
remove(X,[X|Y],Z):-remove(X,Y,Z). % [X|Y] is the input list
remove(X,[F|Y],Z):-remove(X,Y,[F|Z]). % code 2

Answer 1

Оба предиката, которые вы представили - code 1 и code 2 & mdash; сломаны.

И причина, по которой вы не заметили это: запросы .

---

# 1 ) Рассмотрим запрос, показанный в этот предыдущий "ответ" :

?- remove(x, [<b>x</b>,a,b,c,<b>x</b>,d], R).
R = [a,b,c,d]                      % okay

Хорошо? Да, но может быть больше ответов. Давайте нажмем ; ↵ !

;  R = [a,b,c,<b>x</b>,d]                 % BAD!
;  R = [<b>x</b>,a,b,c,d]                 % BAD!
;  R = [<b>x</b>,a,b,c,<b>x</b>,d]               % BAD!
;  false<b>.</b>                          % (no more answers)

Эти три ответа недействительны, так как каждый R содержит некоторые x.

Внизу как: Не просто смотрите некоторые ответы на запросы. Посмотрите на все ответы на вопросы!

---

# 2 ) Программы Prolog содержат различные виды предложений: факты, правила и запросы.

Запросы являются очень - если не самой важной частью вашей программы.

Запросы являются одновременно документацией и спецификацией. Самое главное, они позволяют вам делегировать «механическую» часть разработки программы процессору Prolog.

Так какие запросы писать?

• Начните с самого общего запроса:

  ?- remove(A,B,C).

• Запросы, которые вы ожидаете выполнить:

  ?- remove(x,[x,a,x,p],[a,p]).   % x is first element
  ?- remove(x,[a,x,p,x],[a,p]).   % x is last element
  ?- remove(x,[a,x,p],[a,p]).
  

• Запросы, которые вы ожидаете потерпеть неудачу

  ?- \+ (remove(x,[a,x,p],Ls), dif(Ls,[a,p])).
  

• Наземные запросы:

  ?- remove(x,[],[]).
  

• Неосновные запросы (запросы с переменными):

  ?- remove(X,[a,b,a,c,d,c,a,b],Xs).
  

Суть: Без запросов вы не пишете код, вы пишете только текст.

---

# 3 ) Теперь перейдем к исправлению code 1: посмотрите на оба рекурсивных предложения!

remove(<b>X</b>,[<b>X</b>|Y],Z) :- remove(X,Y,Z).
remove(<b>X</b>,[<b>F</b>|Y],[<b>F</b>|Z]) :- remove(X,Y,Z).

Первое правило связывает X с первым списком [X|Y]. OK!

Второе правило не X с [F|Y] или [F|Z]. BAD!

Добавив prolog-dif goal dif/2 ко второму предложению, мы можем построить это соединение.

---

# 4 ) Готово! Вот полный код для предиката remove/3:

remove(_X, [], []).
remove(X, [X|Y], Z) :-
   remove(X, Y, Z).
remove(X, [F|Y], [F|Z]) :-
   <b>dif(X, F)</b>,
   remove(X, Y, Z).

Answer 2

Рассмотрим вопрос,

?- remove(x, [x,a,b,c,x,d], R).

Проблема с кодом 2 состоит в том, что в какой-то момент после извлечения всех элементов из 2-го списка он становится пустым. На этом этапе, при рекурсии, единственный возможный выбор - это первое предложение, потому что 2-е и 3-е предложение требуют, чтобы у списка была заголовок, чего нет, потому что он пустой.

Таким образом, он пытается выполнить объединение с первым. Теперь первые 2 предиката в порядке, но последний проблематичен.

А именно, он пытается объединить [] = [d, c, b, a | _free_ ]. Что невозможно, потому что [] не является «свободной переменной»

Однако моя терминология может быть неправильной ... но я верю, что суть в этом.