Chapter 2, Building Abstractions with Data

Section - 2.3 Symbolic Data

Exercise 2.60


Only changes are in adjoin-set and union-set. Procedure adjoin-set have $\theta(1)$ time complexity and procedure union-set have $\theta(n)$ time complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#lang sicp

(#%require (only racket/base error))

(define (adjoin-set x set)
  (cons x set)
)

(define (union-set set1 set2)
  (cond ((null? set1) set2)
        ((null? set2) set1)
        (else (append set1 set2))
  )
)  

Clearly the preferred places for this representation are those where it is required to collect/write/create the elements of the set most of the times and only rarely we check presence of element in the set.