Reaching end of list in prolog

Question

Hi,

I've been given the question:

'Define a predcate ordered/1, which cheks if a list of integers is correctly in ascending order. For example, the goal ordered([1,3,7,11]) should succed, 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've been eyeballing this for a good hour or so and can't seem to find a solution. Any ideas?

Thanks

Jon

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. Am I just being stupid and should something like this be included in my 'ordered([N, M|Ns])' definintion?

Answer 1

(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.

Answer 2

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 3

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 4

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