Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
442 views
in Technique[技术] by (71.8m points)

prolog - different/2 - does a pure, determinate definition exist?

different(Xs, Ys) :-
   member(X, Xs),
   non_member(X, Ys).
different(Xs, Ys) :-
   member(Y, Ys),
   non_member(Y, Xs).

While this definition using member/2 and non_member/2 is almost1 perfect from a declarative viewpoint, it produces redundant solutions for certain queries and leaves choice points all around.

What is a definition that improves upon this (in a pure manner probably using if_/3 and (=)/3) such that exactly the same set of solutions is described by different/2 but is determinate at least for ground queries (thus does not leave any useless choice points open) and omits (if possible) any redundant answer?


1 Actually, different([a|nonlist],[]), different([],[b|nonlist]) succeeds. It could equally fail. So a solution that fails for both is fine (maybe even finer).

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Reply

0 votes
by (71.8m points)

First try!

The following code is based on the meta-predicates tfilter/3 and tpartition/4, the monotone if-then-else control construct if_/3, the reified unary logical connective not_t/3, and the reified term equality predicate (=)/3:

different([],[_|_]).
different([X|Xs0],Ys0) :-
   tpartition(=(X),Ys0,Es,Ys1),
   if_(Es=[], true, (tfilter(not_t(=(X)),Xs0,Xs1),different(Xs1,Ys1))).

Sample query:

?- different([A,B],[X,Y]).
                A=Y ,           dif(B,Y),     X=Y
;     A=X           ,     B=X           , dif(X,Y)
;     A=X           , dif(B,X), dif(B,Y), dif(X,Y)
;               A=Y ,               B=Y , dif(X,Y)
;               A=Y , dif(B,X), dif(B,Y), dif(X,Y)
; dif(A,X), dif(A,Y).

Let's observe determinism when working with ground data:

?- different([5,4],[1,2]).
true.

The above approach feels like a step in the right direction... But, as-is, I wouldn't call it perfect.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
OGeek|极客中国-欢迎来到极客的世界,一个免费开放的程序员编程交流平台!开放,进步,分享!让技术改变生活,让极客改变未来! Welcome to OGeek Q&A Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...