9 prolog fold swi-prolog meta-predicate
这是一个已经删除的问题答案引发的问题.该问题可归纳如下:
是否可以折叠列表,折叠时生成列表的尾部？
这就是我的意思.假设我想计算阶乘(这是一个愚蠢的例子,但它仅用于演示),并决定这样做:
fac_a(N, F) :-
must_be(nonneg, N),
( N =< 1
-> F = 1
; numlist(2, N, [H|T]),
foldl(multiplication, T, H, F)
).
multiplication(X, Y, Z) :-
Z is Y * X.
在这里,我需要生成我给出的列表foldl.但是,我可以在常量内存中执行相同的操作(不生成列表而不使用foldl):
fac_b(N, F) :-
must_be(nonneg, N),
( N =< 1
-> F = 1
; fac_b_1(2, N, 2, F)
).
fac_b_1(X, N, Acc, F) :-
( X < N
-> succ(X, X1),
Acc1 is X1 * Acc,
fac_b_1(X1, N, Acc1, F)
; Acc = F
).
这里的要点是,与使用的解决方案不同foldl,它使用常量内存:无需生成包含所有值的列表!
计算阶乘不是最好的例子,但接下来的愚蠢更容易理解.
假设我真的害怕循环(和递归),并且坚持使用折叠来计算阶乘.不过,我仍然需要一份清单.所以这是我可能会尝试的:
fac_c(N, F) :-
must_be(nonneg, N),
( N =< 1
-> F = 1
; foldl(fac_foldl(N), [2|Back], 2-Back, F-[])
).
fac_foldl(N, X, Acc-Back, F-Rest) :-
( X < N
-> succ(X, X1),
F is Acc * X1,
Back = [X1|Rest]
; Acc = F,
Back = []
).
令我惊讶的是,这符合预期.我可以在部分列表的头部使用初始值"播种"折叠,并在消耗当前头部时继续添加下一个元素.定义fac_foldl/4几乎与fac_b_1/4上面的定义相同:唯一的区别是状态保持不同.我的假设是这应该使用常量内存:这个假设是错误的吗？
我知道这很愚蠢,但它可以用于折叠折叠开始时无法知道的列表.在原始问题中,我们必须找到一个连接区域,给出一个xy坐标列表.折叠一次xy坐标列表是不够的(但是你可以在两次传递中完成 ;注意至少有一种更好的方法可以做到这一点,在同一篇维基百科文章中引用,但这也使用了多次传递;总而言之,多次通过算法假设对相邻像素进行恒定时间访问!).
我对原始"地区"问题的解决方案看起来像这样:
set_region_rest([A|As], Region, Rest) :-
sort([A|As], [B|Bs]),
open_set_closed_rest([B], Bs, Region0, Rest),
sort(Region0, Region).
open_set_closed_rest([], Rest, [], Rest).
open_set_closed_rest([X-Y|As], Set, [X-Y|Closed0], Rest) :-
X0 is X-1, X1 is X + 1,
Y0 is Y-1, Y1 is Y + 1,
ord_intersection([X0-Y,X-Y0,X-Y1,X1-Y], Set, New, Set0),
append(New, As, Open),
open_set_closed_rest(Open, Set0, Closed0, Rest).
使用与上面相同的"技术",我们可以将其扭曲成折叠:
set_region_rest_foldl([A|As], Region, Rest) :-
sort([A|As], [B|Bs]),
foldl(region_foldl, [B|Back],
closed_rest(Region0, Bs)-Back,
closed_rest([], Rest)-[]),
!,
sort(Region0, Region).
region_foldl(X-Y,
closed_rest([X-Y|Closed0], Set)-Back,
closed_rest(Closed0, Set0)-Back0) :-
X0 is X-1, X1 is X + 1,
Y0 is Y-1, Y1 is Y + 1,
ord_intersection([X0-Y,X-Y0,X-Y1,X1-Y], Set, New, Set0),
append(New, Back0, Back).
这也"有效".折叠留下了一个选择点,因为我没有fac_foldl/4如上所述表达结束条件,所以我需要在它之后进行切割(丑陋).
您正在触及 Prolog 的几个非常有趣的方面，每个方面都值得单独提出几个问题。我将为您的实际问题提供高水平的答案，并希望您针对您最感兴趣的点提出后续问题。
首先，我将把片段精简到其本质：
本质（N）：-
Foldl(essence_(N), [2|后], 后, _).
Essential_(N, X0, 背部, 休息) :-
( X0 #<N->
X1 #= X0 + 1,
后退 = [X1|休息]
; 返回 = []
）。
请注意，这可以防止创建极大的整数，以便我们可以真正研究此模式的内存行为。
对于你的第一个问题：是的，这在O(1)空间中运行（假设上升整数的空间恒定）。
为什么？因为尽管您不断地在 中创建列表Back = [X1|Rest]，但这些列表都可以很容易地被垃圾收集，因为您没有在任何地方引用它们。
要测试程序的内存方面，请考虑以下查询，并限制 Prolog 系统的全局堆栈，以便您可以通过耗尽（全局）堆栈来快速检测不断增长的内存：
?- 长度(_, E), N #= 2^E, 描绘子句(N), 精华(N), 错误的。
这产生：
1. 2. ... 8388608。 16777216。 ETC。
如果您在某处引用该列表，情况将完全不同。例如：
本质（N）：-
Foldl(essence_(N), [2|返回], 返回, _),
返回=[]。
通过这个非常小的更改，上面的查询将产生：
?- 长度(_, E), N #= 2^E, 描绘子句(N), 精华(N), 错误的。 1. 2. ... 1048576。 错误：超出全局堆栈
因此，是否在某处引用某个术语会显着影响程序的内存需求。这听起来很可怕，但在实践中确实不是一个问题：您要么需要该术语，在这种情况下您需要在内存中表示它，要么您不需要该术语，在这种情况下它不再被引用在你的程序中并且变得适合垃圾收集。事实上，令人惊奇的是，GC 在 Prolog 中也适用于相当复杂的程序，在许多情况下无需多言。
关于你的第二个问题：显然，使用(->)/2几乎总是存在很大的问题，因为它将你限制在特定的使用方向，破坏了我们期望从逻辑关系中获得的普遍性。
对此有几种解决方案。如果你的CLP(FD)系统支持zcompare/3或者类似的功能，你可以essence_/3这样写：
Essential_(N, X0, 背部, 休息) :-
zcompare(C, X0, N),
关闭（C，X0，后退，休息）。
关闭(<, X0, [X1|Rest], Rest) :- X1 #= X0 + 1。
关闭（=，_，[]，_）。
Ulrich Neumerkel 和 Stefan Kral 最近在Indexing dif/2if_/3中引入了另一个非常好的元谓词，称为Indexing dif/2 。我将实施这一点视为一项非常有价值且具有指导意义的练习。讨论这个问题本身就很值得！if_/3
关于第三个问题：拥有 DCG 的国家与此有何关系？如果您想将全局状态传递给多个谓词，其中只有少数谓词需要访问或修改状态，而大多数谓词只是简单地传递状态，那么 DCG 表示法绝对有用。这与 Haskell 中的monad完全相似。
“正常”Prolog 解决方案是用 2 个参数扩展每个谓词，以描述谓词调用之前的状态与其之后的状态之间的关系。DCG 表示法可以让您避免这种麻烦。
重要的是，使用 DCG 表示法，即使您需要全局状态，您也可以几乎逐字地将命令式算法复制到 Prolog，而无需引入许多辅助参数。作为一个例子，请考虑 Tarjan 的强连接组件算法的命令式术语片段：
函数强连接(v)
// 将 v 的深度索引设置为最小的未使用索引
v.index := 索引
v.lowlink := 索引
索引 := 索引 + 1
S.push(v)
这显然利用了全局堆栈和索引，它们通常会成为您需要在所有谓词中传递的新参数。DCG 表示法并非如此！目前，假设全局实体很容易访问，因此您可以在 Prolog 中将整个片段编码为：
scc_(V) -->
vindex_is_index(V),
vlowlink_is_index(V),
索引加一，
s_推(V),
对于它自己的问题来说，这是一个非常好的候选者，所以请将此视为一个预告片。
最后，我有一个一般性的评论：在我看来，我们才刚刚开始寻找一系列非常强大和通用的元谓词，并且解决方案空间仍然很大程度上未被探索。call/N、maplist/[3,4]、foldl/4和其他元谓词绝对是一个好的开始。if_/3有潜力将良好的性能与我们期望的 Prolog 谓词的通用性结合起来。
| 归档时间： |
|
| 查看次数： |
935 次 |
| 最近记录： |