% File : LISTUT.PL
% Author : Bob Welham, Lawrence Byrd, and R.A.O'Keefe
% Converted to NIP: K Johnson, 11.8.87
% Updated: 12 February 1985
% 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.
% I am not sure how much of the original code was by Bob Welham
% and how much by Lawrence Byrd. The layout and comments are by
% R.A.O'Keefe, as are nth*, same_length, shorter_list, and subseq*.
% Keys_and_values has moved to PROJEC.PL.
:- 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
nmembers/3, % List x Set -> Set
nth0/3, % Integer x List -> Elem
nth0/4, % Integer x List -> Elem x List
nth1/3, % Integer x List -> Elem
nth1/4, % Integer x List -> Elem x List
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
same_length/2, % List x List ->
select/4, % Elem x List x Elem -> List
shorter_list/2, % List x List ->
subseq/3, % List -> List x List
subseq0/2, % List -> List
subseq1/2, % List -> List
sumlist/2. % List -> Integer
:- mode
append(?, ?, ?),
correspond(?, +, +, ?),
delete(+, +, -),
last(?, ?),
nextto(?, ?, ?),
nmember(?, +, ?),
nmembers(+, +, -),
nth0(+, +, ?),
nth0(+, ?, ?, ?),
nth1(+, +, ?),
nth1(+, ?, ?, ?),
numlist(+, +, ?),
perm(?, ?),
perm2(?,?, ?,?),
remove_dups(+, ?),
rev(?, ?),
reverse(?, ?),
reverse(?, +, ?),
same_length(?, ?),
select(?, ?, ?, ?),
shorter_list(?, +),
subseq(?, ?, ?),
subseq0(+, ?),
subseq1(+, ?),
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 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) Possible Calling Sequences
% nmember(+,+,-) or nmember(-,+,+) or nmember(-,+,-).
% True when Elem is the Indexth member of List.
% It may be used to select a particular element, or to find where some
% given element occurs, or to enumerate the elements and indices togther.
nmember(Elem, [Elem|_], 1).
nmember(Elem, [_|List], N) :-
nmember(Elem, List, M),
N is M+1.
% nmembers(+Indices, +Answers, -Ans) or nmembers(-Indices, +Answers, +Ans)
% (But not nmembers(-,+,-), it loops.)
% Like nmember/3 except that it looks for a list of arguments in a list
% of positions.
% eg. nmembers([3,5,1], [a,b,c,d,e,f,g,h], [c,e,a]) is true
nmembers([], _, []).
nmembers([N|Rest], Answers, [Ans|RestAns]) :-
nmember(Ans, Answers, N),
nmembers(Rest, Answers, RestAns).
% nth0(+N, +List, ?Elem) is true when Elem is the Nth member of List,
% counting the first as element 0. (That is, throw away the first
% N elements and unify Elem with the next.) It can only be used to
% select a particular element given the list and index. For that
% task it is more efficient than nmember.
% nth1(+N, +List, ?Elem) is the same as nth0, except that it counts from
% 1, that is nth(1, [H|_], H).
nth0(0, [Head|_], Head) :- !.
nth0(N, [_|Tail], Elem) :-
nonvar(N),
M is N-1,
nth0(M, Tail, Elem).
nth0(N,[_|T],Item) :- % Clause added KJ 4-5-87 to allow mode
var(N), % nth0(-,+,+)
nth0(M,T,Item),
N is M + 1.
nth1(1, [Head|_], Head) :- !.
nth1(N, [_|Tail], Elem) :-
nonvar(N),
M is N-1, % should be succ(M, N)
nth1(M, Tail, Elem).
nth1(N,[_|T],Item) :- % Clause added KJ 4-5-87 to allow mode
var(N), % nth1(-,+,+)
nth1(M,T,Item),
N is M + 1.
% nth0(+N, ?List, ?Elem, ?Rest) unifies Elem with the Nth element of List,
% counting from 0, and Rest with the other elements. It can be used
% to select the Nth element of List (yielding Elem and Rest), or to
% insert Elem before the Nth (counting from 1) element of Rest, when
% it yields List, e.g. nth0(2, List, c, [a,b,d,e]) unifies List with
% [a,b,c,d,e]. nth1 is the same except that it counts from 1. nth1
% can be used to insert Elem after the Nth element of Rest.
nth0(0, [Head|Tail], Head, Tail) :- !.
nth0(N, [Head|Tail], Elem, [Head|Rest]) :-
nonvar(N),
M is N-1,
nth0(M, Tail, Elem, Rest).
nth0(N, [Head|Tail], Elem, [Head|Rest]) :- % Clause added KJ 4-5-87
var(N), % to allow mode
nth0(M, Tail, Elem, Rest), % nth0(-,+,+,?).
N is M+1.
nth1(1, [Head|Tail], Head, Tail) :- !.
nth1(N, [Head|Tail], Elem, [Head|Rest]) :-
nonvar(N),
M is N-1,
nth1(M, Tail, Elem, Rest).
nth1(N, [Head|Tail], Elem, [Head|Rest]) :- % Clause added KJ 4-5-87
var(N), % to allow mode
nth1(M, Tail, Elem, Rest), % nth1(-,+,+,?).
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) :-
sort(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).
% same_length(?List1, ?List2)
% is true when List1 and List2 are both lists and have the same number
% of elements. No relation between the values of their elements is
% implied.
% Modes same_length(-,+) and same_length(+,-) generate either list given
% the other; mode same_length(-,-) generates two lists of the same length,
% in which case the arguments will be bound to lists of length 0, 1, 2, ...
same_length([], []).
same_length([_|List1], [_|List2]) :-
same_length(List1, List2).
% select(X, Xlist, Y, Ylist)
% >> NB This is select/4, not select/3 !!
% is true when X is the Kth member of Xlist and Y the Kth element of Ylist
% for some K, and apart from that Xlist and Ylist are the same. You can
% use it to replace X by Y or vice versa.
select(X, [X|Tail], Y, [Y|Tail]).
select(X, [Head|Xlist], Y, [Head|Ylist]) :-
select(X, Xlist, Y, Ylist).
% shorter_list(Short, Long)
% is true when Short is a list is strictly shorter than Long. Long
% doesn't have to be a proper list provided it is long enough. This
% can be used to generate lists shorter than Long, lengths 0, 1, 2...
% will be tried, but backtracking will terminate with a list that is
% one element shorter than Long. It cannot be used to generate lists
% longer than Short, because it doesn't look at all the elements of the
% longer list.
shorter_list([], [_|_]).
shorter_list([_|Short], [_|Long]) :-
shorter_list(Short, Long).
% subseq(Sequence, SubSequence, Complement)
% is true when SubSequence and Complement are both subsequences of the
% list Sequence (the order of corresponding elements being preserved)
% and every element of Sequence which is not in SubSequence is in the
% Complement and vice versa. That is,
% length(Sequence) = length(SubSequence)+length(Complement), e.g.
% subseq([1,2,3,4], [1,3,4], [2]). This was written to generate subsets
% and their complements together, but can also be used to interleave two
% lists in all possible ways. Note that if S1 is a subset of S2, it will
% be generated *before S2 as a SubSequence and *after it as a Complement.
subseq([], [], []).
subseq([Head|Tail], Sbsq, [Head|Cmpl]) :-
subseq(Tail, Sbsq, Cmpl).
subseq([Head|Tail], [Head|Sbsq], Cmpl) :-
subseq(Tail, Sbsq, Cmpl).
% subseq0(Sequence, SubSequence)
% is true when SubSequence is a subsequence of Sequence, but may
% be Sequence itself. Thus subseq0([a,b], [a,b]) is true as well
% as subseq0([a,b], [a]).
% subseq1(Sequence, SubSequence)
% is true when SubSequence is a proper subsequence of Sequence,
% that is it contains at least one element less.
% ?- setof(X, subseq0([a,b,c],X), Xs).
% Xs = [[],[a],[a,b],[a,b,c],[a,c],[b],[b,c],[c]]
% ?- bagof(X, subseq0([a,b,c,d],X), Xs).
% Xs = [[a,b,c,d],[b,c,d],[c,d],[d],[],[c],[b,d],[b],[b,c],[a,c,d],
% [a,d],[a],[a,c],[a,b,d],[a,b],[a,b,c]]
subseq0(List, List).
subseq0(List, Rest) :-
subseq1(List, Rest).
subseq1([_|Tail], Rest) :-
subseq0(Tail, Rest).
subseq1([Head|Tail], [Head|Rest]) :-
subseq1(Tail, Rest).
% sumlist(Numbers, Total)
% is true when Numbers is a list of integers, and Total is their sum.
sumlist(Numbers, Total) :-
sumlist(Numbers, 0, Total).
sumlist([], Total, Total).
sumlist([Head|Tail], Sofar, Total) :-
Next is Sofar+Head,
sumlist(Tail, Next, Total).