0

我想从给定列表中删除所有重复项。

考虑以下代码：

% check if the given element is in the given list 
member(Element,[Element|_]).
member(Element,[_|List]):-member(Element, List).


% append the element only if it's NOT already in the input list 
appending([],X,X).
appending([H|T1],Elem,[H|T2]):- appending(T1,Elem,T2).

appendHlp(ListOrg,Res,Addme):- not(member(Addme,ListOrg)),
                   appending(ListOrg,[Addme],Res).
appendHlp(ListOrg,Res,Addme):- member(Addme,ListOrg),
                   Res=ListOrg.

% remove duplicates 
setify([H|T],Set):-appendHlp(Set,Output,H),
           setify(T,Output).
setify([],_).

当我运行代码时：

1 ?- setify([1,2,3,3,2],X).

输出是：

X = [1, 2, 3|_G2725]

我怎样才能去掉尾巴？

谢谢

4

5 回答 5

4

如果你使用 SWI-Prolog 你可以写

:- use_module(library(lambda)).

setify(L, Set) :-
    foldl(\X^Y^Z^(memberchk(X, Y)->Z=Y; append(Y, [X], Z)), L, [], Set).
于 2013-02-19T22:12:05.670 回答
4

您的问题（表面上）是 member/2 使用未实例化的变量调用，然后“构建”您在输出中看到的部分列表

[trace]  ?- setify([1],X).
   Call: (6) setify([1], _G340) ? creep
   Call: (7) appendHlp(_G340, _G416, 1) ? creep
^  Call: (8) not(member(1, _G340)) ? creep
^  Fail: (8) not(user:member(1, _G340)) ? creep
   Redo: (7) appendHlp(_G340, _G416, 1) ? creep
   Call: (8) lists:member(1, _G340) ? creep
   Exit: (8) lists:member(1, [1|_G409]) ? creep
   Call: (8) _G418=[1|_G409] ? creep
   Exit: (8) [1|_G409]=[1|_G409] ? creep
   Exit: (7) appendHlp([1|_G409], [1|_G409], 1) ? creep
   Call: (7) setify([], [1|_G409]) ? creep
   Exit: (7) setify([], [1|_G409]) ? creep
   Exit: (6) setify([1], [1|_G409]) ? creep
X = [1|_G409] .

这并不容易纠正，因为您使用一种非常复杂的方式来完成一项非常简单的任务。例如，如果您将 member 替换为 memberchk 或member(Addme,ListOrg)，[Addme]=ListOrg您的程序将失败。

我会建议采取一些 Prolog 社区接受的编程习惯。例如，尝试将输入参数放在输出之前。这并不总是可能的，因为 Prolog 是关系型的，但有助于编写更好的代码。

当然， sort/2 会高效且轻松地生成输出。

编辑解决方案可以非常紧凑，在基本的 Prolog 中：

setify([E|R], U) :- memberchk(E, R), !, setify(R, U).
setify([E|R], [E|U]) :- setify(R, U).
setify([], []).

3 ?- setify([1,1,1,2,1,1],L).
L = [2, 1].
于 2013-02-19T17:21:20.240 回答
2

正如 CapelliC 所说，您可以使用sort/2- 它将删除重复项并对元素进行排序。集合通常以排序形式表示。

如果您需要保留元素的原始顺序，这里不是非常有效但非常简单的实现：

setify([H|T], OldSet, NewSet) :-
    ( \+ memberchk(H, OldSet) ->
        append(OldSet, [H], CurrentSet),
        setify(T, CurrentSet, NewSet)
    ;
        setify(T, OldSet, NewSet)
    ).
setify([], OldSet, OldSet).

setify(List, Set) :-
    setify(List, [], Set).
于 2013-02-19T20:01:13.547 回答
1

另一种使用尾递归和单个谓词来完成整个事情的解决方案，但不保留原始顺序。

% Finish recursing / empty list
remdup([], []).

% Recurse tail first, don't add H to the list if already included
remdup([H|T], NoDups) :-
    remdup(T, NoDups),
    member(H, NoDups).

% Second rule failed, so H must be unique - add to NoDups list
remdup([H|T], [H|NoDups]) :-
    remdup(T, NoDups).


?- remdup([1,2,2,3,2,1,3,3,3,2],X).
X = [1, 3, 2] .
于 2013-02-21T18:48:46.540 回答
1

我对Prolog很陌生。这是我想出的删除重复元素的解决方案。希望这可以帮助。

% Define negation of "member"
notmember(X,L) :- not( member(X,L) ).

% Remove duplicates terminal case
removeDups( [], R, R).

% Case where the head element is a member of tail. Drop it.
removeDups( [H|T], R, A ) :- member(H,T) , removeDups( T, R, A ).

% Case where head element is unique
removeDups([H|T], R, A ) :- notmember(H,T), append(A,[H],N), removeDups(T,R,N).

% Main predicate to remove duplicates with original order maintained.
uniq(X,Y) :- removeDups(X,Y,[]).
于 2013-07-13T02:04:07.727 回答