- Write Prolog rules as described in the questions below. You may use any
Prolog builtin predicates. You may need to write auxiliary \helper" rules in
some cases.
Your code may be tested by an automated script, so be sure to do as follows:
Place all de nitions in a single le that can be read without error
by a Prolog interpreter. If you add comment lines, pre x them with a
% (prolog comment symbol)
Submit just this text le electronically as directed on the course
Study Desk page. (Do not submit a word processed or PDF le.)
Use the rule name and arguments exactly as speci ed.
Do NOT submit your test facts. Do not submit (say) a set of
parent facts that you used to test your work.
Questions
1. [2 marks] A Prolog knowledge base contains a set of facts:
parent(parent,child) describes biological parent{child relationships,
and partner(p1,p2 ) describes two adults (who may be married) who
have an intimate relationship and typically live in the same household.
Write the rule stepSibling(Child1,Child2) that is true if Child1 and
Child2 do not share any parents, but each have a parent who is a
partner of one of the other child's parents.
2. [2 marks] Write the rule uniq that collapses sequences of repeated
values in a list.
uniq(L1,L2) if L2 is equal to L1 except that sequences of more than
one occurrence of the same value in L1 are replaced by a single value.
For instance:
?- uniq([x,x,5,6,a,a,a,a,a,1,1],L).
L = [x, 5, 6, a, 1] .
1
3. [2 marks]Write the rule grab that splits a list into an initial list of one
or more repeated elements and the remainder of the list. grab(L,Init,Rest)
if every element of Init is the same, and L is the concatenation of Init
and Rest. For example:
?- grab([5,z,a],Init,Rest).
Init = [5],
Rest = [z, a].
?- grab([5,5,5,z,a],Init,Rest).
Init = [5, 5, 5],
Rest = [z, a].
4. [2 marks] Write the rule freq that counts occurrences of elements in
a sorted list. freq will produce a list of structures of form cnt(S,N)
where S is a list element, and N is the number of times it appears. For
example
?- freq([a],C).
C = [cnt(a, 1)].
?- freq([a,a],C).
C = [cnt(a, 2)].
?- freq([a,a,b,b,b,b,b,c,c,c],C).
C = [cnt(a, 2), cnt(b, 5), cnt(c, 3)].
5. [2 marks] A time, in hours and minutes, is described by the time
structure. For example, 9 hours and 33 minutes would be encoded as
time(9,33).
Write the rule tminus that subtracts two times.
tminus(T1,T2,T3) if T3 = T1 - T2.
You can assume that T2 T1. That is, your rule need only work
when T2 is the same time or earlier than T1. For instance:
?- tminus(time(12,30), time(8,15),D).
D = time(4, 15).
6. [2 marks] Write the rule join(Xs,Ys,Zs). If Xs and Ys are lists of
structures of the form pair(A,B), then Zs is a list of structures of
the form triple(A,B,C). An element appears in Zs for every possible
matching of an element from Xs, and an element from Ys, such that
the rst component of each pair has the same value. When a match
occurs, the triple contains the matching value, and the corresponding
second component from the two matching pairs.
Neither of the input lists are ordered (i.e. they are not sorted). There
can be more than one pair with the same key value in an input list.
There is no required order of elements in the output list.
2
For example:
?- join([pair(1,foo), pair(2,bar), pair(3,baz)], [pair(2,42),
pair(1,zap)],V).
V = [triple(1, foo, zap), triple(2, bar, 42)].
