LISP 函数 Returns True If Atom Is In List

Question

我正在尝试编写一个函数（深度查找），它接受一个列表和另一个参数，如果列表中存在该参数，则 returns T。例如，如果我调用 (deep-find '(A B (C D)) 'C) 它应该 return 为真，但是如果我调用 (deep-find '(A B (C D)) 'F) 它应该 return 为假。这是我到目前为止的代码，但每次都是 return 零：

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

Answer 1

您的代码不会return NIL 每次；它适用于简单的列表。例如 (deep-find '(A B (C D)) 'A) returns T 应该是这样。

您的 cond 中有三种情况：列表结尾、列表头部检查和列表尾部检查。但是，其中没有关于 trees 的内容。因此，如果树中有分支，您需要另一个递归到树的更深层次的条件：

(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 中，列表被定义为 head 和 tail，而树由 car 和 cdr 组成，它们是节点的子节点。请注意，该列表是树的特例。

Common Lisp 提供了几个负责遍历树的函数：

#'替换
#'subst-if
#'等号树

它们等同于处理列表的函数：

#'替换
#'替换-if
#'等于

此处：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)))))

Answer 5

您可以简单地这样做：

(defun deep-find (expr list)
(cond 
    ((equal list expr) t)
    ((not (atom list)) 
        (or 
            (deep-find expr (car list))
            (deep-find expr (cdr list))
        )
    )
)

LISP 函数 Returns True If Atom Is In List

LISP Function that Returns True If Atom Is In List

lisp

recursion

list

common-lisp