在不同的列表上执行成员检查，但是如何？
Perfoming member check on a difference list, but how?
我试图回答另一个问题（虽然是错误的），这导致了关于 "difference lists"（或 "list differences" 的问题，这似乎是一个更合适的名称，除非 "Escherian Construction" 不是' t 首选)
我们有一个完全接地的元素列表 obj(X,Y)（X 和 Y 接地）。我们只想保留第一个 obj(X,_)，其中 X 在从前到后遍历列表时尚未遇到。那些 "first elements" 必须按结果中出现的顺序出现。
让我们通过测试用例具体说明问题：
% 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).
所以，term equivalence，或者在这种情况下不等价，就是解决方案！
我们现在通过了所有测试。
尝试（取自 Logtalk difflist 库对象）：
member(Element, List-Back) :-
List \== Back,
List = [Element|_].
member(Element, List-Back) :-
List \== Back,
List = [_| Tail],
member(Element, Tail-Back).
memberchk/2 应该这样做。使用 here、
中的方法
%% 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 最擅长的事情，以 top-down 方式实例化一个 open-ended 列表。
通过问题中包含的测试。
附录：带打印输出
%% 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]),
!.
由于添加了打印输出，此代码不再是 tail-recursive。原来是，所以在它的踪迹中没有"return"：它只是继续前进，当输入列表遍历到它的末尾时立即停止工作。
查看更多关于区别的信息，例如here.
这个"open-ended list"技术是不是区别列表，但是两者是非常密切相关的。我们实际上不需要任何地方的显式尾巴，除了最后的冻结。所以我们只调用 O(n) length 而不是显式调用 O(1) Tail = [] d 处理差异列表，没什么大不了的。
影响更大的是选择 list 而不是例如树数据结构。树也可以是open-ended，只需要在这里和那里使用var/1。下一步是树的结构。 Top-down open-leaved 树无法旋转（因为所有调用都引用同一个顶部节点）所以它的深度将取决于输入的有序性。为了保持良好的平衡，树木有时需要轮换，因此关闭；我们回到传统的 state-passing 代码，每次调用都获得 两个 树参数——一个在更新之前，另一个在更新之后：the
upd(T1, T2), next(T2, T3), more(T3, T4), ...
之类的。它应该在 真正的 代码中使用。有一些库可以做到这一点。
这个答案的代码很简单，为了简单和说明。
由于我目前需要它，所以我得到了一个更简单的解决方案。假设
差异列表是开放的，意味着对 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 找到它，我们只需创建 Back = [NewElement|Back2] 并继续 [=18] =].
这里是variables/2(ISOterm_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].
我试图回答另一个问题（虽然是错误的），这导致了关于 "difference lists"（或 "list differences" 的问题，这似乎是一个更合适的名称，除非 "Escherian Construction" 不是' t 首选)
我们有一个完全接地的元素列表 obj(X,Y)（X 和 Y 接地）。我们只想保留第一个 obj(X,_)，其中 X 在从前到后遍历列表时尚未遇到。那些 "first elements" 必须按结果中出现的顺序出现。
让我们通过测试用例具体说明问题：
% 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).
所以，term equivalence，或者在这种情况下不等价，就是解决方案！
我们现在通过了所有测试。
尝试（取自 Logtalk difflist 库对象）：
member(Element, List-Back) :-
List \== Back,
List = [Element|_].
member(Element, List-Back) :-
List \== Back,
List = [_| Tail],
member(Element, Tail-Back).
memberchk/2 应该这样做。使用 here、
%% 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 最擅长的事情，以 top-down 方式实例化一个 open-ended 列表。
通过问题中包含的测试。
附录：带打印输出
%% 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]),
!.
由于添加了打印输出，此代码不再是 tail-recursive。原来是，所以在它的踪迹中没有"return"：它只是继续前进，当输入列表遍历到它的末尾时立即停止工作。
查看更多关于区别的信息，例如here.
这个"open-ended list"技术是不是区别列表，但是两者是非常密切相关的。我们实际上不需要任何地方的显式尾巴，除了最后的冻结。所以我们只调用 O(n) length 而不是显式调用 O(1) Tail = [] d 处理差异列表，没什么大不了的。
影响更大的是选择 list 而不是例如树数据结构。树也可以是open-ended，只需要在这里和那里使用var/1。下一步是树的结构。 Top-down open-leaved 树无法旋转（因为所有调用都引用同一个顶部节点）所以它的深度将取决于输入的有序性。为了保持良好的平衡，树木有时需要轮换，因此关闭；我们回到传统的 state-passing 代码，每次调用都获得 两个 树参数——一个在更新之前，另一个在更新之后：the
upd(T1, T2), next(T2, T3), more(T3, T4), ...
之类的。它应该在 真正的 代码中使用。有一些库可以做到这一点。
这个答案的代码很简单，为了简单和说明。
由于我目前需要它，所以我得到了一个更简单的解决方案。假设
差异列表是开放的，意味着对 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 找到它，我们只需创建 Back = [NewElement|Back2] 并继续 [=18] =].
这里是variables/2(ISOterm_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].