如何在递归中使用差异列表？

Question

下面程序的意图如下clist_d(f(a,f(a,a)),R) 结果是所有基本参数的列表，例如 R = [a,a,a]

%Difference list append.
diffapp(X-Y,Y-Z,X-Z). 

%2 base case
clist_d(a,[a]).
clist_d(b,[b]).
clist_d(c,[c]).

%If we get a term f(X,Y) the first term of such list is the element in X,followed by the elements in Y
clist_d(f(X,Y),R) :-
    clist_d(X,R1),
    clist_d(Y,R2),
    diffapp([R1|H]-H,R2-[],R-[]).

%We can also get a g
clist_d(g(X,Y),R) :-
    clist_d(X,R1),
    clist_d(Y,R2),
    diffapp([R1|H]-H,R2-[],R-[]).

但是，该程序存在错误。运行具有以下查询的程序：

?- clist_d(f(a,a),R).
R = [[a],a] ?

如上所示产生错误，单独测试差异列表我得到以下结果

?- X = [a,b,c|T], Y = [1,2,3],diffapp(X-T,Y-[],R-[]).
X = [a,b,c,1,2,3],
T = [1,2,3],
Y = [1,2,3],
R = [a,b,c,1,2,3] ? 
yes

我在我的主程序中犯了一个错误，但我不知道要添加什么才能使我的 diffapp 在那里工作。

Answer 1

对于差异列表，您想在任何地方传递一对参数，并且您确实需要任何追加，因此顶级调用应该是：

clist_d(f(a,f(a,a)),R,[])

输出中嵌套的问题是因为你的基本情况 return 一个列表（R1），然后在追加调用中你使用了它（[R1|H]） .没有追加，那不会发生。

clist_d(f(X,Y),R0,R) :-
  clist_d(X,R0,R1),
  clist_d(Y,R1,R).

clist_d(g(X,Y),R0,R) :-
  clist_d(X,R0,R1),
  clist_d(Y,R1,R).

clist_d(a,[a|R],R).
clist_d(b,[b|R],R).
clist_d(c,[c|R],R).

产生：

| ?- clist_d(f(a,f(a,a)),R,[]).
R = [a,a,a] ? ;
no

如何在递归中使用差异列表？

How to use difference lists in recursion?

prolog

difference-lists