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