CS 342		Additional Homework for Chapter 8	Due: April 10, 1992

General directions: be sure we have given you some specific help
(either in recitation or personally) with each problem
before solving these additional problems.

1.

2.

3. (To make up for problem 2 on page 404).
Before starting on this problem, be sure you understand the right answers
to problem 2 on page 404.

Suppose we represent binary trees in Prolog with terms that either have
the form emptyTree, (tree Leaf), or (tree Left Root Right).
The first is a constant, representing the empty tree,
the second represents a tree with no brances, and the third has two subtrees,
in Left and Right, and a value in Root.
For example, (tree (tree 3) 1 (tree 2)) represents a tree that
might be pictured as:

            1
           / \
          3   2

You are to program the following predicates on trees.
These do not have to be runnable "backwards" but only as specified
in the examples.

a. size, such that (size T N) is true if the tree T has size N.
For example, (infer? (size (tree (tree 3) 1 (tree 2)) 3)) should be satisfied,
and (infer? (size emptyTree N) (print N)) should print 0.

b. depth, such that (depth T N) is true if the tree T has depth N.
For example, (infer? (depth (tree emptyTree) N) (print N)) should print 0,
(infer? (depth (tree 3) N) (print N)) should print 1,
and (infer? (depth (tree (tree 3) 1 (tree 4)) N) (print N)) should print 2.

c. remove, such that (remove T1 T2 T3) is true if T3 is formed from T1 by
removing the subtree T2.  For example,
(infer? (remove (tree (tree 3) 1 (tree 2)) (tree 2) Ans) (print Ans))
should print (tree (tree 3) 1 emptyTree),
(infer? (remove (tree (tree 3) 1 (tree 2)) (tree (tree 3) 1 (tree 2)) Ans)
        (print Ans))
should print emptyTree.

4. (To make up for problem 6 on page 404).
a. What is wrong with the following definition of a predicate
that is supposed to return a list of difference lists,
where the ith element of the result is a singleton difference list
containing the ith element of the argument?

	(infer (singletonize (diff Z Z) nil))
	(infer (singletonize (diff (cons X L) Z) (cons (diff (cons X Z) Z) M))
	  from (singletonize (diff L Z) M))

What we want singletonize to do is for the query
	(infer? (singletonize (diff (cons 1 (cons 2 X)) X) Ans) (print Ans))
to print
	(cons (diff (cons 1 Z1) Z1) (cons (diff (cons 2 Z2) Z2) nil))
or something similar, whereas it actually prints:
	(cons (diff (cons 1 X) X) (cons (diff (cons 2 X) X) nil))

b. Write a predicate, equal, such that (equal A B) is true if and only if
the terms A and B can be unified.
For example, (infer? (equal 1 1)) should be satisfied,
as should (infer? (equal (foo X) (foo 3))), but not (infer? (equal 3 1)).
Hint: there is a *very* simple solution to this problem.

c. Write a single clause version of diffaddtoend without using recursion
or calling diffappend.  For example, the query
	(infer?  (diffaddtoend (diff (cons 1 X) X) 2 M) (print M))
should print
	(diff (cons 1 (cons 2 Q1)) Q1)
	Satisfied

d. (extra credit only)
Compare the efficiency of the program you wrote for part c versus
the program in figure 8.4.  Which is faster?  Explain why.
(If you like, use as your measure of efficiency the number of
"logical inferences", that is, calls to clauses.)

5. (To make up for problem 7 on page 404)

Do parts (c) and (d) on page 404.