如何在 Prolog 中有效地附加 3 个列表？

Question

我知道如何为 2 个列表执行此操作：

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

但是怎么做3呢？没有对 2 个列表使用 append 两次。

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).

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