list 如何在 Prolog 中将元素附加到列表中？

How do you append an element to a list in place in Prolog?

提问by No One in Particular

If I have a list in Prolog such as X = [1, 2, 3, 4], how do I add the element 5 to the end of the list to have X = [1, 2, 3, 4, 5]?

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

The append function needs two lists, ie append(A,B,C) to get A and B concatenated to the list C.

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

I can do this with a temporary list Y = [1, 2, 3, 4] and Z = [5], to then do an append(Y, Z, X), but I don't like having a temporary list.

我可以用一个临时列表 Y = [1, 2, 3, 4] 和 Z = [5] 来做这个，然后做一个 append(Y, Z, X)，但我不喜欢有一个临时列表。

The usual disclaimers apply here - this is not homework and I am just learning Prolog.

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

采纳答案by mndrix

Variables in Prolog can only be assigned once. As soon as X has the value [1,2,3,4] it can never have another value. A temporary variable and append/3, like you mentioned, is the way to do it.

Prolog 中的变量只能赋值一次。一旦 X 具有值 [1,2,3,4]，它就永远不会有另一个值。就像你提到的那样，临时变量和 append/3 就是这样做的方法。

Having said that, you can do one trick which probably isn't recommended. If X = [1,2,3,4,Y] then you can do Y=5 and X now has the value you want. I believe this technique is called a difference list.

话虽如此，你可以做一个可能不推荐的技巧。如果 X = [1,2,3,4,Y] 那么你可以做 Y=5 并且 X 现在有你想要的值。我相信这种技术称为差异列表。

回答by S.L. Barth - Reinstate Monica

As the others have pointed out, you're going to be stuck with the performance issue.
But just as an exercise I decided to try and create a predicate that could append an element to the end of a list, without using append.

正如其他人指出的那样，您将被性能问题所困扰。
但作为一个练习，我决定尝试创建一个谓词，它可以将一个元素附加到列表的末尾，而不使用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).

I would advice that you'd simply use the appendfunction, as a built-in function it is likely to be faster than anything manually crafted.

我建议您只需使用该append函数，作为内置函数，它可能比手动制作的任何东西都快。

回答by Paulo Moura

One declarative solution is to use a difference list (as Daniel suggested in its answer). A difference list gets its name from being usually represented as a difference between two lists: a list and its tail. For example, an empty list can be represented as T-T. A list with the elements 1, 2, and 3 can be represented as [1,2,3| T]-T(note that (-)/2is standard built-in infix operator). The advantage of this representation is that you can append an element to a list in constant time by using a single fact definition of the append/3predicate:

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

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

An usage example:

一个使用示例：

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

If necessary, is not difficult to convert between a "normal" list and a difference list. I leave that as an exercise to you.

如有必要，在“正常”列表和差异列表之间进行转换并不难。我把它留给你作为练习。

回答by Anderson Green

You can't modify lists in Prolog, but you can create a list with an unspecified length:

您不能在 Prolog 中修改列表，但您可以创建一个未指定长度的列表：

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

Then, you can insert an element using nth0/3in SWI-Prolog:

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

:- initialization(main).

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

After this element is inserted, A = [1,2,3,4,5|_].

插入此元素后，A = [1,2,3,4,5|_].

You can also define a function that appends an item to the end of a list in-place, and then use it like this:

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

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

In this example, A = [1,2,3,4,4|_]after these two items are appended.

在本例中，A = [1,2,3,4,4|_]在附加了这两项之后。

回答by Imam Bux

Since Prolog has append which only accepts lists, why don't we use it to insert our element in one of the lists. i.e.

由于 Prolog 有 append 只接受列表，为什么我们不使用它来将我们的元素插入列表之一。IE

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

回答by Daniel Lyons

You're worrying about the wrong end of the problem. Structure sharing can only happen by consing an element onto the beginning of the list. That method has the performance characteristics you want. Because of the way lists are defined, when you append two lists the entire first list will be copied. In this case, that's going to be the whole list. The garbage generated by a one-item list is obviously going to be much smaller than that.

你担心问题的结局是错误的。结构共享只能通过将元素放在列表的开头来实现。该方法具有您想要的性能特征。由于列表的定义方式，当您附加两个列表时，将复制整个第一个列表。在这种情况下，这将是整个列表。单项列表产生的垃圾显然要小得多。

If you really must append, consider building the list backwards and then reversing it once at the end, which is much cheaper, or use difference lists, which enable efficient appending to the end.

如果您确实必须追加，请考虑向后构建列表，然后在最后将其反转一次，这会便宜得多，或者使用差异列表，这样可以高效地追加到末尾。