LISP：为什么 mapcan 不接受我的列表作为参数？

Question

为了简化我的问题：为什么这有效

(mapcan #'(lambda (l) (list '1 '2) ) '(a b))

而这不是

(mapcan #'(lambda (l) '(1 2) ) '(a b))

?

我必须编写一个函数，使用映射函数在给定列表 L 的所有级别上通过列表 D 的所有元素替换一个元素。我尝试为此使用 mapcan：

(defun subAll (l k d)
  (cond 
    ((and (atom l) (eq l k)) 
     d)
    ((and (atom l) (not (eq l k)))
     (cons l '()))
    (t (cons 
         (mapcan #'(lambda (l) (subAll l k d)) l)
         '()))))

但是我得到了这两个输入的以下结果：

1.

(subAll '(1(2(3(4(5(6(7)))))) (2(3(4 7(4(4(4(4)))))))) '7 '(a b))
 => ((1(2(3(4(5(6(A B(4(4(4(4)))))))))) (2(3(4 A B(4(4(4(4)))))))))

2.

(subAll '(1 2 3 (4 2 (3 2 (2)))) '2 '(99 98))
=>Lisp stack overflow.

但是如果替换 ((and (atom l) (eq l k)) d) 和 ((and (atom l) (eq l k)) (list 'a 'b)) 它适用于输入 1。我还制作了自己的函数，它只是解构一个列表并重建它：

(defun lst(l)
(cond
    ((null l) nil)
    (t (cons (car l) ( lst (cdr l))))))

如果将我上面的两个输入的 ((and (atom l) (eq l k)) d) 替换为 ((and (atom l) (eq l k)) (lst d))，它就会工作。

=> ((1(2(3(4(5(6(A B)))))) (2(3(4 A B(4(4(4(4)))))))))
=> ((1 A B 3 (4 A B (3 A B (A B)))))

mapcan只能接受一种特殊的列表吗？如果有人能向我解释为什么这样做或提供其他解决方案，我将不胜感激。（我不能使用任何内置函数，如 list 或 append，只有当我自己制作 append 和 list 时）

我正在使用 GNU CLISP 2.49

Answer 1

简答：

mapcan具有破坏性。

根据 Hyperspec entry on quote、

"The consequences are undefined if literal objects (including quoted objects) are destructively modified."

解决此问题的最简单方法是不使用 mapcan。

(defun subAll (l k d)
  (cond 
    ((and (atom l) (eq l k)) 
     d)
    ((and (atom l) (not (eq l k)))
     (cons l '()))
    (t (cons 
         (loop for elem in l append (subAll elem k d))
         '()))))

根据该定义，

CL-USER> (suball '(1 2 3 (4 2 (3 2 (2)))) '2 '(99 98))
((1 99 98 3 (4 99 98 (3 99 98 (99 98)))))
CL-USER>

长答案：

让我先解决一些风格问题。

请format your code properly。它会让您和试图帮助您的人更容易阅读。

(defun subAll (l k d)
  (cond 
    ((and (atom l) (eq l k)) 
     d)
    ((and (atom l) (not (eq l k)))
     (cons l '()))
    (t (cons 
         (mapcan #'(lambda (l) (subAll l k d)) l)
         '()))))

接下来，Common Lisp 的标准命名风格是train-case。此外，(cons foo '())、(cons foo nil) 和 (list foo) 都是等价的。您也可以使用最短的那个。（您也 不需要 尖锐地引用 lambda 形式，尽管它并没有特别伤害）。

(defun sub-all (l k d)
  (cond 
    ((and (atom l) (eq l k)) 
     d)
    ((atom l)
     (list l))
    (t (list (mapcan #'(lambda (l) (sub-all l k d)) l)))))

让我们看看您的函数在 stack overflow 案例中运行时发生了什么。

; SLIME 2013-04-02
CL-USER> (defun sub-all (l k d)
  (cond 
    ((and (atom l) (eq l k)) 
     d)
    ((atom l)
     (list l))
    (t (list (mapcan #'(lambda (l) (sub-all l k d)) l)))))
;Compiler warnings :
;   In an anonymous lambda form inside SUB-ALL: Undefined function SUB-ALL
SUB-ALL
CL-USER> (trace sub-all)
NIL
CL-USER> (sub-all '(1 2 3 (4 2 (3 2 (2)))) '2 '(99 98))
0> Calling (SUB-ALL (1 2 3 (4 2 (3 2 (2)))) 2 (99 98)) 
 1> Calling (SUB-ALL 1 2 (99 98)) 
 <1 SUB-ALL returned (1)
 1> Calling (SUB-ALL 2 2 (99 98)) 
 <1 SUB-ALL returned (99 98)
 1> Calling (SUB-ALL 3 2 (99 98)) 
 <1 SUB-ALL returned (3)
 1> Calling (SUB-ALL (4 2 (3 2 (2))) 2 (99 98 3)) 
  2> Calling (SUB-ALL 4 2 (99 98 3)) 
  <2 SUB-ALL returned (4)
  2> Calling (SUB-ALL 2 2 (99 98 3)) 
  <2 SUB-ALL returned (99 98 3)
  2> Calling (SUB-ALL (3 2 (2)) 2 (99 98 3)) 
   3> Calling (SUB-ALL 3 2 (99 98 3)) 
   <3 SUB-ALL returned (3)
   3> Calling (SUB-ALL 2 2 (99 98 3)) 
   <3 SUB-ALL returned (99 98 3)
   3> Calling (SUB-ALL (2) 2 (99 98 3)) 
    4> Calling (SUB-ALL 2 2 (99 98 3)) 
    <4 SUB-ALL returned (99 98 3)
   <3 SUB-ALL returned ((99 98 3))
  <2 SUB-ALL returned ((3 99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 (99 98 3 ...

你永远不会真正看到关键突变点，但你可以看到一个更早的等效点（请注意，到第二个 "layer" 调用时，d 是 (99 98 3)，而不是比你最初传入的 (99 98) ）。在那之后不久的某个时候，d 变成了 (99 98 3 (2))，此时循环变成无限，因为你可以在你的替代品中找到你的目标。当我需要 mapcan 时，我通常最终会做的是定义我自己的功能版本。

(defun mappend (fn list)
  (loop for elem in list
     append (funcall fn elem)))

(defun sub-all (tree target replacement)
  (cond 
    ((and (atom tree) (eq tree target)) 
     replacement)
    ((atom tree)
     (list tree))
    (t (list 
         (mappend 
           (lambda (sub) 
             (sub-all sub target replacement))
           tree)))))

这也解决了引用列表的未定义行为。具体来说，根据上面定义的mappend，

CL-USER> (mappend #'(lambda (l) '(1 2)) '(a b))
; in: MAPPEND #'(LAMBDA (L) '(1 2))
;     #'(LAMBDA (L) '(1 2))
; 
; caught STYLE-WARNING:
;   The variable L is defined but never used.
; 
; compilation unit finished
;   caught 1 STYLE-WARNING condition
(1 2 1 2)
CL-USER> (mappend #'(lambda (l) (declare (ignore l)) '(1 2)) '(a b))
(1 2 1 2)
CL-USER>

查看 this answer（已由上面的 Joshua Taylor 链接）了解更多详细信息。

LISP：为什么 mapcan 不接受我的列表作为参数？

LISP: Why doesn't mapcan accept my list give as parameters?

lisp

parameters

clisp

list

common-lisp