scheme-interpreter-story/sets.scm

#lang racket

(provide sorted-list-insert intersects? intersection union subset-of?)

;; A set is represented by a sorted list of increasing integers

;; it may be more efficient to replace these with trees in future

(define (sorted-list-insert key x l)
  (if (null? l)
      (list x)
      (let ((x-k (key x))
	    (y (key (car l))))
	(cond ((<= x-k y) (cons x l))
	      ((> x-k y) (cons (car l) (sorted-list-insert key x (cdr l))))))))

(define (intersects? key s1 s2)
  (cond ((null? s1) #f)
        ((null? s2) #f)
        (else
         (let ((x (key (car s1)))
               (y (key (car s2))))
           (cond ((< x y) (intersects? key (cdr s1) s2))
                 ((= x y) #t)
                 ((> x y) (intersects? key s1 (cdr s2))))))))

(define (intersection key s1 s2)
  (cond ((null? s1) '())
        ((null? s2) '())
        (else
         (let ((x (key (car s1)))
               (y (key (car s2))))
           (cond ((< x y) (intersection key (cdr s1) s2))
                 ((= x y) (cons (car s1) (intersection key (cdr s1) (cdr s2))))
                 ((> x y) (intersection key s1 (cdr s2))))))))

(define (union key s1 s2)
  (cond ((null? s1) s2)
        ((null? s2) s1)
        (else
         (let ((x (key (car s1)))
               (y (key (car s2))))
           (cond ((< x y) (cons (car s1) (union key (cdr s1) s2)))
                 ((= x y) (cons (car s1) (union key (cdr s1) (cdr s2))))
                 ((> x y) (cons (car s2) (union key s1 (cdr s2)))))))))

(define (subset-of? key s1 s2)
  ;; s1 is a subset of s2?
  (cond ((null? s1) #t)
        ((null? s2) #f)
        (else
         (let ((x (key (car s1)))
               (y (key (car s2))))
           (cond ((< x y) #f)
                 ((= x y)
		  ;; NB. dont cdr s2 here in case of multiple occurences
		  (subset-of? key (cdr s1) s2))
                 ((> x y) (subset-of? key s1 (cdr s2))))))))