Lisp 检查 n 树中的节点

Question

我有一个表示为非线性列表的 n 树。树表示为（root list_of_nodes_subtree1 ... list_of_nodes_subtreen）。我需要编写一个函数来测试特定节点是否属于 n 树，并且我必须使用映射函数。我猜正确的是 mapcar，但我不太确定。我试了好几次了，但是我对lambda函数不熟悉，我不确定我是否需要使用它们。

示例：对于表示为 (a (b (c)) (d) (e (f))) 且节点 e => true

的树

Answer 1

您可能需要一个带有两个参数的函数：一棵树和要查找的符号。它可以调用 mapcar，将树和 lambda 传递给它。 lambda 检查列表中的每个元素，如果它是一个符号，它就会求值（eq needle 元素），否则该元素必须是一个子树并且它会递归。根据这个结果，它调用 reduce 将布尔值列表转换为单个值。类似于：

;; Look for NEEDLE in TREE.  NEEDLE should be a symbol.  TREE should
;; be a list of symbols or subtrees.  Return t if NEEDLE is in TREE,
;; NIL otherwise.
(defun is-symbol-in-tree (needle tree)
  (reduce #'or
          (mapcar #'(lambda (element)
                      (cond
                        ((symbolp element) (eq element needle))
                        ((consp element)
                         (symbol-in-tree target-sym element))
                        (t (error "unexpected element in tree"))))
    :initial-value nil))

我没有测试该代码，但就是这个想法。 :-)

参考文献：http://clhs.lisp.se/Body/f_mapc_.htm and http://clhs.lisp.se/Body/f_reduce.htm

如果您对这种编程感到困惑，我建议您阅读 David Touretzky 的“Common Lisp 的简要介绍”。它从基本原理出发，以简单的方式非常清楚地介绍了这些概念。它并不假设 reader 完全理解编程，我发现这很有帮助，因为当我学习 Common Lisp 时，我有 30 年的 C 和 C++ 编程经验可以“忘却”。

我发现这种“应用性”编码风格使代码由内而外流动。例如。在上面的示例中，reduce 出现在 mapcar 之前，即使它将最后计算。顺便说一句，我仍然只是 Common Lisp 的初学者。

Answer 2

所以，首先让我们不要像 1956 年那样编程。让我们想象一下，而不是每个函数都知道树表示的血淋淋的细节，这使得它们又长又难读又脆弱，数据发明了抽象，有两个功能：

node-valuereturns一个节点的值；
node-children returns 节点的子节点作为列表。

那么我们的函数将如下所示：

Is the value we're looking for the node-value of the node? If it is we're done, if not not try each child of the node.

所以最明显的写法是

(defun value-in-tree-p (value node &optional (test #'eql))
  (or (funcall test (node-value node) value)
      (dolist (n (node-children node) nil)
        (when (value-in-tree-p value n test)
          (return-from value-in-tree-p t)))))

但是我们需要使用映射函数，所以我们可以这样做：

(defun value-in-tree-p (value node &optional (test #'eql))
  (or (funcall test (node-value node) value)
      (map nil (lambda (n)
                 (when (value-in-tree-p value n test)
                   (return-from value-in-tree-p t)))
           (node-children node))))

只是读起来有点难。

剩下的就是写node-value和node-children，make-node做树

Answer 3

如果结果 t 或 nil 就足够了，您还可以这样做：

(defun node-in-tree (node tree &key (test #'eql))
  (eq t (mapcar (lambda (x) (if (listp x) 
                                (when (node-in-tree node x) (return-from node-in-tree t))
                                (when (funcall test node x) (return-from node-in-tree t))))
                tree)))

这里的技巧是 return-from 可以在 mapcar 中一旦出现一次 (funcall test node x) 的正例就设法从 lambda 中突破。因此，一旦找到节点，此功能就会停止调查。 (eq t ...) 是必需的，因为 mapcar returns 只要不是 '() 的列表将被解释为 true，尽管它可能仅包含 nil 作为元素。

好的，我明白了，当使用 (map nil ...) 而不是 (mapcar ...) 时，可以摆脱 (eq t ...) 就像@ignisvolens 所做的那样：

(defun node-in-tree (node tree &key (test #'eql))
  (map nil (lambda (x) (if (listp x) 
                           (when (node-in-tree node x) (return-from node-in-tree t))
                           (when (funcall test node x) (return-from node-in-tree t))))
       tree)))

稍微优雅一点的是 mapcan (nil nil nil ...) 作为 mapcar 或 (map nil ...) 的结果只是一个 '().

(defun node-in-tree (node tree &key (test #'eql))
  (mapcan (lambda (x) (if (listp x) 
                          (when (node-in-tree node x) (return-from node-in-tree t))
                          (when (funcall test node x) (return-from node-in-tree t))))
          tree))))

lambda函数可以概括为：

最终解决方案

(defun node-in-tree (node tree &key (test #'eql))
  (mapcan (lambda (x) (when (or (and (listp x) (node-in-tree node x)) 
                                (funcall test node x)) 
                        (return-from node-in-tree t)))
          tree))

或者也不错：

(defun node-in-tree (node tree)
  (if (atom tree) 
      (eql node tree)
      (mapcan #'(lambda (x) (if (node-in-tree node x) (return-from node-in-tree t))) 
              tree)))

Lisp 检查 n 树中的节点

Lisp-check for a node in a n-tree

tree

common-lisp

最终解决方案