%%% version 4.6.13-3 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%% The {log} standard library %%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%% version 4.6.13 %%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % % March 2008 - by Gianfranco Rossi % % Last update: February 2021 % by Maximiliano Cristia' and Gianfranco Rossi % %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % This file contains the {log} definition of a number of predicates, % mostly dealing with sets and lists, which are not provided as primitive % in {log}. % It can be loaded into the {log} environment by issuing the % goal consult_lib (provided 'setloglib.slog' is the name you % give to this file). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% General operations dealing with sets %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% powerset(+S,?PS) is true if PS is the powerset %%% of S (i.e., PS = 2^S) % powerset(S,PS) :- PS = {SS : subset(SS,S)}. %%% cross_product(+A,+B,?CP) is true if CP is the %%% Cartesian product of sets A and B % cross_product(A,B,CP) :- CP = {X : exists([Y,Z], X = [Y,Z] & Y in A & Z in B)}. %%% Generalized union ("\bigcup"). %%% bun(S,R) is true if R is the union of all the elements %%% of the set of sets S % bun({},{}). bun({A/Set},S) :- A nin Set & bun(Set,T) & un(A,T,S). %%% Generalized intersection ("\bigcap"). %%% binters(S,R) is true if R is the inersection of all the %%% elements of the set of sets S % binters({A},A). binters({A/Set},S) :- A nin Set & binters(Set,T) & inters(A,T,S). %%% diff1(?S,?X,?R) is true if R is S\{X} %%% equivalent to diff(S,{X},R) but possibly more efficient % diff1({X/R},X,R) :- X nin R. diff1(S,X,S) :- X nin S. %%% syntactic unification between terms T1 and T2 % eq(T1,T2) :- prolog_call(T1 = T2). %%% symdiff(A,B,C) is true if C is the symmetric difference %%% between A and B % symdiff(A,B,C) :- diff(A,B,M1) & diff(B,A,M2) & un(M1,M2,C). %%% list_to_set(+L,?S) is true if S denotes the set %%% of all elements of the list L % list_to_set([],{}). list_to_set([X|L],{X\S}) :- list_to_set(L,S). %%% int_to_set(+I,?S) is true if S denotes the set %%% of all elements of the interval I % int_to_set(int(A,A),{A}). int_to_set(int(A,B),{A\S}) :- A < B & A1 is A + 1 & int_to_set(int(A1,B),S). %%% like int_to_set/2 but delayed if interval bounds are unknown % dint_to_set(A,B,S) :- delay(int_to_set(int(A,B),S),nonvar(A) & nonvar(B)). %%% set_to_list(+S,?L): true if S is a set and L is a list %%% containing all and only the elements of S, WITHOUT REPETITIONS %%% (all possible permutations of L) % set_to_list({},[]). set_to_list({X/Set},List) :- X nin Set & List = [X|L] & set_to_list(Set,L). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% Dealing with Prolog lists %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% sublist(Sb,L) true if list Sb is a sublist of list L % sublist(Sb,L) :- prefix(Sb,L). sublist(Sb,[_|T]) :- Sb neq [] & sublist(Sb,T). %%% take(N,L,NewL) true if list NewL consists of the %%% first N elements of list L % take(0,_,[ ]). take(N,[H|T],[H|R]) :- N>0 & M is N-1 & take(M,T,R). %%% drop(N,L,NewL) true if list NewL is L with its %%% first N elements removed % drop(0,L,L). drop(N,[_|T],R) :- N >0 & M is N-1 & drop(M,T,R). %%% extract(S,L,NewL): true if S is a set of integer numbers, L is a %%% list of elements of any type, and NewL is a list containing %%% the i-th element of L, for all i in S %%% (e.g., extract({4,2},[a,h,g,m,t,r],L) ==> L = [h,m]) % extract({},_,[]). extract(_,[],[]). extract(Set,List,NewList) :- set_to_list(Set,L) & prolog_call(sort(L,SL)) & extract0(SL,List,NewList). extract0([],_,[]). extract0([N | IndexList], List, NewList) :- nth1(N,List,E) & NewList = [E | L] & extract0(IndexList,List,L). %%% filter(L,S,NewL): true if L is a list, S is a set, and NewL is a %%% list containing the elements of L that are also elements of S; %%% L and NewL also verify the following sublist(NewL, L). %%% (e.g., filter([a,h,g,m,t,r],{m,h,s},L) ==> L = [h,m]) % filter(_,{},[]). filter([],Set,[]) :- Set neq {}. filter([X|List],Set,[X | L]) :- X in Set & filter(List,Set,L). filter([X|List],Set,NewList) :- Set neq {} & X nin Set & filter(List,Set,NewList). %%%%% Redefining Prolog built-ins (for the user convenience) member(X,L) :- prolog_call(member(X,L)). append(L1,L2,L3) :- prolog_call(append(L1,L2,L3)). nth1(X,L,Y) :- prolog_call(nth1(X,L,Y)). length(L,N) :- prolog_call(length(L,N)). reverse(L,R) :- prolog_call(reverse(L,R)). last(L,X) :- prolog_call(last(L,X)). prefix(P,L) :- prolog_call(prefix(P,L)). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% Labeling predicates %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%% label(nat,X): true if X is a natural number %%% when X is a variable, can be used to generate all natural numbers: 0,1,2,... label(nat,X) :- nonvar(X) & integer(X) & X >= 0. label(nat,X) :- var(X) & nat_num(0,X). nat_num(N,N). nat_num(N,M) :- N1 is N+1 & nat_num(N1,M). %%% label(int,X): true if X is an integer number %%% when X is a variable, can be used to generate all integer numbers: 0,1,-1,2,-2,... label(int,X) :- nonvar(X) & integer(X). label(int,X) :- var(X) & int_num(0,X). int_num(N,N). int_num(N,M) :- N neq 0 & M is -(N). int_num(N,M) :- N1 is N+1 & int_num(N1,M). %%% label(list,L): true if L is a list %%% when L is a variable, can be used to generate all lists of increasing %%% length (starting from []) label(list,L) :- nonvar(L) & list(L). label(list,L) :- var(L) & nat_num(0,N) & prolog_call(length(L,N)). %%% label(set,L): true if S is a set %%% when L is a variable, can be used to generate all sets of increasing %%% cardinality (starting from {}) label(set,S) :- nonvar(S) & set(S). label(set,S) :- var(S) & nat_num(0,N) & mode(M) & mode(solver) & solve(size(S,N)) & mode(M). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%% For compatibility with previous releases %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% :- prolog_call(op(700,xfx,[ein,enin])). T ein S :- % for compatibility with previous releases T in S. T enin S :- % for compatibility with previous releases T nin S. einters(S1,S2,S3) :- % for compatibility with previous releases inters(S1,S2,S3). esubset(S1,S2) :- % for compatibility with previous releases subset(S1,S2). essubset(S1,S2) :- % for compatibility with previous releases ssubset(S1,S2). ensubset(S1,S2) :- % for compatibility with previous releases nsubset(S1,S2). dsubset(S1,S2) :- % for compatibility with previous releases esubset(S1,S2). dnsubset(S1,S2) :- % for compatibility with previous releases ensubset(S1,S2). dssubset(S1,S2) :- % for compatibility with previous releases essubset(S1,S2). dinters(S1,S2,S3) :- % for compatibility with previous releases einters(S1,S2,S3). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % Interactive help predicates %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% setlog_lib_help :- nl & write('The {log} library provides a number of predicates, ') & nl & write('mainly dealing with sets and lists, which are not provided ') & nl & write('as primitive in {log}.') & nl & nl & write('It can be loaded into the {log} environment by issuing the ') & nl & write('goal consult_lib (provided ''setloglib.slog'' is the name you ') & nl & write('give to the library file).') & nl.