module 'data.list' {
/** length(List, N).
* Succeeds if List
is a list with N
elements.
*/
length(List, N) :-
'kernel':list_length(List, N).
/** member(X, List).
* Succeeds if List
is a (partial) list whose X
is an element.
*/
member(H, [H | _]).
member(H, [_ | T]) :-
member(H, T).
/** append(A, B, C).
* Succeeds if A
is a list and C
is the
* concatenation of A
and B
.
*/
append([], L, L).
append([H | T0], L, [H | T1]) :-
append(T0, L, T1).
/** flatten(ListOfLists, List).
* flatten([L, ...,
* L], L)
succeeds if
* L
is the concatenation of the lists
* L
, ...,
* L
.
*/
flatten([], []).
flatten([H | T], L) :-
append(H, LT, L),
flatten(T, LT).
/** join(ListOfLists, Delimiter, List).
*
* ListOfLists
and Delimiter
are lists.
*
* join([L, ...,
* L], Delimiter, L)
succeeds if
* L
is the concatenation of
* L
, Delimiter,
* L
, Delimiter, ...,
* L
, Delimiter,
* L
.
*/
join([], _, []).
join([H | T], Delim, L) :-
append(H, LT, L),
join_with_prefix(T, Delim, LT).
/** join_with_prefix(ListOfLists, Delimiter, List).
*
* ListOfLists
and Delimiter
are lists.
*
* join_with_prefix([L, ...,
* L], Delimiter, L)
succeeds if
* L
is the concatenation of
* Delimiter, L
,
* Delimiter, L
, ...,
* Delimiter, L
.
*/
join_with_prefix([], _, []).
join_with_prefix([H | T], Delim, L) :-
append(Delim, L0, L),
append(H, L1, L0),
join_with_prefix(T, Delim, L1).
/** reverse(L0, L1).
* Succeeds if the list L0
unifies with
* the list L1
in reverse order.
*/
reverse(L0, L1) :-
reverse_append(L0, [], L1).
/** reverse_append(A, B, C).
* Succeeds if the list C
is the
* concatenation of the reverse of A
and
* B
.
*/
reverse_append([], L, L).
reverse_append([H | T], L, R) :-
reverse_append(T, [H | L], R).
/** iter(List, F).
*
* F
is a module which implements a predicate do(X)
.
*
* iter([X, ...,
* X], F)
calls
* F:do(X)
* for from to
* .
*/
iter([], _).
iter([H | T], F) :-
F:do(H),
iter(T, F).
/** iter(List0, F, List1).
*
* F
is a module which implements a predicate do(X, Y)
.
*
* iter([X, ...,
* X], F,
* [Y, ...,
* Y])
calls
* F:do(X,
* Y)
* for from to
* .
*/
iter([], _, []).
iter([H0 | T0], F, [H1 | T1]) :-
F:do(H0, H1),
iter(T0, F, T1).
/** iter(List0, List1, List2, F).
*
* F
is a module which implements a predicate do(X, Y, Z)
.
*
* iter([X, ...,
* X],
* [Y, ...,
* Y],
* [Z, ...,
* Z], F)
calls
* F:do(X,
* Y,
* Z)
* for from to
* .
*/
iter([], [], [], _).
iter([H0 | T0], [H1 | T1], [H2 | T2], F) :-
F:do(H0, H1, H2),
iter(T0, T1, T2, F).
/** reverse_iter(List, F).
*
* F
is a module which implements a predicate do(X)
.
*
* reverse_iter([X, ...,
* X], F)
calls
* F:do(X)
, ...,
* F:do(X)
.
*/
reverse_iter([], _).
reverse_iter([H | T], F) :-
reverse_iter(T, F),
F:do(H).
/** morph(List0, F, List1).
*
* List0
is a list.
* F
is a module which implements a predicate do(X, Y)
.
*
* morph([X, ...,
* X], F, List1)
succeeds
* if List1
is the concatenation of
* the lists L, ...,
* L
where
* F:do(X,
* L)
, ...,
* F:do(X,
* L)
.
*/
morph([], _, []).
morph([H | T], F, List) :-
F:do(H, P),
append(P, Tail, List),
morph(T, F, Tail).
/** fold_left(List, Initial, F, Final).
*
* List
is a list.
* F
is a module which implements a predicate do(Item, Old, New)
.
*
* fold_left([X, ...,
* X],
* V, F, V)
succeeds
* if F:(X, V, V), ...,
* F:(X, V, V)
.
*/
fold_left([], Value, _) = Value.
fold_left([H | T], Value, F) = 'data.list':fold_left(T, F:do(H, Value), F).
/** fold_right(List, Initial, F, Final).
*
* List
is a list.
* F
is a module which implements a predicate do(Item, Old, New)
.
*
* fold_left([X, ...,
* X],
* V, F, V)
succeeds
* if F:(X, V, V), ...,
* F:(X, V, V)
.
*/
fold_right([], Value, _) = Value.
fold_right([H | T], Value, F) = F:do(H, 'data.list':fold_right(T, Value, F)).
/** iter_fold(List0, List1, Initial, F, Final).
*
* List0
is a list.
* F
is a module which implements a predicate
* do(Item0, Item1, Old, New)
.
*
* iter_fold([X, ...,
* X],
* [Y, ...,
* Y],
* V, F, V)
* succeeds if
* F:(X, Y, V, V), ...,
* F:(X, Y, V, V)
.
*/
iter_fold([], [], Value, _) = Value.
iter_fold([H0 | T0], [H1 | T1], Value, F) =
'data.list':iter_fold(T0, T1, F:do(H0, H1, Value), F).
/** accumulate(Generator, List).
*
* Generator
is a module which implements a predicate get(X)
.
*
* Calls Generator:get(X)
with a fresh variable
* X
at each call until failure. The predicate
* succeeds if List
is the list
* [X, ..., X]
,
* from the first introduced variable to the last.
*/
accumulate(Generator, List) :-
(
Generator:get(H)
->
List = [H | T],
accumulate(Generator, T)
;
List = []
).
/** init(I, J, Init, List).
*
* I
and J
are integers.
*
*
* Init
is a module which implements a predicate get(N, X)
.
*
* If I
≤ J
, calls
* Init:get(N, XN)
with a fresh variable
* XN
for N
from I
to
* J
. The predicate
* succeeds if List
is the list
* [X, ..., X]
.
* List
is empty if I > J
.
*/
init(I, J, Init, List) :-
(
'data.number':(I =< J)
->
List = [Init:get(I) | Tail],
init('data.number':succ(I), J, Init, Tail)
;
List = []
).
/** split_at_delim_left(List, Delimiter, Left, Right).
* Succeeds if List
is the concatenation of
* Left
, [Delimiter]
, Right
* and Delimiter
does not appear in Left
.
*/
split_at_delim_left([H | T], Delim, L0, L1) :-
(
H = Delim
->
L0 = [],
L1 = T
;
L0 = [H | T0],
split_at_delim_left(T, Delim, T0, L1)
).
/** split(List, Delimiter, ListOfLists).
* Succeeds if List
can be splitted in sub-lists
* separated by the element Delimiter
and
* ListOfLists
enumerates these sub-lists;
* Delimiter
does not appear in sub-lists.
*/
split(L, Delim, LL) :-
(
split_at_delim_left(L, Delim, H, T)
->
LL = [H | TL],
split(T, Delim, TL)
;
LL = [L]
).
/** merge(L0, L1, Preorder, L).
*
* Preorder
is a module with a predicate
* compare(X, Y, R)
which implements a total preorder over the elements of the lists L0
and L1
: R
* is unified to <
, or =
, or >
* whether X
is less than, or equal to, or greather than Y
respectively.
*
*
* L0
and L1
is sorted increasingly with respect to this order.
*
* merge(L0, L1, Preorder, L)
* succeeds if L
is the permutation of the concatenation
* of L0
and L1
which is sorted with respect
* Preorder
and where the relative position of equivalent
* elements with respect to Preorder
is preserved,
* elements of L0
first. */
merge(L0, L1, Preorder, L) :-
(
L0 = [H0 | T0]
->
(
L1 = [H1 | T1]
->
Preorder:compare(H0, H1, R),
(
R = '>'
->
L = [H1 | T],
merge(L0, T1, Preorder, T)
;
L = [H0 | T],
merge(T0, L1, Preorder, T)
)
;
L1 = [],
L = L0
)
;
L0 = [],
L = L1
).
/** merge_sort(List, Preorder, Sorted).
*
* List
is a list.
*
*
* Preorder
is a module with a predicate
* compare(X, Y, R)
which implements a total preorder over the elements of the lists L0
and L1
: R
* is unified to <
, or =
, or >
* whether X
is less than, or equal to, or greather than Y
respectively.
*
* merge_sort(List, Preorder, Sorted).
succeeds if Sorted
is the permutation of List
* stably sorted with respect to Preorder
.
* Runs in where is the length of List
.*/
merge_sort(List, Preorder, Sorted) :-
(
(
List = []
;
List = [_]
)
->
Sorted = List
;
Singletons = 'data.list':iter(List) {
do(X) = [X].
},
module Merge [Preorder] {
do(L0, L1) :-
(
(
L0 = []
;
L0 = [_]
)
->
L1 = L0
;
L0 = [A, B | T0]
->
L1 = ['data.list':merge(A, B, Preorder) | T1],
do(T0, T1)
).
},
module Aux [Merge, Sorted] {
do(LL) :-
(
LL = [Sorted0]
->
Sorted = Sorted0
;
do(Merge:do(LL))
).
},
Aux:do(Singletons)
).
/** split(List, ListTrue, ListFail, Select).
*
* List
is a list.
*
*
* Select
is a module with a predicate
* do(X)
succeeding or failing on elements of List
.
*
* ListTrue
is unified to the sub-list of List
of elements
* X
such that Select:do(X)
succeeds.
* ListFail
is unified to the sub-list of List
of elements
* Y
such that Select:do(Y)
fails.
*/
split([], [], [], _).
split([H | T], ListTrue, ListFail, Select) :-
(
Select:do(H)
->
ListTrue = [H | TT],
split(T, TT, ListFail, Select)
;
ListFail = [H | TF],
split(T, ListTrue, TF, Select)
).
/** quick_sort(List, Preorder, Sorted).
*
* List
is a list.
*
*
* Preorder
is a module with a predicate
* compare(X, Y, R)
which implements a total preorder over the elements of the lists L0
and L1
: R
* is unified to <
, or =
, or >
* whether X
is less than, or equal to, or greather than Y
respectively.
*
* quick_sort(List, Preorder, Sorted).
succeeds if Sorted
is the permutation of List
* stably sorted with respect to Preorder
.
* Runs in where is the length of List
.*/
quick_sort(List, Preorder, Sorted) :-
(
(
List = []
;
List = [_]
)
->
Sorted = List
;
List = [P | T],
split(T, List0, List1) [Preorder, P] {
do(X) :-
Preorder:compare(X, P, '<').
},
quick_sort(List0, Preorder, Sorted0),
quick_sort(List1, Preorder, Sorted1),
append(Sorted0, [P | Sorted1], Sorted)
).
/** longuest_prefix(List, Prefix).
* Succeeds if Prefix
is a prefix of List
,
* preferably the longuest one.
*/
longuest_prefix([H | T0], [H | T1]) :-
longuest_prefix(T0, T1).
longuest_prefix([], _).
/** subst(Src, Table, Tgt).
Src
is a list.
Table
is a list with elements of the form
A => B
where A
and B
are lists.
Succeeds if Tgt
is the list obtained from
Src
by substituting every occurrences of
sub-list A
in Src
by B
,
for every A => B
in Table
.
*/
subst(Src, Table, Tgt) :-
(
Src = []
->
Tgt = []
;
module [Table] {
find([], [H | SrcTail], [H | TgtTail]) :-
subst(SrcTail, Table, TgtTail).
find([From => To | TableTail], Src, Tgt) :-
(
append(From, SrcTail, Src)
->
append(To, TgtTail, Tgt),
subst(SrcTail, Table, TgtTail)
;
find(TableTail, Src, Tgt)
).
}:find(Table, Src, Tgt)
).
delete([], _, []).
delete([H | T], X, L) :-
(
X = H
->
L = U
;
L = [H | U]
),
delete(T, X, U).
select(X, [X | T], T).
select(X, [Y | T], [Y | U]) :-
select(X, T, U).
}