The superscript "(d)" stands for "difficult". Exercises similar to those marked with "(d)" might appear in candidacy exams, but not in the standard exams of CSE 428.
father(a,b). % 1 father(a,c). % 2 father(b,d). % 3 father(b,e). % 4 father(c,f). % 5whose graphical representation is:
a / \ b c / \ | d e fSay which answers, and in which order, are generated by your definitions for the queries
?- brother(X,Y). ?- cousin(X,Y). ?- grandson(X,Y). ?- descendent(X,Y).Justify your answers by drawing the SLD-tree (akas Prolog search tree) for each query, at least schematically.
brother(X,Y) :- father(Z,X), father(Z,Y), not(X=Y). % 6
cousin(X,Y) :- father(Z,X), father(W,Y), brother(Z,W). % 7
grandson(X,Y) :- father(Z,X), father(Y,Z). % 8
descendent(X,Y) :- father(Y,X). % 9 descendent(X,Y) :- father(Z,X), descendent(Z,Y). % 10
?- brother(X,Y). X = b Y = c ; X = c Y = b ; X = d Y = e ; X = e Y = d ; No ?- cousin(X,Y). X = d Y = f ; X = e Y = f ; X = f Y = d ; X = f Y = e ; No ?- grandson(X,Y). X = d Y = a ; X = e Y = a ; X = f Y = a ; No ?- descendent(X,Y). X = b Y = a ; X = c Y = a ; X = d Y = b ; X = e Y = b ; X = f Y = c ; X = d Y = a ; X = e Y = a ; X = f Y = a ; NoWe draw the SLD-tree for the first query. Abbreviation: fa stands for father.
?- brother(X,Y). ------------ | (6) | ?- fa(Z,X), fa(Z,Y), not(X=Y). ------- Z=a X=b / Z=a X=c / Z=b X=d | Z=b X=e \ Z=c X=f \ (1) (2) (3) (4) (5) / / | \ \ ?- fa(a,Y), ?- fa(a,Y), ?- fa(b,Y), ?- fa(b,Y), ?- fa(c,Y), ------- ------- ------- ------- ------- not(b=Y). not(c=Y). not(d=Y). not(e=Y). not(f=Y). / \ / \ / \ / \ | (1) (2) (1) (2) (3) (4) (3) (4) (5) | \ / \ Y=d / \ / \ | ... ... ... ... ?-not(d=d) ?-not(d=e) ... ... ... fail X=b X=c fail fail success X=e fail fail Y=c Y=b X=d Y=e Y=d
naive_reverse([],[]). naive_reverse([X|L],K) :- naive_reverse(L,M), append(M,[X],K).
fast_reverse(L,K) :- rev_aux(L,K,[]). rev_aux([],K,K). rev_aux([X|L],K,M) :- rev_aux(L,K,[X|M]).reverse
:- redefine_system_predicate(member(_,_)). member(X,[X|_]). member(X,[_|L]) :- member(X,L).
:- redefine_system_predicate(subset(_,_)). subset([],_). subset([X|L],K) :- member(X,K), subset(L,K).
disjoint([],_). disjoint([X|L],K) :- not(member(X,K)), disjoint(L,K).
:- redefine_system_predicate(union(_,_,_)). union(L,K,M) :- append(L,K,M).
:- redefine_system_predicate(intersection(_,_,_)). intersection([],_,[]). intersection([X|L],K,M) :- not(member(X,K)), intersection(L,K,M). intersection([X|L],K,[X|M]) :- member(X,K), intersection(L,K,M).
difference([],_,[]). difference([X|L],K,M) :- member(X,K), difference(L,K,M). difference([X|L],K,[X|M]) :- not(member(X,K)), difference(L,K,M).
:- redefine_system_predicate(union(_,_,_)). union([],K,K). union([X|L],K,[X|M]) :- not(member(X,K)), union(L,K,M). union([X|L],K,M) :- member(X,K), union(L,K,M).
:- redefine_system_predicate(union(_,_,_)). union(L,K,M) :- ordered_merge(L,K,M). ordered_merge([],K,K). ordered_merge(L,[],L). ordered_merge([X|L],[Y|K],[X|M]) :- X < Y, ordered_merge(L,[Y|K],M). ordered_merge([X|L],[Y|K],[Y|M]) :- Y < X, ordered_merge([X|L],K,M). ordered_merge([X|L],[Y|K],[X|M]) :- X=:=Y, ordered_merge(L,K,M).Some of the other predicates can be defined more efficiently, by using the fact that lists are ordered:
:- redefine_system_predicate(length(_,_)). length([],0). length([_|L],N) :- length(L,M), N is M+1.
occurrences(_,[],0). occurrences(X,[X|L],N) :- occurrences(X,L,M), N is M+1. occurrences(X,[Y|L],N) :- not(X=Y), occurrences(X,L,N).
occurs(1,[X|_],X). occurs(N,[_|L],X) :- N > 1, M is N-1, occurs(M,L,X).
sumlist([],0). sumlist([X|L],N) :- sumlist(L,M), N is M+X.
?- add_up_list([1,2,3,4],K). K = [1,3,6,10]; no
add_up_list(L,K) :- aux(L,K,0). aux([],[],_). aux([X|L],[Y|K],Z) :- Y is Z+X, aux(L,K,Y).
quicksort([],[]). quicksort([X|L],K) :- split(X,L,L1,L2), quicksort(L1,K1), quicksort(L2,K2), append(K1,[X|K2],K). split(_,[],[],[]). split(X,[Y|L],K,[Y|M]) :- X < Y, split(X,L,K,M). split(X,[Y|L],[Y|K],M) :- X >= Y, split(X,L,K,M).
:- redefine_system_predicate(merge(_,_,_)). merge(L,[],L). merge([],K,K). merge([X|L],[Y|K],[X|M]) :- X < Y, merge(L,[Y|K],M). merge([X|L],[Y|K],[Y|M]) :- X >= Y, merge([X|L],K,M).
emptybt the empty binary tree consbt(N,T1,T2) the binary tree with root N and left and right subtrees T1 and T2
preorder(emptybt,[]). preorder(consbt(N,T1,T2),L) :- preorder(T1,L1), preorder(T2,L2), append([N|L1],L2,L).
search_tree(L,T) :- quicksort(L,K), length(K,N), construct_tree(K,N,T). construct_tree([],0,emptybt). construct_tree(L,N,consbt(X,T1,T2)) :- N1 is N // 2, % integer division N2 is N - N1 - 1, divide(L,N1,L1,[X|L2]), construct_tree(L1,N1,T1), construct_tree(L2,N2,T2). divide(L,0,[],L). divide([X|L],N,[X|L1],L2) :- N > 0, N1 is N-1, divide(L,N1,L1,L2).
arc(a,b).would represent the existence of an arc going from the node a to the node b.
arc(a,b). % 1 arc(a,c). % 2 arc(b,c). % 3 arc(b,d). % 4 arc(c,d). % 5What answers are given for the goal ?- path(a,d,P) by your solution to the last point? Justify your answer by drawing the SLD-tree (akas Prolog search tree), at least schematically.
path(X,Y) :- path_aux(X,Y,[X]). % The third argument is the list of visited nodes path_aux(X,Y,_) :- arc(X,Y). path_aux(X,Y,L) :- arc(X,Z), not(member(Z,L)), path_aux(Z,Y,[Z|L]).
path(X,Y,P) :- path_aux(X,Y,[Y],P). % P is the path; 6 path_aux(X,Y,L,[X|L]) :- arc(X,Y). % The third arg is the list of visited nodes. 7 path_aux(X,Y,L,P) :- arc(Z,Y), not(member(Z,L)), path_aux(X,Z,[Z|L],P). % 8
?- path(a,d,P). P = [a, b, d] ; P = [a, c, d] ; P = [a, b, c, d] ; NoThe SLD-tree is the following. Abbreviation: m stands for member; pa stands for path_aux:
?- path(a,d,P). ----------- | (6) | ?- pa(a,d,[d],P). ------------- | (8) | ?- arc(Z,d), not(member(Z,[d])), pa(a,Z,[Z,d],P). -------- / | Z=b (4) (5) Z=c / | ?- not(m(b,[d])), pa(a,b,[b,d],P). ?- not(m(c,[d])), pa(a,c,[c,d],P). ------------- ------------- / | / | ?- pa(a,b,[b,d],P). ?- pa(a,c,[c,d],P). --------------- --------------- P= / \ / \ [a,b,d] (7) (8) P=[a,c,d] (7) (8) / \ / \ ?- arc(a,b). ... ?- arc(a,c). ?- arc(W,c), not(member(W,[c,d])), pa(a,W,[W,c,d]). -------- fail -------- -------- / / | | (1) (2) W=a (2) (3) W=b / / | | success success ... ?- not(member(b,[c,d])), fail -------------------- pa(a,b,[b,c,d]). | | ?- pa(a,b,[b,c,d]). --------------- / \ P=[a,b,c,d] (7) (8) / \ ?- arc(a,b). ... -------- fail / (1) / success