我在SWI-Prolog中有一些回溯问题
在我的谓词中,我有2个列表作为输入,结果是第三个。
我从L1获取每个元素与nth0 / 3,然后我使用我需要的另一个谓词,所以我追加到第三个列表第二个和元素如果other_pred为真。我正在使用无法用nth0强制回溯,但显然mypred每次都失败,我无法得到我想要的最终列表。
我也尝试使用nth0和索引I,增加它,但它也使谓词失败。如果我检查每次迭代我是否低于L1长度,则同样的问题。
mypred(L1, L2, Result) :-
nth0(_, L1, X),
other_pred(X, L2),
append(L2, [X], Result), fail.
由于你没有给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]
使用列表构造函数。
此代码也使用递归。
递归条款是
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
的调用是该条款中的最后一次调用,所以这是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].