如何在Prolog中高效地添加3份列表？

Question

我知道如何处理两份清单：

append([],L,L).
append([H|T],L,[H|R]):-append(T,L,R).

但是怎么做三次呢？不对两个列表使用附加项两次。

Answer 1

若要有效地追加列表，请考虑使用差异列表。差异列表是使用带有两个列表的术语表示的列表。最常见的表示形式使用(-)/2作为术语的函子。例如，列表[1,2,3]可以表示为：

[1,2,3| Tail]-Tail.

通过跟踪列表尾，即它的开放端，您可以高效地执行几个操作。例如，可以通过实例化尾将元素追加到O(1)中列表的末尾：

add_to_end_of_list(List-Tail, Element, List-Tail2) :-
    Tail = [Element| Tail2].

或者简单地说：

add_to_end_of_list(List-[Element| Tail2], Element, List-Tail2).

我们试试看：

?- add_to_end_of_list([1,2,3| Tail]-Tail, 4, Result).
Tail = [4|_G1006],
Result = [1, 2, 3, 4|_G1006]-_G1006.

现在，附加两个列表是相似的，也是O(1)。我们不需要追加一个元素，而是添加一个元素列表：

dappend(List1-Tail1, Tail1-Tail2, List1-Tail2).

例如：

?- dappend([1,2,3 | Tail1]-Tail1, [4,5,6| Tail2]-Tail2, Result).
Tail1 = [4, 5, 6|Tail2],
Result = [1, 2, 3, 4, 5, 6|Tail2]-Tail2.

我留给你一个练习，用不同的列表来回答你自己的问题。注意，从一个不同的列表到一个封闭的列表，只是一个实例化开放端到空列表的问题。例如：

?- dappend([1,2,3 | Tail1]-Tail1, [4,5,6| Tail2]-Tail2, Result-[]).
Tail1 = [4, 5, 6],
Tail2 = [],
Result = [1, 2, 3, 4, 5, 6].

但是，从封闭列表到差异列表确实需要遍历列表，即O(n)：

as_difflist([], Back-Back).
as_difflist([Head| Tail], [Head| Tail2]-Back) :-
    as_difflist(Tail, Tail2-Back).

当然，构建不同列表的成本可能是问题，也可能不是问题，这取决于如何获得初始列表以及在应用程序中附加列表的频率。

Answer 2

append3(Xs, Ys, Zs, XsYsZs) :-
   append(Xs, YsZs, XsYsZs),
   append(Ys, Zs, YsZs).

尽可能的高效。“成本”是关于“Xs|+|Ys”的“推论”。但是，您可能会尝试像下面这样定义它，并使用大约2欧元(Xs|+|Ys)的推断。

append3bad(Xs, Ys, Zs, XsYsZs) :-
   append(Xs, Ys, XsYs),
   append(XsYs, Zs, XsYsZs).

另外，终止是第一种情况要好得多

append3(Xs, Ys, Zs, XsYsZs)
   terminates_if b(Xs),b(Ys);b(XsYsZs)

意味着需要知道Xs和Ys或XsYsZs使append3/4终止.对比

append3bad(Xs, Ys, Zs, XsYsZs)
   terminates_if b(Xs),b(Ys);b(Xs),b(XsYsZs)
                             ^^^^^

对于append3bad/4，XsYsZs是不够的，而且还必须知道Xs。

Answer 3

希望我能理解这个问题(我不认为下面的解决方案比这里的其他解决方案更有效)，但是你的意思是这样的吗？

append([],[],L,L).
append([],[H|T],L,[H|R]) :- append([],T,L,R).
append([H|T],L0,L1,[H|R]) :- append(T,L0,L1,R).