►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.65 Exercise 2.65

In exercises Exercise 2.63 and Exercise 2.64 we found O(N) algorithms for converting between ordered lists and balanced binary trees. We already have O(N) algorithms for computing the intersections and unions of sets represented as ordered lists. Therefore, we can find the intersections and unions of sets represented as binary trees in O(N) time by first converting from binary trees to lists, then finding the intersection or union of these lists, and finally converting the result back into a tree. As the sum of a fixed number of O(N) processes, this process is also O(N).

I use let* again for clarity. For the sake of avoiding name collisions, I’ve assumed that the intersection-set and union-set procedures for operating on ordered lists are actually suffixed with oset. This is ugly, but remember that it is ugly; we’ll be seeing how to deal with this sort of situation later.

First, I implemented the procedures in the naive way:

(define (intersection-btset set1 set2)
  (let* ((oset1 (tree->list-2 set1))
         (oset2 (tree->list-2 set2))
         (intersection (intersection-oset oset1 oset2)))
    (list->tree intersection)))
(define (union-btset set1 set2)
  (let* ((oset1 (tree->list-2 set1))
         (oset2 (tree->list-2 set2))
         (union (union-oset oset1 oset2)))
    (list->tree union)))

However, this is plainly duplicative. We can extract a new procedure, here named btset-convert-op (a name so bad it will not conflict with anything useful) that takes a procedure as an argument and returns a procedure taking two sets and returning that operation applied to them:

(define (btset-convert-op op)
  (lambda (set1 set2)
    (let* ((oset1 (tree->list-2 set1))
           (oset2 (tree->list-2 set2))
           (list-result (op oset1 oset2)))
      (list->tree list-result))))

Then, we can define our intersection and union procedures easily:

(define intersection-btset (btset-convert-op intersection-oset))
(define union-btset (btset-convert-op union-oset))

Assuming that operations will only take two arguments, I think this is good enough. It could reduce the duplication of tree->list-2 with a map, and applying the operation to this, but this code is more straightforward, and I think this is a win.

But unions and intersections of sets are not only useful as binary operations. There are two different ways to handle this. One is to make btset-convert-op take an arbitrary number of arguments, and process them using the techniques above. However, this means that operations have to handle arbitrary numbers of arguments as well. Another way to solve this problem, and I believe a better way, is to accumulate over all of the sets with the operation.

(define (btset-convert-op op)
  (lambda sets
    (let ((osets (map tree->list-2 sets)))
      (list->tree (accumulate op (car osets) (cdr osets))))))

Despite the naming conventions, I believe this is a reasonable answer.

TODO: I complain about the names. I should fix them.

    ← prev  up  next →