Удалить дубликаты в списке (Prolog)

Я совершенно новичок в Prolog и пробую некоторые упражнения. Один из них:

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

Вот мое решение:

member(X,[X|_]).
member(X,[_|T]) :- member(X,T).

set([],[]).
set([H|T],[H|Out]) :-
    not(member(H,T)),
    set(T,Out).
set([H|T],Out) :-
    member(H,T),
    set(T,Out).

Мне не разрешено использовать какие-либо встроенные предикаты (лучше даже не использовать not/1). Проблема в том, что set/2 дает несколько одинаковых решений. Чем больше повторений в списке входных данных, тем больше решений. Что я делаю не так? Спасибо заранее.

Ответы

Ответ 1

Вы получаете многократные решения из-за обратного отслеживания Prolog. Технически каждое предлагаемое решение является правильным, и именно поэтому оно генерируется. Если вы хотите создать только одно решение, в какой-то момент вам придется прекратить откат. Для этого используется Prolog cut. Вы можете обнаружить, что чтение на этом поможет вам с этой проблемой.

Обновление: правильно. Предикат member() оценивается как true несколькими способами, если первая переменная находится в нескольких положениях во второй переменной.

Я использовал имя mymember() для этого предиката, чтобы не вступать в конфликт с GNU Prolog builtin member() предикат. Теперь моя база знаний выглядит следующим образом:

mymember(X,[X|_]).
mymember(X,[_|T]) :- mymember(X,T).

not(A) :- \+ call(A).

set([],[]).
set([H|T],[H|Out]) :-
    not(mymember(H,T)),
    set(T,Out).
set([H|T],Out) :-
    mymember(H,T),
    set(T,Out).

Итак, mymember(1, [1, 1, 1]). оценивается как true тремя различными способами:

| ?- mymember(1, [1, 1, 1]).

true ? a

true

true

no

Если вы хотите иметь только один ответ, вам придется использовать разрез. Изменение первого определения mymember() на следующее:

mymember(X,[X|_]) :- !.

Решает вашу проблему.

Кроме того, вы можете избежать not() вообще, если хотите, путем определения предиката notamember() самостоятельно. Выбор за вами.

Ответ 2

Вы на правильном пути... Оставайтесь чистыми ---it просто!

Используйте уточненные предикаты равенства =/3 и dif/3 в сочетании с if_/3, как это реализовано в объединении Prolog для AUBUC:

=(X, Y, R) :- X == Y,    !, R = true.
=(X, Y, R) :- ?=(X, Y),  !, R = false. % syntactically different
=(X, Y, R) :- X \= Y,    !, R = false. % semantically different
=(X, Y, R) :- R == true, !, X = Y.
=(X, X, true).
=(X, Y, false) :-
   dif(X, Y).

% dif/3 is defined like (=)/3
dif(X, Y, R) :- X == Y,    !, R = false.
dif(X, Y, R) :- ?=(X, Y),  !, R = true. % syntactically different
dif(X, Y, R) :- X \= Y,    !, R = true. % semantically different
dif(X, Y, R) :- R == true, !, X \= Y.
dif(X, Y, true) :-         % succeed first!
   dif(X, Y).
dif(X, X, false).

if_(C_1, Then_0, Else_0) :-
   call(C_1, Truth),
   functor(Truth,_,0),  % safety check
   ( Truth == true -> Then_0 ; Truth == false, Else_0 ).

На основе этих предикатов мы строим предикат членства list_item_isMember/3. Семантически эквивалентен memberd_truth/3 от @false. Мы переставляем порядок аргументов, чтобы список был первым аргументом. Это позволяет индексировать по первому аргументу, что предотвращает оставление бесполезных точек выбора, как memberd_truth/3.

list_item_isMember([],_,false).
list_item_isMember([X|Xs],E,Truth) :-
   if_(E = X, Truth = true, list_item_isMember(Xs,E,Truth)).

list_set([],[]).
list_set([X|Xs],Ys) :-
    if_(list_item_isMember(Xs,X), Ys = Ys0, Ys = [X|Ys0]),
    list_set(Xs,Ys0).

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

?- list_set([1,2,3,4,1,2,3,4,1,2,3,1,2,1],Xs).
Xs = [4,3,2,1].                         % succeeds deterministically

Редактировать 2015-04-23

Я был вдохновлен @Ludwig ответом set/2, который выглядит так:

set([],[]).
set([H|T],[H|T1]) :- subtract(T,[H],T2), set(T2,T1).

Встроенный предикат subtract/3 SWI-Prolog subtract/3 может быть немонотонным, что может ограничивать его использование. list_item_subtracted/3 является монотонным вариантом этого:

list_item_subtracted([],_,[]).
list_item_subtracted([A|As],E,Bs1) :-
    if_(dif(A,E), Bs1 = [A|Bs], Bs = Bs1),
    list_item_subtracted(As,E,Bs).

list_setB/2 подобен set/2, но основан на list_item_subtracted/3 ---not subtract/3:

list_setB([],[]).
list_setB([X|Xs1],[X|Ys]) :-
    list_item_subtracted(Xs1,X,Xs),
    list_setB(Xs,Ys).

Следующие запросы сравнивают list_set/2 и list_setB/2:

?- list_set([1,2,3,4,1,2,3,4,1,2,3,1,2,1], Xs).
Xs = [4,3,2,1].                          % succeeds deterministically
?- list_setB([1,2,3,4,1,2,3,4,1,2,3,1,2,1],Xs).
Xs = [1,2,3,4].                          % succeeds deterministically

?- list_set(Xs,[a,b]).
   Xs = [a,b]
;  Xs = [a,b,b]
;  Xs = [a,b,b,b] 
...                                      % does not terminate universally
?- list_setB(Xs,[a,b]).
   Xs = [a,b]
;  Xs = [a,b,b]
;  Xs = [a,b,b,b]
...                                      % does not terminate universally

Ответ 3

Более простое (и, скорее всего, более быстрое) решение - использовать библиотечный предикат sort/2, который удаляет дубликаты в O (n log n). Определенно работает в прологе Yap и SWIPL

Ответ 4

Я думаю, что лучший способ сделать это:

set([], []).
set([H|T], [H|T1]) :- subtract(T, [H], T2), set(T2, T1).

Итак, например, ?- set([1,4,1,1,3,4],S) дает вам вывод:

S = [1, 4, 3]

Ответ 5

Добавление моего ответа на этот старый поток:

notmember(_,[]).
notmember(X,[H|T]):-X\=H,notmember(X,T).

set([],[]).
set([H|T],S):-set(T,S),member(H,S).
set([H|T],[H|S]):-set(T,S),not(member(H,S)).

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

Ответ 6

Это работает без вырезания, но ему нужно больше строк и другой аргумент. Если я изменил [H2 | T2] на S в третьей строке, он даст несколько результатов. Я не понимаю, почему.

setb([],[],_).
setb([H|T],[H|T2],A) :- not(member(H,A)),setb(T,T2,[H|A]).
setb([H|T],[H2|T2],A) :- member(H,A),setb(T,[H2|T2],A).
setb([H|T],[],A) :- member(H,A),setb(T,[],A).
set(L,S) :- setb(L,S,[]).

Ответ 7

Вам просто нужно остановить обратный отсчет Prolog.

enter code here
member(X,[X|_]):- !.
member(X,[_|T]) :- member(X,T).

set([],[]).
set([H|T],[H|Out]) :-
   not(member(H,T)),
   !,
set(T,Out).
set([H|T],Out) :-
   member(H,T),
   set(T,Out).

Ответ 8

Используя вспомогательную функцию mymember для Tim, вы можете сделать это, если порядок элементов в наборе не важен:

mymember(X,[X|_]).
mymember(X,[_|T]) :- mymember(X,T).

mkset([],[]).
mkset([T|C], S) :- mymember(T,C),!, mkset(C,S).
mkset([T|C], S) :- mkset(C,Z), S=[T|Z].

Итак, например, ?- mkset([1,4,1,1,3,4],S) дает вам результат:

S = [1, 3, 4]

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

mkset2([],[], _).
mkset2([T|C], S, D) :- mkset2(C,Z,[T|D]), ((mymember(T,D), S=Z,!) ; S=[T|Z]).
mkset(L, S) :- mkset2(L,S,[]).

Это решение, с тем же вводом предыдущего примера, дает вам:

S = [1, 4, 3]

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