Write Prolog ordered predicate

Question

I am trying to write a predicate that succeeds if and only if the numbers in the list are in non-decreasing order. I am having a hard time trying to figure this out. I know that if each element is less than or equal to the previous one then it should return false but I am lost on how to do it.

ordered(L) :- 

Answer 1

Recursion should usually be your first thought for approaching any problem in Prolog. This means:

1. Defining a base case, where you can easily determine that the predicate is true or false

2. In other cases, splitting the problem into parts - one part you can resolve immediately, another you can resolve recursively. These parts of the problem generally correspond to portions of the list.

In the simplest cases, the recursive logic is simply to apply some test to the first element of the list; if it passes, recursively apply the predicate to the remainder of the list.

In your case I think it is a bit more complex, as there is no meaningful way you can test an individual element for orderedness (and maybe that gives you a hint what the base case is ...).

Answer 2

ordered(L) :- ordered2(L).

% empty list is ordered
ordered2([]) :- true.
% list with one element is ordered
ordered2([_]) :- true.
% list is ordered if two first elements are ordered 
% and the rest of list is ordered
ordered2([A,B|T]) :- A=<B, ordered2([B|T]).