如何在Prolog中高效地追加三个列表？

Question

我知道如何对两个列表执行此操作：

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

但如何对3进行操作呢？而不是两次使用append连接2个列表。

- migea

---

"Without ..." 是什么意思？为什么这样做效率不高？ - false

我认为可以使用我的方法将两个列表连接起来，然后再将结果与另一个列表连接起来，就像两次使用我的方法一样。如果可能的话，我想直接这样做。 - migea

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

构建差异列表的成本可能是一个问题，当然这取决于如何获取初始列表以及您的应用程序多频繁地附加列表。

- Paulo Moura

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)

这意味着要使 append3/4 终止，需要知道 Xs 和 Ys 或者 XsYsZs 中的任意一种。

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

对于append3bad/4，其中XsYsZs不足够，还必须知道Xs。

- false

---

我可能错了，但这难道不是正是 OP 所要避免的吗（尽管你关于效率的说法除外）？ - Ami Tavory

append([], L, L). - migea

啊，不行，那是不可能的！你需要使用通常定义的append/3。 - false

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

- Ami Tavory