COT 3541 Fall 2015 Some Prolog Predicates ====================== 1. mother(X,Y) and the predicate print_all_mothers that prints all mothers % mother(X,Y) is satisfied when X is the mother of Y. mother(X,Y) :- parent(X,Y), female(X). % print_mothers prints all pairs X,Y where X is the mother of Y print_mothers :- print_mother_header, print_all_mothers. print_mother_header :- nl,nl,tab(10), write('MOTHER LIST'), nl,tab(10), write('==========='),nl. print_all_mothers :- mother(X,Y), % find the next mother nl, write(X), write(' is the mother of '), write(Y), write('.'), % print it fail. % repeat print_all_mothers. 2. half_sibling(X,Y) and the predicate print_half_siblings that prints all half siblings % print_half_sibling prints all pairs X,Y where X is a % half sibling of Y print_half_siblings :- print_half_sibling_header, print_all_half_siblings. print_half_sibling_header :- nl, nl,tab(10), write('HALF SIBLING LIST'), nl,tab(10), write('================='),nl. print_all_half_siblings :- half_sibling(X,Y), % find the next half sibling nl, write(X), write(' is a half sibling of '), write(Y), write('.'), % print it fail. % repeat print_all_half_siblings. 3. subterm(X,List) is satisfied if List is the list of subterms of X % subterms(T,L) is satisfied if L is % the list of all subterms of T subterms(T,[T]):- atom(T). subterms(T,[T|Rest]):- compound(T), T =..[_|Tail], subtermsOfList(Tail,Rest). % find the subterms of a list of terms subtermsOfList([],[]). subtermsOfList([T|Tail],List):- subterms(T,L1),subtermsOfList(Tail,L2), append(L1,L2,List). 4. a prolog version of quickSort % a prolog version of quicksort % the list has integers and the pivot is the first item quickSort([],[]). quickSort([X],[X]). quickSort([X,Y],[X,Y]):- X < Y. quicksort([X,Y], [Y,X]). quickSort([Pivot|Tail],SortedList):- split(Tail, Pivot, Before, After), % split the tail quickSort(Before,SortedBefore), % sort the 2 halves quickSort(After, SortedAfter), append(SortedBefore, [Pivot|SortedAfter],SortedList). % split the list according to the pivot split([],_,[],[]). split([X |Tail], Pivot, [X| Tail1], Tail2):- X < Pivot, split(Tail, Pivot, Tail1, Tail2). split([X |Tail], Pivot, Tail1, [X| Tail2]):- split(Tail, Pivot, Tail1,Tail2). %atom_list(List) is satisfied if List is a list of atoms atom_list([]). % the empty list is a list of atoms atom_list([ Head | Tail]) :- atom(Head), % Head is an atom atom_list(Tail). % Tail is a list of atoms 5. %is_multi(L) is satisfied if all elements of L have the % form X/N where X is an atom and N is an integer graeter than 0, % and there are no duplications of elements. is_multi([]). is_multi([X/N|Tail]):- atom(X), integer(N), N>0, not(member(X/M,Tail)), % no duplications is_multi(Tail). % the tail is a multiset % not(X) is true if X is satisfiable. not(X):- X,!,fail. not(X). % member(Item ,List) is satisfied if Item occurs in List member(Item, [Item | _]). % Item occurs at the head of the list member(Item, [_|Tail]):- member(Item, Tail). % Item in the tail 6. % form_multi(List, Multi) forms the multiset Multi % from the list List. form_multi([],[]). % if List is empty, so is Multi form_multi([Head | Tail], [Head/Count | Multi2]):- % find Count, the number of occurrences of Head in List % while deleting its occurrences from Tail count_and_delete(Head, Tail, Reduced_Tail,Count), % find the multiset of the reduced tail form_multi(Reduced_Tail, Multi2). % count_and_delete (X, List, Reduced_List, Count) counts how many % times X occurs in List, deletes all occurrences of X from List getting % Reduced_List, and returns the number of occurrences in Count. count_and_delete(_,[],[],1). % X already occured as head count_and_delete(X, [X|Tail], R_Tail,N):- % count and reduce the tail count_and_delete(X,Tail, R_Tail,M), N is M +1. % count the occurrence in front of Tail count_and_delete(X, [Y|Tail], [Y |R_Tail],N):- % count and reduce the tail count_and_delete(X,Tail, R_Tail,N). 7. %multi_lub(M1,M2,M) is satisfied if M is the lub of the multisets M1 and M2. % we do the recursion on M1. multi_lub([],M2,M2). % the lub is M2 multi_lub([X/N |Tail1], M2, [X/P|Rest]):- delete(X/Q,M2,ReducedM2), % delete the X term from M2 P is max(N,Q), % the multiset index is the larger of the two multi_lub(Tail1, ReducedM2, Rest). % process the rest of the items of M1 multi_lub( [X/N |Tail1], M2, [X/N|Rest]):- multi_lub(Tail1, M2, Rest). % X is not in M2 8. %delete(Item,List, ReducedList) is satisfied if we find an occurrence of Item in List % we eliminate it and get ReducedList delete(Item, [Item|Tail],Tail). % the item is at the head delete(Item, [Head |Tail], [Head|ReducedTail]):- delete(Item,Tail,ReducedTail). % find Item in Tail 9. %multi_glb(L1,L2,L) is satisfied if L is the lub of the multisets L1 and L2 % this means that it contains the terms that occur in both L1 and L1 and have as % multiplicity the smallest of the two multiplicities % we use recursion on L1. multi_glb([],L,[]). % since L1 is empty, so is L multi_glb([X/N|Tail], L2, [X/P| Multi]):- member(X/Q,L2), % X occurs in L2 P is min(N,Q), % take the smallest multiplicity multi_glb(Tail,L2,Multi). % find the glb of Tail and L2 multi_glb([ X/N | Tail],L2, L) :- multi_glb(Tail, L2,L). % X is not in L2 10. %flatten(List1,List2) puts all integers of List1 onto List2. % List1 can contain atoms, lists of atoms, lists of lists of atoms, a, s.o. my_flatten([],[]). my_flatten([H|Tail],[H|Tail1]):- integer(H), my_flatten(Tail,Tail1). my_flatten([H|Tail],L):- % H is a list my_flatten(H,L1), % flatten the head my_flatten(Tail,L2), % flatten the tail append(L1,L2,L). % concatenate the two lists 11. % subsequence(List1, List2) is satisfied if the elements of List1 occur in the % same order in List2. subsequence([],L):- L=[]; L = [H|T]. % [] is a subsequence of any sequence subsequence([Head |Tail1], [Head | Tail2]):- subsequence(Tail1,Tail2). % the two lists have the same head subsequence(L1, [Head |Tail2]):- subsequence(L1,Tail2). % L1 is a subsequence of the tail of L2 12. % list_index(X,List,N) is satisfied if X is the Nth item in List list_index(X,[X|_],1). % X is the head of the list list_index(X,[_|Tail],M):- list_index(X, Tail,N), % find X in Tail M is N + 1.