What's wrong with my Prolog "list filler"?

Question

I wrote a simple program to try and populate a list of a given length with elements that meet a certain constraint.

For example, I want to create a list of 4 integers between 0 and 9, which at least contains 3 and 4. I can think of several (thousands, really) such lists:

[3,4,0,0]
[0,3,4,0]
[3,1,9,4]
etc...

But SWI Prolog just returns false. Am I just making some kind of logical mistake, or am I using Prolog wrong?

My code:

is_single_digit_integer(N) :-
  integer(N),
  between(0, 9, N).

filled_list(Given, FillConstraint, OutLen, Out) :-
  is_list(Out),
  length(Out, OutLen),
  length(Given, GivenLen),
  between(0, OutLen, GivenLen),
  maplist(FillConstraint, Out),
  subset(Given, Out).

And running the example I described:

?- filled_list([3,4], is_single_digit_integer, 4, X).

Answer 1

I would like to complement Daniel's answer with a short pointer to logical-purity:

The via regia to general Prolog programs is to use predicates that satisfy properties you expect from logical relations. Such predicates are called pure and monotonic.

For example, in your particular case, you are using the non-monotonic predicates integer/1 and is_list/1. Your issue goes away completely if you instead use predicates that can be used in all directions, such as:

is_single_digit_integer(N) :-
  N in 0..9.

This uses the clpfd constraint (in)/2 to state: N is an integer between 0 and 9.

It works in all of the following cases:

?- is_single_digit_integer(N).
N in 0..9.

?- is_single_digit_integer(3).
true.

?- is_single_digit_integer(20).
false.

In contrast, integer/1 is incomplete:

?- integer(N).
false.

→ No integer exists??

The same holds for is_list/1, which falls critically short already for the most general query:

?- is_list(Ls).
false.

In contrast, to state that Ls is a list, you can for example use:

length(Ls, _)

This works correctly whether or not Ls is instantiated. For example:

?- length(Ls, _).
Ls = [] ;
Ls = [_6650] ;
Ls = [_6650, _6656] ;
Ls = [_6650, _6656, _6662] ;
etc.

To get the most out of Prolog, I recommend to stay in its pure and monotonic subset. This paves the way for relations that can be used in all directions.