計算機プログラムの構造と解釈 第二版 P91 問題2.62

問題が単純に書かれ過ぎているし、θ(n)でとか書かれると一瞬ひるむが、
要は今までの流れで問題を解けば良いのだなと思う。
もうちょっというと、p90のintersection-setをパクれば良い。
実装には他の順序づけされた実装も書いておく。
大体にたようなパターンだよね。

実装

#!/usr/local/bin/gosh
;; -*- coding: utf-8 -*-

(use ggc.debug.trace)
(use math.mt-random)


(define nil '())

(define (element-of-set? x set)
  (cond ((null? set) #f) 
        ((= x (car set)) #t) 
        ((< x (car set)) #f) 
        (else (element-of-set? x (cdr set)))))


(define (adjoin-set x set)
  (cond ((null? set) (cons x nil))
        ((= x (car set)) set)
        ((< x (car set)) (cons x set))
        (else (cons (car set) (adjoin-set x (cdr set))))))


(define (intersection-set set1 set2)
  (if (or (null? set1) (null? set2))
    nil 
    (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 (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)))
                  ((< x2 x1) (cons x2 (union-set set1 (cdr set2)))))))))


(define set1 '(1 2 3 4 5))
(define set2 '(2 3 4 6 7))

;; main
(define (main args)

  (display "set1: ")
  (display set1)
  (newline)
  (display "set2: ")
  (display set2)
  (newline)

  (display "(union-set set1 set2): ")
  (display (union-set set1 set2))
  (newline)

  (display "(union-set set2 set1): ")
  (display (union-set set2 set1))
  (newline)


  (trace union-set)
  (display (union-set set2 set1))
  (newline)


  0)

実行

set1: (1 2 3 4 5)
set2: (2 3 4 6 7)
(union-set set1 set2): (1 2 3 4 5 6 7)
(union-set set2 set1): (1 2 3 4 5 6 7)
0:(union-set (2 3 4 6 7) (1 2 3 4 5))
1:  (union-set (2 3 4 6 7) (2 3 4 5))
2:    (union-set (3 4 6 7) (3 4 5))
3:      (union-set (4 6 7) (4 5))
4:        (union-set (6 7) (5))
5:          (union-set (6 7) ())
            ->(6 7)
          ->(5 6 7)
        ->(4 5 6 7)
      ->(3 4 5 6 7)
    ->(2 3 4 5 6 7)
  ->(1 2 3 4 5 6 7)
; trace: union-set has been called 6 times.
(1 2 3 4 5 6 7)

union-setを6回よんでる。できてそうだ。