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

Question

アイテムがツリーにあるかどうかをチェックする関数を書かなければなりません。

例えば：

(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

Lispでの引用:

最後に、フラット リストだけでなくツリーでも機能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))

使用法：

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"

リスト、ツリー、再帰関数、および再帰検索については、SICP、On Lisp、およびPAIPで詳しく知ることができます。

---

これらの関数が末尾再帰であるかどうかという問題もあります。このような問題は、リストされている書籍でも説明されています。