%   File   : ORDER.PL
%   Author : R.A.O'Keefe
%   Updated: 12 June 1984, conv to K Johnson, NIP 11-8-87
%   Purpose: Define the "ordered" predicates.

:- public
	len/2,
	ordered/1,
	ordered/2.

:- mode
	ordered(+),
	    ordered_(+, +),
	ordered(+, +),
	    ordered_(+, +, +),
	len(?, ?),
	    len_(+, ?),
	    len_(+, +, -).

%   ordered(List)
%   is true when List is a list of terms [T1,T2,...,Tn] such that
%   for all k in 2..n Tk-1 @=< Tk, i.e. T1 @=< T2 @=< T3 ...
%   The output of keysort/2 is always ordered, and so is that of
%   sort/2.  Beware: just because a list is ordered does not mean
%   that it is the representation of an ordered set; it might contain
%   duplicates.  E.g. L = [1,2,2,3] & sort(L,M) => ordered(L) & M\=L.

ordered([]).
ordered([Head|Tail]) :-
	ordered_(Tail, Head).

ordered_([], _).
ordered_([Head|Tail], Left) :-
	Left @=< Head,
	ordered_(Tail, Head).



%   ordered(P, [T1,T2,...,Tn]) means P(T1,T2) & P(T2,T3) & ...
%   i.e. that the second argument is ordered if you regard the
%   first argument as =<.  This is good for generating prefixes
%   of sequences, e.g. L = [1,_,_,_,_] & ordered(times(2),L) yields
%   L = [1,2,4,8,16].

ordered(_, []).
ordered(Relation, [Head|Tail]) :-
	ordered_(Tail, Head, Relation).

ordered_([], _, _).
ordered_([Head|Tail], Left, Relation) :-
	apply(Relation, [Left,Head]),
	ordered_(Tail, Head, Relation).



%   To exploit ordered/2 fully, we need a way of generating lists of
%   a given length.  I trust that a Prolog Standard will demand that
%   length/2 be reversible.  Until then, here is a reversible length.
%   len_/2 generates a list of a given length.  len_/3 measures the
%   length of a given list.  It reports an error if you give it a
%   variable or a list with a variable tail because then it would
%   backtrack forever trying ever longer lists if there was a
%   failure upstream, and this is generally not a useful thing to do.
%   Note: this code is really hacky, that's because of the error
%   detection.  Making len_/3 fail for variables so that len/2 can
%   report the error on the original list, faugh!

len(List, Length) :-
	nonvar(Length),
	!,
	integer(Length),
	len_(Length, List).

len(List, Length) :-
	nonvar(List),		% we know that var(Length)
	len_(List, 0, Length),	% so len_/3 will work for proper lists
	!.			% and fail for vars and non-lists

len(List, Length) :-
	nl, write('! bad arguments in '),
	write(len(List,Length)),
	nl,
	break,
	abort.


len_(0, []).
len_(N, [_|Tail]) :-
	N > 0,
	M is N-1,
	len_(M, Tail).


len_([], Length, Length).
len_([_|Tail], SoFar, Length) :-
	nonvar(Tail),
	Next is SoFar+1,
	len(Tail, Next, Length).