循环结果存储在 Prolog 的列表中

Question

我正在尝试创建一个 Prolog 程序来求解递归方程：

f(1)=2, f(2)=5, f(n)=f(n-1)+2*f(n-2)

我使用下面的 rec 函数进行了管理，但是当我想将结果存储在列表中时遇到了问题（通过函数 recList）。
这是我的实现：

rec(1,2).
rec(2,5).
rec(X,N) :- X1 is X-1, X2 is X-2, rec(X1,N1), rec(X2,N2), N is N1+2*N2.

recList(0,[]).
recList(X,[N|L]) :- rec(X,N), X1 is X-1, recList(X1,L).

我的 recList 实现可以通过第一个值调用它

?- recList(4,X).

->

X = [19, 9, 5, 2] .

但是当我用第二个元素调用它时如果它长于两个元素则不会：

?- rekurList(X,[2]).
X = 1 .

?- rekurList(X,[5,2]).
X = 2 .

?- rekurList(X,[9,5,2]).
ERROR: Arguments are not sufficiently instantiated
ERROR: In:
ERROR:    [9] rec(_12587334,9)
ERROR:    [8] rekurList(_12587360,[9,5|...]) at /locaiton/rec.pl:6
ERROR:    [7] <user>

请问有什么问题吗？

Answer 1

谓词 is/2 失败，因为 is/2 将右侧结构计算为算术表达式。如果它不是有效的算术表达式或数字，is/2 将失败。所以当你打电话给

recList(X, [19, 9, 5, 2]).

你得到 rec/2: Arguments are not sufficiently instantiated。如果你运行示踪剂（在 SWISH 中，在线 SWI：trace, recList(X, [19, 9, 5, 2]). 在 ECLiPSe 中你可以使用 tkeclipse Tools->Tracer）你会得到类似的东西：

Call:recList(_13806, [19, 9, 5, 2])
 Call:rec(_13806, 19)
 Call:_14048 is _13806+-1
 Exception:_14102 is _13806+-1
is/2: Arguments are not sufficiently instantiated

要解决这个问题，你可以这样使用库 clpfd（我使用 SWI 编写了解决方案）：

:- use_module(library(clpfd)).

rec(1,2).
rec(2,5).
rec(X,N):- 
    X1 #> 0,
    X1 #= X-1, 
    rec(X1,N1),
    X2 #> 0,
    X2 #= X-2,  
    rec(X2,N2),
    N #= N1+2*N2, !. %notice the cut (!)

recList(0,[]):-!.
recList(X,[N|L]):- 
    rec(X,N), 
    X1 #= X-1, 
    recList(X1,L).

查询：

?- recList(X, [19, 9, 5, 2]).
X = 4.
false.

?- recList(4,L).
L = [19, 9, 5, 2]
false

注意这里需要剪切!，否则在第一个解之后，如果再点击，计算将永远不会结束。还需要 X1 #> 0 和 X2 #> 0，否则会出现 out of local stack 错误。

循环结果存储在 Prolog 的列表中

Recurrence results stored in list in Prolog

error-handling

recurrence

list

prolog

instantiation-error