Удаление дубликатов в прологе

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

Примечание: я прочитал другие stackoverflows, и я понимаю, как удалять дубликаты, но я не понимаю, почему мой код не работает. (Я выбрал другой подход к другим потокам стека)

Я создал предикат is_member, который, как мне кажется, работает нормально.

is_member(X, [Head,Tail]):-
    X == Head;
    is_member(X, Tail).

И затем мой предикат remove_duplicates

remove_duplicates([Head|Tail], Without):-
    is_member(Head, Tail),
    remove_duplicates(Tail, Without);
    remove_duplicates(Tail, Head).

В моей голове это имеет смысл, он проверяет, является ли голова членом хвоста, и если это так, он не добавляет его в список без,

иначе это делает.

Я явно упускаю здесь что-то банальное,

заранее спасибо


list prolog failure-slice
person user3667111    schedule 16.11.2016    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Давайте немного упростим задачу, сначала рассмотрев is_member/2.

Вы пишете это как:

is_member(X, [Head,Tail]):-
    X == Head;
    is_member(X, Tail).

Подумайте, как легко это неправильно истолковать как:

is_member(X, [Head,Tail]):-
    X == Head,
    is_member(X, Tail).

Упражнение: что я изменил?

По этой причине я рекомендую следующий макет:

is_member(X, [Head,Tail]):-
        (   X == Head
        ;   is_member(X, Tail)
        ).

А теперь перейдем к нескольким тестовым случаям!

Во-первых, всегда рекомендуется публиковать самый общий запрос. Здесь просто спрашивается: Есть ли вообще какие-нибудь решения?

?- is_member(E, Ls).
nontermination

Это не хороший знак!

Итак, давайте попробуем несколько конкретных случаев. Например, a член пустого списка?

?- is_member(a, []).
false.

Это хорошо! Это то, что мы ожидали.

Тогда является ли a членом списка [a]?

?- is_member(a, [a]).
false.

Это определенно неправильно!

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

  1. Запишите, что следует удерживать.
  2. Попробуйте выполнить самый общий запрос, чтобы узнать, сможете ли вы получить ответы от своей программы.
  3. Попробуйте конкретные тестовые примеры.
  4. Подумайте, что на самом деле означает: предикат можно использовать в нескольких направлениях, и во многих из этих случаев то, как вы описали предикат, не имеет смысла. Например, и список, и элемент уже могут быть даны, и в этом случае нечего «добавлять» или «удалять».

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

:- op(950,fy, *).
*_.

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

is_member(X, [Head,Tail]):-
        (   * X == Head
        ;   * is_member(X, Tail)
        ).

что является массовым обобщением вашей исходной программы и фактически декларативно эквивалентно:

is_member(X, [Head,Tail]) :- true.

Тестовый пример выше по-прежнему не работает с этим фрагментом, который показывает, что программа по-прежнему слишком специфична:

?- is_member(a, [a]).
false.
person mat    schedule 16.11.2016
comment
Блестящий ответ, спасибо, я приму твой совет на борт - person user3667111; 16.11.2016
comment
Также я считаю, что исправил ошибку. С: is_member(X, [Head|_]):- X == Head. - person user3667111; 16.11.2016
comment
Это исправляет конкретный тестовый пример is_member(a, [a]), да. Однако попробуйте небольшое обобщение тестового примера: ?- is_member(a, [X]). Это все равно не удается. В целом, я могу только рекомендовать избегать немонотонных предикатов, таких как (==)/2. Их можно безопасно использовать только в очень особых ситуациях и давать неправильные ответы в более общих случаях. Чтобы выразить, что два термина равны, используйте (=)/2. Он корректно работает во всех направлениях. - person mat; 16.11.2016
comment
не должен is_member (a, [X]). неудача? - person user3667111; 16.11.2016
comment
Подумайте: предположим, is_member(a, [X]) терпит неудачу. Тогда это будет означать, если мы прочитаем его декларативно, что для этого запроса нет никаких решений. Однако мы уже установили, что X = a - это решение, потому что is_member(a, [a]) должно быть успешным! Следовательно, поскольку более конкретный случай is_member(a, [a]) завершается успешно, более общий случай is_mumber(a, [X]) определенно не должен завершаться. В противном случае это будет означать, что программа выдает неправильные ответы. - person mat; 16.11.2016
comment
Я прочитал еще немного и обнаружил, что = лучше, чем == - person user3667111; 17.11.2016
comment
Лучший способ - сохранить все, что возможно для сопоставления с образцом: в этом случае вам не нужны ни один из этих предикатов (ни (=)/2 , ни (==)/2), потому что вы можете написать : member_list(E, [E|_]). как простой факт, который является правдой: E является членом каждого списка, имеющего форму [E|_]. Это просто выражает то, что верно, и работает во всех направлениях, для генерации, тестирования и т. Д. - person mat; 17.11.2016