2

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

我们有一个完整的基础元素列表obj(X,Y)（包括基础X和Y基础）。obj(X,_)在从前到后遍历列表时，我们只想保留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).

现在，这很容易使用过滤、list prepend 和 来实现reverse/2，但是使用差异列表和list append呢？

但是，我无法使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).

因此，在这种情况下，术语等价或不等价是解决方案！

我们现在通过了所有的测试。

4

3 回答 3

2

尝试（取自 Logtalkdifflist库对象）：

member(Element, List-Back) :-
    List \== Back,
    List = [Element|_].
member(Element, List-Back) :-
    List \== Back,
    List = [_| Tail],
    member(Element, Tail-Back).
于 2020-04-07T18:57:35.180 回答
1

memberchk/2应该这样做。使用这里的方法，

%% collapse_dl( ++Full, -Short )
collapse_dl( [obj(K,V) | A], B ) :-
    memberchk( obj(K,X), B ),
    ( X = V -> true ; true ),
    collapse_dl( A, B ).
collapse_dl( [], B ) :-
    length( B, _), !.

做 Prolog 最擅长的事情，以自上而下的方式实例化一个开放式列表。

通过问题中包含的测试。

附录：带打印输出

%% collapse_dl( ++Full, -Short )
collapse_dl( [obj(K,V) | A], B ) :-
    format("Enter : ~w relatedto ~w\n", [[obj(K,V) | A], B]),
          % Necessarily find  (find or insert)  obj(K, X) (thanks to the 
          %  uninstantiated X) in list B which has an "unobserved" tail:
    memberchk( obj(K,X), B ),
          % Unify X with V if you can; ignore failure if you can't!
    ( X = V -> true ; true ),
    format("Mid   : ~w relatedto ~w\n", [[obj(K,V) | A], B]),
    collapse_dl( A, B ),
    format("Return: ~w relatedto ~w\n", [[obj(K,V) | A], B]).

collapse_dl( [], B ) :-
    format("Termination: From unobserved-tail-list ~w ",[B]),
    length(B, _), 
    format("to ~w (and don't come back!)\n",[B]),
    !.

由于添加了打印输出，此代码不再是尾递归的。原始是，因此在其跟踪中没有“返回”：它只是前进并在输入列表遍历到其末尾时立即停止工作。

查看更多关于区别的信息，例如这里。

这种“开放式列表”技术不是差异列表，但两者密切相关。除了最后的冻结之外，我们实际上不需要任何地方的显式尾部。所以我们只做O(n) length调用，而不是我们对差异列表做的显式O(1) ，没什么大不了的。 Tail = []

更大的影响是选择列表而不是树数据结构。树也可以是开放式的，只需要在var/1这里和那里使用。下一步是树的结构。自上而下的开叶树不能旋转（因为所有调用都引用同一个顶部节点），因此它的深度将取决于输入的有序性。为了保持良好的平衡，树木有时需要旋转，因此要关闭；我们回到传统的状态传递代码，如果每个调用都有两个树参数——一个在更新之前，另一个在它之后：

    upd(T1, T2), next(T2, T3), more(T3, T4), ...

之类的事情。它应该在实际代码中使用。有一些图书馆可以做到这一点。

为了简单和说明性，这个答案的代码很简单。

于 2020-04-08T08:54:41.277 回答
1

由于我目前需要它，因此我得到了一个更简单的解决方案。假设差异列表是开放的，对于这对List-Back，我们有var(Back)。然后我们可以走捷径，只能通过List：

member_open(_, List) :- var(List), !, fail.
member_open(Element, [Element|_]).
member_open(Element, [_|List]) :- member_open(Element, List).

如果我们想将一个元素附加到List，例如我们没有通过 member_open/2 找到它，我们只需 makeBack = [NewElement|Back2]并继续Back2。

这是variables/2（ISO term_variables/2）以这种方式编写的，因此不需要reverse/1：

variables(T, L) :-
   variables(T, B, B, B2),
   B2 = [],
   L = B.

variables(V, L, B, B) :- var(V), member_open(W, L), V == W, !.
variables(V, L, [V|B], B) :- var(V), !.
variables(T, L, B, B2) :-
   T =.. [_|A],
   variables_list(A, L, B, B2).

variables_list([T|A], L, B, B2) :-
   variables(T, L, B, H),
   variables_list(A, L, H, B2).
variables_list([], _, B, B).

似乎工作：

?- variables(f(X,g(X,Y),Y), L).
L = [X, Y].
于 2021-06-30T19:07:36.380 回答