如何在Prolog中原地向列表追加元素？

Question

如何在Prolog中原地向列表追加元素？

listprologappendin-placedifference-lists

25

如果我在Prolog中有一个列表，例如X = [1, 2, 3, 4]，我该如何将元素5添加到列表末尾，使得X = [1, 2, 3, 4, 5]？

append函数需要两个列表，即append(A,B,C)将A和B连接到列表C。

我可以使用临时列表Y = [1, 2, 3, 4]和Z = [5]来执行append(Y, Z, X)，但我不喜欢使用临时列表。

通常的免责声明适用于此处 - 这不是作业，我只是在学习Prolog。

- No One in Particular

3

简短回答：你不需要，就是不需要。 - repeat

6个回答

12

在Prolog中，变量只能被赋值一次。一旦X有了值[1,2,3,4]，它就再也不能有其他的值了。像你提到的那样，使用临时变量和append/3是解决这个问题的方法。

话虽如此，你可以使用一种可能不被推荐的技巧。如果X=[1,2,3,4,Y]，那么你可以将Y赋值为5，然后X就有了你想要的值。我相信这种技巧被称为差分列表。

- mndrix

@no-one-in-particular 把Prolog变量看作数学变量而不是存储位置。我知道这是一个重大的范式转变，但是一旦你掌握了它，任何Prolog中的东西都会变得相当容易（或至少是逻辑的）。 - Aurélien Bénel

@mndrix - 答案不错。这解决了问题。所以，如果我理解正确，如果我说X=[A,B,C,D]，然后稍后赋值A=[1]，B=[2]，那么X=[[1]，[2]，C，D]。然后，如果我稍后分配C=[3]，D=[4]，那么我最终有X=[[1]，[2]，[3]，[4]]，并且它是固定的。 - No One in Particular

2

为了使用差分列表，您需要跟踪列表中的“空洞”（在此情况下是其尾部）。即差分列表始终是由两个术语组成的一对，一个是带有“空洞”的列表，另一个是“空洞”本身。 “空洞”本身是一个逻辑变量。表示这对的传统方式是使用内置的中缀运算符。 - Paulo Moura

1

不完全是这样。使用 X = [1,2,3,4 | Y]，然后 Y = [5 | Z] 就是差分列表技术：在 X...Y 的末尾添加 5 可以得到长度为 X...Z 的扩展列表。前者的 X...Y 仍然是有效的、更短的差分列表，仍然表示与扩展之前相同的前缀 1,2,3,4。差分列表易于理解为“开放式”列表或前缀。此外，通过这种方式扩展差分列表是 O(1) 操作。 - Will Ness

“不完全准确”是对答案中“我相信这种技术被称为差异列表”的回应。 - Will Ness

3

你无法在Prolog中修改列表，但是你可以创建一个长度未指定的列表：

main :-
    A = [1,2,3,4|_].

然后，你可以在SWI-Prolog中使用nth0/3插入元素：

:- initialization(main).

main :-
    A = [1,2,3,4|_],
    nth0(4,A,5),
    writeln(A).

在这个元素被插入之后，A = [1,2,3,4,5|_]。

您还可以定义一个函数，在原地将项添加到列表的末尾，然后像这样使用它：

:- initialization(main).

append_to_list(List,Item) :-
    List = [Start|[To_add|Rest]],
    nonvar(Start),
    (var(To_add),To_add=Item;append_to_list([To_add|Rest],Item)).

main :-
    A = [1,2,3|_],
    append_to_list(A,4),
    append_to_list(A,4),
    writeln(A).

在这个例子中，当这两个项目被附加后，A = [1,2,3,4,4|_]。

- Anderson Green

你还可以补充说明，每次添加时重新从开放列表的开头回溯将是总体二次的，因此我们可以显式地维护结束变量以进行O(1)的添加 - 这将是差异列表。另一种方法是维护已知长度并直接使用nth0/nth1。 - Will Ness

3

既然Prolog只接受列表作为参数，那么我们为什么不使用它的append函数将元素插入其中一个列表中呢？即：

% E = element, L = list, R = result
% e.g. add_elem_in_list ([1,2,3,4], 5, R).
add_elem_in_list(L, E, R) :- append(L, [E], R).

- Imam Bux

3

一种声明性的解决方案是使用差分列表（如Daniel在其答案中所建议的）。差分列表之所以得名，是因为通常被表示为两个列表之间的差异：一个列表和它的尾部。例如，一个空列表可以表示为T-T。一个包含元素1、2和3的列表可以表示为[1,2,3| T]-T（注意(-)/2是标准内置的中缀运算符）。这种表示的优点是，您可以通过使用append/3谓词的单个事实定义，在常数时间内将元素附加到列表中：

append(L1-T1, T1-T2, L1-T2).

一个使用示例：

?- append([1,2,3,4| T1]-T1, [5| T2]-T2, Result).
T1 = [5|T2],
Result = [1, 2, 3, 4, 5|T2]-T2.

如果需要的话，将“普通”列表转换为差异列表并不难。我将这留给你作为练习。

- Paulo Moura

1

刚刚注意到这是一个非常古老的问题（在互联网时间中）！ - Paulo Moura

s(X): 坚如磐石。 - repeat

2

你正在关注问题的错误方面。结构共享只能通过将元素cons到列表开头来实现。这种方法具有你想要的性能特征。因为列表的定义方式，当你追加两个列表时，整个第一个列表将被复制。在这种情况下，那将是整个列表。一个单项列表所产生的垃圾显然比那大得多。

如果你真的必须追加，请考虑倒序构建列表，然后在最后反转它，这样更便宜，或者使用差分列表，它们可以有效地追加到末尾。

- Daniel Lyons

1

使用经典的“双重反转，前置项目”方法，请使用s（X）！ - repeat

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- S.L. Barth · Accepted Answer

正如其他人指出的那样，您将被卡在性能问题上。
但是作为一次练习，我决定尝试创建一个谓词，可以将元素附加到列表末尾，而不使用append。

% add_tail(+List,+Element,-List)
% Add the given element to the end of the list, without using the "append" predicate.
add_tail([],X,[X]).
add_tail([H|T],X,[H|L]):-add_tail(T,X,L).

我建议你使用内置的append函数，因为它比手动编写的任何东西都更快。请注意保留HTML标签。