Remover duplicatas na lista (Prolog)

Eu sou completamente novo em Prolog e tentando alguns exercícios. Um deles é:

Escreva um conjunto de predicados (InList, OutList) que toma como input uma lista arbitrária e retorna uma lista na qual cada elemento da lista de input aparece apenas uma vez.

Aqui está a minha solução:

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). 

Eu não estou autorizado a usar qualquer um dos predicados embutidos (seria melhor mesmo não usar not/1 ). O problema é que o set/2 fornece várias soluções iguais . Quanto mais repetições na lista de input, mais soluções resultarão. O que estou fazendo de errado? Desde já, obrigado.

Você está obtendo várias soluções devido ao retrocesso do Prolog. Tecnicamente, cada solução fornecida está correta, e é por isso que está sendo gerada. Se você quiser que apenas uma solução seja gerada, terá que parar o retrocesso em algum momento. É para isso que o corte Prolog é usado. Você pode achar que ler sobre isso irá ajudá-lo com esse problema.

Atualização: certo. Seu predicado member() está avaliando como true de várias maneiras diferentes se a primeira variável estiver em múltiplas posições na segunda variável.

Eu usei o nome mymember() para este predicado, para não entrar em conflito com o predicado mymember() GNU Prolog member() . Minha base de conhecimento agora é assim:

 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). 

Então, mymember(1, [1, 1, 1]). avalia como true de três maneiras diferentes:

 | ?- mymember(1, [1, 1, 1]). true ? a true true no 

Se você quiser ter apenas uma resposta, você terá que usar um corte. Alterando a primeira definição de mymember() para isso:

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

Resolve seu problema.

Além disso, você pode evitar not() completamente, se desejar, definindo um predicado notamember() . A escolha é sua.

Você está no caminho certo … Fique puro – é fácil!

Use predicado de igualdade reificado =/3 (aka equal_truth/3 ) em combinação com if_/3 , conforme implementado por @false na união Prolog para 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 ). 

Com base nesses predicados, criamos um predicado de associação reificado list_item_isMember/3 . É semanticamente equivalente com memberd_truth/3 by @false. Nós rearranjamos a ordem dos argumentos para que a lista seja o primeiro argumento. Isso habilita a indexação do primeiro argumento que evita deixar pontos de escolha inúteis por trás, como o memberd_truth/3 criaria.

 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). 

Uma consulta simples mostra que todas as respostas redundantes foram eliminadas e que o objective é bem-sucedido sem deixar pontos de escolha :

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

Editar 2015-04-23

Eu fui inspirado pela resposta de @ Ludwig de set/2 , que é assim:

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

O predicado subtract/3 incorporado do SWI-Prolog pode ser não-monótono, o que pode restringir seu uso. list_item_subtracted/3 é uma variante monótona dele:

 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 é como set/2 , mas é baseado em 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). 

As seguintes consultas comparam list_set/2 e 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].  % consegue deterministicamente
 ? - list_setB ([1,2,3,4,1,2,3,4,1,2,3,1,2,1], Xs).
 Xs = [1,2,3,4].  % consegue deterministicamente

Um pode preferir um ou outro, dependendo da ordem desejada de itens da lista em Xs .

Uma solução mais simples (e provavelmente mais rápida) é usar o predicado / 2 da biblioteca que remove duplicatas em O (n log n). Definitivamente trabalha em YAP prólogo e SWIPL

Eu acho que uma maneira melhor de fazer isso seria:

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

Então, por exemplo ?- set([1,4,1,1,3,4],S) dá a você como saída:

 S = [1, 4, 3] 

Adicionando minha resposta a este segmento antigo:

 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)). 

A única virtude dessa solução é que ela usa apenas os predicados que foram introduzidos no ponto em que esse exercício aparece no texto original .

Isso funciona sem corte, mas precisa de mais linhas e outro argumento. Se eu mudar o [H2 | T2] para S na linha três, ele produzirá vários resultados. Eu não entendo porque.

 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,[]). 

Você apenas tem que parar o retrocesso do 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). 

Usando a function de suporte mymember do Tim, você pode fazer isso se a ordem dos elementos no conjunto não for importante:

 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]. 

Então, por exemplo ?- mkset([1,4,1,1,3,4],S) dá a você como saída:

 S = [1, 3, 4] 

mas, se você quiser um conjunto com os elementos ordenados como na lista, você pode usar:

 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,[]). 

Esta solução, com a mesma input do exemplo anterior, dá a você:

 S = [1, 4, 3] 

Desta vez, os elementos estão na mesma ordem em que aparecem na lista de input.