Пролог: Как удалить предикат, поставляющий даже начало списка

Question

Я, безусловно, неправильно понимаю, как работает Пролог. Этот вопрос специфичен, хотя я ищу объяснение, а не прямое решение проблемы программирования; вопрос "как", а не вопрос "дай мне код".

Вот определение предиката удаления Пролога, о котором я спрашиваю.

delete(A, [A|B], B).  
delete(A, [B, C|D], [B|E]) :-  
    delete(A, [C|D], E).  

Мое недопонимание заключается в том, что мне кажется, что такой вызов, как

delete(a, [3,a,b,c,d], X).  

должен успешно вернуть [3,b,c,d] (что он и делает), но такой вызов, как

delete(a,[1,2,3,a,b,c,d], X)  

не сможет вернуть решения. Однако этот последний вызов на самом деле возвращает хорошее решение [1,2,3,b,c,d].

Причины, по-моему, таковы. (Я думаю, что сейчас мы приближаемся ко всему, что я не понимаю в Прологе.) Что касается этой части определения,

delete(A, [B, C|D], [B|E]) . . . 

похоже, что только один элемент (а именно B), предшествующий заголовку (а именно C), будет когда-либо включен в ответ. Вот почему я не могу понять, как

delete (a, [1,2,3,a,b,c,d], X)

удается вернуть ответ, который включает в себя не только 3, но также 1 и 2, как часть списка решений, но он это делает (как в [1,2,3,b,c,d]). Может кто-нибудь объяснить, как Пролог работает со списками, в этом очень специфическом сценарии, таким образом, который показывает, почему он рассматривает 1 и 2 как часть решения, а не только 3? Большое спасибо.

Answer 1

В качестве небольшой части фона мы можем рассматривать односвязный список, состоящий из двух «конструкторов»: [], пустой список и [H|T], где H - это какое-то значение, присутствующее в заголовок списка и T, хвост, список того, что осталось после H.

Здесь есть два пункта. Первый такой:

delete(A, [A|B], B).

Я бы, вероятно, сформулировал это немного иначе, как delete(Head, [Head|Tail], Tail). Это пункт, который позволяет унификации, такие как:

?- delete(3, [3,a,b,c,d], X).
X = [a, b, c, d] 

Это работает, потому что [H|T]=[3,a,b,c,d] объединит H=3 и T=[a,b,c,d]. Попробуй.

Теперь давайте на минутку подумаем о том, как Пролог выбирает предложение. На каждом этапе Пролог по сути пытается объединиться. Поэтому, когда ему присваивается delete(a, [1,2,3,a,b,c,d], X), Пролог пытается объединить delete(H, [H|T], T) с delete(a, [1,2,3,a,b,c,d], X). Это не может быть успешным, потому что a! = 1. Таким образом, Пролог делает еще одну попытку со вторым предложением, и мы оказываемся здесь:

delete(A, [B, C|D], [B|E]) :-  
    delete(A, [C|D], E).  

Теперь на примере Пролог попытается объединить заголовок предложения с delete(A=a, [B=1,C=2|D=[3,a,b,c,d]], [B=1|E]). Это успешно происходит, потому что нет особой причины, по которой A не может равняться a, B не может равняться 1, C не может равняться 2 и D не может равняться [3,a,b,c,d]. Итак, теперь Пролог переходит на delete(A, [C|D], E) и попытается вызвать delete(a, [2,3,a,b,c,d], E). Если вы включите trace в своем REPL, вы увидите это на работе:

?- trace.
true.

[trace]  ?- delete(a, [1,2,3,a,b,c,d], X).
   Call: (8) delete(a, [1, 2, 3, a, b, c, d], _3240) ? creep
   Call: (9) delete(a, [2, 3, a, b, c, d], _3498) ? creep

По второму вызову вы видите, что Пролог теперь заинтересован в поиске delete(a, [2,3,a,b,c,d], _4120), и это новая переменная, а не переменная из предыдущего вызова. Я могу заверить вас, что то же самое случится еще несколько раз, прежде чем случится что-то новое.

   Call: (9) delete(a, [2, 3, a, b, c, d], _3498) ? creep
   Call: (10) delete(a, [3, a, b, c, d], _3510) ? creep

Однако при следующем вызове можно активировать первое предложение:

   Call: (11) delete(a, [a, b, c, d], _3522) ? creep
   Exit: (11) delete(a, [a, b, c, d], [b, c, d]) ? creep

На этот раз переменная была объединена с чем-то. Это потому, что ваше первое предложение является базовым. Теперь, оглядываясь назад на свое определение, вы можете видеть, что третий аргумент во втором предложении - [B|E], что означает, что он получит значение, когда оба B и E были объединены с чем-то. Таким образом, оставшаяся часть трассировки - это выходы из этого предложения с этой переменной, объединенной с чем-то. Каждый раз, что происходит, это просто B, который был удален из списка до того, как рекурсивный вызов был добавлен к результату:

   Exit: (10) delete(a, [3, a, b, c, d], [3, b, c, d]) ? creep
   Exit: (9) delete(a, [2, 3, a, b, c, d], [2, 3, b, c, d]) ? creep
   Exit: (8) delete(a, [1, 2, 3, a, b, c, d], [1, 2, 3, b, c, d]) ? creep
X = [1, 2, 3, b, c, d] .

И вот оно у вас.

Answer 2

Давайте посмотрим, что происходит с запросом:

?- delete(a,[1,2,3,a,b,c,d], X).

Поскольку a и 1 не могут быть объединены, первое правило не выполняется. Однако второе правило совпадает с A=a, B=1, C=2 и D=[3,a,b,c,d]. Следовательно, рекурсивная цель называется:

delete(a,[2|[3,a,b,c,d]],E)

Опять же, первое правило не совпадает, потому что a отличается от 2. Второе правило снова успешно, на этот раз с A=a, B=2, C=3 и D=[a,b,c,d]. Отсюда и рекурсивный вызов:

delete(a,[3|[a,b,c,d]],E)

Еще раз, первое правило не выполняется, а второе - с A=a, B=3, C=a и D=[b,c,d]. Отсюда и рекурсивный вызов:

delete(a,[a|[b,c,d]],E)

Теперь, во главе первого правила, a=a успешно унифицировано, поэтому правило успешно выполняется с A=a, B=[b,c,d]. Возвращаясь к рекурсиям, получаем:

E=[b,c,d], B=3 therefore [B|E]=[3|[b,c,d]]=[3,b,c,d] 

E = [3,b,c,d], B=2 therefore [B|E]=[2|[3,b,c,d]]=[2,3,b,c,d] 

E = [2,3,b,c,d], B=1 therefore [B|E]=[1|[2,3,b,c,d]]=[1,2,3,b,c,d] 

Итак, Пролог говорит вам, что действительно есть решение:

?- delete(a,[1,2,3,a,b,c,d], X).
X = [1, 2, 3, b, c, d]

Теперь вы спрашиваете, есть ли другие решения, нажав ;

?- delete(a,[1,2,3,a,b,c,d], X).
X = [1, 2, 3, b, c, d] ;

Пролог возвращается к открытой точке выбора и следует рекурсивному правилу до D=[]. Следующий рекурсивный вызов не выполняется для первого правила, поскольку []=[A|B] не может быть объединено. Это также не работает для второго правила, потому что []=[B,C|D] также нельзя объединить. Таким образом, Пролог покорно сообщает, что решений больше нет:

?- delete(a,[1,2,3,a,b,c,d], X).
X = [1, 2, 3, b, c, d] ;
false.