Homework 7 Solution

Submission: along with the usual paper submission at the beginning of the class, also send an email to cs326@cse.unr.edu containing:

• subject: HW 7
• message body: your name
• attachment: the electronic version of your code (only one file with all predicates); the file must be able to load and be tested in the interpretor

For all problems below, you only need to make sure that the predicates correctly find the first solution, as in the examples provided. You do NOT need to worry about what happens when asking for more solutions (with “;”).

1. (56 pts) Consider an implementation of sets with Prolog lists. A set is an unordered collection of elements, without duplicates.

1. (14 pts) Write the rules for a predicate isSet(S), which succeeds if the list S is a set. The following queries show examples of using this predicate:

?- isSet([1,2,5]). Yes

?- isSet([1,2,1,5]). No

1. (14 pts) Write the rules for a predicate subset(A,S), which succeeds if the set A is a subset of the set S. The following query shows an example of using this predicate:

?- subset([2,5], [1,5,3,2]). Yes

1. (14 pts) Write the rules for a predicate union(A,B,C), which succeeds if the union of sets A and B is the set C. The following query shows an example of using this predicate:

?- union([2,5,4], [1,5,3,2], C). C = [4,1,5,3,2]

1. (14 pts) Write the rules for a predicate intersection(A,B,C), which succeeds if the intersection of sets A and B is the set C. The following query shows an example of using this predicate:

?- intersection([2,5,4], [1,5,3,2], C). C = [2,5]

1. (14 pts) Write the rules for a predicate tally(E,L,N), which succeeds if N is the number of occurrences of element E in list L. The following query shows an example of using this predicate:

?- tally(3, [1,2,3,1,2,3], N). N = 2

1. (15 pts) Write the rules for a predicate subst(X,Y,L,L1), which succeeds if list L1 is identical to list L except that all occurrences of X in L are replaced with Y in L1. The following query shows an example of using this predicate:

?- subst(1, 2, [1,2,3,1,2,3], L1).

L1 = [2,2,3,2,2,3]

1. (15 pts) Write the rules for a predicate insert(X,L,L1), which succeeds if list L1 is identical to the sorted list L with X inserted at the correct place. Assume that L is already sorted. The following query shows an example of using this predicate:

?- insert(5, [1,3,4,7], L1).

L1 = [1,3,4,5,7]

1. (Extra Credit - 10 pts) Write the rules for a predicate flatten(A,B), which succeeds if A is a list (possibly containing sublists), and B is a list containing all elements in A and its sublists, but all at the same level. The following query shows an example of using this predicate:

?- flatten([1, [2, [3, 4]], 5], L). L = [1, 2, 3, 4, 5]