Удалить дубликаты в списке (Пролог)
Я совершенно новичок в Прологе и пробую некоторые упражнения. Один из них является:
Напишите набор предикатов (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 дает несколько одинаковых решений. Чем больше повторений в списке ввода, тем больше будет решений. Что я делаю неправильно? Заранее спасибо.
9 ответов
Вы получаете несколько решений из-за отказа Пролога. Технически каждое предоставленное решение является правильным, поэтому оно генерируется. Если вы хотите, чтобы было сгенерировано только одно решение, вам придется прекратить откат в некоторый момент. Это то, для чего используется разрез Prolog. Вы можете найти, что чтение этого поможет вам с этой проблемой.
Обновление: верно. Ваш member() Предикат оценивается как true несколькими различными способами, если первая переменная находится в нескольких позициях во второй переменной.
Я использовал имя mymember() для этого предиката, чтобы не конфликтовать со встроенной GNU Prolog 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() предсказать себя. Выбор за вами.
Более простое (и, вероятно, более быстрое) решение - использовать библиотечный предикат sort/2, который удаляет дубликаты в O(n log n). Определенно работает в Yap прологе и SWIPL
Вы на правильном пути... Оставайтесь чистыми - это просто!
Используйте предикат равного равенства =/3 (ака equal_truth/3) в комбинации с if_/3, как реализовано @false в объединении Пролог для 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).
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]. % преуспевает детерминистически
Редактировать 2015-04-23
Я был вдохновлен ответом @ Людвига set/2, который выглядит так:
set([],[]).
set([H|T],[H|T1]) :- subtract(T,[H],T2), set(T2,T1).
Встроенный предикат SWI-Пролога subtract/3 может быть немонотонным, что может ограничить его использование. list_item_subtracted/3 это монотонный вариант этого:
list_item_subtracted([],_,[]).
list_item_subtracted([A|As],E,Bs1) :-
if_(A = E, Bs = Bs1, Bs1 = [A|Bs]),
list_item_subtracted(As,E,Bs).
list_setB/2 как set/2, но основан на list_item_subtracted/3 ---не 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]. % преуспевает детерминистически?- list_setB([1,2,3,4,1,2,3,4,1,2,3,1,2,1],Xs). Xs = [1,2,3,4]. % преуспевает детерминистически
Один может предпочесть один или другой, в зависимости от желаемого порядка пунктов списка в Xs,
Я думаю, что лучший способ сделать это будет:
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]
Добавляю мой ответ в эту старую ветку:
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)).
Единственное достоинство этого решения заключается в том, что оно использует только те предикаты, которые были введены к тому моменту, когда это упражнение появляется в исходном тексте.
Вы просто должны остановить возвращение Пролога.
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).
/* Remove duplicates from a list without accumulator */
our_member(A,[A|Rest]).
our_member(A, [_|Rest]):-
our_member(A, Rest).
remove_dup([],[]):-!.
remove_dup([X|Rest],L):-
our_member(X,Rest),!,
remove_dup(Rest,L).
remove_dup([X|Rest],[X|L]):-
remove_dup(Rest,L).
Это работает без вырезки, но для этого нужно больше строк и другой аргумент. Если я поменяю [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,[]).
Использование функции поддержки mymember Тим, вы можете сделать это, если порядок элементов в наборе не важен:
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]
На этот раз элементы расположены в том же порядке, в котором они отображаются в списке ввода.