涉及算术运算和计数元素的列表的递归？

Question

我正在努力真正掌握对 Prolog 列表和递归调用的理解。我一直在开发一个程序来跟踪有多少项大于列表的头部，然后递归调用此关系以检查大于下一个元素等。我已经让我的程序工作到可以计算大于头部的元素数量的程度，但是一旦它到达末尾并尝试递归调用下一个元素的关系，它就会失败。根据我所做的研究，这里是我所拥有的以及我认为它应该如何工作：

Input - List = [7,2,4,3,6,9,8,10,12,5].

testHead(List).

testHead([H|T]) :-
    greaterThan(H,T,0),
    teastHead(T).

^我的理解是这个关系从列表中获取头部元素并使用头部和列表的其余部分调用 greaterThan。 greaterThan完成后，应该递归调用testHead(T)测试下一个元素等等。

greaterThan(H,[X|T],C) :-
    H > X ->
    C2 is C+1,
    greaterThan(H,T,C2);
    greaterThan(H,T,C).

^我的理解是greaterThan读入head元素，其余的列表，和一个计数变量。如果头部大于下一个元素，则增加计数并用尾部和新计数递归调用 greaterThan；否则递归调用 greaterThan 而不增加计数。

我的预期输出将是C2 = 12。（7大于5个元素，2大于0个元素，4大于1个元素，以此类推）

当前实际输出为5;然后false。
我的程序似乎对 head 元素进行了正确的评估和递增，但是当它完成该元素的 greaterThan 时，程序 returns false。我曾尝试研究和理解序言中的列表和递归调用，但我一直在碰壁。我不确定它是否失败，因为您不能递归地运行增量关系，或者我的列表关系是否存在其他问题。任何关于如何解决此问题以及 prolog 如何在此处发挥作用的说明都会有所帮助。

Answer 1

让我们从您的第一个代码片段开始：

testHead(List).  
testHead([H|T]) :-
    greaterThan(H,T,0),
    teastHead(T).

你有递归的想法，但我看到了四个问题。

首先：testHead只有一个属性，这意味着（除了true和false）你什么也得不到。所以它看起来应该更像这样：testHead([H|T], L) ....

其次：你需要知道什么时候停止。这通常是谓词的第一行。你的声明：任何匹配项。但它应该这样说：如果没有剩余元素，我可以“return”一个空列表。 testHead([],[]).

第三种：你用固定值0调用greaterThan(H,T,0)，这意味着你想测试“输出”值是否为零。事实并非如此，你想数东西。所以在这里放一个变量：N

第四：如果你已经计算出一个值N，你必须将它转发到输出列表。由于您将从递归调用中获得列表 Nlist，因此您可以创建一个新列表，其中 N 作为头元素，Nlist 作为尾元素，“return” this新列表。

结论：

testHead([],[]).
testHead([H|T],[N|Nlist]) :-
    greaterThan(H,T,N),
    testHead(T,Nlist).

遗憾的是我们还不能测试它，我们必须看看greaterThan/3。您的代码段如下：

greaterThan(H,[X|T],C) :-
    H > X ->
    C2 is C+1,
    greaterThan(H,T,C2);
    greaterThan(H,T,C).

还有一些奇怪的部分。

首先：你需要告诉你什么时候停止。通常你会在空列表 [] 或列表只剩下一个元素 [A] 时停止。如果您对 A 的内容不感兴趣，您可以使用以下划线 _ 开头的“丢弃变量”。这导致：greaterThan(_,[],0)。这意味着：如果我的列表为空，则无论参考值是多少，我的列表中都会有 0 个更大的数字。此外，由于规则的顺序很重要，因此您将其放在您的顶部递归规则。

第二个：你的情况是对的，所以如果H比列表的头部X大，做一些事情，否则通过调用没有 X 的同一个谓词来“忽略”X。问题出现在 something 部分：由于 C2 的值在 C 之前是统一的，因此需要根据 [=38= 计算 C ] 而不是相反。 C is C2+1 意思是：我从递归调用中知道值 C2，因为 H>X 我想在它的值上加一，然后“return”它。

第三：问greaterThan(H,T,C2)就知道C2的值了，所以在后面加上C is C2+1

好的，现在我们得到了：

greaterThan(_,[],0).
greaterThan(H,[X|T],C) :-
    H > X ->
    greaterThan(H,T,C2),
    C is C2+1;
    greaterThan(H,T,C).

testHead([],[]).
testHead([H|T],[N|Nlist]) :-
    greaterThan(H,T,N),
    testHead(T,Nlist).

让我们测试一下！

?- testHead( [7,2,4,3,6,9,8,10,12,5],L).
L = [5, 0, 1, 0, 1, 2, 1, 1, 1, 0] ;
false.

看起来不错，除了你想要的不是列表而是总数。好的，给你：

testHead([],0).
testHead([H|T],New) :-
    greaterThan(H,T,N),
    testHead(T,NN),
    New is NN+N.

?- testHead( [7,2,4,3,6,9,8,10,12,5],N).
N = 12 ;
false.

说明：如果你的输入列表是空的，没有什么可做的，“return”加法中性元素：0.
如果您的输入列表有一个头元素 H，计算“大于 N 的剩余元素”到 greaterThan(H,T,N)。假设您的代码有效，因此您可以为尾部列表 T 调用 testHead(T,NN) 并获得总和值 NN。如果 N 和 NN 这两个值都已知，请添加它们并将其声明为“return”。

涉及算术运算和计数元素的列表的递归？

Recursion on a list involving arithmetic operations and counting elements?

recursion

list

prolog

counting