I want to use a list to hold pending work. Ideally I want to do
something like this:
(let (work-list)
(setf work-list '(work-a work-b work-c))
(loop for work in work-list
do
(print work)
(nconc work-list (list something))))
But I read in the lisp hyperspec (section 3.6):
For list traversal operations, the cdr chain
of the list is not allowed to be destructively modified.
I take this to mean that my way won't work.
Is my reading of the hyper spec correct? If yes, what other
ways of iterating over a list allow modifying the list while
the iteration is happening?
Thanks for any info.
-Ram
In article <·······················@g47g2000cwa.googlegroups.com>,
"Ram Bhamidipaty" <·······@gmail.com> wrote:
> I want to use a list to hold pending work. Ideally I want to do
> something like this:
>
> (let (work-list)
> (setf work-list '(work-a work-b work-c))
> (loop for work in work-list
> do
> (print work)
> (nconc work-list (list something))))
Just to be pedantic, you must not destructively modify a constant list.
You should have created the list with (list 'work-a 'work-b 'work-c)
rather than quoting the list.
>
> But I read in the lisp hyperspec (section 3.6):
>
> For list traversal operations, the cdr chain
> of the list is not allowed to be destructively modified.
>
> I take this to mean that my way won't work.
Correct. This allows the implementation to look ahead in the list,
cache, or perform other optimizations that depend on the structure of
the tail of the list not changing out from under it.
> Is my reading of the hyper spec correct? If yes, what other
> ways of iterating over a list allow modifying the list while
> the iteration is happening?
Instead of using one of the built-in list iteration mechanisms, write it
out yourself using DO, or LOOP with = and THEN operators, etc. Then you
have full control over how you step through the list, and can ensure
that modifying the cdr chain doesn't cause problems.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
"Ram Bhamidipaty" <·······@gmail.com> writes:
>Is my reading of the hyper spec correct? If yes, what other
>ways of iterating over a list allow modifying the list while
>the iteration is happening?
Is there a specific reason why you can't cons up a new result list
while you go?
mkb.
Ram Bhamidipaty wrote:
> I want to use a list to hold pending work. Ideally I want to do
> something like this:
>
> (let (work-list)
> (setf work-list '(work-a work-b work-c))
> (loop for work in work-list
> do
> (print work)
> (nconc work-list (list something))))
>
> But I read in the lisp hyperspec (section 3.6):
>
> For list traversal operations, the cdr chain
> of the list is not allowed to be destructively modified.
>
> I take this to mean that my way won't work.
>
> Is my reading of the hyper spec correct? If yes, what other
> ways of iterating over a list allow modifying the list while
> the iteration is happening?
Incidentally (since your question was already answered), if you're
interested in learning more about queues, there's a good paper by Dick
Waters and Peter Norvig:
http://www.merl.com/publications/TR1991-004/
Queues were touched upon in Norvig's PAIP book. And anything lispwise
by Dick Waters floating on the net should prove interesting to read.
Tayssir
- -
http://www.zmag.org/znetaudio.html
From: Thomas A. Russ
Subject: Re: modify a list while iterating over the same list
Date:
Message-ID: <ymiek8vf5q9.fsf@sevak.isi.edu>
"Ram Bhamidipaty" <·······@gmail.com> writes:
> (let (work-list)
> (setf work-list '(work-a work-b work-c))
> (loop for work in work-list
> do
> (print work)
> (nconc work-list (list something))))
>
> But I read in the lisp hyperspec (section 3.6):
>
> For list traversal operations, the cdr chain
> of the list is not allowed to be destructively modified.
Try the following:
(loop while work-list
as item = (pop work-list)
do (print item)
...
(setq work-list (nconc work-list (list something))))
This lets you work on a changing list. Also, it is important to have
the SETQ even when using NCONC because it can't always be destructive.
If WORK-LIST is NIL, there is nothing that can be destructively modified
and so you would lose the modification.
--
Thomas A. Russ, USC/Information Sciences Institute
From: Peter Seibel
Subject: Re: modify a list while iterating over the same list
Date:
Message-ID: <m2iry6py6m.fsf@beagle.local>
···@sevak.isi.edu (Thomas A. Russ) writes:
> "Ram Bhamidipaty" <·······@gmail.com> writes:
>
>> (let (work-list)
>> (setf work-list '(work-a work-b work-c))
>> (loop for work in work-list
>> do
>> (print work)
>> (nconc work-list (list something))))
>>
>> But I read in the lisp hyperspec (section 3.6):
>>
>> For list traversal operations, the cdr chain
>> of the list is not allowed to be destructively modified.
>
> Try the following:
>
> (loop while work-list
> as item = (pop work-list)
> do (print item)
> ...
> (setq work-list (nconc work-list (list something))))
Though keep in mind that the call to NCONC is going to have to
traverse the full length of WORK-LIST each time through the loop which
may slow things down quite a bit. The following (untested) code should
fix that problem.
(loop with tail = (last work-list)
while work-list
for item = (pop work-list)
do (print item)
(let ((new-item (cons something nil)))
(setf tail
(if work-list
(setf (cdr tail) new-item)
(setf work-list new-item)))))
or this more version which deals with adding an aribtrary number of
new items per iteration:
(loop with tail = (last work-list)
while work-list
for item = (pop work-list)
do (print item)
(let ((new-items (list ...)))
(setf tail (last
(if work-list
(setf (cdr tail) new-items)
(setf work-list new-items))))))
-Peter
--
Peter Seibel * ·····@gigamonkeys.com
Gigamonkeys Consulting * http://www.gigamonkeys.com/
Practical Common Lisp * http://www.gigamonkeys.com/book/