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

user_2954547 0
Viewed 94

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).
prolog
2 Answers

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.

user_16135730

Both integer(N) and is_list(Out) assume bound variables and fail on uninstantiated variables. The solution is to remove them:

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

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

You can see it works now:

?- filled_list([3,4], is_single_digit_integer, 4, X).
X = [0, 0, 3, 4] ;
X = [0, 0, 4, 3] ;
X = [0, 1, 3, 4] ;
X = [0, 1, 4, 3] .

I think you're trying to use these predicates as if they are type constraints, but Prolog just doesn't work like that. Trust in your types a bit and everything will be fine; after all, between isn't going to give you anything but integers and length isn't going to give you anything but lists.

Bonus trick:

?- filled_list([3,4], between(0,9), 4, X).
X = [0, 0, 3, 4] ;
X = [0, 0, 4, 3] ;
X = [0, 1, 3, 4] ;
X = [0, 1, 4, 3] ;
X = [0, 2, 3, 4] .
user_8128180
Related