Prolog-递归追加到列表返回false



Title说明了一切,但我们又来了。试图递归地附加到Prolog中的列表中,而我之前通过使用";临时缓冲器";(通过nb_setval/nb_getval(我想学习如何以稍微合适的方式递归地附加到列表中。

我知道Prolog是围绕绑定工作的,一旦绑定了某个东西,就很难操作它,所以一开始我对此持保留态度,但我理解为什么它不太起作用:

recursiveAppend([], _).
recursiveAppend([H|T], Output):-
append(H, [], Output),
recursiveAppend(T, Output).

这让我更改了代码并转到以下位置:

recursiveAppend([], _).
recursiveAppend([H|T], Output):-
append(H, Output, NewOutput),
recursiveAppend(T, NewOutput).

我曾希望这会奏效,因为这对我自己和其他人来说都很有意义,同时也搜索了其他StackOverflow问题。不幸的是,在SWI-Prolog中调用此谓词只返回false

?- recursiveAppend([1, 2, 3, 4, 5], L1). false

在这种情况下,预期/期望的结果是:

?- recursiveAppend([1, 2, 3, 4, 5], L1). L1 = [1, 2, 3, 4, 5].

为了清楚起见,如果";丰满的":

recursiveAppend([H|T], Output):-
% H is 1, Output is []
append(H, Output, NewOutput),
% NewOutput is [1]
recursiveAppend(T, NewOutput).
recursiveAppend([H|T], Output):-
% H is 2, Output is [1]
append(H, Output, NewOutput),
% NewOutput is [1, 2]
recursiveAppend(T, NewOutput).
recursiveAppend([H|T], Output):-
% H is 3, Output is [1, 2]
append(H, Output, NewOutput),
% NewOutput is [1, 2, 3]
recursiveAppend(T, NewOutput).
recursiveAppend([H|T], Output):-
% H is 4, Output is [1, 2, 3]
append(H, Output, NewOutput),
% NewOutput is [1, 2, 3, 4]
recursiveAppend(T, NewOutput).
recursiveAppend([H|T], Output):-
% H is 5, Output is [1, 2, 3, 4]
append(H, Output, NewOutput),
% NewOutput is [1, 2, 3, 4, 5]
recursiveAppend(T, NewOutput).
recursiveAppend([], _). % First argument (list) is empty, and the second argument (list) has been populated (with [1, 2, 3, 4, 5]), program done.

任何和所有的帮助都是感谢的,尽管这个问题可能已经被问了一百万次了!

"递归追加";在Prolog中通常没有意义。该问题应包括有关您试图解决的问题的信息。目前情况并非如此;这是关于你如何试图解决你的问题。";如何";是";递归追加";,但这几乎肯定不是你真正应该解决这个问题的方式。如果我们知道问题是什么,而不是你认为你想如何解决它,我们可以提供更好的帮助。

以问题为例,从https://stackoverflow.com/a/64092447/4391743:

?- recursiveAppend([1, 2, 3], Ys).
Ys = [1, 2, 3].
?- recursiveAppend(Xs, [1, 2, 3]).
Xs = [1, 2, 3] ;
% nontermination after first answer
?- recursiveAppend([1, 2, X], [A, B, 3]).
X = 3,
A = 1,
B = 2.
?- recursiveAppend([1, 2 | Rest], [A, B, 3, 4]).
Rest = [3, 4],
A = 1,
B = 2 ;
% nontermination after first answer

如果这是你想要的,那么你似乎想要的是一个";列表副本";谓语这里有一个更短、更快、更完整的:

list_copy([], []).
list_copy([X | Xs], [X | Ys]) :-
list_copy(Xs, Ys).

这不存在上述谓词所具有的非终止问题:

?- list_copy([1, 2, 3], Ys).
Ys = [1, 2, 3].
?- list_copy(Xs, [1, 2, 3]).
Xs = [1, 2, 3].
?- list_copy([1, 2, X], [A, B, 3]).
X = 3,
A = 1,
B = 2.
?- list_copy([1, 2 | Rest], [A, B, 3, 4]).
Rest = [3, 4],
A = 1,
B = 2.

如果其中一个参数是列表,另一个是变量,则将建立一个新的列表结构并将其绑定到该变量。

但是。。。为什么你需要一个新的列表结构?在纯Prolog中,你无法判断两个项是相同的(即共享相同的内存位置(还是";只是";结构上平等。你通常也不在乎(或者不应该(。(在非纯Prolog中,有关于共享和显式复制的知识的用途,但我们也不知道你想做什么。(

因此,如果我们不能判断;复制";确实是一个副本或只是";相等项";,那么我们根本不需要复制。只要统一,我们就可以得到与上述完全相同的行为:

?- [1, 2, 3] = Ys.
Ys = [1, 2, 3].
?- Xs = [1, 2, 3].
Xs = [1, 2, 3].
?- [1, 2, X] = [A, B, 3].
X = 3,
A = 1,
B = 2.
?- [1, 2 | Rest] = [A, B, 3, 4].
Rest = [3, 4],
A = 1,
B = 2.

没有复制,当然也没有"复制";递归追加";是实现统一所必需的,Prolog知道如何为您实现统一。

如果这不是你想要的,请告诉我们实际问题是什么;递归追加";几乎可以肯定不是。

Prolog是一种不同的编程范式。它要求你";忘记";你所知道的关于编程的一切,以开放的心态学习。不要试图在使用"Prolog"时学习Prolog;普通的";变量和不同的值,Prolog变量只有一个值或没有。它们可能只在回溯时取不同的值,并试图为程序中的所有变量找到另一组满足所有给定谓词的值。

建议你读一些书,比如;立即学习Prolog";。许多州立大学的教程可以在互联网上免费获得。

根据您最近编辑的Calling recursiveAppend示例,这里有一个符合该示例的代码。

recursiveAppend(X, Y) :- recursiveAppend(X, [], Y).
recursiveAppend([], X, X).
recursiveAppend([H|T], Current, Output):-
append(Current, [H], NewTemp),
recursiveAppend(T, NewTemp, Output).

您以前的代码返回false,因为append需要列表作为参数。因此,添加一个整数(输入列表的项(将始终失败。我创建了一个版本recursiveAppend/3,以在第二个arg中累积当前列表。在列表的末尾,当前列表将成为最终输出。你能用更多的例子进一步测试它吗?并告诉我们它是否按要求工作。

最新更新