Geek Answers Handbook

LISP: Why mapcan cannot accept my list as parameters?

To simplify my question: why does it work

(mapcan #'(lambda (l) (list '1 '2) ) '(ab))

and it is not

 (mapcan #'(lambda (l) '(1 2) ) '(ab))

?

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

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

but I get the following results for these two inputs:

one.

 (subAll '(1(2(3(4(5(6(7)))))) (2(3(4 7(4(4(4(4)))))))) '7 '(ab)) => ((1(2(3(4(5(6(AB(4(4(4(4)))))))))) (2(3(4 AB(4(4(4(4)))))))))

2.

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

But if you replace ((and (atom l) (eq lk)) d) with ((and (atom l) (eq lk)) (list 'a 'b)) it works for input 1. Also I made my own function which simply deconstructs the list and reconstructs it:

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

and it works if you replace ((and (atom l) (eq lk)) d) with ((and (atom l) (eq lk)) (lst d)) for both of my inputs above.

  • => ((1(2(3(4(5(6(AB)))))) (2(3(4 AB(4(4(4(4)))))))))

  • => ((1 AB 3 (4 AB (3 AB (AB)))))

Can mapcan only accept a special kind of list? If anyone can explain to me why he is doing this, or give another solution, I would be grateful. (I cannot use any built-in functions like list or append only if I make my own list and list)

I am using GNU CLISP 2.49

+3
list parameters lisp common-lisp clisp
source share
1 answer

Short answer:

mapcan is destructive.

According to Hypertext Record on quote ,

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

The easiest way to fix this is to not use mapcan .

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

with this 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 first solve some style problems.

Please format your code correctly . This will simplify reading, both for you and for people who are trying to help you.

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

Next, the standard naming style for Common Lisp is train-case . In addition, (cons foo '()) , (cons foo nil) and (list foo) equivalent. You can also use the shortest. (You also don't need forms with a sharp lambda quote, although that doesn't really hurt).

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

Let's see what happens to your function when it runs during this case of stack overflow .

 ; SLIME 2013-04-02 CL-USER> (defun sub-all (lkd) (cond ((and (atom l) (eq lk)) d) ((atom l) (list l)) (t (list (mapcan #'(lambda (l) (sub-all lkd)) 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 see the critical moment of a mutation, but you can see an earlier equivalent (note that the second “layer” of d calls is (99 98 3) , not the (99 98) that you passed first). At some point, shortly after this, d becomes (99 98 3 (2)) , and at that moment the cycle becomes infinite, because you can find your target inside your replacement. What I usually do when I need a mapcan defines 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 applies to Undefined behavior for quoted lists. In particular, with the above definition of mappend ,

 CL-USER> (mappend #'(lambda (l) '(1 2)) '(ab)) ; 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)) '(ab)) (1 2 1 2) CL-USER>

Check out this answer (already related to Joshua Taylor above) for more details.

+4
source share

More articles:


All Articles