6

我想知道一个 Prolog 可能包含这样的内置调用：

accum(generator, filter, accumulator)
Calculates all solutions to generator.
For each one, if filter can be proved, accumulator is proved.
Backtracks to find all solutions to filter and generator.
Accumulator may backtrack internally, but multiple proofs of accumulator are 
  conjoined, not backtracked.

因此，例如，要在不使用递归的情况下对列表求和，您可以编写：

X is 0, accum(member(Val,List), True, X is X + Val).

是否有任何带有此构造的 Prolog 或等价物？请记住，我是 Prolog 的新手，可能会遗漏一些明显的东西。

4

3 回答 3

5

SWI-Prolog library(aggregate)有一个强大的接口，例如

aggregate_all(sum(Val), member(Val,List), Sum)

聚合和生成之间的（显然很简单）变量共享是通过您可能感兴趣的谓词foreach /2 获得的。

在 SWI-Prolog 中，您可以?- edit(library(aggregate)).研究内部结构......

library(aggregate) 效率相对较低，但加上 SWI-Prolog nb_ (non backtrackable) 数据结构应该可以很好地完成它的工作......

关于不可回溯的数据结构：这是我的“自建”累加器的示例，通过nb_setarg /3 实现。

于 2013-10-17T13:55:18.497 回答
3

在 Mercury 的标准库中，“解决方案”模块提供了这样的功能。

请注意，X is X + Val它不会为 X 分配新值。如果 Val 为零，则该语句为 true，如果它是任何其他数字，则为 false，这可能不是您的意思。像这样的累加器通常表示为初始值和最终值之间的关系。

在 Mercury 中，您的示例可以写成：

:- import_module solutions.
...
sumlist(List, Sum) :-
    Generator = (pred(Val::out) is nondet :- member(Val, List), true),
    Accumulator = (pred(X::in, Y::in, Z::out) is det :- Z = X + Y),
    aggregate(Generator, Accumulator, 0, Sum).

不需要单独的过滤器参数，因为它可以作为生成器的一部分包含在内。

于 2014-10-05T12:03:21.953 回答
3

我假设您的意思是没有显式递归？如果是这样，您可以使用高阶谓词列表 fold left 的实现，以及 lambda 表达式以避免需要辅助谓词。以 Logtalk 为例，您可以编写：

?- Sum0 is 0, meta::fold_left([X,Y,Z]>>(Z is Y+X), Sum0, [1,2,3], Sum).
Sum0 = 0,
Sum = 6.

Logtalk 可以用作大多数 Prolog 实现（http://logtalk.org/）的后端编译器。您还可以将 Ulrich 的lambda库 ( http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/ISO-Hiord.html ) 与受支持的 Prolog 编译器一起使用，以及提供左折叠谓词的 Prolog 库同样的结果。以现在 YAP 为例：

$ yap
...
 ?- use_module(library(lambda)).
...
 ?- use_module(library(maplist)).
...
 ?- Sum0 is 0, foldl(\X^Y^Z^(Z is Y+X), [1,2,3], Sum0, Sum).
Sum = 6,
Sum0 = 0.

简而言之，fold left 谓词遍历列表，递归地将其第一个参数中的闭包应用到列表元素和累加器，返回最终的累加器值。

于 2013-10-17T13:40:57.700 回答