Определите предикат maxlist (List, Max), чтобы Max был наибольшим числом в списке чисел List

Question

Упражнение 3.17 «Прологическое программирование для искусственного интеллекта» Иван Бтрако

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

1. Возьмите первый и второй элементы, сравните их и получите максимум
2. Возьмите этот максимум и сравните его с третьим элементом в список и, если он больше, переписать максимум и повторить до список пуст.

Однако я не понимаю данное решение, и я попытался отследить его и потерпел неудачу. У меня проблемы с отображением MaxRest в Max & в базовом случае. Кроме того, я не понимаю, почему пролог не выдает ошибку при объединении [X, Y | Rest] с [Y | T]. Пример [1,3, [7,2]] с [3 | [7,2]].

max(X,Y,X):-
   X>=Y.
max(X,Y,Y):-
  X<Y.

maxlist( [X], X). %what does this line do?
maxlist( [X,Y|Rest], Max):- 
  maxlist( [Y|Rest], MaxRest),
  max(X, MaxRest,Max).

Любая трассировка помощи будет принята с благодарностью.

Answer 1

Предикаты Пролога определяют отношения в терминах логики, которая говорит, что глава предложения истинна, если (:-) тело истинно.Это поможет вам правильно прочитать предикат:

max(X,Y,X):-
   X>=Y.

Это говорит о том, что:

X - это максимум X и Y , если X >= Y верно.

Аналогичным образом вы можете прочитать предложение для max(X,Y,Y).

Теперь посмотрите на:

maxlist( [X], X).

Здесь мыпереопределив maxlist, чтобы обозначить максимальное значение списка.В данном конкретном пункте говорится, что:

X является максимальным значением списка [X].

Нет условий , если (:-) в этом случае, так как никакие другие условия не нужны для установления этого правила.

Тогда есть рекурсивное предложение:

maxlist( [X,Y|Rest], Max):- 
  maxlist( [Y|Rest], MaxRest),
  max(X, MaxRest,Max).

Это говорит о том, что:

Max - максимальное значение списка [X,Y|Rest] , если MaxRest - максимум списка [Y|Rest], а Max - максимальное значение X и MaxRest.

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

Я не понимаю, почему пролог не выдает ошибку при объединении [X,Y|Rest] с [Y|T]

Я не понимаю этот комментарий.Нигде в вашем коде Пролог не пытается объединить эти два термина.Ваши примерные термины [1,3,[7,2]] и [3|[7,2]] не объединятся, потому что первый - это список из трех элементов: 1, 3 и [7,2], тогда как другой - это список из 3 элементов: 3, 7 и2. Чтобы два списка можно было различить, он не только должен иметь одинаковую длину, но и каждый соответствующий термин в списке должен быть одинаковым.

Что бы тогда делало [X,Y|Rest] и [Y|T] единичными?Вы можете написать [X,Y|Rest] как [X|[Y|Rest]], что позволяет легко увидеть, что они недопустимы, если выполняются следующие условия:

X = Y,
[Y|Rest] = T

Другими словами, списки должны иметь (а) как минимумдва элемента, и (б) первые два элемента одинаковы.

Answer 2

Поскольку вы понимаете max/3, это не будет объяснено.

maxlist( [X], X). %what does this line do?
maxlist( [X,Y|Rest], Max):- 
  maxlist( [Y|Rest], MaxRest),
  max(X, MaxRest,Max).

Это классический шаблон рекурсивного списка, который выполняет рекурсию перед обработкой элемента.Обычный шаблон рекурсивного списка с хвостовым вызовом -

process_list([H|T],R) :-
  process_item(H,R),
  process_list(T,R).
process_list([],R).

, но здесь это

process_list([H|T],R) :-
  process_list(T,R),
  process_item(H,R).
process_list([],R).

, где элемент обрабатывается после повторения в списке.

Также это обрабатывает два элемента одновременно, то есть

 [H1,H2|T]

, потому что для сравнения нужны два элемента.

Этот

maxlist( [X,Y|Rest], Max):- 
  maxlist( [Y|Rest], MaxRest),

просто снимает значения сперечислите и поместите их в стек, чтобы при возврате он имел одно значение для сравнения, то есть MaxRest, что является максимумом всех значений, которые были в Rest, и текущее значение X.Вы можете подумать, что это должно быть Y, но когда в списке есть только один элемент, список на самом деле [Y|[]], который действительно [Y] с совпадениями с шаблоном в этом пункте maxlist( [X], X)..

Так что же делает maxlist( [X], X).?Обычным базовым случаем для списка является просто predicate([],R). для возврата списка, но в этом случае в качестве значения должно быть возвращено только одно последнее значение, поэтому это вынимает X из списка в первом параметре и возвращает егов качестве значения во втором параметре, так что оно становится MaxRest, что является максимальным значением, когда в списке есть только один элемент.Когда выполняется max(X, MaxRest,Max), он имеет значение для MaxRest возврата из обратного отслеживания и X в стеке при деконструкции списка.В результате получается Max, который возвращается как третий параметр в maxlist( [X,Y|Rest], Max), который становится значением для MaxRest при повторном возврате.

Задавать вопросы, если это не имеет смысла.

---

Я не понимаю, почему Пролог не выдает ошибку при объединении [X, Y | Rest] с [Y | Rest].

Пример [1,3, [7,2]] с [3 | [7,2]]

На самом деле

?- [1,3,[7,2]] = [3|[7,2]].
false.

, так что пока вашпример дает ошибку, это не то, что делается с

[X,Y|Rest] and [Y|Rest]

Начните со списка [1,2,3,4] и объедините его с [X,Y|Rest]

?- [1,2,3,4] = [X,Y|Rest].
X = 1,
Y = 2,
Rest = [3, 4].

Обратите внимание, что [Y|Rest] тогда будет [2|[3,4]].

?- [1,2,3,4] = [X,Y|Rest],A = [Y|Rest].
X = 1,
Y = 2,
Rest = [3, 4],
A = [2, 3, 4].

Не пытайтесь объединить [X,Y|Rest] с [Y|Rest], а вместо этого объедините Rest с Rest и Y с Y, X хранится в стеке, ноне передается на следующий уровень стекафрейма .

Если вы действительно хотите понять список, используйте его, чтобы увидеть их

?- write_term([1,2,3,4],[dotlists(true)]).
.(1,.(2,.(3,.(4,[]))))
true.

Если у вас есть версия 4книгу см. рис. 3.1 на стр. 61.