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

To simplify my question: why this works

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

and this doesn't

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

I have to write a function that substitutes an element through all elements of list D at all levels of a given list L, using Map Functions. I tried using mapcan for this:

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

but I get following results for these 2 inputs:

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

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

But if replace ((and (atom l) (eq l k)) d) with ((and (atom l) (eq l k)) (list 'a 'b)) it works for input 1. Also I`ve made my own function that just deconstructs a list and reconstructs it:

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

and it work if a replace ((and (atom l) (eq l k)) d) with ((and (atom l) (eq l k)) (lst d)) for both of my inputs above.

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

Does mapcan accept only a special kind of list? If anyone can explain to me why it does that or give another solution I would be grateful. ( I can't use any built in functions like list or append, only if I make my own append and list)

I am using GNU CLISP 2.49

Short answer:

mapcan is destructive.

As per the Hyperspec entry on quote,

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

The easiest way to fix this is not to use 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))
         '()))))

with that definition,

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>

Long Answer:

Let me get some style issues out of the way first.

Please format your code properly. It'll make it easier to read, both for you and people trying to help you.

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

Next, the standard naming style for Common Lisp is train-case. Also, (cons foo '()), (cons foo nil) and (list foo) are all equivalent. You may as well use the shortest one. (You also don't need to sharp-quote lambda forms, though it doesn't particularly hurt).

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

Lets take a look at what happens to your function as it runs during that stack overflow case.

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

You never actually get to see the critical mutation point, but you can see an earlier equivalent (notice that by the second "layer" of calls, d is (99 98 3), rather than the (99 98) that you passed in initially). At some point shortly after that, d becomes (99 98 3 (2)), at which point the loop goes infinite because you can find your target inside of your replacement. What I generally end up doing when I need mapcan is defining my own functional version.

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

This also gets around the Undefined behavior for quoted lists. Specifically, with the above definition of 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>

Check out this answer (already linked by Joshua Taylor above) for more details.

Recommended topics

Hot tags