如何在prolog中获得给定数字的总和？

Question

我是初学者,我正在练习练习.所以我试图在列表中得到给定数字的总和.我想用这个:

my_last(X, [X]).  
my_last(X, [_|L]) :- my_last(X, L).

(从这里)

作为我的向导.这是我获得总和的代码:

listsum(X, []).                  
listsum(X, [H|L]):-
    X is H + listsum(X, L).

当我编译它时,它说

practice.pl:3:可评估listsum(_G139,_G140)不存在
practice.pl:2:单例变量:[X]

然后当我尝试listsum(0, [1,2,3]).它返回false.

我仍然不太了解prolog,并在prolog中列出和递归.

Answer 1

算术

正如您已经发现的,可以使用(is)/2运算符在Prolog中处理算术运算.这是因为在Prolog中,一切都只是象征性的微积分:默认情况下,事物没有意义,所以统一(=)/2不会知道这(+)/2是指例如加法.

现在,你的问题是你在里面使用常规谓词(is)/2(这是你的递归调用).由于(is)/2只执行算术运算,因此不会评估谓词调用.它甚至不识别它,因为它不是算术函数.

这里的修复是影响对变量的递归调用的结果,然后在(is)/2调用中使用它:

listsum(X,[]).
listsum(Result, [Head|Tail]) :-
    listsum(SumOfTail, Tail),
    Result is Head + SumOfTail.

基本案例正确性

但是,如果您测试该代码,您将无法获得所需的结果.原因是你的基本情况还有另一个问题.正如你写的那样,空列表的总和不是"任何东西"

listsum(X,[]).

(X是一个自由变量,因此可以是任何东西).

相反,它是0:

listsum(0, []).

结果代码是:

listsum(0, []).
listsum(Result, [Head|Tail]) :-
    listsum(SumOfTail, Tail),
    Result is Head + SumOfTail.

参数顺序

现在,作为旁注,在Prolog中,一个约定是输出变量应该放在谓词的末尾,而输入变量应该放在谓词的开头,所以为了按照需要行事我们可以重构如下:

listsum([], 0).
listsum([Head|Tail], Result) :-
    listsum(Tail, SumOfTail),
    Result is Head + SumOfTail.

尾调用优化

现在,我们仍然可以使用更先进的技术来改进这个谓词.例如,我们可以引入尾调用,以便可以执行尾调用优化(googlable),这要归功于称为累加器的声明性编程的惯用语:

listsum(List, Sum) :-
    listsum(List, 0, Sum).

listsum([], Accumulator, Accumulator).

listsum([Head|Tail], Accumulator, Result) :-
    NewAccumulator is Accumulator + Head,
    listsum(Tail, NewAccumulator, Result).

这背后的想法是在递归的每一步更新中间结果(通过向列表添加列表的当前头的值),然后只是说明当列表为空时,该中间值是最终值.

获得更多通用课程

正如您在Prolog中可能已经注意到的那样,谓词通常可以通过多种方式使用.例如,length/2可用于发现列表的长度:

?- length([1, 2, 3], Length).
Length = 3.

或者使用所需长度的自由变量构建骨架列表:

?- length(List, 3).
List = [_G519, _G522, _G525].

在这里,你可能已经注意到你不能问Prolog什么是有以下总和的列表6:

?- listsum(L, 6).
ERROR: is/2: Arguments are not sufficiently instantiated

这是因为,为了"倒退",Prolog必须在调用(is)/2运算符时解决方程.虽然你的很简单(只有加法),但算法在一般情况下不能以这种方式解决.

为了克服该问题,可以使用约束编程.一个非常好的库可供SWI,clpfd使用.

这里的语法是:

:- use_module(library(clpfd)).

listsum(List, Sum) :-
    listsum(List, 0, Sum).

listsum([], Accumulator, Accumulator).

listsum([Head|Tail], Accumulator, Result) :-
    NewAccumulator #= Accumulator + Head,
    listsum(Tail, NewAccumulator, Result).

现在我们可以用另一种方式使用我们的谓词,我们希望我们可以使用它:

?- listsum(L, 6).
L = [6] ;
L = [_G1598, _G1601],
_G1598+_G1601#=6 ;
L = [_G1712, _G1715, _G1718],
_G1712+_G1715#=_G1728,
_G1728+_G1718#=6 . % Here I interrupted the answer but it would not terminate.

我们甚至可以要求解决问题的所有方法:

?- listsum(L, X).
L = [],
X = 0 ;
L = [X],
X in inf..sup ;
L = [_G2649, _G2652],
_G2649+_G2652#=X . % Here I interrupted the answer but it would not terminate

我刚刚提到这一点,以便你意识到(is)/2应该避免使用,并且首选使用约束编程来获得最常用的程序.