Prolog - 递归列表构建 [英] Prolog - recursive list building

问题描述

对于我正在编写的程序，我需要制作一个列表列表，其中成对的数字代表一个乘积和 2 个给定数字的总和.

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

这是我所拥有的:

s1(0, X).s1(Q, X) :-N 是 Q - 1，乘(2, 3, Y),A = Y ,添加(2, 3, Z),B = Z，addToEnd([A], [B], X),s1(N,X).乘法(A，B，C):-C 是 A * B.添加(A，B，C):-C 是 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]]

解决方案

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

这意味着 X = 1. 会将 1 统一为 X，但如果您添加 X = 2. 之后在您的查询中 (X = 1, X = 2.)，Prolog 会说 false.这背后的原因是你不能将1和2统一起来，X真正变成了1，因此X不能统一为2.

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

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

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

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

先说一句:

multiply(2, 3, Y),A = Y ,添加(2, 3, Z),B = Z，addToEnd([A], [B], X),

可以写

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

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

现在，让我们暂时忘记 addToEnd/3 并考虑一下您想要什么.

如果您输入 s1(0, Q)，您真的希望 Q 保持免费吗?因为这就是你目前所说的.在这种情况下，将 Q 绑定到 [] 会更有意义.此外，您很快就会看到，这将是一个很好的递归基本情况.

s1(0, []).

是说的捷径

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

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

然后，我会作弊一点，但只是要保持清醒.您可以声明，当从 s1(4, Q) 到 s1(5, Q) 时，您希望 Q 多保留一些微积分的值.

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

s1(N, [SomeCalculus|Q]) :-上一个 N 是 N - 1，s1(上一个N，Q).

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

s1(N, [SomeCalculus|Q]) :-上一个 N 是 N - 1，X 是 2 * 3，Y 是 2 + 3，SomeCalculus = [X, Y],s1(上一个N，Q).

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

s1(N, [[X, Y]|Q]) :-上一个 N 是 N - 1，X 是 2 * 3，Y 是 2 + 3，s1(上一个N，Q).

所以完整的程序将是:

s1(0, []).s1(N, [[X, Y]|Q]) :-上一个 N 是 N - 1，X 是 2 * 3，Y 是 2 + 3，s1(上一个N，Q).

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

那么让我们再次编辑程序:

s1(0, []).s1(N, [[X, Y]|Q]) :-N＞0,上一个 N 是 N - 1，X 是 2 * 3，Y 是 2 + 3，s1(上一个N，Q).

现在一切都很好.

我希望这能帮助您更好地理解如何通过递归构建正确的谓词.我没有花太多时间更正你的 addToEnd/3 谓词，因为我对变量的漫无边际应该已经告诉你很多关于它的问题.

for a program I'm writing I need to make a list of lists, with pairs of numbers representing a product and sum of 2 given numbers.

For now I have a function which I can specify how many times I want to add a list to the list, which will be expanded with the full functionality later.

Here's what I have:

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

However, when I run s1(2,X) for example, I get [6,5] returned, then nothing else, it just hangs. When I run s1(0,X), i get true, then false when I hit ;

Can anyone help me with this? I can't see what I'm doing wrong, I feel like it should work!

To clarify how I feel this should work: I call s1(2,X). N = 1, [6,5] added to list in X([[6,5]]) s1(1,X). N=0, [6,5] added to the list in X ([[6,5],[6,5]]) s1(0,X). X = [[6,5],[6,5]]

解决方案

So, there are many things to say here. First and foremost, as in most declarative languages, a variable cannot really change value.

What that means is that X = 1. will unify 1 to X as you'd expect, but if you add X = 2. after that in your query (X = 1, X = 2.), Prolog will say false. The reason behind that is that you cannot unify 1 with 2 and that X has truly become 1, therefore X cannot be unified to 2.

Though, and that differs from Haskell, Ocaml and the like, you can bind partially a variable, as in X = h(Y).. You'll then be able to further unify it X = h(a(Z))., while you couldn't in the languages mentionned earlier (where a variable is really just an alias for a value).

Why does he tell me all that you wonder? Well, that's your main problem here. You first bind X to [6, 5], and then expect to further bind it to some other things. Once a variable is ground (ie does not contain any free variable inside itself), you cannot ever change its value again.

So here your recursion won't do anything but eventually prove X false. Here it doesn't however since you end up calling addToEnd/3 with the same arguments each time ([6], [5] and [6, 5]).

That being said, let's look at how we could improve your code.

First, a remark:

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

can be written

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

without any loss of information since you do not use A and B again.

Now, let's forget about addToEnd/3 for a moment and think about what you want.

If you enter s1(0, Q), do you really want Q to stay free? Because that's what you state at the moment. It'd make more sense to bind Q to [] in that case. Plus, that'll make a good recursive base case as you'll soon see.

s1(0, []).

is a shortcut to say

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

since Prolog does unification in clause heads (the part before :-).

Then, I'll cheat a little but it'll just be to stay clear. You could state that when going from s1(4, Q) to s1(5, Q) you expect Q to hold one more value of some calculus.

Here, we could state that as follows:

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

Now, we just have to give a value to SomeCalculus:

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

or, if you followed correctly, we could directly write:

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

So the complete program would be:

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

Now, if you test that, you might remark that the program loops just as yours when you hit the ; key. That's because Prolog thinks the second clause can apply to 0 too.

So let's edit the program once more:

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

Now everything is fine.

I hope this'll help you to get a better understanding of how to build a proper predicate through recursion. I didn't spend much time correcting your addToEnd/3 predicate because my rambling about variables should already have told you a lot about what's wrong about it.

这篇关于Prolog - 递归列表构建的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！