patternMinor
Prolog predicate for adjacency of integers with all signatures and no spurious choice points
Viewed 0 times
signaturesprologallwithpointspredicatechoiceforspuriousand
Problem
I want to create a predicate nearby(X,Y) which represents "X and Y are integers 1 apart from each other" and fully satisfies:
In other words it must work for any combination of two bound inputs or one bound and one free input, and must have no spurious choice point when both inputs are bound.
Is this the best way to do so? Note that while I understand that using a built in predicate like
%%! nearby(+X:Int, +Y:Int) is semidet.
%%! nearby(+X:Int, -Y:Int) is multi.
%%! nearby(-X,Int, +Y:int) is multi.In other words it must work for any combination of two bound inputs or one bound and one free input, and must have no spurious choice point when both inputs are bound.
Is this the best way to do so? Note that while I understand that using a built in predicate like
plus might make the code more readable, would it inevitably end up substituting down to something like this?nearby2(X,Y) :- nonvar(X), X = Y.
nearby2(X,Y) :- nonvar(X), Y is X+1.
nearby2(X,Y) :- nonvar(X), Y is X-1.
nearby2(X,Y) :- var(X), nonvar(Y), nearby2(Y,X).
nearby3(X,Y) :- nonvar(X), nonvar(Y), nearby2(X,Y), !.
nearby3(X,Y) :- nearby2(X,Y).Solution
The best way to reason about integers is to use your Prolog system's CLP(FD) constraints.
For example, in SICStus Prolog and SWI-Prolog:
This works in all directions out of the box.
For example, with both arguments integers:
Second, with only one argument known:
Third, with both arguments variables:
etc.
All serious Prolog systems ship with CLP(FD) constraints, and I recommend you use them when describing relations over integers. Just state the constraints and let Prolog do the reasoning for you.
Note that the predicate is semideterministic: It either fails or succeeds precisely once. You can use
For example, in SICStus Prolog and SWI-Prolog:
:- use_module(library(clpfd)).
nearby(X, Y) :- abs(X - Y) #= 1.This works in all directions out of the box.
For example, with both arguments integers:
?- nearby(1, 2).
true.Second, with only one argument known:
?- nearby(X, 3).
X in 2\/4,
_G1047+3#=X,
_G1047 in -1\/1.Third, with both arguments variables:
?- nearby(X, Y).
_G1085+Y#=X,
_G1085 in -1\/1.etc.
All serious Prolog systems ship with CLP(FD) constraints, and I recommend you use them when describing relations over integers. Just state the constraints and let Prolog do the reasoning for you.
Note that the predicate is semideterministic: It either fails or succeeds precisely once. You can use
labeling/2 to enumerate solutions if the domains are finite.Code Snippets
:- use_module(library(clpfd)).
nearby(X, Y) :- abs(X - Y) #= 1.?- nearby(1, 2).
true.?- nearby(X, 3).
X in 2\/4,
_G1047+3#=X,
_G1047 in -1\/1.?- nearby(X, Y).
_G1085+Y#=X,
_G1085 in -1\/1.Context
StackExchange Code Review Q#115593, answer score: 2
Revisions (0)
No revisions yet.