将部分列表折叠

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的解决方案不同，这个解决方案使用恒定的内存：不需要生成带有所有值的列表！

计算阶乘不是最好的例子，但易于理解接下来的愚蠢。

假设我非常害怕循环（和递归），并坚持使用fold来计算阶乘。然而，我仍然需要一个列表。因此，我可能会尝试以下操作：

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的定义相同：唯一的区别在于状态的维护方式不同。我的假设是，这应该使用恒定的内存：这个假设是错误的吗？ 我知道这很傻，但它可能对于折叠无法在折叠开始时知道的列表非常有用。在原始问题中，我们需要给出一组x-y坐标的连接区域。仅对x-y坐标列表进行一次折叠是不够的（您可以使用两次通过方法；请注意，至少有一种更好的方法在同一维基百科文章中引用，但这也使用多个通过；总体而言，多通道算法假设可以恒定时间访问相邻像素！）。

我对原始“区域”问题的自己的解决方案看起来像这样：

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中的隐式状态有些相似，但我必须承认我从未完全弄清楚它是如何工作的；它们是否相关？

- user1812457

---

“fold over a partial list” 在哪里是 SWI 特定的呢？foldl/4绝对不是 SWI 特定的。它甚至出现在 Richard O'Keefe 的库提案中。任何初学者都可以在任何 Prolog 系统中实现它。[tag: swi-prolog] 标签应该保留用于清楚地说明与 SWI 相关的问题，以便用户更轻松地找到这些相关问题。将任何使用 SWI 提供的单个谓词的地方标记为“SWI”会使查找此类实例变得不可能。 - mat

@mat 我刚刚在阅读同样的内容：向下滚动查找“Higher order list predicates”。foldl/4就在那里。然而，must_be/2不在其中。它是否在标准库中？ - user1812457

@mat Prolog代码只能在单个 Prolog系统中运行，它是特定于该系统的。任何试图在其他系统中执行代码的人都会遇到错误。在某些提案中指定谓词并不意味着它成为标准，特别是对于像fold/4这样有多个合理参数顺序的情况。 - Paulo Moura

我知道这种情况经常发生。但请阅读有关标签的文档：它们旨在使将来对问题的搜索更容易，而不是表示发布者的特定情况。只有从后一种观点来看，标记用户系统才有意义，但在该页面上标记系统无法按照标签系统的工作方式运行。未来的读者应该很容易地找到与其系统相关的问题。用无关的问题混淆他们的标签会使他们过滤相关问题变得更加困难。 - mat

未来的读者不应该被迫进行试错，只能使用一个通用的“prolog”标签来寻找答案，而这个标签只适用于特定的系统。一个令人讨厌的后果是用户认为他们使用的Prolog系统是损坏的，因为它无法运行那些所谓的通用答案。另一个令人讨厌的后果，在SO中也很常见，即用户（即使是高级用户）认为某个谓词是标准内置谓词，而实际上它是一个库谓词，远非在Prolog系统中是标准（官方或事实上）。 - Paulo Moura

Answer 1

您涉及了Prolog的几个非常有趣的方面，每个方面都值得单独提出几个问题。我将为您的实际问题提供高层次的答案，并希望您就最感兴趣的问题发布后续问题。

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

essence(N) :- foldl(essence_(N), [2|Back], Back, _).

essence_(N, X0, Back, Rest) :- ( X0 #< N -> X1 #= X0 + 1, Back = [X1|Rest] ; Back = [] ).

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

对于您的第一个问题：是的，这在O（1）空间中运行（假设引起整数的空间是恒定的）。

为什么？因为尽管您不断地在“Back = [X1 | Rest]”中创建列表，但是由于您没有在任何地方引用它们，所以所有这些列表都可以轻松地进行垃圾回收。

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

``` ?- length(_, E), N #= 2^E, portray_clause(N), essence(N), false. ```

这将产生以下结果： ``` 1. 2. ... 8388608. 16777216. 等等。 ```

如果您在某个地方引用了列表，则情况将完全不同。例如：

``` essence(N) :- foldl(essence_(N), [2|Back], Back, _), Back = []. ```

通过这个非常小的更改，上述查询将产生以下结果：

``` ?- length(_, E), N #= 2^E, portray_clause(N), essence(N), false. 1. 2. ... 1048576. ERROR: Out of global stack ```

因此，一个术语是否被引用会显著影响程序的内存需求。听起来很可怕，但实际上在实践中几乎不是问题：如果需要该术语，则必须在内存中表示它；如果不需要该术语，则它在程序中不再被引用并变得易于垃圾回收。事实上，令人惊奇的是，在Prolog中，即使对于相当复杂的程序，GC也能够很好地工作，因此在许多情况下不需要过多地谈论它。

---

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

有几种解决方法。如果您的 CLP(FD) 系统支持 zcompare/3 或类似功能，则可以按以下方式编写 essence_/3：

essence_(N, X0, Back, Rest) :-
        zcompare(C, X0, N),
        closing(C, X0, Back, Rest).
closing(<, X0, [X1|Rest], Rest) :- X1 #= X0 + 1.
closing(=, _, [], _).

另一个非常好的元谓词叫做if_/3，最近由 Ulrich Neumerkel 和 Stefan Kral 在 Indexing dif/2 中介绍。我认为使用 if_/3 实现这一点是非常值得的，并且对于学习也很有益。讨论这个问题也是非常值得的，需要单独提问！

---

第三个问题：具有DCGs的状态与此有何关系？如果您想将全局状态传递给几个谓词，其中只有少数需要访问或修改状态，而大多数仅通过状态，则DCG符号肯定很有用。这与Haskell中的monads完全类似。

“正常”的Prolog解决方案是为每个谓词添加2个参数，以描述调用谓词之前的状态和调用后的状态之间的关系。DCG符号可让您避免这种麻烦。

重要的是，使用DCG符号，即使需要全局状态，您也可以将命令算法几乎逐字复制到Prolog中，而无需引入许多辅助参数。作为此示例，请考虑Tarjan的强连通分量算法的片段，在命令式术语中：

这明显使用了全局的堆栈和索引，通常情况下你需要在所有的谓词中传递这些参数。但是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 谓词期望的通用性相结合。

- mat

---

感谢您对一个有点冗长的问题给出了详尽的答案。现在，我对使用foldl的奇怪方法唯一的实际问题来自于结束条件，因为我不确定它是什么。当foldl的第一个参数是一个适当的列表时，结束条件是“列表为空”。在第一个示例（阶乘）和您的“本质”示例中，我们有一个额外的参数来表达结束条件是什么。然而，在“区域”示例中，结束条件是“列表为空”...您看到循环逻辑了吗？ - user1812457

我理解问题“是否有一种不使用cut的干净方法来关闭列表”也适用于阶乘示例，因为即使两个分支都可以逻辑上应用（尝试使用更一般的查询），你也会不纯地承诺一个条件分支。虽然这种方法比使用!/0更局部，但仍然很糟糕，因为它削弱了代码的普适性。由于我们在讨论这么多问题，我希望看到“区域示例的好元谓词是什么”的问题被分解成自己的问题，并提供指针。 - mat

Answer 2

如果你的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），其中下一个列表元素仅在“访问”前一个元素后生成（下面会详细说明）。然后，factorial只是将multiplication折叠到惰性列表上，从而实现恒定的内存使用。

理解这个例子的关键是记住，Prolog列表实际上只是具有名称“。”（实际上，在Swi-Prolog 7中名称已更改，但这对本讨论不重要）的二元项，其中第一个元素表示列表项，第二个元素表示尾部（或终止元素-空列表，[]）。例如，[1,2,3]可以表示为：

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

然后，freeze 的定义如下：

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与“任何东西”统一时，需要调用L=[1|Tail]
3. 调用L = [A|Rest]
4. Prolog将L与.(A, Rest)统一
5. 这个统一触发了L=[1|Tail]的执行
6. 显然，此时已经绑定到.(A, Rest)的L将与.(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个。

- anonymous

---

我的问题中第二个例子怎么样？阶乘只是一个原理证明，而且选择不太好。第二个例子现在存在一个真正的问题（我不知道何时关闭列表），我仍然不确定如何处理它。freeze 有帮助吗？ - user1812457

Answer 3

根据Boris的要求，第二个例子使用freeze实现。老实说，我不太确定这是否回答了问题，因为代码（以及问题）相当牵强，但是在这里。至少我希望这会给其他人一个冻结可能有用的想法。为简单起见，我使用1D问题而不是2D，但更改代码以使用2个坐标应该相当容易。

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

值得注意的是，列表元素仅用于通知生成器停止。所有计算状态都存储在累加器中。 Boris，请澄清这是否解决了您的问题。更准确地说，您试图将哪种数据传递给fold step处理程序（Item、Accumulator、Next Accumulator）？

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作为第一个参数传递。

- anonymous

---

我现在有其他事情要忙，所以需要一些时间来仔细阅读和使用你的示例，但我会尽快处理并告诉你。 - user1812457