10

我是 prolog 的新手,我正在做一些练习。所以我试图得到一个列表中给定数字的总和。我正在尝试使用这个:

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中的列表和递归。

4

2 回答 2

25

算术

正如您已经发现的那样,算术可以在 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应该避免使用 ,并且应该首选使用约束编程来获得最通用的程序。

于 2012-07-17T11:01:42.940 回答
2

如果可能,请使用而不是普通的旧(is)/2(和朋友)。

clpfdsum/3提供了一个符合您需求的逻辑纯谓词!

于 2015-05-05T13:27:20.430 回答