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

I know how to do it for 2 lists:

我知道如何为2个列表做到这一点:

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

but how to do it for 3? Without using the append for 2 lists twice.

但如何做到3?不使用追加2个列表两次。

3 个解决方案

#1

To append lists efficiently, consider using difference lists. A difference list is a list expressed using a term with two lists. The most common representation uses (-)/2 as the functor for the term. For example, the list [1,2,3] can be expressed as:

要有效地附加列表,请考虑使用差异列表。差异列表是使用具有两个列表的术语表达的列表。最常见的表示使用( - )/ 2作为该术语的函子。例如,列表[1,2,3]可表示为:

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

By keeping track of the list tail, i.e. of its open end, you can do several operations efficiently. For example, you can append an element to end of the list in O(1) by instantiating the tail:

通过跟踪列表尾部,即其开放端,您可以有效地执行多个操作。例如,您可以通过实例化尾部将元素附加到O(1)中的列表末尾:

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

Or simply:

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

Let's try it:

我们来试试吧:

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

Now, appending two lists is similar and also O(1). Instead of appending an element, we want to append a list of elements:

现在,附加两个列表是相似的,也是O(1)。我们不想附加元素,而是追加元素列表:

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

For example:

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

I leave to you as an exercise to answer your own question using difference lists. Note that going from a difference list to a closed list, is simply a question of instantiating the open end to the empty list. For example:

我留给你作为练习,用差异列表回答你自己的问题。请注意,从差异列表到关闭列表,只是将开放端实例化为空列表的问题。例如:

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

However, going from a closed list to a difference list does requires you to traverse the list, which is O(n):

但是,从关闭列表到差异列表确实要求您遍历列表,即O(n):

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

The cost of constructing the difference lists may or may not be an issue, of course, depending on how you get the initial lists and how often you will be appending lists in your application.

当然,构建差异列表的成本可能是也可能不是问题,具体取决于您获取初始列表的方式以及在应用程序中添加列表的频率。

#2

Hope I understood the question (and I don't think the following is more efficient than the other solutions here), but did you mean something like this?

希望我能理解这个问题(我不认为以下内容比其他解决方案更有效),但你的意思是这样吗?

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

#3

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

Is as efficient, as it can get. Cost is about |Xs|+|Ys| inferences. However, you might have attempted to define it like the following with about 2|Xs|+|Ys| inferences.

尽可能高效,尽可能高效。成本约为| Xs | + | Ys |推论。但是,您可能尝试使用约2 | Xs | + | Ys |来定义它,如下所示推论。

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

Also, termination is much better in the first case:

此外,在第一种情况下终止更好:

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

meaning that either Xs and Ys or XsYsZs needs to be known to make append3/4 terminate ... versus

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

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

for append3bad/4, where XsYsZs is not sufficient, but additionally also Xs has to be known.

对于append3bad / 4,其中XsYsZs不足,但另外还必须知道Xs。

#1

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