在 SWI-Prolog 中打破 between/3 基于 "loop"，同时保持其后的选择点

Question

我需要遍历从 1 到 Length 的一系列数字（例如使用 between/3），其中 Length 是给定列表的长度。迭代数字，比如 N，然后应用于谓词，比如 do_something，直到它停止失败。也就是说，do_something 搜索正确的 N，然后必须删除 between/3 的所有选择点。但是，所有do_something的选择点都必须执行N。

拳头尝试是这样的：

% main(+InputList, -N, -OutputList)
main(InputList, N, OutputList) :-
  length(InputList, Length),
  between(1, Length, N),

  % cut all between/3 choice points as soon as Num is instantiated
  freeze(Num, !),

  do_something(InputList, N, OutputList),
  Num is N.

这没有用，因为 freeze/2 没有削减 between/3 选择点。 when/2 的版本也不起作用。我想，这是因为 freeze/2 和 when/2 都是在单独的线程中执行的，不会影响 between/3 所在的主线程。

一段时间后，我得到了以下代码，它可以完成所需的工作，但效率低下：

main(InputList, N, OutputList) :-
  length (InputList, Length),
  between(1, Length, N),
  do_something(InputList, N, _),

  % cut all prior choice points as soon as proper N is found
  !,

  % start do_something over!
  do_something(InputList, N, OutputList).

效率低下是do_something的选择点选择得当N被执行了两次。首先是在剪辑之前，然后是在剪辑之后。

虽然这个解决方案适用于我的情况，但它不适用于所有 do_something 个选择点必须只执行一次的一般情况。

请注意，N 必须是 1..Length 范围之外的最小值，并且事先无法得知。因此用 do_something.

搜索它

有更好的解决办法吗？有没有一种方法可以实现类似于 between/3 的谓词，它可以在以某种方式发出信号时停止？是否可以有一个专门的内置谓词来执行所需的操作？任何富有成效的想法都将受到高度赞赏。

Answer 1

希望我理解你的问题描述：

main(InputList, N, OutputList) :-
    length(InputList, Length),
    between(1, Length, N),
    findall(
        OutputList0,
        do_something(InputList,N,OutputList0),
        OutputLists
    ),
    % cut all prior choice points as soon as proper N is found
    OutputLists = [_|_],
    !,
    member(OutputList, OutputLists).

findall/3 调用将 return Solutions = [] 直到 do_something/3 谓词成功。当发生这种情况时，findall/3 调用确保对于 N 的值，访问 do_something(InputList, N, OutputList) 的所有选择点。下面的剪辑然后修复了 N 的值，你可以从那里开始。

P.S. 更新了您在评论中描述的更改，使其适用于您的案例。如果您不想收集所有解决方案，有一些非便携式黑客可以只找到给定数量的解决方案。

Answer 2

还有另一种可能使用 *->/2，它是 ->/2 的变体，不会杀死条件的选择点。现在我们不在那里我们想要杀死一个 older 选择点。我不知道是否有Prolog系统可以这样做。自某些标记以来，大多数都有杀死所有选择点的规定，但我不知道有一个杀死特定的选择点。因此，我们必须插入一些代码来有条件地停止进一步处理。这导致：

main(InputList, N, OutputList) :-
    length(InputList, Length),
    State = state(cont),
    between(1, Length, N),
    (   State = state(cont)
    ->  true
    ;   !,
        fail
    ),
    (   do_something(InputList, N, OutputList)
    *-> nb_setarg(1, State, stop)
    ;   fail
    ).

这完全是不可移植的，虽然许多系统有 *->（有时命名为 if/3）并且许多系统有某种形式的不可回溯分配，但如果你绝望，你可以使用 assert/retract为此。

在线查看 SWISH

Paulo 的回答当然更便于携带。这应该更快，并且在返回第一个之前不会评估 do_something 的所有解决方案，它也不会评估 do_something 两次。

Answer 3

原来between/3是分心。我们不需要它，因此一个简单、高效、便携的解决方案是可能的：

main(InputList, N, OutputList) :-
    length(InputList, Length),
    Length >= 1,
    main(1, Length, InputList, OutputList).

main(N, Length, InputList, OutputList) :-
    (   do_something(InputList, N, OutputList) *->
        true
    ;   N < Length,
        M is N + 1,
        main(M, Length, InputList, OutputList)
    ).

与 Jan 的解决方案一样，它不会在返回第一个之前评估 do_something/3 的所有解决方案，也不会评估谓词两次。但它也不需要讨厌的和不可移植的 nb_setarg/2 谓词技巧。

请注意，正如 Jan 所说，可以找到 soft-cut 控制结构 *->/2 或其 if/3 元谓词变体在几个 Prolog 系统中（包括，以一种或另一种形式，CxProlog、Ciao Prolog、ECLiPSe、GNU Prolog、JIProlog、SICStus Prolog、SWI-Prolog 和 YAP）。

P.S。我保留我的第一个答案，因为它更便携，并且举例说明了一种可能对其他问题有用的模式。

在 SWI-Prolog 中打破 between/3 基于 "loop"，同时保持其后的选择点

Breaking between/3 based "loop" in SWI-Prolog while maintaining choice points that follow it

loops

prolog

prolog-cut