将项目替换为列表中的每个匹配项

Question

我刚刚开始学习 Lisp。我的问题是每次出现在列表中时我都试图替换它。我必须使用递归并且没有任何循环来做到这一点。该函数以 (subste x y L).

开头

示例为：

(subste 7 t '(it is 7)) → (IT IS T)
(subste 7 nil '(7 is not to (7))) → (NIL IS not TO (NIL))
(subste 7 nil '(5 is not (22))) → (5 is not (22))

这是我目前所要做的：

(defun subste (x y L)
  (cond ((null L) nil)
        ((not (= (car L) x))
         subste (x y (cdr L)))
        ((= (car L) x)
         (let L 'y))))

我已经运行多次并对其进行了多次调整，但考虑到错误消息提供的信息很少并且才刚刚开始学习 Lisp，所以运气不佳。谢谢

Answer 1

SUBST 已经实现了您想要的行为。您似乎只是希望新旧元素的顺序不同，所以一个简单的包装器就可以：

(defun subste (x y l)
  (subst y x l))

如果您想自己实现，下面是一个简单的版本。注意不同的分支：

递归树总是涉及对树的第一个元素进行递归调用，对树的其余部分进行另一个元素。
Return nil 在树的尽头。
如果我们找到要替换的元素，我们会更改它。
对于任何其他原子，我们不需要递归，我们只是 return 原子。

这里是例子：

(defun subste (x y l)
  (cond ((null l) nil)
        ((eql l x) y)
        ((atom l) l)
        (T (cons (subste x y (first l))
                 (subste x y (rest l))))))

此版本不完整：您无法替换非 eql 元素（如字符串或子列表）。如果需要，您可以添加一个测试函数作为参数，而不是始终使用 EQL。

Answer 2

写一个subst的实现只是遍历树，检查树中的节点是否与old相同，并将它们替换为 new。在 Common Lisp 中，像这样的函数通常采用 test 函数来确定如何比较元素（通常是 key 函数，但我已经此处省略）。这导致了这样的事情：

(defun my-subst (old new tree &key (test 'eql))
  "Returns a completely fresh tree like TREE, but with occurrences of
OLD replaced by NEW.  The resulting tree shares no structure with the 
original TREE, except for leaves."
  (cond
    ;; If the current tree is the OLD element,
    ;; return the NEW element instead.
    ((funcall test old tree) new)
    ;; If the current tree is a cons cell,
    ;; call MY-SUBST recursively on both
    ;; the CAR and CDR of the tree, and
    ;; then CONS the results back together.
    ((consp tree) (cons (my-subst old new (car tree) :test test)
                        (my-subst old new (cdr tree) :test test)))
    ;; Otherwise, just return TREE.
    (t tree)))

(my-subst 'x 42 '(1 x 2 (3 x (4 (x) 5))))
;=> (1 42 2 (3 42 (4 (42) 5)))

现在，由该实现创建的 return 树总是全新的。也就是说，即使 old 元素 never 出现在树中，您仍然会得到一棵全新的树。根据您的用例，这可能有点浪费内存。检查递归调用的结果是否与其输入相同可能是有益的。在这种情况下，您可以 return 输入：

(defun my-subst (old new tree &key (test 'eql))
  "Returns a tree like TREE, but with occurrences of OLD
replaced by NEW.  The resulting tree may share structure
with TREE."
  (cond
    ((funcall test old tree) new)
    ((consp tree)
     (let ((new-car (my-subst old new (car tree) :test test))
           (new-cdr (my-subst old new (cdr tree) :test test)))
       (if (and (eq (car tree) new-car)
                (eq (cdr tree) new-cdr))
           tree
           (cons new-car new-cdr))))
    (t tree)))

(let* ((t1 '(1 x 2 (3 x (4 (x) 5))))
       (t2 (my-subst 'x 42 t1))
       (t3 (my-subst 'y 84 t1)))
  (list (eq t1 t2)
        (eq t1 t3)))

;=> (NIL T) ; t1 != t2, but t1 == t3

您想要哪种取决于具体情况，但最好能够两者都做到。

将项目替换为列表中的每个匹配项

Substituting item to every occurance in a list

lisp

recursion

replace

list

common-lisp