为什么 prolog 输出一个奇怪的树状列表? [英] Why prolog outputs a weird tree-like list?

问题描述

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

In this Prolog code I intend to list the first N primes,

(...)

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

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

And it works fine if I want the list ordered backwards:

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

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

But if I change the last line of the code from [P|L] to [L|P] like this:

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

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

What am I missing? This is driving me mad!

推荐答案

太好了，您已经发现向列表的结尾添加元素的问题.在 Prolog 中，我们可以用

Great, so you've discovered the problem of adding elements to the end of a list. In Prolog, we can do it with

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

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

wait, what? How to read this? We must know the calling convention here. We expect L and Z to come in as uninstantiated variables, and we arrange for L from now on to point to a newly created cons node with X at its head, and Z its tail. Z to be instantiated, possibly, in some future call.

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

IOW what we create here is an open-ended list, 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 在这里并不是真正需要的，因为它在递归调用链中携带 [] ，保持不变.所以我们可以在没有 Z 参数的情况下重写 primeListAcc，这样它的最后一个子句将是

We can see now that Z is not really needed here, as it carries the [] down the chain of recursive calls, unchanged. So we can re-write primeListAcc without the Z argument, so that its final clause will be

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

保持 Z 作为未实例化的变量允许它以后也可能使用非空列表实例化(当然，只一次(除非发生回溯)).这构成了差异列表"技术的基础.

Keeping Z around as uninstantiated variable allows for it to be later instantiated possibly with a non-empty list as well (of course, only once (unless backtracking occurs)). This forms the basis of "difference list" technique.

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

To answer your literal question - here, consider this interaction transcript:

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)not一个列表.原子作为数字，不是列表.

the [a|b] output is just how a cons node gets printed, when its tail (here, b) is not a list. Atoms, as numbers, are not lists.

这篇关于为什么 prolog 输出一个奇怪的树状列表?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！