HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Prolog predicate for adjacency of integers with all signatures and no spurious choice points

Submitted by: @import:stackexchange-codereview··
0
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:

%%! 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:

:- 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.