Reaching end of list in prolog

Question

I've been given the question:

Define a predicate ordered/1, which checks if a list of integers is correctly in ascending order. For example, the goal ordered([1,3,7,11]) should succeed, as should the goal ordered([1,3,3,7]), whereas the goal ordered([1,7,3,9]) should fail.

So far I have this:

ordered([]).    
ordered([N, M|Ns]):-
    append(M, Ns, Tail),
    ordered(Tail),
    N =< M.

But it fails on every list.

I have deduced that the reason it fails is because it reaches the end number in the list then tries to compare that number against an empty list. Obviously this fails because you can't compare an integer to an empty list. Even if you could and it, say, returned 0 for an empty list, it would still return false as the number would be greater than 0, not less than.

I can't find a solution... Any ideas? Thanks, Jon.

---

Edit

So, some slightly amended code:

ordered([]).
ordered([N]):-
    N >= 0.
ordered([N, M|Ns]):-
    append(M, Ns, Tail),
    ordered(Tail),
    N =< M.

This now works for ordered([1]), but bigger lists still don't run correctly.

Should I include something like ordered([N, M|Ns]) in the definition?

Answer 1

A short but slow version:

increasing_freeze_slow(L) :-
    freeze(L, increasing_freeze_slow_(L, [])).

increasing_freeze_slow_([], _).
increasing_freeze_slow_([H|T], Ps) :-
    % Apply when_ground_gte to the previous list elements
    maplist(when_ground_gte(H), Ps),
    freeze(T, increasing_freeze_slow_(T, [H|Ps])).

% When comparable, is greater than or equal
when_ground_gte(High, Low) :-
    when((ground(High), ground(Low)), High @>= Low).

Results in swi-prolog:

?- increasing_freeze_slow(L), length(L, 4).
L = [_A, _B, _C, _D],
when((ground(_B), ground(_A)), _B@>=_A),
when((ground(_C), ground(_B)), _C@>=_B),
when((ground(_C), ground(_A)), _C@>=_A),
when((ground(_D), ground(_C)), _D@>=_C),
when((ground(_D), ground(_B)), _D@>=_B),
when((ground(_D), ground(_A)), _D@>=_A).

It will compare all the list elements to all of the other list elements, as soon as they are comparable with certainty.

This comes with a performance penalty, but allows e.g.:

?- increasing_freeze_slow(L), L = [1,X,3], X = 2.
L = [1, 2, 3],
X = 2.

?- increasing_freeze_slow(L), L = [1,X,3], X = 99.
false.

Answer 2

Having much better performance than my previous answer involving freeze:

ascending_or_equal_freeze(L) :-
    freeze(L, ascending_or_equal_freeze_start1_(L)).

ascending_or_equal_freeze_start1_([]).
ascending_or_equal_freeze_start1_([H|T]) :-
    ascending_or_equal_freeze_start2_(T, H).

ascending_or_equal_freeze_start2_([], _).
ascending_or_equal_freeze_start2_([H|T], P) :-
    % Need 2 elements, to start comparison
    ascending_or_equal_freeze_([P,H|T], []).

ascending_or_equal_freeze_([], _).
ascending_or_equal_freeze_([H|T], Before) :-
    ascending_or_equal_freeze_search_(Before, <,  H),
    ascending_or_equal_freeze_search_(T, >,  H),
    (   ground(H) ->
        % Can cut the list short, H is completely comparable
        Before1 = [H]
    ;   Before1 = [H|Before]
    ),
    freeze(T, ascending_or_equal_freeze_(T, Before1)).

ascending_or_equal_freeze_search_(L, Comp, P) :-
    ascending_or_equal_freeze_search_loop_(L, Comp, P, [], L).

ascending_or_equal_freeze_search_loop_(L, Comp, P, Visited, OrigL) :-
    (   \+ \+ L = []
    % End of list - resume search when P is instantiated further
    ->  ascending_or_equal_freeze_when_(OrigL, Comp, P)
    ;   L = [H|T],
        (   ?=(H, P)
        % Can compare with certainty
        ->  compare_or_equal(Comp, H, P, ActualComp),
            (   ActualComp = (=)
            % Elements in-between must be same
            ->  maplist(=(P), Visited)
            ;   true
            )
        ;   ascending_or_equal_freeze_search_loop_(T, Comp, P, [H|Visited], OrigL)
        )
    ).

ascending_or_equal_freeze_when_(L, Comp, P) :-
    (   \+ \+ L = []
    % Nothing to compare
    ->  true
    ;   term_variables(P, Vars),
        (   Vars == []
        % P is ground
        ->  true
        % Resume search when instantiated further
        ;   when_nonvar_any(Vars, ascending_or_equal_freeze_search_(L, Comp, P))
        )
    ).

compare_or_equal(Comp, X, Y, ActualComp) :-
    compare(C, X, Y),
    compare_or_equal_(C, Comp, ActualComp).

compare_or_equal_(=, _, =).
compare_or_equal_(<, <, <).
compare_or_equal_(>, >, >).

when_nonvar_any([], _).
when_nonvar_any([H|T], Action) :-
    nonvar_elem_cond([H|T], Cond),
    when(Cond, Action). 
    
nonvar_elem_cond([H|T], L) :-
    nonvar_elem_cond_(T, H, L).
    
nonvar_elem_cond_([], H, nonvar(H)).
nonvar_elem_cond_([H|T], P, nonvar(P);L) :-
    nonvar_elem_cond_(T, H, L).

Results in swi-prolog:

?- ascending_or_equal_freeze(L), L = [1,2,X,Y,5,6|T].
L = [1, 2, X, Y, 5, 6|T],
when(nonvar(X), ascending_or_equal_freeze_search_([2], <, X)),
when(nonvar(X), ascending_or_equal_freeze_search_([Y, 5, 6|T], >, X)),
when(nonvar(Y), ascending_or_equal_freeze_search_([X, 2], <, Y)),
when(nonvar(Y), ascending_or_equal_freeze_search_([5, 6|T], >, Y)),
freeze(T, ascending_or_equal_freeze_(T, [6])).

?- numlist(1, 4000, L), time(ascending_or_equal_freeze(L)).
% 64,000 inferences, 0.004 CPU in 0.004 seconds (98% CPU, 15798229 Lips)

% Automatically joins up logically-equal segments
?- L = [_, b, _, _, _, _, X, _], ascending_or_equal_freeze(L), X = b.
L = [_A, b, b, b, b, b, b, _B],
X = b,
when(nonvar(_A), ascending_or_equal_freeze_search_([b, b, b, b, b, b, _B], >, _A)),
when(nonvar(_B), ascending_or_equal_freeze_search_([b, b, b, b, b, b], <, _B)).

Answer 3

To efficiently use first-argument indexing:

ordered([]).
ordered([H|T]) :-
    ordered_(T, H).

ordered_([], _).
ordered_([H|T], P) :-
    P @=< H,
    ordered_(T, H).

Result in swi-prolog:

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

?- ordered([a,b,c,d,g]).
true.

?- ordered([b,c,a,d]).
false.

This does not leave an unwanted choicepoint, uses standard order (so works with not just integers), and is fast. Performance comparison:

JonB:

?- garbage_collect, numlist(1, 1_000_000, L), time(ordered(L)).
% 3,999,996 inferences, 0.872 CPU in 0.873 seconds (100% CPU, 4589226 Lips)

vs this:

?- garbage_collect, numlist(1, 1_000_000, L), time(ordered(L)).
% 2,000,001 inferences, 0.046 CPU in 0.046 seconds (100% CPU, 43662698 Lips)

Answer 4

If your Prolog system supports clpfd, check if it offers the library predicate clpfd:chain/2.

:- use_module(library(clpfd)).

If so, simply write:

?- chain([1,3,7,11],#<).
true.

?- chain([1,3,3,7],#=<).
true.
?- chain([1,3,3,7],#<).
false.

?- chain([1,7,3,9],#<).
false.

Answer 5

If you are using SICStus Prolog, my previous answer will not work, as the clpfd library in SICStus Prolog does not offer the library predicate chain/3 included with SWI-Prolog's clpfd library.

:- use_module(library(clpfd)).
:- assert(clpfd:full_answer).

Don't panic! Simply implement predicate ordered/1 like this:

ordered([]).
ordered([X|Xs]) :- 
   ordered_prev(Xs,X).

ordered_prev([]     ,_ ).
ordered_prev([X1|Xs],X0) :- 
   X0 #=< X1,
   ordered_prev(Xs,X1).

Let's see it in action with SICStus Prolog 4.3.2. Here's the most general query:

?- ordered(Xs).
  Xs = []
; Xs = [_A]
; Xs = [_A,_B],    _A#=<_B,          _A in inf..sup, _B in inf..sup
; Xs = [_A,_B,_C], _A#=<_B, _B#=<_C, _A in inf..sup, _B in inf..sup, _C in inf..sup
... % an infinity of solutions follows: omitted for the sake of brevity.

And here are the queries the OP suggested:

?- ordered([1,3,7,11]).
yes                                  % succeeds deterministically
?- ordered([1,3,3,7]).
yes                                  % succeeds deterministically
?- ordered([1,7,3,9]).
no

Note that both succeeding queries in above example did not leave any useless choicepoints behind, thanks to first argument indexing.

Answer 6

Don't use append/3.

edit1 to satisfy @false. In order to make it tail recursive friendly it has to eliminate backtracking. This is tail-recursive and only slight variation on @Xonix:

ordered([X|[]]):-!.

ordered([X,Y|Ys]) :- 
    X =< Y,
    !,
    ordered([Y|Ys]).

edit2 Take it a step further to eliminate lists that have less than two elements

ordered([X,Y|[]]):- X =< Y,!.

ordered([X,Y|Ys]) :- 
    X =< Y,
    !,
    ordered([Y|Ys]).

Answer 7

I think your solution is not also tail-recursion-friendly. Think something like that would do:

ordered([]) :-!.
ordered([_]):-!.
ordered([A,B|T]) :-
    A =< B,
    !,
    ordered([B|T]).

Answer 8

Well that, in the end, was rediculously easy to fix.

Here is the correct code.

ordered([]).

ordered([N, M|Ns]):-
 append([M], Ns, Tail),
 ordered(Tail),
 N =< M.

ordered([M]).

ordered([M]). deals with the single-element list as described above.

The real root of my problem was not including [] around the M in the append function.

Whats the ettiquette regarding awarding the correct answer? You've both helped muchly.

Jon

Answer 9

You're quite right: according to your code there are only two possible ways a list can be ordered:

1. It's empty
2. The first two items are in the correct order, and the rest of the list is ordered

Those are certainly both correct statements, but what about the list [3]? Isn't that ordered too? Obviously a list with only one element is ordered, yet you have no provision for expressing that: it fits neither your base case nor your recursive case.

The single-element list is another case hiding here that you haven't addressed yet. Since this is independent of the two rules you've already defined, you might want to consider a way to address this special case separately.

Answer 10

(assuming this is homework, I hesitate to give a complete solution).

Looking at your code, try to find out how it would unify ?- ordered([1]). Run this query mentally (or using trace/0) and see what it does, step by step, and how it computes its result.

Also, please try to get "returns a value" out of your mind when thinking prolog. Prolog predicates don't return anything.