%   File   : /usr/lib/prolog/lists
%   Author : Lawrence Byrd + R.A.O'Keefe
%   Updated: 20 May 1983
%   Purpose: list processing utilities
%   Needs  : select/3	 from ./sets for perm/2
%	     listtoset/2 from ./sets for remove_dups/2

%   The code was originally written by Lawrence Byrd.  The layout
%   and comments are by R.A.O'Keefe.

:- public
	append/3,			%   List x List -> List
	correspond/4,			%   Elem <- List x List -> Elem
	delete/3,			%   List x Elem -> List
	last/2,				%   List -> Elem
	nextto/3,			%   Elem, Elem <- List
	nmember/3,			%   Elem <- Set -> Integer
	numlist/3,			%   Integer x Integer -> List
	perm/2,				%   List -> List
	perm2/4,			%   Elem x Elem -> Elem x Elem
	remove_dups/2,			%   List -> Set
	rev/2,				%   List -> List
	reverse/2,			%   List -> List
	sumlist/2.			%   List -> Integer

:- mode
	append(?, ?, ?),
	correspond(?, +, +, ?),
	delete(+, +, -),
	last(?, ?),
	nextto(?, ?, ?),
	nmember(?, +, ?),
	numlist(+, +, ?),
	perm(?, ?),
	perm2(?,?, ?,?),
	remove_dups(+, ?),
	rev(?, ?),
	reverse(?, ?),
	reverse(?, +, ?),
	sumlist(+, ?),
	sumlist(+, +, ?).


%   append(Prefix, Suffix, Combined)
%   is true when all three arguments are lists, and the members of Combined
%   are the members of Prefix followed by the members of Suffix.  It may be
%   used to form Combined from a given Prefix and Suffix, or to take a given
%   Combined apart.  E.g. we could define member/2 (from ./sets) as
%	member(X, L) :- append(_, [X|_], L).

append([], L, L).
append([H|T], L, [H|R]) :-
	append(T, L, R).



%   correspond(X, Xlist, Ylist, Y)
%   is true when Xlist and Ylist are lists, X is an element of Xlist, Y is
%   an element of Ylist, and X and Y are in similar places in their lists.

correspond(X, [X|_], [Y|_], Y) :- !.
correspond(X, [_|T], [_|U], Y) :-
	correspond(X, T, U, Y).



%   delete(List, Elem, Residue)
%   is true when List is a list, in which Elem may or may not occur, and
%   Residue is a copy of List with all elements equal to Elem deleted.

delete([], _, []) :- !.
delete([Kill|Tail], Kill, Rest) :- !,
	delete(Tail, Kill, Rest).
delete([Head|Tail], Kill, [Head|Rest]) :- !,
	delete(Tail, Kill, Rest).



%   last(Last, List)
%   is true when List is a List and Last is its last element.  This could
%   be defined as last(X,L) :- append(_, [X], L).

last(Last, [Last]) :- !.
last(Last, [_|List]) :-
	last(Last, List).



%   nextto(X, Y, List)
%   is true when X and Y appear side-by-side in List.  It could be written as
%	nextto(X, Y, List) :- append(_, [X,Y], List).
%   It may be used to enumerate successive pairs from the list.

nextto(X,Y, [X,Y|_]).
nextto(X,Y, [_|List]) :-
	nextto(X,Y, List).



%   nmember(Elem, List, Index)
%   is true when Elem is the Indexth member of List.  Could be written as
%	nmember(X, L, N) :- append(B, [X|_], L), length(B, M), N is M+1.
%   It may be used to select a particular element, or to find where some
%   given element occurs, or to enumerate the elements and indices together.

nmember(Elem, [Elem|_], 1).
nmember(Elem, [_|List], N) :-
	nmember(Elem, List, M),
	N is M+1.



%   numlist(Lower, Upper, List)
%   is true when List is [Lower, ..., Upper]
%   Note that Lower and Upper must be integers, not expressions, and
%   that if Upper < Lower numlist will FAIL rather than producing an
%   empty list.

numlist(Upper, Upper, [Upper]) :- !.
numlist(Lower, Upper, [Lower|Rest]) :-
	Lower < Upper,
	Next is Lower+1,
	numlist(Next, Upper, Rest).



%   perm(List, Perm)
%   is true when List and Perm are permutations of each other.  Of course,
%   if you just want to test that, the best way is to keysort/2 the two
%   lists and see if the results are the same.  Or you could use list_to_bag
%   (from BagUtl.Pl) to see if they convert to the same bag.  The point of
%   perm is to generate permutations.  The arguments may be either way round,
%   the only effect will be the order in which the permutations are tried.
%   Be careful: this is quite efficient, but the number of permutations of an
%   N-element list is N!, even for a 7-element list that is 5040.

perm([], []).
perm(List, [First|Perm]) :-
	select(First, List, Rest),	%  tries each List element in turn
	perm(Rest, Perm).



%   perm2(A,B, C,D)
%   is true when {A,B} = {C,D}.  It is very useful for writing pattern
%   matchers over commutative operators.  It is used more than perm is.

perm2(X,Y, X,Y).
perm2(X,Y, Y,X).



%   remove_dups(List, Pruned)
%   removes duplicated elements from List.  Beware: if the List has
%   non-ground elements, the result may surprise you.

remove_dups(List, Pruned) :-
	listtoset(List, Pruned).



%   reverse(List, Reversed)
%   is true when List and Reversed are lists with the same elements
%   but in opposite orders.  rev/2 is a synonym for reverse/2.

rev(List, Reversed) :-
	reverse(List, [], Reversed).

reverse(List, Reversed) :-
	reverse(List, [], Reversed).

reverse([], Reversed, Reversed).
reverse([Head|Tail], Sofar, Reversed) :-
	reverse(Tail, [Head|Sofar], Reversed).



%   sumlist(Numbers, Total)
%   is true when Numbers is a list of integers, and Total is their sum.
%   Note that in Dec-10 compiled Prolog this will only work as stated;
%   interpreters will almost certainly accept integer expressions.  Also
%   note here as elsewhere in Prolog arithmetic that machine arithmetic
%   wraps round: on the Dec-10 (2^17 - 1)+1 = -2^17 .  Whether wrapping
%   or floating happens in C-Prolog is controlled by all_float.

sumlist(Numbers, Total) :-
	sumlist(Numbers, 0, Total).

sumlist([], Total, Total).
sumlist([Head|Tail], Sofar, Total) :-
	Next is Sofar+Head,
	sumlist(Tail, Next, Total).