list - Prolog - 递归地将数字附加到列表

Question

我刚刚开始学习 Prolog，但我在思考递归概念时遇到了麻烦。现在，仅出于练习的目的，我正在尝试编写一个程序，将 10 个数字附加到一个列表，然后打印出该列表。

这个程序的 self 强加规则是列表必须在主谓词中“声明”(我不确定这是否是 Prolog 的正确词)，它调用另一个谓词将数字附加到列表.

这是我目前所拥有的，我知道它不会起作用，因为我正试图在 addToList 谓词的末尾重新定义 List，它是语言不允许。

% Entry point that declares a list (`List`) to store the 10 numbers
printList(List) :-
    addToList(0, List),
    writeln(List).

% Base case - once we hit 11 we can stop adding numbers to the list
addToList(11, _).

% First case - this predicate makes adding the first number easier for me...
addToList(0, List) :-
    append([], [0], NewList),
    addToList(1, NewList),
    append([],  NewList, List). % This is valid, but List will just be [0] I think..

% Cases 1-10
addToList(Value, List) :-
    append(List, [Value], NewList),
    NextVal is Value+1,
    addToList(NextVal, NewList),
    append([], NewList, List). % This is INVALID since List is already defined

这个程序将开始于:

printList(List).

是否有一种简单的方法来更改我编写的损坏程序以使其正常工作？我对如何获取存储在 List 中的数字感到非常迷茫。

Answer 1

你在程序上思考，在序言中你不能改变变量。您正在尝试自己构建列表。在 prolog 风格中，您尝试声明所需列表的约束。如果 nlist/2 是一个给出 N 个数字列表的谓词，那么它的属性到底是什么？ nlist(0, []). 如果 nlist(N, Xs) 则 nlist(N+1, [N+1 | Xs])。所以你只需编写这些，让 prolog 负责构建。

nlist(0, []).
nlist(N, [N | Xs]) :-
    N>0, N1 is N-1,
    nlist(N1, Xs).

如果您对递归调用的发生方式感到困惑，请尝试使用 trace/0 或 trace/1。您可以在以下跟踪中看到调用是如何完成的。您可以通过调用 trace(nlist) 获得它。

?- nlist(3, X).
 T Call: nlist(3, _78)
 T Call: nlist(2, _902)
 T Call: nlist(1, _1464)
 T Call: nlist(0, _2026)
 T Exit: nlist(0, [])
 T Exit: nlist(1, [1])
 T Exit: nlist(2, [2, 1])
 T Exit: nlist(3, [3, 2, 1])
X = [3, 2, 1]

比较程序化风格的代码会如下

addToList(11, A, A).

% Cases 1-10
addToList(Value, List, NewList) :-
    Value < 11,  append(List, [Value], Temp),
    NextVal is Value+1,
    addToList(NextVal, Temp, NewList).

这个给出的中间参数就是累加器。当您达到 11 时，累加器就是答案。

?- addToList(1, [], X).
X = [1, 2, 3, 4, 5, 6, 7, 8, 9|...] 

?- addToList(5, [], X).
X = [5, 6, 7, 8, 9, 10] 

查看示例跟踪以及它们在 nlist 和 addToList 中的区别。尝试找出差异及其发生的原因。

?- addToList(7, [], X).
 T Call: addToList(7, [], _33565254)
 T Call: addToList(8, [7], _33565254)
 T Call: addToList(9, [7, 8], _33565254)
 T Call: addToList(10, [7, 8, 9], _33565254)
 T Call: addToList(11, [7, 8, 9, 10], _33565254)
 T Exit: addToList(11, [7, 8, 9, 10], [7, 8, 9, 10])
 T Exit: addToList(10, [7, 8, 9], [7, 8, 9, 10])
 T Exit: addToList(9, [7, 8], [7, 8, 9, 10])
 T Exit: addToList(8, [7], [7, 8, 9, 10])
 T Exit: addToList(7, [], [7, 8, 9, 10])
X = [7, 8, 9, 10]