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

Question

为了简化我的问题:为什么这行得通

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

这不是

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

?

我必须编写一个函数，使用 Map 函数在给定列表 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. => ((1(2(3(4(5(6(A B))))) (2(3(4 A B(4(4(4(4)))) ))))))

2. => ((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)))))

---

让我们看一下您的函数在堆栈溢出 情况下运行时发生了什么。

; 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 ...

你永远不会真正看到关键突变点，但你可以看到一个更早的等价物(注意在调用的第二个“层”，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 链接)了解更多详情。