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

Question

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

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

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

(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

对内部（局部）函数使用 labels：

(defun get-path(l x)
    (labels ((prepend-path (elt)
                (cons (car l) (get-path elt 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))
                     (prepend-path (cadr l)))
            ;; the node was found on the right branch
            ((not(equal (get-path (caddr l) x) nil))
                     (prepend-path (caddr l))))))

或者，您可以使用 flet 而不是 labels，因为您没有相互引用的内部函数。就个人而言，我使用 labels 并且几乎从不使用 flet 因为这个原因（加上重新缩进函数的开销。）

Answer 2

这个呢？

(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，但这在这里可能有点矫枉过正。

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

编辑

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

测试

(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)

Answer 3

我将合并最后两个 cond 子句。你想检查左边，看看那里有没有路，如果有，就走，如果没有，就检查右边。然后，无论哪一个产生了一条路径（如果有的话），你都想附加到那个路径上。这可能看起来像这样。首先，为了方便起见，有几个函数：

(defun element (tree)
  (first tree))

(defun left (tree)
  (second tree))

(defun right (tree)
  (third tree))

现在，解决方案的真正内容：

(defun get-path (element tree)
  (cond
    ;;  A null tree is empty and doesn't match anything.
    ((null tree) '())
    ;; If the element of this tree is the element, then we have a
    ;; partial path of length 1: (ELEMENT).
    ((eql element (element tree)) (list element))
    ;; Othweise, let PATH be the path on the left or the path on the
    ;; right, whichever exists.
    (t (let ((path (or (get-path element (left tree))
                       (get-path element (right tree)))))
         ;; If there's no path on either side, then return NIL.
         ;; Otherwise, prepend the current element onto the path that
         ;; exists.
         (if (null path) '()
             (list* (element tree) path))))))

请注意 list* 与 cons 做同样的事情，但它更清楚地表明您正在使用列表，而不仅仅是cons细胞。您也可以使用 cons。

我们可以确认这按预期工作：

(defparameter *tree* '(A (B) (C (D) (E))))

(get-path 'c *tree*) ;;=> (A C)
(get-path 'd *tree*) ;;=> (A C D)
(get-path 'f *tree*) ;;=> NIL

Answer 4

你可以做的是复制照应 conda and ifa macros from TXR Lisp in Common Lisp. (Source code here; good luck!)enter link description here

那你可以这样写，用照应it变量引用get-path表达式。

(conda
  ;; 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) it))
  ;; the node was found on the right branch
  ((not (equal (get-path (caddr l) x) nil)) (cons (car l) it)))

conda 对于 (not x) 和 (null x) 形式的表达式（在 TXR Lisp 中也是 (false x) ）很聪明。如果测试表达式是其中之一，那么它会递归到 x 中，找出 "anaphoric it".

请注意 it 绑定到 places 而不仅仅是绑定到 values。 it的target不仅不会被求值不止一次，如果target是一个地方，那么it就是指那个地方：

(ifa (< x 10)
  (inc it)) ;; increments x.

ifa这方面是借助placelet宏实现的，Common Lisp中不存在。一个快速而肮脏的替代方法是使用 symbol-macrolet。唯一的问题是表示一个地点的符号宏允许对该地点进行多次评估，而 placelet 对一个地点进行一次评估。生成的词汇符号然后表示存储位置，而不是整个表达式。

ifa 旨在与 Paul Graham 的 aif 擦地板，或者补充它； conda 平凡地基于 ifa。

顺便说一下，不要写

这样的表达式

(not (equal whatever nil))

在 Lisp 中！首先，如果与nil进行比较，equal 相等性并没有特别的意义；只有 nil 是 equal 到 nil，并且根据 eq 相等，所以你还不如：

(not (eq whatever nil))

其次，对于某事不是 eq 到 nil 意味着某事是真的。也就是说：

(if (not (eq foo nil)) do-this)   ---same-as--> (if foo do-this)

!

如果我们重构您的代码以摆脱这些东西，那么如果 aif（以及基于它的 acond）我们有 Paul Graham 风格的照应会更好。也就是说：

(ifa (not (equal (get-path whatever) nil))) (list it))

变为：

(aif (get-path whatever) (list it))

其中 it 是整个测试表达式的值，而不是该表达式中经过巧妙选择的成分。

在 ifa 下，使用

稍微更冗长地表示

(ifa (true (get-path whatever)) (list it))

其中true可以定义为

(defun true (x) (identity x)).

如果没有这个额外的包装，ifa 会将 it 绑定到 whatever。

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

How to avoid duplicating code in cond clause LISP?

lisp

common-lisp

编辑

测试