2.3.3 Example: Representing Sets

SICP

http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-16.html#%_sec_2.3.3


集合の操作として、

  • 順序づけられていない集合の場合
  • 順序づけた集合の場合
  • Binary Treeとして現した場合

の三種類がでてくるとこ。


問題自体も大して難しくなく、全体的にスルーしてもいいかなぁ、という印象。

問題2.59

union-set(和集合)

(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))))
問題2.60

重複するリストの場合のそれぞれの操作。

(define adjoin-set cons)
(define union-set append)

効率は、より長いリストを操作するので悪くなる。
重複リストが優位な応用って何だろう？？？ でも、実際の現場では重複していることの方が多いか。

問題2.61

順序づけされたリストのadjoin-set

(define (adjoin-set x set)
  (cond ((null? set) (list x))
	     ((= x (car set)) set)
	     ((< x (car set)) (cons x set))
	     (else (cons (car set) (adjoin-set x (cdr set))))))
問題2.62

順序づけられたリストのunion-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)))
			    ((< x2 x1)
		             (cons x2 (union-set set1 (cdr set2)))))))))
問題2.63

a. 同じ結果になる。
b. tree->list1はリストの連結にappendを使用しているため、appendの操作にO(n)の計算量が余計に必要となる。

問題2.64

a. リストを真ん中の要素で半分に分割する。右側の先頭値をBinary Treeの先頭とし、左側と右側のリストをそれぞれ再帰的にBinary Treeに変換する。
b. O(n)でいいのかな。

問題2.65

Binary Tree版のunion-setとintersection-set。Binary Treeをリストに変換して、リスト操作をして、リストをBinary Treeに変換する。

(define (union-set set1 set2)
  (list->tree (union (tree->list set1) (tree->list set2)))
  (define (union l1 l2)
	(cond ((null? l1) l2)
		   ((null? l2) l1)
		   (else
		     (let ((h1 (car l1))
			     (h2 (car l2)))
			 (cond ((= h1 h2) (cons h1 (union (cdr l1) (cdr l2))))
				    ((< h1 h2) (cons h1 (union (cdr l1) l2)))
				    ((< h2 h1) (cons h2 (union l1 (cdr l2))))))))))

(define (intersection-set set1 set2)
  (list->tree (intsersection (tree->list set1) (tree->list set2)))
  (define (intersection l1 l2)
	(cond ((null? l1) l2)
		   ((null? l2) l1)
		   (else
		     (let ((h1 (car l1))
			     (h2 (car l2)))
			 (cond ((= h1 h2) (cons h1 (intersection (cdr l1) (cdr l2))))
				    ((< h1 h2) (intersection (cdr l1) l2))
				    ((< h2 h1) (intersection l1 (cdr l2)))))))))
問題2.66

レコードになっている場合のlookup.

(define (lookup given-key set-of-records)
  (cond ((null? set-of-records) #f)
	     ((= given-key (key (entry set-of-records)))
	       (entry (set-of-records)))
	     ((< given-key (key (entry set-of-records)))
	       (element-of-set? given-key (left-branch set-of-records)))
             ((> given-key (key (entry set-of-records)))
		(element-of-set? given-key (right-branch set-of-records)))))