prolog - 折叠部分列表

Question

这是一个已删除的对该问题的回答引发的问题。这个问题可以概括如下：

是否可以折叠列表，折叠时生成列表的尾部？

这就是我的意思。假设我想计算阶乘（这是一个愚蠢的例子，但它只是为了演示），并决定这样做：

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 坐标列表折叠一次是不够的（但是您可以分两次进行；请注意，至少有一种更好的方法可以做到这一点，在同一篇 Wikipedia 文章中引用，但这也使用了多次；总的来说，多遍算法假设对相邻像素的恒定时间访问！）。

我自己对原始“区域”问题的解决方案如下所示：

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上面那样清楚地表达结束条件，所以我需要在它之后进行切割（丑陋）。

问题

• 有没有一种干净的方法来关闭列表并删除削减？在阶乘示例中，我们知道何时停止，因为我们有额外的信息；但是，在第二个示例中，我们如何注意到列表的后面应该是空列表？
• 有没有我遗漏的隐藏问题？
• 这看起来有点类似于带有 DCG 的隐式状态，但我不得不承认我从来没有完全了解它是如何工作的；这些有联系吗？

Answer 1

您正在触及 Prolog 的几个非常有趣的方面，每个方面都值得单独提出几个单独的问题。我将对您的实际问题提供一个高层次的回答，并希望您就您最感兴趣的点发表后续问题。

首先，我将片段精简到其本质：

本质（N）：-
        折叠（本质_（N），[2|返回]，返回，_）。

本质_（N，X0，背部，休息）：-
        ( X0 #< N ->
            X1 #= X0 + 1,
            返回 = [X1|休息]
        ; 返回 = []
        ）。

请注意，这可以防止创建非常大的整数，以便我们可以真正研究这种模式的内存行为。

对于您的第一个问题：是的，它在O(1)空间中运行（假设出现整数的空间恒定）。

为什么？因为尽管您在 中不断创建列表Back = [X1|Rest]，但这些列表都可以很容易地被垃圾收集，因为您没有在任何地方引用它们。

要测试程序的内存方面，请考虑以下查询，并限制 Prolog 系统的全局堆栈，以便您可以通过耗尽（全局）堆栈来快速检测增长的内存：

?- 长度（_，E），
   N #= 2^E,
   描绘子句（N），
   精华(N),
   错误的。

这产生：

1.
2.
...
8388608。
16777216。
等等

如果您在某处引用该列表，情况将完全不同。例如：

本质（N）：-
        foldl(essence_(N), [2|Back], Back, _),
        返回 = []。

通过这个非常小的更改，上述查询产生：

?- 长度（_，E），
   N #= 2^E,
   描绘子句（N），
   精华(N),
   错误的。
1.
2.
...
1048576。
错误：超出全局堆栈

因此，某个术语是否在某处被引用会显着影响程序的内存需求。这听起来很吓人，但实际上几乎不是问题：您要么需要该术语，在这种情况下您无论如何都需要在内存中表示它，或者您不需要该术语，在这种情况下它不再被引用在您的程序中并变得适合垃圾收集。事实上，令人惊奇的是 GC 在 Prolog 中也能很好地处理相当复杂的程序，在许多情况下不需要多说。

---

关于你的第二个问题：显然，使用(->)/2几乎总是有很大的问题，因为它将你限制在特定的使用方向上，破坏了我们对逻辑关系所期望的普遍性。

有几种解决方案。如果你的 CLP(FD) 系统支持zcompare/3或类似的特性，你可以这样写essence_/3：

本质_（N，X0，背部，休息）：-
        zcompare(C, X0, N),
        关闭（C，X0，返回，休息）。

关闭（<，X0，[X1|Rest]，Rest）：- X1 #= X0 + 1。
关闭（=，_，[]，_）。

Ulrich Neumerkel 和 Stefan Kralif_/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),
        index_plus_one，
        s_push(V),

对于自己的问题，这是一个非常好的候选者，因此请考虑将其作为预告片。

---

最后，我有一个概括性的评论：在我看来，我们只是在寻找一系列非常强大和通用的元谓词的开始，解决方案空间仍然很大程度上是未开发的。call/N, maplist/[3,4],foldl/4和其他元谓词绝对是一个好的开始。if_/3有可能将良好的性能与我们期望 Prolog 谓词的通用性结合起来。

Answer 2

根据 Boris 的要求，第二个示例使用freeze实现。老实说，我不太确定这是否能回答问题，因为代码（以及 IMO 问题）相当做作，但它就是这样。至少我希望这会让其他人知道冻结可能对什么有用。为简单起见，我使用 1D 问题而不是 2D，但将代码更改为使用 2 个坐标应该是相当简单的。

总体思路是具有 (1) 生成新的 Open/Closed/Rest/etc 的功能。基于前一个的状态，（2）“无限”列表生成器，可以被告知“停止”从“外部”生成新元素，以及（3）折叠“无限”列表的 fold_step 函数，在每个列表上生成新状态列表项，如果该状态被认为是最后一个，则告诉生成器停止。

值得注意的是，list 的元素仅用于通知生成器停止。所有计算状态都存储在累加器中。

鲍里斯，请澄清这是否可以解决您的问题。更准确地说，您试图将什么样的数据传递给折叠步骤处理程序（项目、累加器、下一个累加器）？

adjacent(X, Y) :-
    succ(X, Y) ;
    succ(Y, X).

state_seq(State, L) :-
    (State == halt -> L = [], !)
    ;
    freeze(L, (
        L = [H|T],
        freeze(H, state_seq(H, T))
    )).

fold_step(Item, Acc, NewAcc) :-
    next_state(Acc, NewAcc),
    NewAcc = _:_:_:NewRest,
    (var(NewRest) ->
        Item = next ;
        Item = halt
    ).

next_state(Open:Set:Region:_Rest, NewOpen:NewSet:NewRegion:NewRest) :-
    Open = [],
    NewOpen = Open,
    NewSet = Set,
    NewRegion = Region,
    NewRest = Set.

next_state(Open:Set:Region:Rest, NewOpen:NewSet:NewRegion:NewRest) :-
    Open = [H|T],
    partition(adjacent(H), Set, Adjacent, NotAdjacent),
    append(Adjacent, T, NewOpen),
    NewSet = NotAdjacent,
    NewRegion = [H|Region],
    NewRest = Rest.

set_region_rest(Ns, Region, Rest) :-
    Ns = [H|T],
    state_seq(next, L),
    foldl(fold_step, L, [H]:T:[]:_, _:_:Region:Rest).

对上面代码的一个很好的改进是让 fold_step 成为一个高阶函数，将 next_state 作为第一个参数传递。

Answer 3

如果您的 Prolog 实现支持freeze/2或类似谓词（例如 Swi-Prolog），那么您可以使用以下方法：

fac_list(L, N, Max) :-
    (N >= Max, L = [Max], !)
    ;
    freeze(L, (
        L = [N|Rest],
        N2 is N + 1,
        fac_list(Rest, N2, Max)
    )).

multiplication(X, Y, Z) :-
    Z is Y * X.

factorial(N, Factorial) :-
    fac_list(L, 1, N),
    foldl(multiplication, L, 1, Factorial).

上面的示例首先定义了一个谓词 ( fac_list )，它创建一个从 N 到最大值 (Max) 递增的整数值的“惰性”列表，其中下一个列表元素仅在前一个元素被“访问”后生成（更多内容见下文）。然后，阶乘只是将乘法折叠到惰性列表上，导致内存使用量恒定。

理解此示例如何工作的关键是记住 Prolog 列表实际上只是名称为 '.' 的 arity 2 的术语。（实际上，在 Swi-Prolog 7 中名称已更改，但这对于本次讨论并不重要），其中第一个元素表示列表项，第二个元素表示尾部（或终止元素 - 空列表，[]）。例如。[1, 2, 3] 可以表示为：

.(1, .(2, .(3, [])))

然后，冻结定义如下：

freeze(+Var, :Goal)
    Delay the execution of Goal until Var is bound

这意味着如果我们调用：

freeze(L, L=[1|Tail]), L = [A|Rest].

然后将发生以下步骤：

1. freeze(L, L=[1|Tail])被调用
2. Prolog“记住”当L将与“anything”统一时，它需要调用L=[1|Tail]
3. L = [A|Rest]被称为
4. Prolog 将L与.(A, Rest)统一起来
5. 这种统一触发L=[1|Tail]的执行
6. 显然，这将L统一起来，此时 L 绑定到.(A, Rest)和.(1, Tail)
7. 结果，A与 1 统一。

我们可以将这个例子扩展如下：

freeze(L1, L1=[1|L2]),
freeze(L2, L2=[2|L3]),
freeze(L3, L3=[3]),
L1 = [A|R2], % L1=[1|L2] is called at this point
R2 = [B|R3], % L2=[2|L3] is called at this point
R3 = [C].    % L3=[3] is called at this point

这与前面的示例完全一样，只是它逐渐生成 3 个元素，而不是 1 个。