Prolog tries to find multiple solutions when only one exists

user_15072974 0
Viewed 264

I've made a basic predicate ascending/1 to check if a list is in ascending order, on https://swish.swi-prolog.org.

ascending([]).
ascending([_]).
ascending([X, Y| T]) :-
    X =< Y,
    ascending([Y|T]).

It shows the following if I query ?- ascending([1, 2, 4, 6]).:

1

As in, it tries to find more solutions. Pressing Next, 10, 100 or 1,000 just returns false, which is a mystery in and of itself - true and false at the same time? Maybe that's because of the anonymous _? Have I not defined completely enough? Why is it not just returning true?

prolog-toplevel prolog
1 Answers

Most Prolog systems implement first-argument indexing, which allows avoid creating spurious choice-points. Assuming that and a call with the first argument bound, in the case of your code, the Prolog runtime is able to able to distinguish between the first clause, whose first argument is an atom, and the two other clauses, whose first argument are lists. But not able (in general) to distinguish between the second and third clauses and avoid trying both for a goal where the first argument is a list. This results in the creation of a choice-point. Hence the results your get:

?- ascending([1, 2, 4, 6]).
true ;
false.

But we can improve on your solution. For example:

ascending([]).
ascending([Head| Tail]) :-
    ascending(Tail, Head).

ascending([], _).
ascending([Head| Tail], Previous) :-
    Previous =< Head,
    ascending(Tail, Head).

We will now get:

?- ascending([1, 2, 4, 6]).
true.

?- ascending([1, 2, 4, 6, 1]).
false.
user_6346290
Related