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