修正
SICPの 2.3.3 Example: Representing Sets あたりを Python でやってみた
scheme (original code)
Scheme(Gauche)でfalseとtrueを使うとエラーになるから、#fと#tに変えてやってみた
;2.3.3 Example: Representing Sets ;Sets as unordered lists (define (element-of-set? x set) ; (cond ((null? set) false) (cond ((null? set) #f) ; ((equal? x (car set)) true) ((equal? x (car set)) #t) (else (element-of-set? x (cdr set))))) ;test (element-of-set? 1 '(1 2 3));#t (element-of-set? 1 '(4 5 6));#f (element-of-set? 1 '(4 5 6 1));#t (define (adjoin-set x set) (if (element-of-set? x set) set (cons x set))) ;test (adjoin-set 1 '(1 2 3)) ;(1 2 3) (adjoin-set 1 '(4 5 6)) ;(1 4 5 6) (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)))) ;test (intersection-set '(1 2 3) '(4 5 6)) ;() (intersection-set '(1 2 3 4 5) '(1 2)) ;(1 2) (intersection-set '(4 5) '(4 5 6)) ;(4 5) ;Sets as ordered lists (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))))) ;test (element-of-set? 1 '(4 5 6)) ;#f (element-of-set? 5 '(4 5 6)) ;#t (element-of-set? 9 '(4 5 6)) ;#f (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))))))) ;test (intersection-set '(1 2 3) '(4 5 6)) ;() (intersection-set '(1 2 3 4 5) '(1 2)) ;(1 2) (intersection-set '(4 5) '(4 5 6)) ;(4 5) ;Sets as binary trees (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))))) ;test (element-of-set? 7 '(7 '('(3 '(1 5)) '(9 '11)))) ;#t (element-of-set? 3 '(3 '('(1) '(7 '(5 '(9 11)))))) ;#t (element-of-set? 5 '(5 '('(3 '1) '(9 '(7 11))))) ;#t
python
#2.3.3 Example: Representing Sets #Sets as unordered lists def element_of_set(x, set): if not set: return False if x == set[0]: return True else: return element_of_set(x, set[1:]) #test print element_of_set(1, [1,2,3]) #True print element_of_set(1, [4,5,6]) #False print element_of_set(1, [4,5,6,1]) #True def adjoin_set(x, set): if element_of_set(x, set): return set return [x] + set #test print adjoin_set(1, [1,2,3]) #[1, 2, 3] print adjoin_set(1, [4,5,6]) #[1, 4, 5, 6] def intersection_set(set1, set2): if not set1 or not set2: return [] if element_of_set(set1[0], set2): return [set1[0]] + intersection_set(set1[1:], set2) else: return intersection_set(set1[1:], set2) #test print intersection_set([1, 2, 3], [4, 5, 6]) #[] print intersection_set([1, 2, 3, 4, 5], [1, 2]) #[1, 2] print intersection_set([4, 5], [4, 5, 6]) #[4, 5] #Sets as ordered lists def element_of_set_q(x, set): if not set: return False if x == set[0]: return True if x < set[0]: return False else: return element_of_set_q(x, set[1:]) #test print element_of_set_q(1, [4,5,6]) #False print element_of_set_q(5, [4,5,6]) #True print element_of_set_q(9, [4,5,6]) #False def intersection_set(set1, set2): if not set1 or not set2: return [] x1 = set1[0] x2 = set2[0] if x1 == x2: return [x1] + intersection_set(set1[1:], set2[1:]) if x1 < x2: return intersection_set(set1[1:], set2) if x2 < x1: return intersection_set(set1, se2[1:]) #test print intersection_set([1,2,3], [4,5,6]) #[] print intersection_set([1,2,3,4,5], [1,2]) #[1, 2] print intersection_set([4,5], [4,5,6]) #[4, 5] #Sets as binary trees def entry(tree): return tree[0] def left_branch(tree): return tree[1] def right_branch(tree): return tree[2] def make_tree(entry, left, right): return [entry, left, right] def element_of_set_q(x, set): if not set: return False if x == entry(set): return True if x < entry(set): return element_of_set_q(x, left_branch(set)) if x > entry(set): return element_of_set_q(x, right_branch(set)) #test print element_of_set_q(7, [7, [[3, [1, 5]], [9,[11]]]]) #True print element_of_set_q(3, [3, [[1], [7, [5, [9, 11]]]]]) #True print element_of_set_q(5, [5, [[3,[1]], [9, [7, 11]]]]) #True