Re: Adding many elements to a list

[Pascal J. Bourguignon]

Nordlöw <per.nordlow@gmail.com> writes:

> What is the most efficient way of performing lots of successive
> appends of elements to the same list?
>
> If we start with defining the list
>
> (setq l '(a b))
>
> then the Emacs manual says that we can use
>
> (nconc l '(c d)))

No, that's not possible.  You mustn't modify a literal data.  See what happens 
if you do it:

(defun f ()
   (setq l '(a b))
   (nconc l '(c d)))

(list (f) (f)) --> (#1=(a b . #2=(c d . #2#)) #1#)
A third call to (f) will result in an infinite loop.

What you should do, is to build a new list everytime you want to
modify it with nconc.  You should also try to avoid setq and rather
use let:

(defun g ()
  (let ((l (list 'a 'b)))
    (nconc l (list 'c 'd))
    l))

(list (g) (g) (g)) --> ((a b c d) (a b c d) (a b c d))


> I have noticed that this works in all cases except when l is nil.

Of course.  As I wrote above, you mustn't modify a literal data.  And
in the case of nil, you just cannot modify it, since it's a constant. 


> To make this case work aswell we need to do use
>
> (setq l (nconc l '(c d))))
>
>
> Or can we use setcar or setcdr in a more clever way?

No.  setcar and setcdr take cons cells, not symbols.  nil is a symbol.

> Reflections?

In general in Lisp, it's more efficient to build the lists from the
end to the head: push on the head instead.  If the final result is in
the reversed order, you can always reverse it.

(defun h ()
   (let ((l (list 'c 'd)))
      (append '(a b) l)))

(list (h) (h) (h)) --> ((a b c d) (a b c d) (a b c d))

Notice that we used a literal list as argument to append. This is
possible because append copies all its arguments but the last.  And
since append doesn't make a copy of the last argument, we provided it
a new list so it may be modified:

(list (let ((l (h)))
         (nconc l (list 3 4))
         l)
      (h)
      (h)) --> ((a b c d 3 4) (a b c d) (a b c d))


(defun i ()
   (let ((l '(c d)))
      (append '(a b) l)))

(list (i) (i) (i)) --> ((a b . #1=(c d)) (a b . #1#) (a b . #1#))

(list (let ((l (i)))
         (nconc l (list 3 4))
         l)
      (i)
      (i)) --> ((a b . #1=(c d 3 4 3 4)) (a b . #1#) (a b . #1#))


So better use (require 'cl) (push new-item list)
   or (cons new-item list)
   or (append (list new-items...) list)
and possibly (reverse the-result), or (nreverse the-result) if you
took care of producing a list that doesn't share tail (ie. like g or
h, but not like f or i),


than (nconc list (list new-items...))  or (append list (list new-items...)).  
Using these later forms inside a loop will kill your time complexity.

-- 
__Pascal Bourguignon__