在编写纯关系序言程序时,可以使用精心放置的 cut 吗?
In writing a purely relational prolog program, is it ok to use a carefully placed cut?
我正在尝试编写一个管理键值存储的关系序言程序。初始代码取自我在互联网上找到的一些讲座幻灯片(http://people.eng.unimelb.edu.au/pstuckey/book/course.html -- 参见:使用数据结构幻灯片)。
newdic([]).
addkey(D0,K,I,D) :- D = [p(K,I)|D0].
delkey([],_,[]).
delkey([p(K,_)|D],K,D).
delkey([p(K0,I)|D0],K,[p(K0,I)|D]) :-
dif(K, K0), delkey(D0,K,D).
此代码允许使用同一键添加多个值 -- 这对我来说很好。但是,它还会添加相同的键值对两次,例如
?- newdic(D), addkey(D, a, 1, D2), addkey(D2, a, 1, D3), lookup(D3, a, X).
D = [],
D2 = [p(a, 1)],
D3 = [p(a, 1), p(a, 1)],
X = 1
D3 包含 p(a,1) 两次。
为确保不会发生这种情况,我添加了以下代码;并确保回溯找不到替代的 addkey 子句,我在第一个子句的末尾添加了一个剪切。
对于纯关系程序来说这是公平的游戏吗——或者是确保不添加重复键值对的更好方法——不使用 cut。
newdic([]).
addkey(D0,K,I,D0) :- lookup(D0, K, I), !. % if the key already do nothing
addkey(D0,K,I,D) :- D = [p(K,I)|D0].
delkey([],_,[]).
delkey([p(K,_)|D],K,D).
delkey([p(K0,I)|D0],K,[p(K0,I)|D]) :-
dif(K, K0), delkey(D0,K,D).
这会导致以下结果:
?- newdic(D), addkey(D, a, 1, D2), addkey(D2, a, 1, D3), lookup(D3, a, X).
D = [],
D2 = D3, D3 = [p(a, 1)],
X = 1.
不,有更多解决方案可用 -- 程序 returns 立即。
非常感谢任何建议,
丹尼尔
注意:顺便说一句:如果我为相同的键添加不同的值,则剪切确实允许回溯以识别相同键的第二个值:
?- newdic(D), addkey(D, a, 1, D2), addkey(D2, a, 1, D3), addkey(D3, a, 2, D4), lookup(D4, a, X).
D = [],
D2 = D3, D3 = [p(a, 1)],
D4 = [p(a, 2), p(a, 1)],
X = 2 ;
D = [],
D2 = D3, D3 = [p(a, 1)],
D4 = [p(a, 2), p(a, 1)],
X = 1.
您可以使用 if-then-else 代替 cut:
addkey(D0,K,I,D0) :-
( lookup(D0, K, I) ->
D = D0 % if the key already [exists] do nothing
; D = [p(K,I)|D0] ).
SWI Prolog 具有用于处理键值对和关联的库谓词。我没有仔细查看它们是否符合您的情况,但需要考虑一些事情。
如果您想推出自己的解决方案,您可以递归地写出 addkey/4
并保持关系行为:
addkey([], K, V, [p(K,V)]). % Add to empty dict
addkey([p(K,V)|T], K, _, [p(K,V)|T]). % Don't add
addkey([p(K,V)|T], Kadd, Vadd, [p(K,V)|TK]) :-
dif(Kadd, K),
addkey(T, Kadd, Vadd, TK).
如果密钥是唯一的,则此实现会添加。如果您使用不同的值尝试相同的键,它会忽略添加并返回相同的字典(这通常是键值对字典的行为方式)。您可以很容易地增强它以获得键值对的唯一性。当然,您使用的 Prolog 需要包含 dif/2
,或者您需要推出自己的 dif/2
。 :)
我正在尝试编写一个管理键值存储的关系序言程序。初始代码取自我在互联网上找到的一些讲座幻灯片(http://people.eng.unimelb.edu.au/pstuckey/book/course.html -- 参见:使用数据结构幻灯片)。
newdic([]).
addkey(D0,K,I,D) :- D = [p(K,I)|D0].
delkey([],_,[]).
delkey([p(K,_)|D],K,D).
delkey([p(K0,I)|D0],K,[p(K0,I)|D]) :-
dif(K, K0), delkey(D0,K,D).
此代码允许使用同一键添加多个值 -- 这对我来说很好。但是,它还会添加相同的键值对两次,例如
?- newdic(D), addkey(D, a, 1, D2), addkey(D2, a, 1, D3), lookup(D3, a, X).
D = [],
D2 = [p(a, 1)],
D3 = [p(a, 1), p(a, 1)],
X = 1
D3 包含 p(a,1) 两次。
为确保不会发生这种情况,我添加了以下代码;并确保回溯找不到替代的 addkey 子句,我在第一个子句的末尾添加了一个剪切。
对于纯关系程序来说这是公平的游戏吗——或者是确保不添加重复键值对的更好方法——不使用 cut。
newdic([]).
addkey(D0,K,I,D0) :- lookup(D0, K, I), !. % if the key already do nothing
addkey(D0,K,I,D) :- D = [p(K,I)|D0].
delkey([],_,[]).
delkey([p(K,_)|D],K,D).
delkey([p(K0,I)|D0],K,[p(K0,I)|D]) :-
dif(K, K0), delkey(D0,K,D).
这会导致以下结果:
?- newdic(D), addkey(D, a, 1, D2), addkey(D2, a, 1, D3), lookup(D3, a, X).
D = [],
D2 = D3, D3 = [p(a, 1)],
X = 1.
不,有更多解决方案可用 -- 程序 returns 立即。
非常感谢任何建议,
丹尼尔
注意:顺便说一句:如果我为相同的键添加不同的值,则剪切确实允许回溯以识别相同键的第二个值:
?- newdic(D), addkey(D, a, 1, D2), addkey(D2, a, 1, D3), addkey(D3, a, 2, D4), lookup(D4, a, X).
D = [],
D2 = D3, D3 = [p(a, 1)],
D4 = [p(a, 2), p(a, 1)],
X = 2 ;
D = [],
D2 = D3, D3 = [p(a, 1)],
D4 = [p(a, 2), p(a, 1)],
X = 1.
您可以使用 if-then-else 代替 cut:
addkey(D0,K,I,D0) :-
( lookup(D0, K, I) ->
D = D0 % if the key already [exists] do nothing
; D = [p(K,I)|D0] ).
SWI Prolog 具有用于处理键值对和关联的库谓词。我没有仔细查看它们是否符合您的情况,但需要考虑一些事情。
如果您想推出自己的解决方案,您可以递归地写出 addkey/4
并保持关系行为:
addkey([], K, V, [p(K,V)]). % Add to empty dict
addkey([p(K,V)|T], K, _, [p(K,V)|T]). % Don't add
addkey([p(K,V)|T], Kadd, Vadd, [p(K,V)|TK]) :-
dif(Kadd, K),
addkey(T, Kadd, Vadd, TK).
如果密钥是唯一的,则此实现会添加。如果您使用不同的值尝试相同的键,它会忽略添加并返回相同的字典(这通常是键值对字典的行为方式)。您可以很容易地增强它以获得键值对的唯一性。当然,您使用的 Prolog 需要包含 dif/2
,或者您需要推出自己的 dif/2
。 :)