lisp - 如何避免在 cond 子句 LISP 中重复代码？

Question

我应该在 LISP 中找到从根到给定节点的路径。最好使用纯函数方法。

二叉树表示使用子列表，例如: (A (B) (C (D) (E))) - A 是根，B 是 A 的左 child ，C 是 A 的右 child ，D 是 C 和 E 的左 child C 的右 child 。

在我看来，应该有一些方法可以避免重复调用以下函数:

(get-path (cadr l) x)

(get-path (caddr l) x)

我是 LISP 的新手，我不知道也似乎找不到解决方案，但我认为必须有一种 - 纯 - 功能性的方式来做到这一点。也许使用 lambda？不过，不确定如何。我使用了错误的方法吗？非常感谢任何形式的帮助。

;;; l is the list with the binary tree
;;; x is the node we are looking for
(defun get-path(l x) 
    (cond
            ;; nothing to search for anymore
            ((null l) nil)
            ;; found the node we were looking for
            ;; in this case we return a list containing only x
            ((equal (car l) x) (list x))
            ;; the node was found on the left branch
            ((not(equal (get-path (cadr l) x) nil))
                     (cons (car l) (get-path (cadr l) x)))
            ;; the node was found on the right branch
            ((not(equal (get-path (caddr l) x) nil))
                     (cons (car l) (get-path (caddr l) x))))) 

Answer 1

这个呢？

(defun root-path (tree element)
  (when tree
    (cons (first tree)
          (unless (eql (first tree) element)
            (or (root-path (second tree) element)
                (root-path (third tree) element)
                (return-from root-path nil))))))

您甚至应该定义有意义的命名函数，例如 tree-value left-subtree 和 right-subtree，但这在这里可能有点矫枉过正.

在上面，请注意 when (resp. unless) 在条件失败时用于其 nil 值(resp. succeed ).如果您愿意，可以使用 cond 或 if 表达式进行翻译。这里唯一重复的是双 (first tree) 值，它可能会被编译器优化掉，或者手动使用周围的 let 绑定(bind)。

编辑

原始代码无效。解决方案是使用 Joshua 的答案，但我不会复制粘贴到这里，所以我添加了 return-from 表达式。虽然它有效，但您的老师和/或同事可能不喜欢这种方法；-)

测试

(mapcar (lambda (n) (root-path '(A (B) (C (D) (E))) n))
        '(a b c d e f))

=> ((a) (a b) (a c) (a c d) (a c e) nil)