Exercises

Write a procedure according to each of the specifications below. Try to do as many of them as possible. For each one, check that (whether) your solution works for various patterns of argument instantiation. Once you get used to list processing, you should not have any problems with 1--5, but 6 and 7 are a bit more difficult--treat them as a challenge!

1. union(A,B,C) where set C contains one copy each of the elements that are members of both set A and set B.
2. intersection(A,B,C) where set C is the intersection of sets A and B.
3. difference(A,B,C) where set C contains those members of set A which do not occur in set B.
4. subst(A,B,C,D) where list D is list C with element A substituted for all occurrences of element B.
5. equal(X,Y) if X and Y are the same set.
6. Trace the reverse procedure defined above. You will find that it is very inefficient, since conc is called once for every single element of the list. Try to define a reverse that doesn't use conc. Hint: define a ternary predicate, called as follows:

   reverse(X,Y) :- reverse0(X,[],Y).
   

7. nth(N,L,E) where E is the Nth element of list L.

   First assume N is represented in successor notation, i.e. s(s(s(0))). Once you have done this, you can try to write a version with ordinary Arabic numbers and arithmetic expressions. To do this, you need to know that instead of using =, you use a binary infix operator is (why is it not possible to use =?). Here is an example:

   ?- X is (5 + 7) - 2.
    
   X = 10 
   yes
   

   All variables in a complex arithmetic expression (e.g. (5+ 7) - 2)) must be bound when the goal is invoked. This means that is is strictly non-logical, and there will be problems with calling the ordinary number-version of nth with certain patterns of argument instantiation. You can find out more about arithmetics in Prolog in Arithmetics in unit More About Prolog.