如何在 Prolog 中有效地附加 3 个列表? [英] How do I append 3 lists efficiently in Prolog?

问题描述

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

I know how to do it for 2 lists:

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

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

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

推荐答案

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

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:

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

通过跟踪列表尾部，即它的开放端，您可以高效地进行多项操作.例如，您可以通过实例化尾部，在 O(1) 中将一个元素附加到列表的末尾:

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:

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).我们想附加一个元素列表，而不是附加一个元素:

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

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.

我留给您练习使用差异列表回答您自己的问题.请注意，从差异列表到封闭列表，只是将开放端实例化为空列表的问题.例如:

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

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

However, going from a closed list to a difference list does requires you to traverse the list, which is 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.

这篇关于如何在 Prolog 中有效地附加 3 个列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！