library(lists)This library module provides operations on lists. Exported predicates:
select(?Element, ?Set, ?Residue)selectchk(+Element, +Set, ?Residue)select/3 what memberchk/2 is to member/2. That is, it locates
the first occurrence of Element in Set, and deletes it, giving Residue.
It is steadfast in Residue.
append(+ListOfLists, -List) append(Lists, Appended) :-
( foreach(List,Lists),
fromto(Appended,S0,S,[])
do append(List, S, S0)
).
append(?Prefix, ?Tail1, ?List1, ?Tail2, ?List2)append(Prefix, Tail1, List1) and append(Prefix, Tail2, List2)
are both true. You could call append/3 twice, but that is order-
dependent. This will terminate if Prefix is a proper list or if
either List1 or List2 is a proper list.
correspond(?X, ?Xlist, ?Ylist, ?Y)select/4.
delete(+List, +Kill, -Residue)select(Kill, List, Residue).
If List is not proper, delete/3 will fail. Kill and the elements of
List should be sufficiently instantiated for \= to be sound.
Could be defined as:
delete(List, Kill, Residue) :-
( foreach(X,List),
fromto(Residue,S0,S,[]),
param(Kill)
do (X = Kill -> S0 = S ; S0 = [X|S])
).
delete(+List, +Kill, +Count, -Residue)delete/4 may fail. Kill and the elements of
List should be sufficiently instantiated for \= to be sound.
is_list(+List)keys_and_values(?[K1-V1,...,Kn-Vn], ?[K1,...,Kn], ?[V1,...,Vn])keysort/2 wants and
produces) into separate lists of Keys and of Values. It may just as
well be used for building a list of pairs from a pair of lists. In
fact one usually wants just the keys or just the values, but you can
supply _ as the other argument. For example, suppose you wanted to
sort a list without having duplicates removed. You could do
keys_and_values(RawPairs, RawKeys, _),
keysort(RawPairs, OrdPairs),
keys_and_values(OrdPairs, OrdKeys, _).
Could be defined as:
keys_and_values([], [], []).
keys_and_values([Key-Value|Pairs], [Key|Keys], [Value|Values]) :-
keys_and_values(Pairs, Keys, Values).
last(+List, -Last)last(L, X) :- append(_, [X], L).
nextto(?X, ?Y, +List)nextto(X, Y, List) :- append(_, [X,Y|_], List).
It may be used to enumerate successive pairs from the list.
List should be proper, otherwise nextto/3 will generate it.
nth0(?N, ?List, ?Elem)nth0(0, [H|T], H).
Either N should be an integer, or List should be proper.
nth1(?N, ?List, ?Element)nth1(1, [H|T], H).
This is just like nth0/3 except that it counts from 1 instead of 0.
Either N should be an integer, or List should be proper.
nth0(?N, ?List, ?Elem, ?Rest)nth0(2, List, c, [a,b,d,e]) unifies List with [a,b,c,d,e].
This can be seen as inserting Elem after the Nth element of Rest
if you count from 1 rather than 0.
Either N should be an integer, or List or Rest should be proper.
nth1(?N, ?List, ?Elem, ?Rest)nth1(2, List, b, [a,c,d,e]) unifies List with [a,b,c,d,e].
Either N should be an integer, or List or Rest should be proper.
one_longer(?Longer, ?Shorter)length(Longer,N), length(Shorter,M), succ(M,N)
for some integers M, N. It was
written to make {nth0,nth1}/4 able to find the index, just as
same_length/2 is useful for making things invertible.
perm(+List, ?Perm)perm/2 is to generate permutations. You should not use this
predicate in new programs; use permutation/2 instead. List must be
a proper list. Perm may be partly instantiated.
permutation(?List, ?Perm)perm/2, it will work even when List is not a proper list.
It even acts in a marginally sensible way when Perm isn't proper
either, but it will still backtrack forever.
Be careful: this is quite efficient, but the number of permutations of an
N-element list is N!, and even for a 7-element list that is 5040.
perm2(?A,?B, ?C,?D)proper_length(+List, ?Length)remove_dups(+List, ?Pruned)reverse(?List, ?Reversed)reverse/2 can backtrack forever trying ever
longer lists.
rev(+List, ?Reversed)reverse/2 which only works one way around.
Its List argument must be a proper list whatever Reversed is.
You should use reverse/2 in new programs, though rev/2 is
faster when it is safe to use it.
same_length(?List1, ?List2)same_length(?List1, ?List2, ?Length)select(?X, ?Xlist, ?Y, ?Ylist)selectchk(?X, +Xlist, ?Y, +Ylist)select/4 as memberhck/2 is to member/2. That is, it finds the
first K such that X unifies with the Kth element of Xlist and Y with
the Kth element of Ylist, and it commits to the bindings thus found.
If you have Keys and Values in "parallel" lists, you can use this to
find the Value associated with a particular Key (much better methods
exist). Except for argument order, this is identical to correspond/4,
but selectchk/4 is a member of a coherent family. Note that the
arguments are like the arguments of memberchk/2, twice.
shorter_list(?Short, ?Long)subseq(?Sequence, ?SubSequence, ?Complement)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.
subseq0(+Sequence, ?SubSequence)subseq0([a,b], [a,b]) is true as well
as subseq0([a,b], [a]). Sequence must be a proper list, since
there are infinitely many lists with a given SubSequence.
?- 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]]
subseq1(+Sequence, ?SubSequence)sumlist(+Numbers, ?Total) sumlist(Numbers, Total) :-
( foreach(X,Numbers),
fromto(0,S0,S,Total)
do S is S0+X
).
transpose(?X, ?Y)append_length(?Prefix, ?Suffix, ?List, ?Length)append(Prefix, Suffix, List), length(Prefix, Length).
The normal use of this is to split a List into a Prefix of
a given Length and the corresponding Suffix, but it can be
used any way around provided that
Length is instantiated, or
Prefix is a proper list, or
List is a proper list.
append_length(?Suffix, ?List, ?Length)append_length(Prefix, Suffix, List, Length) is true.
When you don't want to know the Prefix, you should call this
predicate, because it doesn't construct the Prefix argument,
which append_length/4 would do.
prefix_length(?List, ?Prefix, ?Length) prefix(List, Prefix) &
length(Prefix, Length).
The normal use of this is to find the first Length elements of
a given List, but it can be used any way around provided that
Length is instantiated, or
Prefix is a proper list, or
List is a proper list.
It is identical in effect to append_length(Prefix, _, List, Length).
proper_prefix_length(?List, ?Prefix, ?Length) proper_prefix(List, Prefix) &
length(Prefix, Length).
The normal use of this is to find the first Length elements of
a given List, but it can be used any way around provided that
Length is instantiated, or
Prefix is a proper list, or
List is a proper list.
It is logically equivalent to prefix(Prefix, List, Length), Length > 0.
suffix_length(+List, ?Suffix, ?Length) suffix(List, Suffix) &
length(Suffix, Length).
The normal use of this is to return the last Length elements of
a given List. For this to be sure of termination,
List must be a proper list.
If Length is instantiated or Suffix is a proper list, this predicate
is determinate.
proper_suffix_length(+List, ?Suffix, ?Length) proper_suffix(List, Suffix) &
length(Suffix, Length).
The normal use of this is to return the last Length elements of
a given List. For this to be sure of termination,
List must be a proper list.
If Length is instantiated or Suffix is a proper list, this predicate
is determinate.
rotate_list(+Amount, ?List, ?Rotated) append(Prefix, Suffix, List) &
append(Suffix, Prefix, Rotated) &
( Amount >= 0 & length(Prefix, Amount)
| Amount =< 0 & length(Suffix, Amount)
).
That is to say, List rotated LEFT by Amount is Rotated.
Amount must already be instantiated. As it is a strict input,
it must come first.
rotate_list(?List, ?Rotated)rotate_list(1, List, Rotated), but is a bit less
heavy-handed.
rotate_list(X, Y) rotates X left one place yielding Y.
rotate_list(Y, X) rotates X right one place yielding Y.
Either List or Rotated should be a proper list.
sublist(+Whole, ?Part, ?Before, ?Length, ?After)length(Alpha, Before)
length(Part, Length)
length(Omega, After)
cons(?Head, ?Tail, ?List)append([Head], Tail, List). No restrictions.
last(?Fore, ?Last, ?List)append(Fore, [Last], List).
Fore or Last should be proper. It is expected that List will
be proper and Fore unbound, but it will work in reverse too.
head(?List, ?Head)tail(?List, ?Tail)prefix(?List, ?Prefix)proper_prefix(?List, ?Prefix)suffix(?List, ?Suffix)proper_suffix(?List, ?Suffix)segment(?List, ?Segment)proper_segment(?List, ?Segment)segment/2 which is not a solution of proper_segment/2
is segment(List,List). So proper_segment/2 has one solution fewer.
cumlist(:Pred, +[X1,...,Xn], ?V0, ?[V1,...,Vn])cumlist(:Pred, +[X1,...,Xn], +[Y1,...,Yn], ?V0, ?[V1,...,Vn])cumlist(:Pred, +[X1,...,Xn], +[Y1,...,Yn], +[Z1,...,Zn], ?V0, ?[V1,...,Vn])cumlist/4 maps a ternary predicate Pred down the list [X1,...,Xn] just as
scanlist/4 does, and returns a list of the results. It terminates
when the lists runs out. If Pred is bidirectional, it may be
used to derive [X1...Xn] from V0 and [V1...Vn], e.g.
cumlist(plus, [1,2,3,4], 0, /* -> */ [1,3,6,10]) and
cumlist(plus, [1,1,1,1], /* <- */ 0, [1,2,3,4]).
Could be defined as:
cumlist(Pred, Xs, V0, Cum) :-
( foreach(X,Xs),
foreach(V,Cum),
fromto(V0,V1,V,_),
param(Pred)
do call(Pred,X,V1,V)
).
cumlist(Pred, Xs, Ys, V0, Cum) :-
( foreach(X,Xs),
foreach(Y,Ys),
foreach(V,Cum),
fromto(V0,V1,V,_),
param(Pred)
do call(Pred,X,Y,V1,V)
).
cumlist(Pred, Xs, Ys, Zs, V0, Cum) :-
( foreach(X,Xs),
foreach(Y,Ys),
foreach(Z,Zs),
foreach(V,Cum),
fromto(V0,V1,V,_),
param(Pred)
do call(Pred,X,Y,Z,V1,V)
).
maplist(:Pred, +List) maplist(Pred, Xs) :-
( foreach(X,Xs),
param(Pred)
do call(Pred, X)
).
maplist(:Pred, +OldList, ?NewList) maplist(Pred, Xs, Ys) :-
( foreach(X,Xs),
foreach(Y,Ys),
param(Pred)
do call(Pred, X, Y)
).
maplist(:Pred, +Xs, ?Ys, ?Zs) maplist(Pred, Xs, Ys, Zs) :-
( foreach(X,Xs),
foreach(Y,Ys),
foreach(Z,Zs),
param(Pred)
do call(Pred, X, Y, Z)
).
map_product(Pred, Xs, Ys, PredOfProduct)maplist(P, Xs, L) is the analogue of Miranda's
let L = [ P x | x <- Xs ]
so map_product(P, Xs, Ys, L) is the analogue of Miranda's
let L = [ P x y | x <- Xs; y <- Ys ]
That is, if Xs = [X1,...,Xm], Ys = [Y1,...,Yn], and P(Xi,Yj,Zij), L = [Z11,...,Z1n,Z21,...,Z2n,...,Zm1,...,Zmn]. It is as if we formed the cartesian product of Xs and Ys and applied P to the (Xi,Yj) pairs. Could be defined as:
map_product(Pred, Xs, Ys, Zs) :-
( foreach(X,Xs),
fromto(Zs,S0,S,[]),
param([Ys,Pred])
do ( foreach(Y,Ys),
fromto(S0,[Z|S1],S1,S),
param([X,Pred])
do call(Pred, X, Y, Z)
)
).
scanlist(:Pred, [X1,...,Xn], ?V1, ?V)scanlist(:Pred, [X1,...,Xn], [Y1,...,Yn], ?V1, ?V)scanlist(:Pred, [X1,...,Xn], [Y1,...,Yn], [Z1,...,Zn], ?V1, ?V)scanlist/4 maps a ternary relation Pred down a list. The computation is
Pred(X1,V1,V2), Pred(X2,V2,V3), ..., Pred(Xn,Vn,V)
So if Pred is plus/3, scanlist(plus, [X1,...,Xn], 0, V) puts the
sum of the list elements in V.
Note that the order of the arguments passed to Pred is the same
as the order of the arguments following Pred. This also holds
for scanlist/5 and scanlist/6, e.g.
scanlist(Pred, Xs, Ys, Zs, V1, V) calls Pred(X3,Y3,Z3,V3,V4).
Could be defined as:
scanlist(Pred, Xs, V0, V) :-
( foreach(X,Xs),
fromto(V0,V1,V2,V),
param(Pred)
do call(Pred, X, V1, V2)
).
scanlist(Pred, Xs, Ys, V0, V) :-
( foreach(X,Xs),
foreach(Y,Ys),
fromto(V0,V1,V2,V),
param(Pred)
do call(Pred, X, Y, V1, V2)
).
scanlist(Pred, Xs, Ys, Zs, V0, V) :-
( foreach(X,Xs),
foreach(Y,Ys),
foreach(Z,Zs),
fromto(V0,V1,V2,V),
param(Pred)
do call(Pred, X, Y, Z, V1, V2)
).
some(:Pred, +List)somechk/2 is to some/2 as memberchk/2 is to member/2.
member(X,L) <-> some(=(X), L).
memberchk(X, L) <-> somechk(=(X), L).
some(Pred,L) <-> member(X, L), call(Pred,X).
This acts on backtracking like member/2; List should be a proper list.
some(:Pred, +[X1,...,Xn], ?[Y1,...,Yn])some(:Pred, +[X1,...,Xn], ?[Y1,...,Yn], ?[Z1,...,Zn])somechk(:Pred, +[X1,...,Xn])memberchk/2).
somechk(:Pred, +[X1,...,Xn], ?[Y1,...,Yn])memberchk/2).
somechk(:Pred, +[X1,...,Xn], ?[Y1,...,Yn], ?[Z1,...,Zn])memberchk/2).
convlist(:Rewrite, +OldList, ?NewList)maplist/3 and include/3.
Each element of NewList is the image under Rewrite of some
element of OldList, and order is preserved, but elements of
OldList on which Rewrite is undefined (fails) are not represented.
Thus if foo(K,X,Y) :- integer(X), Y is X+K.
then convlist(foo(1), [1,a,0,joe(99),101], [2,1,102]).
OldList should be a proper list.
Could be defined as:
convlist(Pred, Xs, News) :-
( foreach(X,Xs),
fromto(News,S0,S,[]),
param(Pred)
do (call(Pred,X,N) -> S0 = [N|S] ; S0 = S)
).
exclude(:Pred, +Xs, ?SubList)exclude(:Pred, +Xs, +Ys, ?SubList)exclude(:Pred, +Xs, +Ys, +Zs, ?SubList) exclude(Pred, Xs, News) :-
( foreach(X,Xs),
fromto(News,S0,S,[]),
param(Pred)
do (call(Pred,X) -> S0 = S ; S0 = [X|S])
).
exclude(Pred, Xs, Ys, News) :-
( foreach(X,Xs),
foreach(Y,Ys),
fromto(News,S0,S,[]),
param(Pred)
do (call(Pred,X,Y) -> S0 = S ; S0 = [X|S])
).
exclude(Pred, Xs, Ys, Zs, News) :-
( foreach(X,Xs),
foreach(Y,Ys),
foreach(Z,Zs),
fromto(News,S0,S,[]),
param(Pred)
do (call(Pred,X,Y,Z) -> S0 = S ; S0 = [X|S])
).
include(:Pred, +Xs, ?SubList)include(:Pred, +Xs, +Ys, ?SubList)include(:Pred, +Xs, +Ys, +Zs, ?SubList) include(Pred, Xs, News) :-
( foreach(X,Xs),
fromto(News,S0,S,[]),
param(Pred)
do (call(Pred,X) -> S0 = [X|S] ; S0 = S)
).
include(Pred, Xs, News) :-
( foreach(X,Xs),
fromto(News,S0,S,[]),
param(Pred)
do (call(Pred,X) -> S0 = [X|S] ; S0 = S)
).
include(Pred, Xs, Ys, News) :-
( foreach(X,Xs),
foreach(Y,Ys),
fromto(News,S0,S,[]),
param(Pred)
do (call(Pred,X,Y) -> S0 = [X|S] ; S0 = S)
).
include(Pred, Xs, Ys, Zs, News) :-
( foreach(X,Xs),
foreach(Y,Ys),
foreach(Z,Zs),
fromto(News,S0,S,[]),
param(Pred)
do (call(Pred,X,Y,Z) -> S0 = [X|S] ; S0 = S)
).
partition(:Pred, +List, ?Less, ?Equal, ?Greater)include/3 and exclude/3 which has some pretensions
to being logical. For each X in List, we call Pred(X,R), and route
X to Less, Equal, or Greater according as R is <, =, or > .
group(:Pred, +List, ?Front, ?Back)append(Front, Back, List), maplist(Pred, Front),
and Front is as long as possible.
group(:Pred, +Key, +List, ?Front, ?Back)append(Front, Back, List), maplist(call(Pred,Key), Front),
and Front is as long as possible. Strictly speaking we don't need it;
group(call(Pred,Key), List, Front, Back) would do just as well.
group(:Pred, +List, ?ListOfLists)append(ListOfLists, List), each element of ListOfLists
has the form [Head|Tail] such that group(Pred, Head, Tail, Tail, []),
and each element of ListOfLists is as long as possible. For example,
if you have a keysorted list, and define same_key(K-_, K-_), then
group(same_key, List, Buckets) will divide List up into Buckets of
pairs having the same key.
ordered(+List)<¯ 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.
ordered(+P, +[T1,T2,...,Tn])<¯, the list is ordered.
This is good for generating prefixes of sequences,
e.g. L = [1,_,_,_,_], ordered(times(2), L) yields L = [1,2,4,8,16].
max_member(?Xmax, +[X1,...,Xn])<¯) of X1,...,Xn.
If the list is empty, it fails quietly.
Could be defined as:
max_member(Maximum, [Head|Tail]) :-
( foreach(X,Tail),
fromto(Head,M0,M,Maximum)
do (X<¯M0 -> M = M0 ; M = X)
).
min_member(?Xmin, +[X1,...,Xn])<¯) of X1,...,Xn.
If the list is empty, it fails quietly.
Could be defined as:
min_member(Minimum, [Head|Tail]) :-
( foreach(X,Tail),
fromto(Head,M0,M,Minimum)
do (M0<¯X -> M = M0 ; M = X)
).
max_member(:P, ?Xmax, +[X1,...,Xn])<¯ .
Could be defined as:
max_member(Pred, Maximum, [Head|Tail]) :-
( foreach(X,Tail),
fromto(Head,M0,M,Maximum),
param(Pred)
do (call(Pred,X,M0) -> M = M0 ; M = X)
).
min_member(:P, ?Xmin, +[X1,...,Xn])<¯ .
Could be defined as:
min_member(Pred, Minimum, [Head|Tail]) :-
( foreach(X,Tail),
fromto(Head,M0,M,Minimum),
param(Pred)
do (call(Pred,M0,X) -> M = M0 ; M = X)
).
select_min(?Element, +Set, ?Residue)<¯) element
of Set, and Residue with a list of all the other elements.
select_min(:Pred, ?Element, +Set, ?Residue)select_max(?Element, +Set, ?Residue)select_max(:Pred, ?Element, +Set, ?Residue)increasing_prefix(?Sequence, ?Prefix, ?Tail)append(Prefix, Tail, Sequence)
and Prefix, together with the first element of Tail,
forms a monotone non-decreasing sequence, and
no longer Prefix will do. Pictorially,
Sequence = [x1,...,xm,xm+1,...,xn]
Prefix = [x1,...,xm]
Tail = [xm+1,...,xn]
x1 <¯ x2 <¯ ... <¯ xm <¯ xm+1
not xm+1 <¯ xm+2
This is perhaps a surprising definition; you might expect
that the first element of Tail would be included in Prefix.
However, this way, it means that if Sequence is a strictly
decreasing sequence, the Prefix will come out empty.
increasing_prefix(:Order, ?Sequence, ?Prefix, ?Tail)increasing_prefix/3, except that it uses the
binary relation Order in place of <¯.
decreasing_prefix(?Sequence, ?Prefix, ?Tail)decreasing_prefix(:Order, ?Sequence, ?Prefix, ?Tail)increasing_prefix/[3,4] check X(R)Y, these
routines check Y(R)X.
clumps(+Items, -Clumps)append(Clumps, Items)
==)
keyclumps(+Pairs, ?Clumps)append(Clumps, Pairs)
==) Keys.
clumped(+Items, ?Counts)clumps(Items, Clumps), then each Item-Count pair in Counts corresponds
to an element [Item/*1*/,...,Item/*Count*/] of Clumps.
Items must be a proper list of terms for which sorting would have been
sound. In fact, it usually is the result of sorting.
keyclumped(+Pairs, ?Groups)keyclumps(Pairs, Clumps), then for each K-[I1,...,In] pair in Groups
there is a [K-I1,...,K-In] clump in Clumps.
Pairs must be a proper list of pairs for which keysorting would have
been sound. In fact, it usually is the result of keysorting.