2

我需要遍历between/3从 1 到Length给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可以在以某种方式发出信号时停止的谓词？是否有一个专门的内置谓词可以满足需要？任何富有成效的想法都将受到高度赞赏。

4

3 回答 3

4

还有另一种使用*->/2的可能性，它是 ->/2 的变体，不会杀死条件的选择点。现在我们不存在我们想要杀死一个较旧的选择点。我不知道是否有 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在线查看

保罗的回答肯定更便携。这应该会更快，并且不会do_something在返回第一个之前评估所有解决方案，也不会评估 do_something 两次。

于 2018-11-21T15:17:21.247 回答
3

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

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调用将返回，Solutions = []直到do_something/3谓词成功。发生这种情况时，findall/3调用会确保对于 的值N，所有的选择点do_something(InputList, N, OutputList)都被访问。然后，以下剪切修复了 的值，N您可以从那里开始。

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

于 2018-11-20T11:45:24.377 回答
2

事实证明，这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 所说，软切割控制结构*->/2或其if/3元谓词变体可以在多个 Prolog 系统中找到（包括，以一种或另一种形式，CxProlog、Ciao Prolog、ECLiPSe、GNU Prolog、JIProlog 、SICStus Prolog、SWI-Prolog 和 YAP）。

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

于 2018-11-21T17:17:48.540 回答