算术
正如您已经发现的那样,算术可以在 Prolog 中使用(is)/2
运算符进行处理。这是因为在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.
尾调用优化
现在,我们仍然可以使用更先进的技术来改进这个谓词。例如,我们可以引入尾调用,以便可以执行尾调用优化(可搜索),这要归功于称为累加器的声明式编程习语:
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
应该避免使用 ,并且应该首选使用约束编程来获得最通用的程序。