(setf x '(1 2 3))
(setf y x) (setf z x)
I want to be able to extend y and z so they stay synchronized. For
example (add-to-end y 4) makes both y and z '(1 2 3 4).
(defun add-to-end (list value)
(do ((p list (cdr p)))
((endp (cdr p)) (rplacd p
(if (listp value) value (list value))))))
But how to extend the list from another side so the pointer stays at the
same place? Is it safe to use nreverse like that:
(defun add-to-start (list value)
(nreverse list) (add-to-end list value) (nreverse list))
It works, but looking at Hyperspec I'm not sure if nreverse would be
behaving well all the time.
--
|a\o/r|,-------------.,---------- Timofei Shatrov aka Grue ------------.
| m"a ||FC AMKAR PERM|| mail: grue at mail.ru http://grue3.tripod.com |
| k || PWNZ J00 || Kingdom of Loathing: Grue3 lvl 18 Seal Clubber |
`-----'`-------------'`-------------------------------------------[4*72]
····@mail.ru (Timofei Shatrov) writes:
> (setf x '(1 2 3))
> (setf y x) (setf z x)
>
> I want to be able to extend y and z so they stay synchronized. For
> example (add-to-end y 4) makes both y and z '(1 2 3 4).
>
> (defun add-to-end (list value)
> (do ((p list (cdr p)))
> ((endp (cdr p)) (rplacd p
> (if (listp value) value (list value))))))
>
> But how to extend the list from another side so the pointer stays at the
> same place?
You cannot, as is.
> Is it safe to use nreverse like that:
No. It's highly implementation dependant.
> (defun add-to-start (list value)
> (nreverse list) (add-to-end list value) (nreverse list))
>
> It works, but looking at Hyperspec I'm not sure if nreverse would be
> behaving well all the time.
In some implementations. (clisp is known to keep the first and last
conses as first and last, and to reverse the cdr only of the conses in
the middle).
There are several solutions.
You could add one header cons:
(setf x (cons :header (list 1 2 3)))
(setf y x z x)
Then:
(push (cdr y) 0)
z --> (:header 0 1 2 3)
To make the meaning clearer, you could use a structure, or an object:
(defstruct mutable-list head)
(setf x (make-mutable-list :head (list 1 2 3)))
(setf y x z x)
(type-of y) --> mutable-list
(push (mutable-list-head y) 0)
(mutable-list-head z) --> (0 1 2 3)
You could use a 1-element vector:
(setf x (make-array 1 :initial-contents (list 1 2 3)))
(setf y x z x)
(push (aref y 0) 0)
(aref z 0) --> (0 1 2 3)
z --> #((0 1 2 3))
I'd advise using more complex structure or object, where you could do
some bookkeeping: (defstruct mutable-list length head tail) so you can
get the length and you can append at the end in O(1). And you can
write generic functions to get the same API as normal cons lists.
One advantage of these solutions is that they work when the list is
empty too.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Nobody can fix the economy. Nobody can be trusted with their finger
on the button. Nobody's perfect. VOTE FOR NOBODY.
In article <················@news.readfreenews.net>,
····@mail.ru (Timofei Shatrov) wrote:
> (setf x '(1 2 3))
> (setf y x) (setf z x)
>
> I want to be able to extend y and z so they stay synchronized. For
> example (add-to-end y 4) makes both y and z '(1 2 3 4).
>
> (defun add-to-end (list value)
> (do ((p list (cdr p)))
> ((endp (cdr p)) (rplacd p
> (if (listp value) value (list value))))))
>
> But how to extend the list from another side so the pointer stays at the
> same place? Is it safe to use nreverse like that:
>
> (defun add-to-start (list value)
> (nreverse list) (add-to-end list value) (nreverse list))
>
> It works, but looking at Hyperspec I'm not sure if nreverse would be
> behaving well all the time.
Nothing you try will work for the case where the list starts out empty.
The generally accepted solution is to add a level of indirection.
Instead of referring to the list directly from the variables, go through
a structure or an extra cons cell:
(defstruct reference
value)
(setf y (make-reference :value x))
(setf z y)
(defun add-to-end (ref value)
(setf (reference-value ref)
(append (reference-value ref) (list value))))
Note that this design allows you to enhance it for efficiency. The
reference structure could hold on to a reference to the last cons in the
list, so that it can append to it in O(1) time rather than O(n) time; if
you're repeatedly adding to the list this would reduce an
exponential-time algorithm to linear-time.
I'm trying to remember who's law it is that any problem in computer
science can be solved with sufficient levels of indirection.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
Barry Margolin <······@alum.mit.edu> writes:
> I'm trying to remember who's law it is that any problem in computer
> science can be solved with sufficient levels of indirection.
According to Wikipedia[1] it was Butler Lampson.
-Peter
[1] http://en.wikipedia.org/wiki/Butler_Lampson
--
Peter Seibel * ·····@gigamonkeys.com
Gigamonkeys Consulting * http://www.gigamonkeys.com/
Practical Common Lisp * http://www.gigamonkeys.com/book/
Timofei Shatrov wrote:
> (setf x '(1 2 3))
Note that '(1 2 3) is a constant, which a Lisp program cannot modify
without losing conformity to ANSI CL.
> (setf y x) (setf z x)
>
> I want to be able to extend y and z so they stay synchronized. For
> example (add-to-end y 4) makes both y and z '(1 2 3 4).
What this means is that you want Y and Z to be two names of one
variable.
I don't know of any way to do this, short of using symbol macros.
(defvar x (list 1 2 3))
(define-symbol-macro z x)
Now z is a synonym for x. The question is, why do you need two names
for the same thing? The one justification is that someone else named
the original thing and the name is too inconveniently long:
(define-symbol-macro mypackage:short
yourpackage:some-pretty-darn-long-name)
> But how to extend the list from another side so the pointer stays at the
> same place? Is it safe to use nreverse like that:
A better question is, what if Y starts out as an empty list, so that
its value holds the symbol NIL? You cannot extend the NIL object so
that another copy of it in another variable inherits that extension.
That is to say, an empty list cannot be destructively modified to a
non-empty one.
That is why what you are asking for essentially requires a single
variable with multiple names. That covers all the cases.
> (defun add-to-start (list value)
> (nreverse list) (add-to-end list value) (nreverse list))
>
> It works, but looking at Hyperspec I'm not sure if nreverse would be
> behaving well all the time.
NREVERSE keeps all of the cons cells of a list, but rearranges their
order. All references to the original list will become references to
the last cons of the newly rearranged list.
On 6 Aug 2005 10:28:45 -0700, "Kaz Kylheku" <········@gmail.com> tried
to confuse everyone with this message:
>
>Now z is a synonym for x. The question is, why do you need two names
>for the same thing?
The user can input different commands with different syntax. There is a
hash-table that corresponds the first word in command to its possible
syntaxes. Some commands are naturally synonyms like "take" and "get". So
if a user extends the "get" command with a new syntax the "take" command
should be extended as well (although the user has the choice to extend
them independently).
Anyway, I've did it with a one slot structure. Symbol-macros don't work
in my case because (gethash foo bar) is not a symbol :).
--
|a\o/r|,-------------.,---------- Timofei Shatrov aka Grue ------------.
| m"a ||FC AMKAR PERM|| mail: grue at mail.ru http://grue3.tripod.com |
| k || PWNZ J00 || Kingdom of Loathing: Grue3 lvl 18 Seal Clubber |
`-----'`-------------'`-------------------------------------------[4*72]
Pascal Bourguignon wrote:
> "Kaz Kylheku" <········@gmail.com> writes:
>
> > Timofei Shatrov wrote:
> >> (setf x '(1 2 3))
> >
> > Note that '(1 2 3) is a constant, which a Lisp program cannot modify
> > without losing conformity to ANSI CL.
> > [...]
> > NREVERSE keeps all of the cons cells of a list, but rearranges their
> > order. All references to the original list will become references to
> > the last cons of the newly rearranged list.
>
> You started well, but unfortunately, CLHS doesn't specifies the later.2
> Implementations are allowed to do this:
Ah yes. NREVERSE can for instance work by keeping the cell linkage
exactly as it is, while reshuffling the contents of the CAR fields.