Prolog to check if list is sorted (ascending or descending)-CodePudding

I want to write a predicate which will determine if a list is sorted or not (ascending or descending both would return true)

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

This works when I want to check only one particular order, how can I use it for both ascending and descending?

CodePudding user response：

You are trying to find out if a list is monotonic. It is monotonic if any part of it is:

Increasing.
Decreasing.
A combination of equality with only one of: increasing elements or decreasing elements.

So first we need to write a predicate to find out monotony.

% Base cases:

    % In case of equality it does not fail and the result may be undefined.
    monotony([X, X], _) :- !.

    % In other case, simply match the monotony.
    monotony([X, Y], P) :- call(P, X, Y), !.

% Recursive cases:

    % if the monotony is clearly determined at the head
    % match this monotony with the rest of the list.
    monotony([X,Y|T], P) :-
        comp(P, X, Y), P \= (=), !, monotony([Y|T], P).

    % if the monotony is not determined at the head or if it was determined
    % earlier but we now have an stable segment (one were the items are equal) then
    % try to determine the monotony from the rest of the list.
    monotony([_,Y|T], P) :- monotony([Y|T], P).

When using SWI-Prolog, and in this case, comp may be the standard compare predicate only for numbers because it only gives <, > and = as comparison predicates (see ?- help(compare).). For other types a more general comparison must be used. For example:

comp(@<, X, Y) :- X @< Y, !.
comp(@>, X, Y) :- X @> Y, !.
comp(=, _, _).

Then, only remains to define the main predicate:

is_sorted(L) :- monotony(L, _).

CodePudding user response：

You can pass the order predicate to is_sorted.

is_sorted(_, []).
is_sorted(_, [_]).
is_sorted(P, [X,Y|T]):- call(P, X, Y), is_sorted(P, [Y|T]).

Here P can be any predicate which takes two arguments.

?- is_sorted(=<, [1, 2, 3, 4, 4]).
true 
?- is_sorted(<, [1, 2, 3, 4, 4]).
false.

?- is_sorted(>, [4, 3, 1, 0, -2]).
true 
?- is_sorted(@<, [hey, how]).
true 
?- is_sorted(@<, [hey, how, are]).
false.

To check if the list is sorted in either ascending or descending order:

sorted_any([]).
sorted_any([_]).
sorted_any([X, Y | T]) :-
    (X = Y) -> sorted_any([Y|T]);
    (
    (X < Y) -> is_sorted(=<, [Y|T]);
    is_sorted(>=, [Y|T])
    ).