EoPL reading (12) 1.2.4 Exercises

scheme EoPL

Exercise 1.17-1

二分探索木を parse するナニ。最初、ついクセで cdr 使ってしまった。REPL で色々確認。

gosh> (define l '(14 (7 () (12 () ()))
                     (26 (20 (17 () ())
                             ())
                         (31 () ())))) 
l
gosh> l
(14 (7 () (12 () ())) (26 (20 (17 () ()) ()) (31 () ())))
gosh> (car l)
14
gosh> (cadr l)
(7 () (12 () ()))
gosh> (cddr l)
((26 (20 (17 () ()) ()) (31 () ())))
gosh> (caddr l)
(26 (20 (17 () ()) ()) (31 () ()))
gosh>

ええと左の部分木は cadr で右の部分木は caddr で良い?
で、以下な実装。

(define (path n bst)
  (define (path-inner rslt l)
    (cond ((equal? n (car l)) rslt)
	  ((< n (car l))
	   (path-inner (cons 'left rslt) (cadr l)))
	  ((> n (car l))
	   (path-inner (cons 'right rslt) (caddr l))))
    )
  (path-inner '() bst)
  )

試験してみたら以下。

$ make
Testing path ...                                                 failed.
discrepancies found.  Errors are:
test (path 17 '(14 (7 () (12 () ()))
                      (26 (20 (17 () ())
                              ())
                          (31 () ())))) should return (right left left): expects (right left left) => got (left left right)
$

とほほ。cons してるから逆に積まれるのか。これって再起でナニするとどうなるんかな。

(define (path n bst)
  (cond ((equal? n (car bst)) '())
	((< n (car bst))
	 (cons 'left (path n (cadr bst))))
	((> n (car bst))
	 (cons 'right (path n (caddr bst)))))
  )

こっちの方が簡潔ですな。ちなみに繰り返し版が以下。

(define (path n bst)
  (define (path-inner rslt l)
    (cond ((equal? n (car l)) (reverse rslt))
	  ((< n (car l))
	   (path-inner (cons 'left rslt) (cadr l)))
	  ((> n (car l))
	   (path-inner (cons 'right rslt) (caddr l))))
    )
  (path-inner '() bst)
  )

reverse してます。微妙。