In this problem we further our study of deep recursion. We wish to define four deeply recursive procedures. The first two, subst-all and substq-all, have the following form:

(define subst-all

(lambda (new old list)

...))

and

(define substq-all

(lambda (new old list)

...))

These procedures should replace each occurence of the item old in list with the item new. subst-all should use equal? for comparisons while substq-all should use eq? for comparisons. This means that substq-all should be used in the case where new and old are only bound to symbols.

Some test forms might be:

(subst-all 'z 'a '(a (b (a c)) (a (d a))))

==> (z (b (z c)) (z (d z)))

(subst-all 0 '(1) '(((1) (0))))

==> ((0 (0)))

(subst-all 'one 'two '())

==> ()

The third function, insert-left-all, should have a similar form:

(define insert-left-all

(lambda (new old list)

...))

This function should insert the item new to the left of each occurrence of the item old in list. You may use the test forms:

(insert-left-all 'z 'a '(a ((b a) ((a (c))))))

==> (z a ((b z a) ((z a (c)))))

(insert-left-all 'z 'a '(((a))))

==> (((z a)))

(insert-left-all 'z 'a '())

==> ()

insert-left-all should use equal? for comparisons.

Finally, the fourth function, sum-all, should have the form:

(define sum-all

(lambda (n-tuple)

...))

This procedure should have an argument which is an n-tuple of numbers, however, such an n-tuple may contain items which are n-tuples, and so on. Try your function on the following forms:

(sum-all '((1 3) (5 7) (9 11))) ==> 36

(sum-all '(1 (3 (5 (7 (9)))))) ==> 25

(sum-all '()) ==> 0

Analyze the performance of your function sum-all.