►zthomae’s SICP solutions
▼2 Chapter 2
2.1 Exercise 2.1
2.2 Exercise 2.2
2.3 Exercise 2.3
2.4 Exercise 2.4
2.5 Exercise 2.5
2.6 Exercise 2.6
2.7 Exercise 2.7
2.8 Exercise 2.8
2.9 Exercise 2.9
2.10 Exercise 2.10
2.11 Exercise 2.11
2.12 Exercise 2.12
2.13 Exercise 2.13
2.14 Exercise 2.14
2.15 Exercise 2.15
2.16 Exercise 2.16
2.17 Exercise 2.17
2.18 Exercise 2.18
2.19 Exercise 2.19
2.20 Exercise 2.20
2.21 Exercise 2.21
2.22 Exercise 2.22
2.23 Exercise 2.23
2.24 Exercise 2.24
2.25 Exercise 2.25
2.26 Exercise 2.26
2.27 Exercise 2.27
2.28 Exercise 2.28
2.29 Exercise 2.29
2.30 Exercise 2.30
2.31 Exercise 2.31
2.32 Exercise 2.32
2.33 Exercise 2.33
2.34 Exercise 2.34
2.35 Exercise 2.35
2.36 Exercise 2.36
2.37 Exercise 2.37
2.38 Exercise 2.38
2.39 Exercise 2.39
2.40 Exercise 2.40
2.41 Exercise 2.41
2.42 Exercise 2.42
2.43 Exercise 2.43
2.44 Exercise 2.44
2.45 Exercise 2.45
2.46 Exercise 2.46
2.47 Exercise 2.47
2.48 Exercise 2.48
2.49 Exercise 2.49
2.50 Exercise 2.50
2.51 Exercise 2.51
2.52 Exercise 2.52
2.53 Exercise 2.53
2.54 Exercise 2.54
2.55 Exercise 2.55
2.56 Exercise 2.56
2.57 Exercise 2.57
2.58 Exercise 2.58
2.59 Exercise 2.59
2.60 Exercise 2.60
2.61 Exercise 2.61
2.62 Exercise 2.62
2.63 Exercise 2.63
2.64 Exercise 2.64
2.65 Exercise 2.65
2.66 Exercise 2.66
2.67 Exercise 2.67
2.68 Exercise 2.68
2.69 Exercise 2.69
2.70 Exercise 2.70
2.71 Exercise 2.71
2.72 Exercise 2.72
2.73 Exercise 2.73
2.74 Exercise 2.74
2.75 Exercise 2.75
2.76 Exercise 2.76
2.77 Exercise 2.77
2.78 Exercise 2.78
2.79 Exercise 2.79
2.80 Exercise 2.80
2.81 Exercise 2.81
2.82 Exercise 2.82
2.83 Exercise 2.83
2.84 Exercise 2.84
2.85 Exercise 2.85
2.86 Exercise 2.86
2.87 Exercise 2.87
2.88 Exercise 2.88
2.89 Exercise 2.89
2.90 Exercise 2.90
2.91 Exercise 2.91
2.92 Exercise 2.92
2.93 Exercise 2.93
2.94 Exercise 2.94
2.95 Exercise 2.95
2.96 Exercise 2.96
2.97 Exercise 2.97
    ← prev  up  next → 

2.64 Exercise 2.64

NOTE: This is not quite going to be in the form of a "short paragraph". I hope you understand.

We are asked to explain how the following procedure partial-tree works:

(define (partial-tree elts n)
  (if (= n 0)
      (cons '() elts)
      (let ((left-size (quotient (- n 1) 2)))
        (let ((left-result (partial-tree elts left-size)))
          (let ((left-tree (car left-result))
                (non-left-elts (cdr left-result))
                (right-size (- n (+ left-size 1))))
            (let ((this-entry (car non-left-elts))
                  (right-result (partial-tree (cdr non-left-elts)
                                              right-size)))
              (let ((right-tree (car right-result))
                    (remaining-elts (cdr right-result)))
                (cons (make-tree this-entry left-tree right-tree)
                      remaining-elts))))))))

Before beginning, I would first reformat the procedure using a form we haven’t learned yet, let*, which allows for earlier bindings available to later ones. This removes the need for the creeping indentation we see above.

(define (partial-tree elts n)
  (if (= n 0)
      (cons '() elts)
      (let* ((left-size (quotient (- n 1) 2))
             (left-result (partial-tree elts left-size))
             (left-tree (car left-result))
             (non-left-elts (cdr left-result))
             (right-size (- n (+ left-size 1)))
             (this-entry (car non-left-elts))
             (right-result (partial-tree (cdr non-left-elts) right-size))
             (right-tree (car right-result))
             (remaining-elts (cdr right-result)))
        (cons (make-tree this-entry left-tree right-tree) remaining-elts))))

This procedure is more involved than most we’ve worked with so far, but if we break down what every definition is computing, we can piece together what the procedure is doing fairly easily. We’ll do it line-by-line.

(if (= n 0)

...)

This sets up the base case of the procedure, which is clearly going to be recursive. We can look at the way partial-tree is called to understand what the base case means:

(define (list->tree elements)
(car (partial-tree elements (length elements))))

So n is the number of elements that this call of partial-tree is going to process. If there are none left, then we evaluate

(cons '() elts)

and return an empty list (meaning an empty tree – there are no elements left to add) paired with the elts we passed to partial-tree.

(let* ((left-size (quotient (- n 1) 2))

...))

This sets up the general case. It exists inside a let* form (or the first of quite a few regular lets in the original), giving us a scope to define values that we will use to get our result. The first of these is left-size, which is (n - 1) / 2. We’ll see why we subtract 1 later; for now, just understand that this is our value called left-size.

(left-result (partial-tree elts left-size))

The value left-result is given the meaning of the tree representation of left-size elements from elts. Instead of creating a sublist with just this many elements, we use the n argument in partial-tree to regulate how many elements are taken in all of the recursive calls (as seen here – we’re only turning the first half of the list into a tree).

(left-tree (car left-result))
(non-left-elts (cdr left-result))

We know that partial-tree, in the base case, returns a pair consisting of an empty list and the elements passed to it that weren’t used in that base case. This confirms that, in general, the car of the pair is the generated tree (which in the base case is empty) and the cdr is the remaining elements (which in the base case is all of them).

Can we be sure that non-left-elts will contain the elements not used in the left side of the tree? We can start to imagine why this might be correct with a case where n is equal to 1. Clearly, left-size will be 0, making left-result an empty list, left-tree an empty tree, and non-left-elts contain all of our original elements, none of which are in left-tree. The reasons for this behavior will become clearer in a moment, but it is at least plausible that this works.

(right-size (- n (+ left-size 1)))

This is similar to left-size, and is probably the number of elements that are going to be in the right-side tree. And again, we see that the size is not equal to n minus left-size, but is one less than that. In other words, left-size and right-size, moving inward, leave one element in the middle of the list. And what is this used for? We can see in the next line:

(this-entry (car non-left-elts))

We assign the first element in non-left-elts to a new value, this-entry. It is reasonable to suspect that this is going to be the root of the tree. This makes it obvious why the sizes of the left and right branches leave space for one more element – of course the root element of a tree can’t be in either of its subtrees. This is what happens to the first element of elts in the case considered above, where n is 1 – exactly as we would expect.

(right-result (partial-tree (cdr non-left-elts) right-size))

This computes the right side of the tree, using right-size and the elements of non-left-elts following the root of the tree.

(right-tree (car right-result))
(remaining-elts (cdr right-result))

These correspond to the definitions earlier, getting the computed tree and the elements not used it in from the pair produced by partial-tree.

Having now processed all of the bindings in the let* expression, we only have the body of the procedure left:

(cons (make-tree this-entry left-tree right-tree) remaining-elts)

This is just the general case of the result we saw earlier in the base case, and have used twice in the procedure so far. By this time, it should be clear how it works.

Evaluating list->tree on the given list, we get the following tree:

(5

(1 ()

(3 () ()))

(9 (7 () ())

(11 () ())))

Or, in a particularly bad graphical style,

5

|- 1

|  |- 3

|  |-

|

|- 9

|- 7

|- 11

***

Now that we understand how the procedure works, what is the order of growth in time complexity? Actually, it’s rather easy. Even though we have recursive calls to partial-tree, we are careful to only visit every element of the list once. Once elements are added to a tree, they are never visited again, and elements that haven’t been added to the tree yet are not visited until they are explicitly added to it. And elements are added to the tree with an O(1) cons. Therefore, the procedure has an order of growth in execution time of O(N).

    ← prev  up  next →