1

在这个 Prolog 代码中，我打算列出前 N 个素数，

(...)

biggerPrime(N,P) :-
    isPrime(N),
    P is N,
    !.

biggerPrime(N,P) :-
    N1 = N+1,
    biggerPrime(N1,P).

primeListAcc(0,A,R,R) :- !.

primeList(N,L) :-
    primeListAcc(N,1,[],L).

primeListAcc(N,A,L,R) :-
    N1 is N-1,
    biggerPrime(A,P),
    A1 is P+1,
    primeListAcc(N1,A1,[P|L],R).

如果我希望列表向后排序，它可以正常工作：

?- primeList(5,L).
L = [11, 7, 5, 3, 2].

但是，如果我将代码的最后一行从 [P|L] 更改为 [L|P]，如下所示：

primeListAcc(N,A,L,R) :-
        N1 is N-1,
        biggerPrime(A,P),
        A1 is P+1,
        primeListAcc(N1,A1,[L|P],R).

我得到：

?- primeList(5,L).
L = [[[[[[]|2]|3]|5]|7]|11].

我错过了什么？这让我发疯！

4

2 回答 2

2

回想一下，列表要么是空列表，要么[]是具有函子'.'和两个参数的项，其第二个参数是列表。语法[P|Ps]是 term 的简写符号，'.'(P, Ps)如果Ps是一个列表，它就是一个列表（就像您的示例中的情况一样）。'.'(Ps, P)另一方面，术语也可以写成[Ps|P]（如您所做的那样），如果不是列表，则P不是列表。您可以使用 获取反向列表reverse/2。

于 2013-03-31T19:59:47.437 回答
1

太好了，所以您发现了将元素添加到列表末尾的问题。在 Prolog 中，我们可以使用

add(X,L,Z):- L=[X|Z].

等等，什么？怎么读这个？我们必须知道这里的调用约定。我们期望 L和Z作为未实例化的变量进入，并且我们L从现在开始安排指向一个新创建的cons节点X，其头部和Z尾部。Z可能在将来的某个调用中被实例化。

IOW 我们在这里创建的是一个开放式列表，L = [X|Z] = [X, ...]：

primeList(N,L) :-
    primeListAcc(N,1,[],L).

primeListAcc(N,A,Z,L) :- N > 0,   % make it explicitly mutually-exclusive,
    N1 is N-1,                    %   do not rely on red cuts which are easily
    biggerPrime(A,P),             %   invalidated if clauses are re-arranged!
    A1 is P+1,                    
    L = [P|R],                    % make L be a new, open-ended node, holding P
    primeListAcc(N1,A1,Z,R).      % R, the tail of L, to be instantiated further

primeListAcc(0,A,R,R).            % keep the predicate's clauses together

现在我们可以看到Z这里并不真正需要它，因为它[]沿着递归调用链向下传递，没有改变。primeListAcc所以我们可以在没有参数的情况下重写Z，这样它的最后一个子句将是

primeListAcc(0,A,R):- R=[].

保留Z为未实例化的变量允许稍后用非空列表实例化它（当然，只有一次（除非发生回溯））。这构成了“差异列表”技术的基础。

要回答您的字面问题 - 在这里，请考虑以下交互记录：

1 ?- X=[a|b].

X = [a|b] 
2 ?- X=[a|b], Y=[X|c].

X = [a|b]
Y = [[a|b]|c]

当它的尾部（这里， ）不是列表时，[a|b]输出就是 cons 节点的打印方式。原子，作为数字，不是列表。b

于 2013-04-01T12:41:14.567 回答