diff options
author | Ben Sima <ben@bsima.me> | 2019-03-23 23:58:26 -0700 |
---|---|---|
committer | Ben Sima <ben@bsima.me> | 2019-03-23 23:58:26 -0700 |
commit | f50cecf2cb77cc073cb86a6016468a09d1c49fb0 (patch) | |
tree | 1ca9eda0a93a2e04e2dc44df8fc5113375a72c3d /lore/sicp/set.scm | |
parent | 5d4e34f146a358041099299d2f86a546eed25dea (diff) |
Add semi-working bs
Diffstat (limited to 'lore/sicp/set.scm')
-rw-r--r-- | lore/sicp/set.scm | 42 |
1 files changed, 42 insertions, 0 deletions
diff --git a/lore/sicp/set.scm b/lore/sicp/set.scm new file mode 100644 index 0000000..3d60c5c --- /dev/null +++ b/lore/sicp/set.scm @@ -0,0 +1,42 @@ +;; A set module, based on binary trees (from sicp) + +(define (entry tree) (car tree)) +(define (left-branch tree) (cadr tree)) +(define (right-branch tree) (caddr tree)) + +(define (make-tree entry left right) + (list entry left right)) + +(define (element-of-set? x set) + (cond ((null? set) #f) + ((= x (entry set)) #t) + ((< x (entry set)) + (element-of-set? x (left-branch set))) + ((> x (entry set)) + (element-of-set? x (right-branch set))))) + +(define (adjoin-set x set) + (cond ((null? set) (make-tree x '() '())) + ((= x (entry set)) set) + ((< x (entry set)) + (make-tree (entry set) + (adjoin-set x (left-branch set)) + (right-branch set))) + ((> x (entry set)) + (make-tree (entry set) + (left-branch set) + (adjoin-set x (right-branch 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))))))) |