回溯问题SWI-Prolog

Question

我在SWI-Prolog中遇到了一些回溯问题

在我的谓词中，我有两个列表作为输入，结果是第三个列表。

我从L1中获取nth0/3的每个元素，然后使用另一个我需要的谓词，因此我将第二个和元素追加到第三个列表中，如果other_pred为真。我使用了fail来强制使用nth0回溯，但显然mypred每次都会失败，并且我无法获得我想要的最终列表。

我还尝试将nth0与索引I一起使用，增加了它，但这也会使谓词失败。如果我在每次迭代中检查i是否小于L1长度，也会出现同样的问题。

mypred(L1, L2, Result) :-

    nth0(_, L1, X),
    other_pred(X, L2),
    append(L2, [X], Result), fail.

Answer 1

由于您没有给出other_pred/2的代码，因此将使用member/2。

mypred([H1|T1], L2, [H1|R]) :-
    member(H1,L2),
    mypred(T1,L2,R).

mypred([H1|T1], L2, R) :-
    \+ member(H1,L2),
    mypred(T1,L2,R).

mypred([],_,[]).

示例运行：

?- mypred([1,3,5], [1,2,4,5], R).
R = [1, 5] ;
false.

?- mypred([], [1,2,4,5], R).
R = [].

?- mypred([1,3,5], [], R).
R = [].

?- mypred([1,3,5], [2,4,6], R).
R = [].

?- mypred([1,3,5], [1,3,5], R).
R = [1, 3, 5] ;
false.

虽然您可以通过列表构造函数使用nth0/3，但|/2更好，请参阅：Lists

在这段代码中，[H1|T1]和[H1|R]使用list构造函数。

这段代码还使用了递归。

递归子句是

mypred([H1|T1], L2, [H1|R]) :-
    member(H1,L2),
    mypred(T1,L2,R).

mypred([H1|T1], L2, R) :-
    \+ member(H1,L2),
    mypred(T1,L2,R).

因为谓词mypred/3在子句中被调用。另外，因为对mypred/3的调用是子句中的最后一个调用，所以this is tail-recursive。

递归谓词的基本情况是

mypred([],_,[]).

这是如何工作的

mypred([1,3,5], [1,2,5], R).

第一个参数的列表[1,3,5]是否与第一个谓词匹配

mypred([H1|T1], L2, [H1|R]) :-
    member(H1,L2),
    mypred(T1,L2,R).

这成功地实现了以下统一

H1 = 1
T1 = [3,5]
L2 = [1,2,5]
R = _

执行子句中的下一行：

member(H1,L2)

这是成功的。

执行子句中的最后一行：

mypred(T1,L2,R)

这与第一个谓词匹配

mypred([H1|T1], L2, [H1|R]) :-
    member(H1,L2),
    mypred(T1,L2,R).

这成功地实现了以下统一

H1 = 3
T1 = [5]
L2 = [1,2,5]
R = _

执行子句中的下一行：

member(H1,L2)

这将失败并回溯。

因为有另一个用于my_pred/3的子句，所以尝试使用它。

mypred([H1|T1], L2, R) :-
    \+ member(H1,L2),
    mypred(T1,L2,R).

这成功地实现了以下统一

H1 = 3
T1 = [5]
L2 = [1,2,5]
R = _

执行子句中的下一行：

\+ member(H1,L2)

这是成功的。

这种为谓词尝试不同子句的模式仍在继续。在这一点上，这将跳过细节，直到使用第三个子句。

当第一个参数的列表为[]时，使用第三个子句，

mypred([],_,[]).

现在可以开始回溯了。

因为唯一可以调用第三个子句的代码行是

mypred(T1,L2,R).

在第一和第二条款中，R与[]是统一的。

现在，根据调用列表的子句的不同，第三个参数中的列表将以不同的方式构造。

如果使用了第二个子句，则第三个参数将使用

mypred([H1|T1], L2, R)

因此，列表只是返回未更改的内容。

但是，如果使用了第一个子句，则第三个参数将使用

mypred([H1|T1], L2, [H1|R])

但这一次，第三个参数的结果将是执行子句时的值H1和R的值。所以如果H1是5，R是[]，那么[H1|R]就是[5|[]]，也就是[5]。

下面是一个跟踪运行

mypred([1,3,5], [1,2,5], R).

这样你就可以调用查看所有的细节。

?- trace.
[trace]  ?- mypred([1,3,5], [1,2,5], R).
   Call: (8) mypred([1, 3, 5], [1, 2, 5], _1844)
   Unify: (8) mypred([1, 3, 5], [1, 2, 5], [1|_2090])
   Call: (9) lists:member(1, [1, 2, 5])
   Unify: (9) lists:member(1, [1, 2, 5])
   Exit: (9) lists:member(1, [1, 2, 5])
   Call: (9) mypred([3, 5], [1, 2, 5], _2090)
   Unify: (9) mypred([3, 5], [1, 2, 5], [3|_2096])
   Call: (10) lists:member(3, [1, 2, 5])
   Unify: (10) lists:member(3, [1, 2, 5])
   Fail: (10) lists:member(3, [1, 2, 5])
   Redo: (9) mypred([3, 5], [1, 2, 5], _2090)
   Unify: (9) mypred([3, 5], [1, 2, 5], _2090)
   Call: (10) lists:member(3, [1, 2, 5])
   Unify: (10) lists:member(3, [1, 2, 5])
   Fail: (10) lists:member(3, [1, 2, 5])
   Redo: (9) mypred([3, 5], [1, 2, 5], _2090)
   Call: (10) mypred([5], [1, 2, 5], _2090)
   Unify: (10) mypred([5], [1, 2, 5], [5|_2096])
   Call: (11) lists:member(5, [1, 2, 5])
   Unify: (11) lists:member(5, [1, 2, 5])
   Exit: (11) lists:member(5, [1, 2, 5])
   Call: (11) mypred([], [1, 2, 5], _2096)
   Unify: (11) mypred([], [1, 2, 5], [])
   Exit: (11) mypred([], [1, 2, 5], [])
   Exit: (10) mypred([5], [1, 2, 5], [5])
   Exit: (9) mypred([3, 5], [1, 2, 5], [5])
   Exit: (8) mypred([1, 3, 5], [1, 2, 5], [1, 5])
R = [1, 5] ;
   Redo: (10) mypred([5], [1, 2, 5], _2090)
   Unify: (10) mypred([5], [1, 2, 5], _2090)
   Call: (11) lists:member(5, [1, 2, 5])
   Unify: (11) lists:member(5, [1, 2, 5])
   Exit: (11) lists:member(5, [1, 2, 5])
   Fail: (10) mypred([5], [1, 2, 5], _2090)
   Fail: (9) mypred([3, 5], [1, 2, 5], _2090)
   Redo: (9) lists:member(1, [1, 2, 5])
   Fail: (9) lists:member(1, [1, 2, 5])
   Redo: (8) mypred([1, 3, 5], [1, 2, 5], _1844)
   Unify: (8) mypred([1, 3, 5], [1, 2, 5], _1844)
   Call: (9) lists:member(1, [1, 2, 5])
   Unify: (9) lists:member(1, [1, 2, 5])
   Exit: (9) lists:member(1, [1, 2, 5])
   Fail: (8) mypred([1, 3, 5], [1, 2, 5], _1844)
false.

如果您使用的是SWI-Prolog，则执行此查询组合以调出GUI跟踪器，这更便于学习。

?- gtrace.
[trace]  ?- mypred([1,3,5], [1,2,5], R).   

评论中的每条建议

以下是其他一些细微的代码变化和性能度量。

mypred_01([H1|T1], L2, [H1|R]) :-
    member(H1,L2),
    mypred_01(T1,L2,R).

mypred_01([H1|T1], L2, R) :-
    \+ member(H1,L2),
    mypred_01(T1,L2,R).

mypred_01([],_,[]).

mypred_02(L1,L2,R) :-
    mypred_02_helper(L1,L2,[],R).

mypred_02_helper([H1|T1],L2,R0,R) :-
    (
        member(H1,L2)
    ->
        mypred_02_helper(T1,L2,[H1|R0],R)
    ;
        mypred_02_helper(T1,L2,R0,R)
    ).

mypred_02_helper([],_,R,R).

mypred_03(L1,L2,R) :-
    mypred_03_helper(L1,L2,[],R0),
    reverse(R0,R).

mypred_03_helper([H1|T1],L2,R0,R) :-
    (
        member(H1,L2)
    ->
        mypred_03_helper(T1,L2,[H1|R0],R)
    ;
        mypred_03_helper(T1,L2,R0,R)
    ).

mypred_03_helper([],_,R,R).

mypred_04(L1,L2,R) :-
    mypred_04_helper(L1,L2,[],R).

mypred_04_helper([H1|T1],L2,R0,R) :-
    (
        memberchk(H1,L2)
    ->
        mypred_04_helper(T1,L2,[H1|R0],R)
    ;
        mypred_04_helper(T1,L2,R0,R)
    ).

mypred_04_helper([],_,R,R).

mypred_05(L1,L2,R) :-
    mypred_05_helper(L1,L2,[],R0),
    reverse(R0,R).

mypred_05_helper([H1|T1],L2,R0,R) :-
    (
        memberchk(H1,L2)
    ->
        mypred_05_helper(T1,L2,[H1|R0],R)
    ;
        mypred_05_helper(T1,L2,R0,R)
    ).

mypred_05_helper([],_,R,R).

以下是性能结果。

?- findall(N, between(1,100000,N), L1),time(mypred_01(L1,[1,10,100,10000,100000],R)).
% 1,400,020 inferences, 0.109 CPU in 0.103 seconds (106% CPU, 12800183 Lips)
L1 = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
R = [1, 10, 100, 10000, 100000] ;
% 36 inferences, 0.000 CPU in 0.000 seconds (?% CPU, Infinite Lips)
false.

?- findall(N, between(1,100000,N), L1),time(mypred_02(L1,[1,10,100,10000,100000],R)).
% 799,988 inferences, 0.063 CPU in 0.062 seconds (101% CPU, 12799808 Lips)
L1 = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
R = [100000, 10000, 100, 10, 1].

?- findall(N, between(1,100000,N), L1),time(mypred_03(L1,[1,10,100,10000,100000],R)).
% 800,059 inferences, 0.047 CPU in 0.053 seconds (88% CPU, 17067925 Lips)
L1 = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
R = [1, 10, 100, 10000, 100000].

?- findall(N, between(1,100000,N), L1),time(mypred_04(L1,[1,10,100,10000,100000],R)).
% 299,999 inferences, 0.031 CPU in 0.041 seconds (77% CPU, 9599968 Lips)
L1 = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
R = [100000, 10000, 100, 10, 1].

?- findall(N, between(1,100000,N), L1),time(mypred_05(L1,[1,10,100,10000,100000],R)).
% 300,005 inferences, 0.031 CPU in 0.032 seconds (98% CPU, 9600160 Lips)
L1 = [1, 2, 3, 4, 5, 6, 7, 8, 9|...],
R = [1, 10, 100, 10000, 100000].