アイテムがツリー内にあるかどうかをチェックする関数を書く方法は？

Question

アイテムがツリー内にあるかどうかをチェックする関数を書く必要があります。例えば

：

On Lispを引用

(defun find-in-tree (item tree) 
    ...) 

(find-in-tree 2 '(1 (3 4 (2))) 2) ;; should give T 
(find-in-tree 2 '(1 (3 4))) ;; should give NIL 

Answer 1

：

最後に、rfind-if、樹木だけでなく、フラットなリスト上で動作find-ifの再帰バージョン考える：

(defun rfind-if (fn tree) 
    (if (atom tree) 
     (and (funcall fn tree) tree) 
     (or (rfind-if fn (car tree)) 
      (if (cdr tree) (rfind-if fn (cdr tree)))))) 

を

例はほとんどありません：

CL-USER> (find-if #'(lambda (x) (eq x 2)) '(1 (3 4 (2)))) ;; FIND-IF is the standard function 
NIL 
CL-USER> (rfind-if #'(lambda (x) (eq x 2)) '(1 (3 4 (2)))) 
2 
CL-USER> (rfind-if #'(lambda (x) (eq x 2)) '((1 (2) 3) (3 4))) 
2 
CL-USER> (rfind-if #'(lambda (x) (eq x 2)) '((1 3) (3 4))) 
NIL 
CL-USER> (rfind-if (fint #'numberp #'oddp) '(2 (3 4) 5)) 
3 

さて、findの再帰バージョン：

(defun find/tree (item tree &optional (test #'eq)) 
    (rfind-if #'(lambda (el) (funcall test el item)) tree)) 

使用法：あなたはSICPにリスト、木、再帰関数と再帰検索についての詳細を調べることができます

CL-USER> (find 2 '((1 (2) 3) (3 4))) ;; FIND is the standard function, again 
NIL 
CL-USER> (find/tree 2 '((1 (2) 3) (3 4))) 
2 
CL-USER> (find/tree "2" '((1 ("2") 3) (3 4))) 
NIL 
CL-USER> (find/tree "2" '((1 ("2") 3) (3 4)) #'equal) 
"2" 

、 On LispおよびPAIP。

---

これらの機能がテール再帰的であるかどうかという疑問もあります。このような問題については、上の書籍でも議論されています。