Skip to main content
Code Review

Return to Question

added 10 characters in body; edited tags; edited title
Source Link
Jamal
Jamal
  • 35.2k
  • 13
  • 134
  • 238

Union-set intersection-set for a binary-tree implementation of sets [SICP ex. 2.65]

From SICP:

Exercise 2.65. UseExercise 2.65

Use the results of exercises 2.63 and 2.64 to give (n) implementations of union-set and intersection-set for sets implemented as (balanced) binary trees.41

I wrote the following answer:

(define (union-set a b)
  (define (rec set1 set2)
    (cond ((null? set1) set2)
          ((null? set2) set1)
          ((= (car set1) (car set2)) (cons (car set1) (union-set (cdr set1) (cdr set2))))
          ((> (car set1) (car set2)) (cons (car set1) (union-set (cdr set1) set2)))
          (else (cons (car set2) (rec set1 (cdr set2))))))
  (let ((ls-result (rec (tree->list a) (tree->list b))))
    (partial-tree ls-result (length ls-result))))

(define (intersection-set a b)
  (define (rec set1 set2)
    (cond ((or (null? set1) (null? set2)) '())
          ((= (car set1) (car set2)) (cons (car set1) (rec (cdr set1) (cdr set2))))
          ((> (car set1) (car set2)) (rec set1 (cdr set2)))
          ((> (car set2) (car set1)) (rec (cdr set1) set2))))
  (let ((ls-result (rec (tree->list a) (tree->list b))))
    (partial-tree ls-result (length ls-result))))

Is this answer ok? Could it be better?

Union-set intersection-set for a binary-tree implementation of sets [SICP ex. 2.65]

From SICP:

Exercise 2.65. Use the results of exercises 2.63 and 2.64 to give (n) implementations of union-set and intersection-set for sets implemented as (balanced) binary trees.41

I wrote the following answer:

(define (union-set a b)
  (define (rec set1 set2)
    (cond ((null? set1) set2)
          ((null? set2) set1)
          ((= (car set1) (car set2)) (cons (car set1) (union-set (cdr set1) (cdr set2))))
          ((> (car set1) (car set2)) (cons (car set1) (union-set (cdr set1) set2)))
          (else (cons (car set2) (rec set1 (cdr set2))))))
  (let ((ls-result (rec (tree->list a) (tree->list b))))
    (partial-tree ls-result (length ls-result))))

(define (intersection-set a b)
  (define (rec set1 set2)
    (cond ((or (null? set1) (null? set2)) '())
          ((= (car set1) (car set2)) (cons (car set1) (rec (cdr set1) (cdr set2))))
          ((> (car set1) (car set2)) (rec set1 (cdr set2)))
          ((> (car set2) (car set1)) (rec (cdr set1) set2))))
  (let ((ls-result (rec (tree->list a) (tree->list b))))
    (partial-tree ls-result (length ls-result))))

Is this answer ok? Could it be better?

Union-set intersection-set for a binary-tree implementation of sets

From SICP:

Exercise 2.65

Use the results of exercises 2.63 and 2.64 to give (n) implementations of union-set and intersection-set for sets implemented as (balanced) binary trees.41

I wrote the following answer:

(define (union-set a b)
  (define (rec set1 set2)
    (cond ((null? set1) set2)
          ((null? set2) set1)
          ((= (car set1) (car set2)) (cons (car set1) (union-set (cdr set1) (cdr set2))))
          ((> (car set1) (car set2)) (cons (car set1) (union-set (cdr set1) set2)))
          (else (cons (car set2) (rec set1 (cdr set2))))))
  (let ((ls-result (rec (tree->list a) (tree->list b))))
    (partial-tree ls-result (length ls-result))))

(define (intersection-set a b)
  (define (rec set1 set2)
    (cond ((or (null? set1) (null? set2)) '())
          ((= (car set1) (car set2)) (cons (car set1) (rec (cdr set1) (cdr set2))))
          ((> (car set1) (car set2)) (rec set1 (cdr set2)))
          ((> (car set2) (car set1)) (rec (cdr set1) set2))))
  (let ((ls-result (rec (tree->list a) (tree->list b))))
    (partial-tree ls-result (length ls-result))))

Is this answer ok? Could it be better?

Don't prefix question title with a tag
Link
edit approved Oct 15, 2011 at 14:10
MPelletier
edit approved Oct 15, 2011 at 14:10
MPelletier
  • 826
  • 3
  • 10
  • 22

(Scheme) [SICP ex. 2.65] union Union-set intersection-set for a binary-tree implementation of sets [SICP ex. 2.65]

Tweeted twitter.com/#!/StackCodeReview/status/61036396600770560
Source Link
jaresty
jaresty
  • 2.3k
  • 1
  • 25
  • 46

(Scheme) [SICP ex. 2.65] union-set intersection-set for a binary-tree implementation of sets

From SICP:

Exercise 2.65. Use the results of exercises 2.63 and 2.64 to give (n) implementations of union-set and intersection-set for sets implemented as (balanced) binary trees.41

I wrote the following answer:

(define (union-set a b)
  (define (rec set1 set2)
    (cond ((null? set1) set2)
          ((null? set2) set1)
          ((= (car set1) (car set2)) (cons (car set1) (union-set (cdr set1) (cdr set2))))
          ((> (car set1) (car set2)) (cons (car set1) (union-set (cdr set1) set2)))
          (else (cons (car set2) (rec set1 (cdr set2))))))
  (let ((ls-result (rec (tree->list a) (tree->list b))))
    (partial-tree ls-result (length ls-result))))

(define (intersection-set a b)
  (define (rec set1 set2)
    (cond ((or (null? set1) (null? set2)) '())
          ((= (car set1) (car set2)) (cons (car set1) (rec (cdr set1) (cdr set2))))
          ((> (car set1) (car set2)) (rec set1 (cdr set2)))
          ((> (car set2) (car set1)) (rec (cdr set1) set2))))
  (let ((ls-result (rec (tree->list a) (tree->list b))))
    (partial-tree ls-result (length ls-result))))

Is this answer ok? Could it be better?