76 lines
2.2 KiB
Racket
76 lines
2.2 KiB
Racket
#lang sicp
|
|
|
|
|
|
;;(define (element-of-set? x set)
|
|
;; (cond ((null? set) false)
|
|
;; ((equal? x (car set)) true)
|
|
;; (else (element-of-set? x (cdr set)))))
|
|
|
|
;;(define (adjoin-set x set)
|
|
;; (if (element-of-set? x set)
|
|
;; set
|
|
;; (cons x set)))
|
|
|
|
;;(define (intersection-set set1 set2)
|
|
;; (cond ((or (null? set1) (null? set2)) '())
|
|
;; ((element-of-set? (car set1) set2)
|
|
;; (cons (car set1)
|
|
;; (intersection-set (cdr set1) set2)))
|
|
;; (else (intersection-set (cdr set1) set2))))
|
|
|
|
|
|
;;(define (union-set set1 set2)
|
|
;; (cond ((null? set1) set2)
|
|
;; ((null? set2) set1)
|
|
;; ((not (element-of-set? (car set1) set2))
|
|
;; (cons (car set1) (union-set (cdr set1) set2)))
|
|
;; (else (union-set (cdr set1) set2))))
|
|
|
|
;; With duplicates
|
|
|
|
;;(define (adjoin-set x set) (cons x set))
|
|
|
|
;;(define (union-set set1 set2) (append set1 set2))
|
|
|
|
;; Efficiency is dependent on the number duplicates in the underlying list
|
|
;; This increases with each operation. For smaller numbers of duplicates
|
|
;; adjoin and union should be much cheaper than the no-duplicate versions.
|
|
|
|
;; ORDERED
|
|
|
|
(define (element-of-set? x set)
|
|
(cond ((null? set) false)
|
|
((= x (car set)) true)
|
|
((< x (car set)) false)
|
|
(else (element-of-set? x (cdr set)))))
|
|
|
|
(define (intersection-set set1 set2)
|
|
(if (or (null? set1) (null? set2))
|
|
'()
|
|
(let ((x1 (car set1)) (x2 (car set2)))
|
|
(cond ((= x1 x2)
|
|
(cons x1
|
|
(intersection-set (cdr set1)
|
|
(cdr set2))))
|
|
((< x1 x2)
|
|
(intersection-set (cdr set1) set2))
|
|
((< x2 x1)
|
|
(intersection-set set1 (cdr set2)))))))
|
|
|
|
(define (adjoin-set x set)
|
|
(cond ((null? set) (list x))
|
|
((equal? x (car set)) set)
|
|
((< x (car set)) (cons x set))
|
|
(else (adjoin-set x (cdr set)))))
|
|
|
|
(define (union-set set1 set2)
|
|
(cond ((null? set1) set2)
|
|
((null? set2) set1)
|
|
(else
|
|
(let ((x1 (car set1))
|
|
(x2 (car set2)))
|
|
(cond ((= x1 x2) (cons x1 (union-set (cdr set1) (cdr set2))))
|
|
((< x1 x2) (cons x1 (union-set (cdr set1) set2)))
|
|
(else (cons x2 (union-set set1 (cdr set2)))))))))
|
|
|