How can I select integers from a list in Prolog?

Question

I'm trying to create a predicate in Prolog select_integers(X, L) that holds true if L is a list containing every integer in X (X contains multiple types of values).

Here's what I have so far:

select_integers([], []).
select_integers([X|XS], L) :-
    integer(X),
    member(X, L),
    select_integers(XS, L).

What am I missing here? How can I improve this to get the result I want? (It currently returns false for whatever I do)

Answer 1

If I look into your program, I see integer(X) which is better replaced by when(nonvar(X), integer(X)) since it has otherwise no declarative meaning. Just believe me.

But now, once you have a pure program, we can locate the errors thanks to the declarative properties of Prolog.

The best is to ask Prolog directly, what it thinks:

?- select_integers(Xs, Ys).
   Xs = Ys, Ys = []  % expected success
;  loops.

Not much. The loop does not help us. It simply says that Prolog's engine got into an infinite loop no matter why. But we can specialize the query. Like so:

?- Xs = [_], Ys = [_], select_integers(Xs, Ys).
   false. % unexpected failure

Maybe you would have preferred Xs = [1], Ys = [1] instead. I just tried the possible maximum.

Remark that I had to restrict both Xs and Ys to a list with a single element. Otherwise the query loops.

The situation is now much better, for an unexpected failure means that we can diagnose the program. In particular, we can generalize the program by removing some parts. I found this generalization of your program:

:- initialization( ( Xs = [_], Ys = [_], select_integers(Xs, Ys) ) ).
:- op(950, fy, *).
*_.

select_integers(_/*[]*/,[]).
select_integers([X|XS],L) :-
   * when(nonvar(X), integer(X) ),
   * member(X,L),
   select_integers(XS,L).

_{(To obtain that fragment, I saved everything into a file, added * to some goals and said make repeatedly (which is built-in in SWI and there is this module for SICStus), always looking out for an error message that the goal failed. So I tried to take away from your program as much as possible)}

Everything that remained is responsible for the failure. Everything else is not needed to produce the failure. It might be right or wrong, we know not. Actually the culprit is the L! If you look at the rule reading it right-to-left, it reads:

Provided select_integers(XS,L) is true, then it follows (the :- is meant to symbolize an arrow) that select_integers([X|XS], L) is true.

In other words, the second argument will always remain of the same length. And there is only []! So the second argument can only be the empty list.

select_integers([],[]).
select_integers([X|XS],[X|L]) :-
   when(nonvar(X), integer(X) ),
   select_integers(XS,L).

?- Xs = [_], select_integers(Xs, Ys).
   Xs = Ys, Ys = [_A],
   when(nonvar(_A), integer(_A)).
   % missing further answer

So this program is now true for lists being all integers. But it still fails for lists not being integers. Here is a quick fix for this:

select_integers([],[]).
select_integers([X|XS],[X|L]) :-
   when(nonvar(X), integer(X) ),
   select_integers(XS,L).
select_integers([X|XS],L) :-
   when(nonvar(X), \+integer(X) ),
   select_integers(XS,L).

?- Xs = [_], select_integers(Xs, Ys).
   Xs = Ys, Ys = [_A],
   when(nonvar(_A), integer(_A))
;  Xs = [_A], Ys = [],
   when(nonvar(_A), \+integer(_A)).

There are more concise ways to express this. As with:

integer_t(X, T) :-
   when(nonvar(X), ( integer(X) -> T = true ; T = false ) ).

select_integers(Xs, Is) :-
   tfilter(integer_t, Xs, Is).

In a system that does not support when/2 (nor freeze/2) you can still be on the safe side with:

integer_t(X, T) :-
   functor(X,_,_),
   ( integer(X) -> T = true ; T = false ).

Using tfilter/3.

Answer 2

I think you need another case.

case1 for the empty list.

case 2 for when the item is an integer add it to the second list

case 3 for when the item is not an integer dont add it to the second list.

select_integers([],[]).
select_integers([X|XS],[X|L]) :-
 integer(X),
 select_integers(XS,L).
select_integers([X|XS],L) :-
 \+integer(X),
 select_integers(XS,L).

You can and might want to change it so that L does not have duplicates if x has duplicates. You could do this with another case, or a separate predicate.

You could also make it more relational maybe by looking at the reif stuff e.g in swi http://www.complang.tuwien.ac.at/ulrich/Prolog-inedit/swi/reif.pl for example a start could be:

int_t(X,T):-
 integer(X),
 T = true.
int_t(X,T):-
 \+integer(X),
 T = false.

 ?- tinclude(int_t,[a,b,1,2,3,4,5],X).
 X = [1, 2, 3, 4, 5] .

This is not fully relational though, as :

?- tinclude(int_t,[A,B],[A,B]).
false.

Both of these are not complete answers, but might help you along.