子字符串的基本 LISP 递归替换

Question

我试图用"X"替换列表中给定字符串的任何出现，在递归函数中使用基本的LISP命令(例如没有mapcar(。

(defun removetext (symbol list replaced)
(if (not list)   ; if initial list has been exhausted, return replaced list
replaced
(progn
(if (eql (car list) symbol)   ; otherwise, if first element of list = symbol, replace with "X"
(removetext symbol (cdr list) (cons "X" replaced)) 
(removetext symbol (cdr list) (cons (car list) replaced)) ; otherwise keep it 
)
(format t "~D" replaced)
)
)
)

如果我用(removetext "E" '(A B C D E F F E) "")调用它，这不起作用。

这将返回NIL，打印输出看起来像(F F E D C B A . )(F E D C B A . )(E D C B A . )(D C B A . )(C B A . )(B A . )(A . )。

我希望它返回(A B C D X F F X).

Answer 1

(defun removetext (symbol list replaced)
(if (null list)
(reverse replaced)
(if (eql (car list) symbol)
(removetext symbol (cdr list) (cons 'x         replaced)) 
(removetext symbol (cdr list) (cons (car list) replaced)))))

例：

CL-USER > (removetext 'E '(A B C D E F F E) ())
(A B C D X F F X)

Answer 2

到目前为止，其他答案都没有解决代码中的重要问题。 给定这个略有不同但结构相似的函数版本：

(defun replace-thing (list thing by &key (test #'eql))
(labels ((replace-it (tail replaced)
(if (null tail)
(reverse replaced)
(progn
(if (funcall test (first tail) thing)
(replace-it (rest tail) (cons by replaced)) 
(replace-it (rest tail) (cons (first tail) replaced)))
(format t "~&got ~S~%" replaced)))))
(replace-it list '())))

这将以与你的方式之一相同的方式失败：

> (replace-thing '(a b c) 'a 'c)
(b c)
(c)
nil
nil

它失败的原因是因为progn做了什么。 你写过

(progn
... compute the thing you care about ...
(format ...))

progn的值是其主体中最后一种形式的值，因此在这种情况下，(format ...)的值nil。

对此有两种解决方案：一种适合您，另一种更通用。

适合您的解决方案是意识到replaced永远不会改变(您的功能不会发生突变，这很好(，因此您可以先安全地打印它：

(progn
(format t "~& ~S~%" replaced)
(if (funcall test (first tail) thing)
(replace-it (rest tail) (cons by replaced)) 
(replace-it (rest tail) (cons (first tail) replaced))))

此更改将使我的函数正常工作。

一个更一般的解决方案是意识到你想要的是某种形式，比如说first-thing当用作

(first-thing
thing1
...
thingn)

将：

1. 按顺序做它身体里的事情;
2. 然后返回其中第一个的值。

好吧，您可以非常轻松地将这样的表单编写为宏。 这是一个稍微受限制的版本：

(defmacro first-thing (thing1 &body more-things)
(let ((sn (make-symbol "STASH")))
`(let ((,sn ,thing1))
,@more-things
,sn)))

然后

> (first-thing 1 (print "hi") (print "there"))
"hi" 
"there" 
1

但实际上你不需要这样做：CL 同时提供了这个受限制的和一个更通用的：

• 受限制的 是prog1–(prog1 thing1 ... thingn)按顺序计算事物，然后返回第一件事的第一个值;
• 一般的multiple-value-prog1–(multiple-value-prog1 thing1 ... thingn)按顺序计算事物，然后返回第一个事物的所有值。

multiple-value-prog1几乎肯定比prog1更昂贵，因为它需要在某处存储多个值，因此几乎可以肯定是concons。 在您的情况下，您只需要prog1，因此您的函数(我的版本(的一个版本是：

(defun replace-thing (list thing by &key (test #'eql))
(labels ((replace-it (tail replaced)
(if (null tail)
(reverse replaced)
(prog1
(if (funcall test (first tail) thing)
(replace-it (rest tail) (cons by replaced)) 
(replace-it (rest tail) (cons (first tail) replaced)))
(format t "~& ~S~%" replaced)))))
(replace-it list '())))

和

> (replace-thing '(a b c) 'a 'z)
(b z)
(z)
nil
(z b c)

Answer 3

如果要替换字符串的出现，则需要传递字符串列表。您传递了一个符号列表，而不是字符串。现在，您仍然可以将这些符号替换为特定的字符串，但它们本身不是字符串。该列表：

'(a b c d e f e)

是符号列表，而不是字符串：

(defun remove-text (str lst)
(if (atom lst)
lst
(if (string-equal (symbol-name (car lst)) str)
(cons "X" (remove-text str (cdr lst)))
(cons (car lst) (remove-text str (cdr lst))))))

我们可以传递一个字符串作为参数进行检查，然后传递一个符号列表。我们的基本情况将测试列表是否是一个原子，此时我们将简单地返回列表。如果没有，我们将使用 string-equal 来查看列表的汽车的符号名称(这将返回符号的字符串值(是否等于我们的字符串。如果是这种情况，我们可以将"X"缺点到列表的开头，然后再次递归调用该函数。如果没有，我们可以简单地将列表的汽车骗到列表的开头，然后再次递归调用该函数。此函数不是尾递归的，但它是递归的，它确实避免创建新的列表结构来存储您的结果，而不会破坏性地改变原始列表的结构。我们可以在下面进行测试：

CL-USER> (remove-text "E" '(a b c d e f f e))
(A B C D "X" F F "X")