How to improve this code that looks for a specific number in a list?

Question

I'm writing prolog code that finds a certain number; a number is the right number if it's between 0 and 9 and not present in a given list. To do this I wrote a predicate number/3 that has the possible numbers as the first argument, the list in which the Rightnumber cannot be present and the mystery RightNumber as third argument:

number([XH|XT], [H|T], RightNumber):-
    member(XH, [H|T]), !,
    number(XT, [H|T], RightNumber).
number([XH|_], [H|T], XH):-
    \+ member(XH, [H|T]).

so this code basically says that if the Head of the possible numbers list is already a member of the second list, to cut of the head and continue in recursion with the tail. If the element is not present in the second list, the second clause triggers and tells prolog that that number is the RightNumber. It's okay that it only gives the first number that is possible, that's how I want to use it.

This code works in theory, but I was wondering if there's a better way to write it down? I'm using this predicate in another predicate later on in my code and it doesn't work as part of that. I think it's only reading the first clause, not the second and fails as a result.

Does anybody have an idea that might improve my code?

sample queries:

?- number([0,1,2,3,4,5,6,7,8,9], [1,2], X).
       X = 3
?- number([0,1,2,3,4,5,6,7,8,9], [1,2,3,4,5,6,7,8,0], X).
       X = 9

Answer 1

First, the code does not work. Consider:

?- number(Xs, Ys, N).
nontermination

This is obviously bad: For this so-called most general query, we expect to obtain answers, but Prolog does not give us any answer with this program!

So, I first suggest you eliminate all impurities from your program, and focus on a clean declarative description of what you want.

I give you a start:

good_number(N, Ls) :-
        N in 0..9,
        maplist(#\=(N), Ls).

This states that the relation is true if N is between 0 and 9, and N is different from any integer in Ls. See clpfd for more information about CLP(FD) constraints.

Importantly, this works in all directions. For example:

?- good_number(4, [1,2,3]).
true.

?- good_number(11, [1,2,3]).
false.

?- good_number(N, [1,2,3]).
N in 0\/4..9.

And also in the most general case:

?- good_number(N, Ls).
Ls = [],
N in 0..9 ;
Ls = [_2540],
N in 0..9,
N#\=_2540 ;
Ls = [_2750, _2756],
N in 0..9,
N#\=_2756,
N#\=_2750 .

This, with only two lines of code, we have implemented a very general relation.

Also see logical-purity for more information.

Answer 2

First of all, your predicate does not work, nor does it check all the required constraints (between 0 and 9 for instance).

Several things:

• you unpack the second list [H|T], but you re-pack it when you call member(XH, [H|T]); instead you can use a list L (this however slightly alters the semantics of the predicate, but is more accurate towards the description);
• you check twice member/2ship;
• you do not check whether the value is a number between 0 and 9 (and an integer anyway).

A better approach is to construct a simple clause:

number(Ns, L, Number) :-
    member(Number, Ns),
    integer(Number),
    0 =< Number,
    Number =< 9,
    \+ member(Number, L).

A problem that remains is that Number can be a variable. In that case integer(Number) will fail. In logic we would however expect that Prolog unifies it with a number. We can achieve this by using the between/3 predicate:

number(Ns, L, Number) :-
    member(Number, Ns),
    between(0, 9, Number),
    \+ member(Number, L).

We can also use the Constraint Logic Programming over Finite Domains library and use the in/2 predicate:

:- use_module(library(clpfd)).

number(Ns, L, Number) :-
    member(Number, Ns),
    Number in 0..9,
    \+ member(Number, L).

There are still other things that can go wrong. For instance we check non-membership with \+ member(Number, L). but in case L is not grounded, this will fail, instead of suggesting lists where none of the elements is equal to Number, we can use the meta-predicate maplist to construct lists and then call a predicate over every element. The predicate we want to call over every element is that that element is not equal to Number, so we can use:

:- use_module(library(clpfd)).

number(Ns, L, Number) :-
    member(Number, Ns),
    Number in 0..9,
    maplist(#\=(Number), L).