代码之家 › 专栏 › 技术社区 › Valera Grishin

在swi prolog中中断基于/3的“循环”,同时保持后面的选择点

prolog-cut prolog loops

2

Valera Grishin · 技术社区 · 7 年前

我需要迭代一系列数字(例如使用 between/3 )从1到 Length 在哪里? 长度 是给定列表的长度。迭代数,比如 N ,然后应用于谓词,例如 do_something 直到它停止失败。也就是说, 多西 搜索正确的 n 之后所有的选择点 之间/ 3 必须删除。然而,所有的选择点 多西 适当地 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 不切 之间/ 3 选择点。一个版本 when/2 也不起作用。我想,这是因为两者都是 冻结/2 和 何时/ 2 在单独的线程中执行,不影响主线程 之间/ 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).

效率低下就是 多西 正确的选择点 n 执行两次。先切前,再切后。

虽然这个解决方案在我的案例中有效,但是它不适用于一般案例 多西 选择点只能执行一次。

注意 n 要求最少 1..Length 范围和事先未知。因此用 做点什么 .

有更好的解决办法吗?有没有实现类似于 之间/ 3 有什么信号会停下来?是否可以有一个专门的内置谓词来执行所需的操作?任何富有成果的想法都受到高度赞赏。

3 回复 | 直到 7 年前

1

2

Paulo Moura 7 年前

结果是 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_s解决方案一样,它不评估 do_something/3 在返回第一个谓词之前,它也不会对谓词进行两次计算。但它也不需要肮脏和不便携的 nb_setarg/2 谓词技巧。

注意,正如简所说的, 软切割 控制结构, *->/2 ,或其 if/3 元谓词变体,可以在几个prolog系统中找到(包括一种或另一种形式的cxprolog、ciao prolog、eclipse、gnu prolog、jiprolog、sicstus prolog、swi prolog和yap)。

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

2

3

Paulo Moura 7 年前

希望我能理解你的问题描述:

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 谓词成功。当这种情况发生时, 芬德尔3 调用确保,对于该值 N ,所有的选择点 do_something(InputList, N, OutputList) 被访问。然后,下面的剪切将固定 n 你可以从那里走。

附笔。 根据您在评论中描述的更改进行更新,使其适用于您的案例。如果你不想收集所有的解决方案,有一些非便携式黑客只会找到给定数量的解决方案。

3

Jan Wielemaker 7 年前

还有另一种可能 *->/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),并且许多系统有某种形式的不可回溯分配,而如果您不顾一切,则可以使用断言/收回。

在线查看: SWISH

保罗的答案当然更便于携带。不过,这应该更快,而且不能评估 do_something 在返回第一个之前,它也不会评估两次做什么。