-
Notifications
You must be signed in to change notification settings - Fork 1
/
self_study_answers.pl
132 lines (123 loc) · 5.27 KB
/
self_study_answers.pl
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
%%% Movies Database Queries %%%
%%% Q1 %%%
% In which year was the movie American Beauty released
% ?- movie(american_beauty,Y).
% NB. This is a query to be typed in at the Prolog prompt;
% you can turn it into a clause by naming the query, e.g. american_beauty_year(Y) :- movie(american_beauty,Y).
% Find a movie that was released in the year 2000?
% ?- movie(M,2000).
% Find a movie that was released before 2000?
% ?- movie(M,Y),Y<2000.
% Find the name and year of a movie?
% ?- movie(M,Y).
% Find an actor who has appeared in more than one movie?
% ?- actor(M1,A,_),actor(M2,A,_),M1@<M2. % or just M1\=M2.
% Find a director who has directed a movie in which the actress Scarlett Johansson appeared?
% ?- actress(M,scarlett_johansson,_),director(M,D).
% Find an actor who has also directed a movie?
% ?- director(M,A),actor(M,A,_).
% Find an actor or actress who has also directed a movie?
% (Hint: to do this in a single query you will need to use the ; disjunction operator)
% ?- director(M,A),(actor(M,A,_);actress(M,A,_)).
%%% Q2 %%%
% released_since(M,Y) <- movie M was released after year X
released_since(M,Y) :- movie(M,X), X>Y.
% released_between(M,Y1,Y2) <- movie M was released between year X and year Y inclusive
released_between(M,Y1,Y2) :- movie(M,Y), Y>=Y1, Y=<Y2.
% same_year_as(M1,M2) <- movie M1 was released in the same year as movie M2
same_year_as(M1,M2) :- movie(M1,Y), movie(M2,Y), M1\=M2.
% newer(M1,M2) <- movie M1 was released after movie M2
newer(M1,M2) :- movie(M1,Y1), movie(M2,Y2), Y1>Y2.
% cast_member(A,M) <- person A was an actor or actress in movie M
% (Give as a two predicates)
cast_member(A,M) :- actor(M,A,_).
cast_member(A,M) :- actress(M,A,_).
% cast_member2(A,M) <- person A was an actor or actress in movie M
% (Give as a single predicate using the ; disjunction operator)
cast_member2(A,M) :- actor(M,A,_) ; actress(M,A,_).
% directed_by(X,Y) <- person X has been in a movie directed by Y
% (Hint: re-use your cast_member/2 predicate)
directed_by(X,Y) :- director(M,Y), cast_member(X,M).
%%% Q3 %%%
% What's the difference between these queries?
% ?- actor(M1,D,_),actor(M2,D,_). -- returns every actor as M1 and M2 are not necessarily different
% ?- actor(M1,D,_),actor(M2,D,_),M1\=M2. -- succeeds twice for every pair of different movies
% ?- actor(M1,D,_),actor(M2,D,_),M1@<M2. -- succeeds once for every pair of different movies
%%% Q4 %%%
% Why do these queries return answers multiple times?
% ?- director(_,D),actor(_,D,_).
% ?- director(_,D),actress(_,D,_).
% Answer: if D directed n movies and acted in m movies, the query succeeds n*m times.
% We will see later how to avoid this.
%%% List processing predicates %%%
%%% Q5 %%%
% element(X,Ys) <- X is an element of the list Ys
element(X,[X|Ys]).
element(X,[_|Ys]) :-
element(X,Ys).
% remove_one(X,Ys,Zs) <- list Zs is list Ys without one occurrence of X
remove_one(X,[X|Ys],Ys).
remove_one(X,[Y|Ys],[Y|Zs]) :-
remove_one(X,Ys,Zs).
% remove_one2(X,Ys,Zs) <- list Zs is list Ys without one occurrence of X
% if it occurs in Ys, and Zs is Ys otherwise
% NB. Not entirely correct as it will also succeed if X occurs in Ys and Zs=Ys
remove_one2(X,[],[]).
remove_one2(X,[X|Ys],Ys).
remove_one2(X,[Y|Ys],[Y|Zs]) :-
remove_one2(X,Ys,Zs).
% remove_all(X,Ys,Zs) <- list Zs is list Ys without any occurrences of X
% NB. Not entirely correct as it will also succeed with some occurrences of X in Zs
remove_all(X,[],[]).
remove_all(X,[X|Ys],Zs) :-
remove_all(X,Ys,Zs).
remove_all(X,[Y|Ys],[Y|Zs]) :-
remove_all(X,Ys,Zs).
%%% Q6 %%%
% subset(Xs,Ys) <- every element of list Xs occurs in list Ys
subset([],_).
subset([X|Xs],Ys) :-
element(X,Ys),
subset(Xs,Ys).
% proper_subset(Xs,Ys) <- every element of list Xs occurs in list Ys, and
% Ys has at least one element more than Xs
proper_subset([],[_|_]).
proper_subset([X|Xs],Ys) :-
remove_one(X,Ys,Zs),
proper_subset(Xs,Zs).
% subset_ord(Xs,Ys) <- every element of list Xs occurs in the same order in list Ys
subset_ord([],_).
subset_ord([X|Xs],[X|Ys]) :-
subset_ord(Xs,Ys).
subset_ord(Xs,[_|Ys]) :-
subset_ord(Xs,Ys).
%%% Q7 %%%
% subseq1(Xs,Ys) <- every element of list Xs occurs in the same order and contiguously in list Ys
subseq1([],_).
subseq1([B|Bs],ABC) :-
append(_,BC,ABC),
append([B|Bs],_,BC).
% subseq2(Xs,Ys) <- every element of list Xs occurs in the same order and contiguously in list Ys
% NB. The first two clauses can be combined into subseq2(Xs,Ys) :- append(Xs,_,Ys)
% i.e., the original base case
subseq2([],_).
subseq2([X|Xs],Ys) :-
append([X|Xs],_,Ys).
subseq2([X|Xs],[_|Ys]) :-
subseq2([X|Xs],Ys).
%%% Pattern matching %%%
%%% Q8 %%%
diff(x,x,1).
diff(minus(U),x,minus(RU)) :- diff(U,x,RU).
diff(plus(U,V),x,plus(RU,RV)) :- diff(U,x,RU),diff(V,x,RV).
diff(minus(U,V),x,minus(RU,RV)) :- diff(U,x,RU),diff(V,x,RV).
diff(times(U,V),x,plus(times(U,RV),times(V,RU))) :- diff(U,x,RU),diff(V,x,RV).
%%% Q9 %%%
simp(times(U,1),V) :- simp(U,V).
simp(plus(U,0),V) :- simp(U,V).
simp(plus(U,U),times(2,V)) :- simp(U,V).
simp(minus(U,U),0).
% Some kind of base case is needed; multiple solutions could be avoided by demanding that U is atomic
simp(U,U).
% Keep top-level the same, simplify at lower level
simp(plus(U,X),plus(V,Y)) :- simp(U,V),simp(X,Y).