Re: Basic questions about elisp

[David Kastrup <dak@gnu.org>]

Francis Moreau <francis.moro@gmail.com> writes:

> On Nov 5, 12:50 pm, Lennart Borgman <lennart.borg...@gmail.com> wrote:
>> On Thu, Nov 5, 2009 at 12:13 PM, Francis Moreau <francis.m...@gmail.com> wrote:
>> > I'm iterating over a list using dotimes, but in the body of dotimes,
>> > the list can mutate. For example I have:
>>
>> >  (dolist (elt lst)
>> >    ;; some codes
>> >    (nconc lst '(2)))
>>
>> > This adds/appends a new element to 'lst' list. It looks like 'dotimes'
>> > doesn't like it.

dolist.

>>
>> > So I eventually wrote it like this
>>
>> >    (setq i 0)
>> >    (while (< i (length lst))
>> >          ;; some codes
>> >          (x-nconc lst '(2))))
>> >      (setq i (1+ i)))
>>
>> > which is a bit ugly,

This looks like you would use (elt lst i) inside of the loop, quite a
bad idea since you get quadratic behavior.

> I'd like to iterate over all elements of the list even if the element
> are appended during the loop execution.
>
> For example if the list is (1 2) before entering in the loop and then
> during the first iteration the code append '3' to the list so it
> becomes (1 2 3), I'd like the loop to iterate over the '3' element as
> well. 'dotimes' doesn't seem to do that.

dolist

> I noticed that I used 'x-nconc' without giving its definition: it is
> something I wrote for my own need: it's the same as 'nconc' except if
> the list given in parameter is nil then 'x-nconc' creates a new list
> and assigns it to its first parameter.
>
> I did the following macro to do that, although I'm not sure it's the
> good thing to do:
>
>   (defmacro x-nconc (l e)
>     `(if (null ,l) (setq ,l ,e) (nconc ,l ,e)))

Actually, that's pretty stupid since it is exactly the same as
(defmacro (l e) `(setq ,l (nconc ,l ,e)))

It is less obscure to use nconc in the same manner as append, namely
using the return value (and accepting the side-effect for efficiency's
sake).  And then you don't need your personal macro and get more
readable code.

The usual iteration would be something like

(while lst
  <do something with (car lst)>
  <maybe append something to lst>
  (setq lst (cdr lst)))

If you really want efficiency, you'll not append something to lst in
order to avoid quadratic behavior.  Then you'd rather do something like

(let ((iter lst) app)
  (while
    (progn
       (while iter
          <do something with (car iter)>
          <maybe (push something app)>
          (setq lst (cdr lst)))
        app)
     (setq iter (nreverse app) app nil)))

Note that this does not change the original list at all.  If that's not
what is desired, you can write the last setq as

(setq iter (nreverse app) lst (nconc lst iter) app nil)

This still is suboptimal since the nconc will repeatedly traverse the
same elements.  Better solutions will track the additions also by just
pushing them, and do the concatenation as the very last step.

-- 
David Kastrup