Perfoming成员检查差异列表，但是如何? [英] Perfoming member check on a difference list, but how?

问题描述

我试图回答另一个问题(虽然是错误的)，但这导致了一个关于差异列表"(或列表差异")的问题，这似乎是一个更合适的名称，除非"Escherian Construction"不是首选. >

我们有一个元素obj(X,Y)的完整列表(X和Y都接地).我们只想保留从前到后遍历列表时尚未遇到X的第一个obj(X,_).这些第一个元素"必须按出现顺序出现在结果中.

让我们通过测试用例指定问题:

% Testing

:- begin_tests(collapse_dl).   

test(one)   :- collapse_dl([],[]).
test(two)   :- collapse_dl([obj(a,b)],
                           [obj(a,b)]).
test(three) :- collapse_dl([obj(a,b),obj(a,c)],
                           [obj(a,b)]).
test(four)  :- collapse_dl([obj(a,b),obj(a,c),obj(b,j)],
                           [obj(a,b),obj(b,j)]).
test(five)  :- collapse_dl([obj(a,b),obj(a,c),obj(b,j),obj(a,x),obj(b,y)],
                           [obj(a,b),obj(b,j)]).

:- end_tests(collapse_dl).

rt :- run_tests(collapse_dl).

现在，使用过滤，列表前缀和reverse/2易于实现，但是使用差异列表和列表追加呢?

但是，我无法使seen/2谓词正常工作.它检查obj(A,_)是否已在差异列表中.但是该谓词的适当终止是什么?

% This is called

collapse_dl([],[]) :- !. 
collapse_dl([X|Xs],Out) :-
   Dlist = [X|Back]-Back,        % create a difflist for the result; X is surely in there (as not yet seen) 
   collapse_dl(Xs,Dlist,Out).    % call helper predicate  

% Helper predicate

collapse_dl([],Ldown,Lup):-               % end of recursion; bounce proper list back up
   Ldown = Lup-[].                        % the "back" of the difflist is unified with [], so "front" becomes a real list, and is also Lup                    

collapse_dl([obj(A,_)|Objs],Ldown,Out) :- 
   seen(obj(A,_),Ldown),                  % guard: already seen in Ldown?
   !,                                     % then commit
   collapse_dl(Objs,Ldown,Out).           % move down chain of induction

collapse_dl([obj(A,B)|Objs],Ldown,Out) :-
   \+seen(obj(A,_),Ldown),                % guard: not yet seen in Ldown?
   !,                                     % then commit
   Ldown = Front-Back,                    % decompose difference list   
   Back = [obj(A,B)|NewTail],             % NewTail is fresh! Append via difflist unification magic
   collapse_dl(Objs,Front-NewTail,Out).   % move down chain of induction; Front has been refined to a longer list

% Membership check in a difference list 

seen(obj(A,_),[obj(A,_)|_Objs]-[]) :- !.  % Yup, it's in there. Cut retry.
seen(Obj,[_|Objs]-[]) :- ...              % But now???

更新

带有Paulo的代码段:

% Membership check in a difference list 

seen(Element, List-Back) :-
    List \== Back,
    List = [Element|_].    
seen(Element, List-Back) :-
    List \== Back,
    List = [_| Tail],
    seen(Element, Tail-Back).

因此，术语当量或在这种情况下不等价！

我们现在通过了所有测试.

解决方案

尝试(取自Logtalk 库对象):

member(Element, List-Back) :-
    List \== Back,
    List = [Element|_].
member(Element, List-Back) :-
    List \== Back,
    List = [_| Tail],
    member(Element, Tail-Back).

I tried to answer another question (wrongly though) and this led to a question on "difference lists" (or "list differences", which seems a more appropriate name, unless "Escherian Construction" isn't preferred)

We have a fully ground list of elements obj(X,Y) (both X and Y ground). We want to retain only the first obj(X,_) where X hasn't been encountered yet when going through the list front to back. Those "first elements" must appear in order of appearance in the result.

Let's specify the problem through test cases:

% Testing

:- begin_tests(collapse_dl).   

test(one)   :- collapse_dl([],[]).
test(two)   :- collapse_dl([obj(a,b)],
                           [obj(a,b)]).
test(three) :- collapse_dl([obj(a,b),obj(a,c)],
                           [obj(a,b)]).
test(four)  :- collapse_dl([obj(a,b),obj(a,c),obj(b,j)],
                           [obj(a,b),obj(b,j)]).
test(five)  :- collapse_dl([obj(a,b),obj(a,c),obj(b,j),obj(a,x),obj(b,y)],
                           [obj(a,b),obj(b,j)]).

:- end_tests(collapse_dl).

rt :- run_tests(collapse_dl).

Now, this is easy to implement using filtering, list prepend and reverse/2, but what about using difference lists and list append?

however, I'm not able to get the seen/2 predicate to work. It checks whether obj(A,_) is already in the difference list. But what's a proper termination for this predicate?

% This is called

collapse_dl([],[]) :- !. 
collapse_dl([X|Xs],Out) :-
   Dlist = [X|Back]-Back,        % create a difflist for the result; X is surely in there (as not yet seen) 
   collapse_dl(Xs,Dlist,Out).    % call helper predicate  

% Helper predicate

collapse_dl([],Ldown,Lup):-               % end of recursion; bounce proper list back up
   Ldown = Lup-[].                        % the "back" of the difflist is unified with [], so "front" becomes a real list, and is also Lup                    

collapse_dl([obj(A,_)|Objs],Ldown,Out) :- 
   seen(obj(A,_),Ldown),                  % guard: already seen in Ldown?
   !,                                     % then commit
   collapse_dl(Objs,Ldown,Out).           % move down chain of induction

collapse_dl([obj(A,B)|Objs],Ldown,Out) :-
   \+seen(obj(A,_),Ldown),                % guard: not yet seen in Ldown?
   !,                                     % then commit
   Ldown = Front-Back,                    % decompose difference list   
   Back = [obj(A,B)|NewTail],             % NewTail is fresh! Append via difflist unification magic
   collapse_dl(Objs,Front-NewTail,Out).   % move down chain of induction; Front has been refined to a longer list

% Membership check in a difference list 

seen(obj(A,_),[obj(A,_)|_Objs]-[]) :- !.  % Yup, it's in there. Cut retry.
seen(Obj,[_|Objs]-[]) :- ...              % But now???

Update

With Paulo's code snippet:

% Membership check in a difference list 

seen(Element, List-Back) :-
    List \== Back,
    List = [Element|_].    
seen(Element, List-Back) :-
    List \== Back,
    List = [_| Tail],
    seen(Element, Tail-Back).

So, term equivalence, or dis-equivalence in this case, is the solution!

We now pass all the test.

解决方案

Try (taken from Logtalk difflist library object):

member(Element, List-Back) :-
    List \== Back,
    List = [Element|_].
member(Element, List-Back) :-
    List \== Back,
    List = [_| Tail],
    member(Element, Tail-Back).

这篇关于Perfoming成员检查差异列表，但是如何?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！