在 Prolog 的追加操作中使用差异列表有什么缺点？

Question

这是有关差异列表的问题的后续问题。

一般append/3或conc/3的写法如下：

append([], L, L).
append([H1|T1], L2, [H1|L3]):-
    append(T1, L2, L3).

这种递归的缺点是，当将长列表作为第一个参数时，它不能有效运行，因为在开始实际附加之前需要处理整个列表。

为了提高效率，我们可以使用不同的列表，只需要变量实例化，不需要递归来追加列表。

append_d(A1-Z1, Z1-Z2, A1-Z2).

问题是，无论我在哪里寻找append/3谓词的定义，都会使用前者，而不是所谓的更有效的替代方案。这是为什么？使用差异列表有什么缺点？它们不能证明效率的提高是合理的吗？

Answer 1

我想使用差异列表版本append而不是经典版本的唯一“缺点”append/3是您可能没有开始的差异列表。换句话说，如果您有这样的列表：

[a,b,c]

而不是这个：

[a,b,c|Back]

...那么如果你想在它的末尾添加一些东西，你必须遍历它。

只要您要将列表相互附加，您实际上从一开始就会使用差异列表。顺便说一句，在现代 Prolog 中，通常使用列表和其余部分的单独参数。以下是一些使用差异列表的 SWI-Prolog 库谓词：

• findall/4
• read_pending_codes/3
• phrase/3（DCG 在@mat 的回答中进行了讨论）

这个列表绝对不是详尽的。要点是，这些谓词通过使用差异列表，允许您在恒定时间内向列表后面添加更多内容。

一旦您发现自己append/3在编写的程序中使用附加列表，您就应该考虑使用差异列表。至于缺点，只要您不需要附加列表，您就需要携带一个不用于任何用途的额外参数：那么，只需一个列表就足够了。

此外，append/3正如通常实现的那样，它可以做的事情不仅仅是追加列表。尝试以下查询：

?- append(A, B, [1,2,3]). % split a list
?- append([1,2,3], Back, List). % make a difference list
?- append(Prefix, _, [a,b,c,d]). % list prefix
?- append(_, Suffix, [a,b,c,d]). % list suffix

等等。

Prolog 队列是很好地利用差异列表的一个很好的例子（参见这个答案的底部，示例是从 Richard O'Keefe 的“The Craft of Prolog”中以简化形式窃取的）。

后记

虽然您可以定义“差异列表附加”谓词，但通常这是不必要的，因为它仅增加了间接级别。假设我正在编写一个谓词，它采用二叉树并为您提供按序遍历产生的差异列表（列表及其背面）：

% tree_inorder_list(+Tree, -List, -Back)
tree_inorder_list(nil, List, List).
tree_inorder_list(t(X, L, R), List, Back) :-
    tree_inorder_list(L, List, [X|List0]),
    tree_inorder_list(R, List0, Back).

使用单独的谓词进行附加只会添加代码。

是的，这可以写成 DCG！它看起来好多了：

tree_inorder(nil) --> [].
tree_inorder(t(X, L, R)) -->
    tree_inorder(L),
    [X],
    tree_inorder(R).

而不是查询：

?- tree_inorder_list(Tree, List, []).

您必须查询 DCG 版本：

?- phrase(tree_inorder(T), List).

您可以使用listing/1来查看此 DCG 定义如何转换为 Prolog 谓词：

?- listing(tree_inorder//1).
tree_inorder(nil, A, A).
tree_inorder(t(D, A, E), B, G) :-
    tree_inorder(A, B, C),
    C=[D|F],
    tree_inorder(E, F, G).

true.

这与上面的差异列表定义相同（除了一个统一，C=[D|F]，它不是内联的）。

并且因为存在 diff-list ，所以您可以在差异列表模式下在多棵树上phrase/3使用，并在恒定时间内连接列表：tree_inorder//1

?- list_to_search_tree([c,a,b], A),
   phrase(tree_inorder(A), List, Back),
   list_to_search_tree([z,y,z,z,x], B),
   phrase(tree_inorder(B), Back).
A = t(b, t(a, nil, nil), t(c, nil, nil)),
B = t(y, t(x, nil, nil), t(z, nil, nil)),
List = [a, b, c, x, y, z],
Back = [x, y, z].

（感谢@WillNess 建议添加此内容）