Exercise 2.30 -- 2.32

Exercise 2.30

Define a procedure square-tree analogous to the square-list procedure of Exercise 2.21. That is, square-tree should behave as follows:

(square-tree
 (list 1
       (list 2 (list 3 4) 5)
       (list 6 7)))
; (1 (4 (9 16) 25) (36 49))

Solution

(define (square-tree tree)
    (map (lambda (subtree)
             (if (pair? subtree)
                 (square-tree subtree)
                 (square subtree)))
         tree))

Exercise 2.31

Abstract your answer to Exercise 2.30 to produce a procedure tree-map with the property that square-tree could be define as

(define (square-tree tree) (tree-map square tree)

Solution

(define (tree-map proc tree)
    (map (lambda (subtree)
             (if (pair? subtree)
                 (tree-map proc subtree)
                 (proc subtree)))
         tree))

Exercise 2.32

We can represent a set as a list of distinct elements, and we can represent the set of all subsets of the set as a list of lists. For example, if the set is (1 2 3), then the set of all subsets is

(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3))

Complete the following definition of a procedure that generates the set of subsets of a set and give a clear explanation of why it works:

(define (subsets s)
    (if (null? s)
        (list nil)
        (let ((rest (subset (cdr s))))
             (append rest (map ?? rest)))))

Solution

(define (subset s)
    (if (null? s)
        (list '())
        (let ((rest (subset (cdr s))))
             (append rest (map (lambda (ls) (cons (car s) ls))
                               rest)))))

Start with a collection containing only the empty set ('()) we extend the collection by firstly including all set perviously in the collection and then adding the sets created by adding an additional unique element to each of the sets already in the collection. To illustrate:

; starting with the empty set
(())

; collection extended by including the new set (3),
; created by adding 3 to the empty
(() (3))

; extend the old collection by including the sets created
; by adding the new element, 2, to existing sets
(() (3) (2) (3 2))

...