24 lines
635 B
Scheme
24 lines
635 B
Scheme
#lang sicp
|
|
|
|
; element-of-set? is the exact same
|
|
; O(n)
|
|
(define (element-of-set? x set)
|
|
(cond ((null? set) false)
|
|
((equal? x (car set)) true)
|
|
(else (element-of-set? x (cdr set)))))
|
|
|
|
; O(1)
|
|
(define (adjoin-set x set)
|
|
(cons x set)) ; we don't have to check anymore
|
|
|
|
; O(n), where n is the length of set1
|
|
(define (union-set set1 set2)
|
|
(append set1 set2))
|
|
|
|
; intersection-set can still be the exact same
|
|
; O(n^2)
|
|
(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))))
|