Prolog - 递归列表构建

Question

对于我正在编写的程序，我需要制作一个列表列表，其中成对的数字代表一个产品和两个给定数字的总和。

现在我有一个函数，我可以指定将列表添加到列表中的次数，稍后将使用完整的功能对其进行扩展。

这是我所拥有的:

s1(0, X).
s1(Q, X) :-
    N is Q - 1,
    multiply(2, 3, Y),
    A = Y ,
    add(2, 3, Z),
    B = Z,
    addToEnd([A], [B], X),
    s1(N,X).

multiply(A, B, C):-
    C is A * B.

add(A, B, C) :-
    C is A + B.

addToEnd([], L, L).
addToEnd([H|T], L2, [H|L3]) :-
    addToEnd(T, L2, L3).

但是，当我运行 s1(2,X)例如，我得到 [6,5]返回，然后没有别的，它只是挂起。当我运行 s1(0,X) ，我得到 true ，然后 false当我点击 ;
谁能帮我这个？我看不出我做错了什么，我觉得它应该工作!

为了澄清我觉得这应该如何工作:
我调用 s1(2,X). N = 1 , [6,5]已添加到 X([[6,5]]) 中的列表中 s1(1,X). N=0 , [6,5]已添加到 X ([[6,5],[6,5]]) 中的列表中 s1(0,X). X = [[6,5],[6,5]]

Answer 1

所以，这里有很多话要说。首先，与大多数声明性语言一样，变量不能真正改变值。

这意味着 X = 1.将统一1至X如您所料，但如果您添加 X = 2.在您的查询( X = 1, X = 2. )之后，Prolog 会说 false .背后的原因是无法统一1与 2那X真正变成了1 ，因此 X不能统一到2 .

不过，这与 Haskell、Ocaml 等不同，您可以部分绑定(bind)变量，如 X = h(Y). .然后您将能够进一步统一它X = h(a(Z)). ，而您不能在前面提到的语言中(其中变量实际上只是值的别名)。

为什么他告诉我你想知道的一切？嗯，这是你的主要问题。你先绑定(bind)X至[6, 5] ，然后期望进一步将其绑定(bind)到其他一些东西。一旦一个变量被接地(即它本身不包含任何自由变量)，你就不能再改变它的值了。

所以在这里你的递归不会做任何事情，但最终证明 X错误的。但是，这里没有，因为您最终调用了 addToEnd/3每次使用相同的参数( [6] ， [5] 和 [6, 5] )。

话虽如此，让我们看看我们如何改进您的代码。

首先，备注:

multiply(2, 3, Y),
A = Y ,
add(2, 3, Z),
B = Z,
addToEnd([A], [B], X),

可以写

multiply(2, 3, Y),
add(2, 3, Z),
addToEnd([Y], [Z], X),

不会丢失任何信息，因为您不使用 A和 B再次。

现在，让我们忘记 addToEnd/3想一想你想要什么。

如果输入 s1(0, Q) , 你真的要 Q保持自由？因为这就是你现在所说的。绑定(bind) Q 会更有意义至 []在这种情况下。另外，您很快就会看到，这将成为一个很好的递归基本案例。

s1(0, []).

是说的捷径

s1(0, Q) :- Q = [].

因为 Prolog 在子句头中进行了统一( :- 之前的部分)。

然后，我会作弊一点，但只是为了保持清醒。您可以声明，当从 s1(4, Q) 开始时至 s1(5, Q)你期望 Q 再持有一些微积分的值。

在这里，我们可以声明如下:

s1(N, [SomeCalculus|Q]) :-
    PreviousN is N - 1,
    s1(PreviousN, Q).

现在，我们只需给 SomeCalculus 赋值。 :

s1(N, [SomeCalculus|Q]) :-
    PreviousN is N - 1,
    X is 2 * 3,
    Y is 2 + 3,
    SomeCalculus = [X, Y],
    s1(PreviousN, Q).

或者，如果你正确地遵循，我们可以直接写:

s1(N, [[X, Y]|Q]) :-
    PreviousN is N - 1,
    X is 2 * 3,
    Y is 2 + 3,
    s1(PreviousN, Q).

所以完整的程序是:

s1(0, []).
s1(N, [[X, Y]|Q]) :-
    PreviousN is N - 1,
    X is 2 * 3,
    Y is 2 + 3,
    s1(PreviousN, Q).

现在，如果您对此进行测试，您可能会注意到当您点击 ; 时程序会像您的一样循环。 key 。那是因为 Prolog 认为第二个子句可以适用于 0。
也。

所以让我们再次编辑程序:

s1(0, []).
s1(N, [[X, Y]|Q]) :-
    N > 0,
    PreviousN is N - 1,
    X is 2 * 3,
    Y is 2 + 3,
    s1(PreviousN, Q).

现在一切都很好。

我希望这将帮助您更好地了解如何通过递归构建适当的谓词。我没有花太多时间纠正你的 addToEnd/3谓词，因为我对变量的漫无边际应该已经告诉你很多关于它的错误之处。