如果原子在列表中返回True的LISP函數

Question

我試圖編寫一個函數（deep-find），該函數接受列表和另一個參數，並返回T，如果該參數存在於列表中。例如，如果我調用(deep-find '(A B (C D)) 'C)它應該返回true，但如果我調用(deep-find '(A B (C D)) 'F)它應該返回false。這裏是我到目前爲止的代碼，但它返回零每次：

(defun deep-find (L n) 
    (cond 
    ((null L) nil) 
    ((equal n (car L)) t) 
    ((deep-find (cdr L) n)))) 

Answer 1

您的代碼不NIL每次返回;它適用於簡單的列表。例如，(deep-find '(A B (C D)) 'A)應該返回T。

您的cond有三種情況：列表結束，列表頭部檢查和列表尾部檢查。但是，樹木沒有任何意義。所以，你需要一個遞歸到樹的更深層次的樹的一個分支的情況下，另一種情況：

(defun deep-find (L n) 
    (cond 
    ((null L) nil) 
    ((equal n (car L)) t) 
    ((listp (car L))    ; in case of a branch, 
    (or (deep-find (car L) n) ; check the branch, 
     (deep-find (cdr L) n))) ; and check rest of the list 
    ((deep-find (cdr L) n)))) 

Answer 2

另一種方式，

(defun deep-see (lis arg) 
(let ((result)) 
    (cond 
    ((not (null lis)) 
    (loop for item in lis do 
    (cond 
     ((not (equal item arg)) 
     (cond ((listp item) (setf result (deep-see item arg))))) 
     ((equal item arg) (setf result t)))))) 
    result)) 

用法：(deep-see '(a v c (e (c (((d)))) f)) 'd) => T

(deep-see '(a v c (e (c (((d e)))) f)) '(d e)) => T

Answer 3

你調用的是一個二叉樹。在Common Lisp列表中定義爲頭部和尾部，而樹由car和cdr組成，它們是節點的子節點。請注意，該列表是樹的特例。

Common Lisp中提供了負責遍歷樹幾個功能：

• ＃ 'SUBST
• ＃' SUBST-如果
• ＃'等於樹

它們是當量爲功能在列表上：

• ＃'sub stitute
• ＃ '代替，如果
• ＃' 等於

這裏：http://lisptips.com/post/43404489000/the-tree-walkers-of-cl你會發現原來的提示。據此，以下代碼可能會解決您的問題：

(defun deep-find (lst elt) 
    (prog1 nil 
    (subst-if t (constantly nil) lst 
       :key (lambda (x) 
        (when (eql elt x) 
         (return-from deep-find t)))))) 

Answer 4

如果您添加更多的靈活性，有時這類問題會變得更加容易。

例如考慮通用二進制樹，而不是隻列表（即是二進制樹的特定子的情況下），並假設爲(deep-find 'a 'a)正確的答案應該是T的代碼變得更短，更優雅：

(defun deep-find (tree item) 
    (or (equal tree item) 
     (and (consp tree) 
      (or (deep-find (car tree) item) 
       (deep-find (cdr tree) item)))))