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([L1, ..., * Ln], L) succeeds if * L is the concatenation of the lists * L1, ..., * Ln. */ flatten([], []). flatten([H | T], L) :- append(H, LT, L), flatten(T, LT). /** join(ListOfLists, Delimiter, List). * * ListOfLists and Delimiter are lists. * * join([L1, ..., * Ln], Delimiter, L) succeeds if * L is the concatenation of * L1, Delimiter, * L2, Delimiter, ..., * Ln-1, Delimiter, * Ln. */ 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([L1, ..., * Ln], Delimiter, L) succeeds if * L is the concatenation of * Delimiter, L1, * Delimiter, L2, ..., * Delimiter, Ln. */ 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([X1, ..., * Xn], F) calls * F:do(Xi) * for i from 1 to * n. */ 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([X1, ..., * Xn], F, * [Y1, ..., * Yn]) calls * F:do(Xi, * Yi) * for i from 1 to * n. */ 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([X1, ..., * Xn], * [Y1, ..., * Yn], * [Z1, ..., * Zn], F) calls * F:do(Xi, * Yi, * Zi) * for i from 1 to * n. */ 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([X1, ..., * Xn], F) calls * F:do(Xn), ..., * F:do(X1). */ 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([X1, ..., * Xn], F, List1) succeeds * if List1 is the concatenation of * the lists L1, ..., * Ln where * F:do(X1, * L1), ..., * F:do(Xn, * Ln). */ 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([X1, ..., * Xn], * V0, F, Vn) succeeds * if F:(X1, V0, V1), ..., * F:(Xn, Vn-1, Vn). */ 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([X1, ..., * Xn], * Vn, F, V0) succeeds * if F:(Xn, Vn, Vn-1), ..., * F:(X1, V1/math>, V0). */ 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([X1, ..., * Xn], * [Y1, ..., * Yn], * V0, F, Vn) * succeeds if * F:(X1, Y1, V0, V1), ..., * F:(Xn, Yn/math>, Vn-1, Vn). */ 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(Xi) with a fresh variable * Xi at each call until failure. The predicate * succeeds if List is the list * [X1, ..., Xn], * 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 IJ, calls * Init:get(N, XN) with a fresh variable * XN for N from I to * J. The predicate * succeeds if List is the list * [XI, ..., XJ]. * 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 O(n n) where n 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 O(n 2) where n 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). }