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