CODEWITHSUNDEEP
sortingprolog
Cassandra
Cassandra

Reputation: 217

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

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?

Upvotes: 1

Views: 1554

Answers (4)

Nicholas Carey
Nicholas Carey

Reputation: 74197

To determine if a list is sorted in ascending order is trivial:

ordered_ascending( []       ) .  % the empty list is ordered in ascending sequence.
ordered_ascending( [X]      ) .  % A list of length 1 is ordered in ascending sequence.
ordered_ascending( [A,B|Cs] ) :- % A list of length > 1 is ordered if...
  A @=< B ,                      % A is less than or equal to B, and
  ordered_ascending( [B|Cs] ) .  % the remainder of the list (less A) is similarly ordered.

Similarly, determining if a list is ordered in descending sequence is just as easy:

ordered_descending( []       ) .  % the empty list is ordered in ascending sequence.
ordered_descending( [X]      ) .  % A list of length 1 is ordered in ascending sequence.
ordered_descending( [A,B|Cs] ) :- % A list of length > 1 is ordered if...
  A @>= B ,                       % A is greater than or equal to B, and
  ordered_descending( [B|Cs] ) .  % the remainder of the list (less A) is similarly ordered.

Add a wrapper to provide the needed determinism and you are all set:

ordered( Xs ) :- ordered_ascending(  Xs ) , ! .
ordered( Xs ) :- ordered_descending( Xs ) , ! .

You can make it more efficient, by adding some smarts to the wrapper:

ordered( []  ) .
ordered( [X] ) .
ordered( [X,Y|Zs] ) :- X @=< Y , ordered_ascending(  [Y|Zs] ) , ! .
ordered( [X,Y|Zs] ) :- X @>= Y , ordered_descending( [Y|Zs] ) , ! .

You'll notice that I discard the 1st element of the list here, as we don't need to test it again.

Upvotes: 0

salva
salva

Reputation: 10234

It is usually a good idea to look for solutions that do not require unification of more than the head and the tail of a list. That removes the need to use cuts in order to avoid leaving choice points open during evaluation.

sorted([]).
sorted([H|T]) :- sorted(T, H, _).

sorted([], _, _).
sorted([H|T], Last, Dir) :-
    compare(Dir1, H, Last),
    (   Dir1 = (=)
    ->  true
    ;   Dir1 = Dir),
    sorted(T, H, Dir).

Upvotes: 1

slago
slago

Reputation: 5509

You can use compare/3 to instantiate the order (ascending or descending), as soon as the first pair of distinct adjacent elements is found in the list.

sorted(L) :- sorted(L, _).

sorted([], _).
sorted([_], _) :- !.
sorted([X,X|R], Order) :- !, sorted([X|R], Order).
sorted([X,Y|R], Order) :- compare(Order, X, Y), sorted([Y|R], Order).

Examples:

?- sorted([ann, bob, coy]).
true.

?- sorted([coy, bob, bob, ann]).
true.

?- sorted([coy, bob, dan, bob, ann]).
false.

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

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

?- sorted([1-coy, 2-ann, 3-bob]).
true.

?- sorted([5-coy, 4-ann, 3-bob]).
true.

?- sorted([1-coy, 4-ann, 3-bob]).
false.

Upvotes: 3

rajashekar
rajashekar

Reputation: 3753

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])
    ).

Upvotes: 1

Related Questions