pereira@sri-unix.UUCP (08/15/83)
% File : LISTUT.PL
% Author : Lawrence Byrd + R.A.O'Keefe
% Updated: 20 May 1983
% Purpose: list processing utilities
% This module requires
% select/3 (from SetUtl.Pl) for perm/2
% listtoset/2 (from SetUtl.Pl) for remove_dups/2
% If you don't want those routines, it can be used on its own.
% 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 defined member/2 (from SetUtl.Pl) 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 .
sumlist(Numbers, Total) :-
sumlist(Numbers, 0, Total).
sumlist([], Total, Total).
sumlist([Head|Tail], Sofar, Total) :-
Next is Sofar+Head,
sumlist(Tail, Next, Total).