Mikalai wrote:
> Can you point any good / standard implementation of doubly linked
> lists?
> Thanks.
>
What, in Lisp? You'd need something like:
(defclass double-cons-cell ()
value
previous
next)
Where previous and next are double-cons-cells themselves.
Eli Gottlieb wrote:
> You'd need something like:
>
> (defclass double-cons-cell ()
> value
> previous
> next)
>
> Where previous and next are double-cons-cells themselves.
How about dotted lists: (value previous . next)
(CAR '(value previous . next)) => value
(CADR '(value previous . next)) => previous
(CDDR '(value previous . next)) => next
Then you can think of 'AD' as 'AscenD', and 'DD' as 'DescenD'.
But tread gently, or your head will start to spin...
Mattias
"Mattias Nilsson" <········@bredband.net> writes:
> Eli Gottlieb wrote:
>
> > You'd need something like:
> >
> > (defclass double-cons-cell ()
> > value
> > previous
> > next)
> >
> > Where previous and next are double-cons-cells themselves.
>
> How about dotted lists: (value previous . next)
>
> (CAR '(value previous . next)) => value
> (CADR '(value previous . next)) => previous
> (CDDR '(value previous . next)) => next
>
> Then you can think of 'AD' as 'AscenD', and 'DD' as 'DescenD'.
> But tread gently, or your head will start to spin...
Here's some basic stuff based on that idea:
<URL: http://rydis.no-ip.org:11147/src/dll.lisp >.
No guarantees or anything, of course, but I think it worked a year
or two ago, at least.
',mr
--
[Emacs] is written in Lisp, which is the only computer language that is
beautiful. -- Neal Stephenson, _In the Beginning was the Command Line_
Martin Rydstr|m wrote:
> "Mattias Nilsson" <········@bredband.net> writes:
>
>>Eli Gottlieb wrote:
>>
>>
>>>You'd need something like:
>>>
>>>(defclass double-cons-cell ()
>>> value
>>> previous
>>> next)
>>>
>>>Where previous and next are double-cons-cells themselves.
>>
>>How about dotted lists: (value previous . next)
>>
>>(CAR '(value previous . next)) => value
>>(CADR '(value previous . next)) => previous
>>(CDDR '(value previous . next)) => next
>>
>>Then you can think of 'AD' as 'AscenD', and 'DD' as 'DescenD'.
>>But tread gently, or your head will start to spin...
>
>
> Here's some basic stuff based on that idea:
> <URL: http://rydis.no-ip.org:11147/src/dll.lisp >.
>
> No guarantees or anything, of course, but I think it worked a year
> or two ago, at least.
>
> ',mr
>
Doubly linked lists are hard to implement without a reference or pointer
type (a reference can only point to a known object or nil, that's the
difference). Why doesn't Lisp have references?
From: Bill Atkins
Subject: Re: Doubly-linked list implementation?
Date:
Message-ID: <87vevxku17.fsf@rpi.edu>
Eli Gottlieb <···········@gmail.com> writes:
> Martin Rydstr|m wrote:
>> "Mattias Nilsson" <········@bredband.net> writes:
>>
>>>Eli Gottlieb wrote:
>>>
>>>
>>>>You'd need something like:
>>>>
>>>>(defclass double-cons-cell ()
>>>> value
>>>> previous
>>>> next)
>>>>
>>>>Where previous and next are double-cons-cells themselves.
>>>
>>>How about dotted lists: (value previous . next)
>>>
>>>(CAR '(value previous . next)) => value
>>>(CADR '(value previous . next)) => previous
>>>(CDDR '(value previous . next)) => next
>>>
>>>Then you can think of 'AD' as 'AscenD', and 'DD' as 'DescenD'.
>>>But tread gently, or your head will start to spin...
>> Here's some basic stuff based on that idea:
>> <URL: http://rydis.no-ip.org:11147/src/dll.lisp >.
>> No guarantees or anything, of course, but I think it worked a year
>> or two ago, at least.
>> ',mr
>>
> Doubly linked lists are hard to implement without a reference or
> pointer type (a reference can only point to a known object or nil,
> that's the difference). Why doesn't Lisp have references?
What Lisp are you talking about? In Common Lisp, all objects (except
for numbers and characters, at a minimum) are references. This is how
eq works and why you must call copy-seq and copy-tree.
Implementing a doubly-linked list in Lisp is not hard in the least.
(defclass node ()
((value :accessor value-of :initarg :value)
(next :accessor next-of :initarg :next)
(prev :accessor prev-of :initarg :prev)))
Then you simply assign the next object to next and the previous object
to prev.
(let ((x (make-instance 'node :value 3))
(y (make-instance 'node :value 4)))
(setf (next-of x) y)
(setf (prev-of x) nil)
(setf (prev-of y) x)
(setf (next-of y) nil)
(eq x (prev-of (next-of x))))
;; => t
Bill
From: Bill Atkins
Subject: Re: Doubly-linked list implementation?
Date:
Message-ID: <873bj1w08s.fsf@rpi.edu>
···@zedat.fu-berlin.de (Stefan Ram) writes:
> Bill Atkins <············@rpi.edu> writes:
>>>Doubly linked lists are hard to implement without a reference
>>>or pointer type (a reference can only point to a known object
>>>or nil, that's the difference). Why doesn't Lisp have
>>>references?
>>What Lisp are you talking about? In Common Lisp, all objects
>>(except for numbers and characters, at a minimum) are
>>references.
>
> Yes, that's also the way I recently implemented a traversal
> for property lists to enumerate every property name.
>
> ( let
> ( ( x plist )) ; let x point to the start of the propertylist
> ( loop while x do
> ( let*
> ( ( name ( car x ))
> ( value ( getf plist name )))
> ( use name value )
> ( setq x( cddr x ))))) ; let x point to the next pair
The spacing in your code is really annoying - as others have pointed
out, it is difficult to read such bizarrely formatted code.
Here is the standard way of formatting your snippet:
(let ((x plist))
(loop while x do
(let* ((name (car x))
(value (getf plist name)))
(use name value)
(setq x (cddr x)))))
That code is not particularly idiomatic, though - see my sample below.
>
> I tried to find a special plist loop like "dolist", but
> did not find one in Common Lisp, so I used the above approach.
>
> I also read recommendations to use hash lists instead of the
> �historic� plists. But I believe that for name-value-pair-sets
> with only a few pairs, property list are still a good choice.
>
> In a similar Emacs Lisp loop, I found the author using "(cdr
> (cdr x))" instead of "(cddr x)" and wandered why he was using
> this more complicated notation.
There should never be a situation where (cddr x) has any kind of speed
advantage over (cdr (cdr x)). I'm not sure I follow what you're
saying.
> Now I suddenly see, that in the above code �(get plist name )�
> seems not to be the most efficient choice, �(cadr x)� should
> be more efficient. I will try this.
A simple way to enumerate the property names of a plist is:
(loop for name in plist by #'cddr
collect name)
For example:
(defvar x '(:plis 3 :foo 3 :bar 5 :baz 44)) ;; => X
(loop for name in x by #'cddr
collect name) ;; => (:plis :foo :bar :baz)
--
Bill Atkins
Bill Atkins <············@rpi.edu> writes:
> ···@zedat.fu-berlin.de (Stefan Ram) writes:
>
>> Bill Atkins <············@rpi.edu> writes:
>>>>Doubly linked lists are hard to implement without a reference
>>>>or pointer type (a reference can only point to a known object
>>>>or nil, that's the difference). Why doesn't Lisp have
>>>>references?
>>>What Lisp are you talking about? In Common Lisp, all objects
>>>(except for numbers and characters, at a minimum) are
>>>references.
>>
>> Yes, that's also the way I recently implemented a traversal
>> for property lists to enumerate every property name.
>>
>> ( let
>> ( ( x plist )) ; let x point to the start of the propertylist
>> ( loop while x do
>> ( let*
>> ( ( name ( car x ))
>> ( value ( getf plist name )))
>> ( use name value )
>> ( setq x( cddr x ))))) ; let x point to the next pair
>
> The spacing in your code is really annoying - as others have pointed
> out, it is difficult to read such bizarrely formatted code.
>
> Here is the standard way of formatting your snippet:
>
> (let ((x plist))
> (loop while x do
> (let* ((name (car x))
> (value (getf plist name)))
> (use name value)
> (setq x (cddr x)))))
>
> That code is not particularly idiomatic, though - see my sample below.
>
>>
>> I tried to find a special plist loop like "dolist", but
>> did not find one in Common Lisp, so I used the above approach.
>>
>> I also read recommendations to use hash lists instead of the
>> �historic� plists. But I believe that for name-value-pair-sets
>> with only a few pairs, property list are still a good choice.
>>
>> In a similar Emacs Lisp loop, I found the author using "(cdr
>> (cdr x))" instead of "(cddr x)" and wandered why he was using
>> this more complicated notation.
>
> There should never be a situation where (cddr x) has any kind of speed
> advantage over (cdr (cdr x)). I'm not sure I follow what you're
> saying.
Try: (disassemble (compile nil (lambda (x) (cddr x))))
and: (disassemble (compile nil (lambda (x) (cdr (cdr x)))))
In clisp we get the same output.
In any case, car, cdr, cddr, etc are low level functions.
You should use abstractions. For example:
(defun pkey (x) (car x))
(defun pvalue (x) (cadr x))
(defun pnext (x) (cddr x))
Now, assume you have a different kind of data structure, where your
abstractions are:
(defun ostuff (x) (car x))
(defun orest (x) (cdr x))
and you want to skip one rest:
(defun oskip (x) (orest (orest x)))
When you disassemble oskip and pnext, you may notice they're identical.
Now, if you are lazy, and you are just prototyping some
quick-and-dirty code, instead of defining these procedural
abstractions, you may use directly car, cdr, etc...
Then instead of oskip, you may write: (cdr (cdr x)) and instead of
pnext, you may write (cddr x) and still convey the nuance: you are
thinking about procedural abstractions you haven't implemented but
conceptually, these are not the same operation and they don't work on
the same type of data structure. Well, it's all only in your head
anyways. Of course, it would be an impair to write (cddr x) when you
mean oskip^W (cdr (cdr x))...
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
Eli Gottlieb <···········@gmail.com> writes:
> Martin Rydstr|m wrote:
> > "Mattias Nilsson" <········@bredband.net> writes:
> >>Eli Gottlieb wrote:
> >>>You'd need something like:
> >>>(defclass double-cons-cell ()
> >>> value
> >>> previous
> >>> next)
> >>>Where previous and next are double-cons-cells themselves.
> >>How about dotted lists: (value previous . next)
> >>(CAR '(value previous . next)) => value
> >>(CADR '(value previous . next)) => previous
> >>(CDDR '(value previous . next)) => next
> >>Then you can think of 'AD' as 'AscenD', and 'DD' as 'DescenD'.
> >>But tread gently, or your head will start to spin...
> > Here's some basic stuff based on that idea:
> > <URL: http://rydis.no-ip.org:11147/src/dll.lisp >.
> > No guarantees or anything, of course, but I think it worked a year
> > or two ago, at least.
> Doubly linked lists are hard to implement without a reference or
> pointer type (a reference can only point to a known object or nil,
> that's the difference). Why doesn't Lisp have references?
Since nil is a known object, I don't quite follow. A Lisp variable
can either point to a known object or be unbound. A cons can contain
any known object. It wasn't hard at all to do doubly-linked lists
with cons cells. Whether Lisp has references or not probably depends
on what you mean by references; I don't get your definition.
',mr
--
[Emacs] is written in Lisp, which is the only computer language that is
beautiful. -- Neal Stephenson, _In the Beginning was the Command Line_
Martin Rydstr|m wrote:
> Eli Gottlieb <···········@gmail.com> writes:
>
>>Martin Rydstr|m wrote:
>>
>>>"Mattias Nilsson" <········@bredband.net> writes:
>>>
>>>>Eli Gottlieb wrote:
>>>>
>>>>>You'd need something like:
>
>
>>>>>(defclass double-cons-cell ()
>>>>> value
>>>>> previous
>>>>> next)
>
>
>>>>>Where previous and next are double-cons-cells themselves.
>
>
>>>>How about dotted lists: (value previous . next)
>
>
>>>>(CAR '(value previous . next)) => value
>>>>(CADR '(value previous . next)) => previous
>>>>(CDDR '(value previous . next)) => next
>
>
>>>>Then you can think of 'AD' as 'AscenD', and 'DD' as 'DescenD'.
>>>>But tread gently, or your head will start to spin...
>
>
>>>Here's some basic stuff based on that idea:
>>><URL: http://rydis.no-ip.org:11147/src/dll.lisp >.
>>>No guarantees or anything, of course, but I think it worked a year
>>>or two ago, at least.
>
>
>>Doubly linked lists are hard to implement without a reference or
>>pointer type (a reference can only point to a known object or nil,
>>that's the difference). Why doesn't Lisp have references?
>
>
> Since nil is a known object, I don't quite follow. A Lisp variable
> can either point to a known object or be unbound. A cons can contain
> any known object. It wasn't hard at all to do doubly-linked lists
> with cons cells. Whether Lisp has references or not probably depends
> on what you mean by references; I don't get your definition.
>
> ',mr
>
If I have a pair of variables called x and y:
(setf x 10)
(setf y x)
(incf x)
y ====> 10
If Lisp had a reference type I could say:
(setf x 10)
(setf y &x) ; To use C's address-taking semantic
(incf x)
y ====> 11
That's what I mean by references. A variable is a reference to an
object in Lisp, but what about references to other variables? The only
form in which Lisp currently has those is instances of classes.
Eli Gottlieb <···········@gmail.com> writes:
> (setf y &x) ; To use C's address-taking semantic
This whole business is pretty silly, but what you want is ' instead of &:
CL-USER(1): (setf x 10)
10
CL-USER(2): (setf y 'x)
X
CL-USER(4): (setf x 11)
11
CL-USER(5): (symbol-value y)
11
/Jon
--
'j' - a n t h o n y at romeo/charley/november com
jayessay wrote:
> Eli Gottlieb <···········@gmail.com> writes:
>
>
>
>>(setf y &x) ; To use C's address-taking semantic
>
>
> This whole business is pretty silly, but what you want is ' instead of &:
>
> CL-USER(1): (setf x 10)
> 10
> CL-USER(2): (setf y 'x)
> X
> CL-USER(4): (setf x 11)
> 11
> CL-USER(5): (symbol-value y)
> 11
>
>
> /Jon
>
I didn't know about symbol-value. I suppose that allows symbols to be
used as first-class references, doesn't it?
Eli Gottlieb <···········@gmail.com> writes:
> jayessay wrote:
> > Eli Gottlieb <···········@gmail.com> writes:
> >
> >>(setf y &x) ; To use C's address-taking semantic
> > This whole business is pretty silly, but what you want is ' instead
> > of &:
> > CL-USER(1): (setf x 10)
> > 10
> > CL-USER(2): (setf y 'x)
> > X
> > CL-USER(4): (setf x 11)
> > 11
> > CL-USER(5): (symbol-value y)
> > 11
> > /Jon
> >
> I didn't know about symbol-value. I suppose that allows symbols to be
> used as first-class references, doesn't it?
I don't know what you mean by "first-class reference". Also, note
that the above is bogus because it doesn't declare *x* and *y*, and
note that it only makes sense if you have symbols (by declaring them
via defparameter, say, they will be dynamic and available, but
lexicals will (more than likely) be compiled away by runtime.)
You just have to know what it is you are doing and why and if it makes
any sense in the larger scheme (i.e., is it a good solution to a
problem or a crappy one based on old thinking, e.g., references).
As someone else noted, a "right way" to do this is to use boxing.
Also, you can search for locatives.
/Jon
--
'j' - a n t h o n y at romeo/charley/november com
Eli Gottlieb <···········@gmail.com> writes:
> jayessay wrote:
>> Eli Gottlieb <···········@gmail.com> writes:
>>
>>>(setf y &x) ; To use C's address-taking semantic
>> This whole business is pretty silly, but what you want is ' instead
>> of &:
>> CL-USER(1): (setf x 10)
>> 10
>> CL-USER(2): (setf y 'x)
>> X
>> CL-USER(4): (setf x 11)
>> 11
>> CL-USER(5): (symbol-value y)
>> 11
>> /Jon
>>
> I didn't know about symbol-value. I suppose that allows symbols to be
> used as first-class references, doesn't it?
A symbol is bigger than a cons. I'd use conses to build references.
But the point is that in practice, in real programs, you never need a
reference to a single number or characters. You alway have more
complex and compound data, like arrays, lists, structures or objects,
and then it works as you want:
(defparameter *x* (vector 10 20))
(defparameter *y* *x*)
(incf (aref *x* 0))
*y* --> (11 20)
That's why references or locative are almost never needed, and why
they're not in the standard.
What a surprise! Common Lisp is minimalist too!
--
__Pascal Bourguignon__ http://www.informatimago.com/
What is this talk of 'release'? Klingons do not make software 'releases'.
Our software 'escapes' leaving a bloody trail of designers and quality
assurance people in it's wake.
From: Marcin 'Qrczak' Kowalczyk
Subject: Re: Doubly-linked list implementation?
Date:
Message-ID: <87fymzb84m.fsf@qrnik.zagroda>
jayessay <······@foo.com> writes:
> This whole business is pretty silly, but what you want is ' instead of &:
>
> CL-USER(1): (setf x 10)
> 10
> CL-USER(2): (setf y 'x)
> X
> CL-USER(4): (setf x 11)
> 11
> CL-USER(5): (symbol-value y)
> 11
But this works only for special variables, not for lexical variables.
A reference to a lexical variable can be emulated by a pair of functions:
one to get its value and another to set it.
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Marcin 'Qrczak' Kowalczyk <······@knm.org.pl> writes:
> jayessay <······@foo.com> writes:
>
> > This whole business is pretty silly, but what you want is ' instead of &:
> >
> > CL-USER(1): (setf x 10)
> > 10
> > CL-USER(2): (setf y 'x)
> > X
> > CL-USER(4): (setf x 11)
> > 11
> > CL-USER(5): (symbol-value y)
> > 11
>
> But this works only for special variables, not for lexical variables.
Right, I already noted this.
/Jon
> A reference to a lexical variable can be emulated by a pair of functions:
> one to get its value and another to set it.
Among others
/Jon
--
'j' - a n t h o n y at romeo/charley/november com
Eli Gottlieb <···········@gmail.com> writes:
> That's what I mean by references. A variable is a reference to an
> object in Lisp, but what about references to other variables? The
> only form in which Lisp currently has those is instances of classes.
Why don't you search in google groups? This is asked all the time and
the answer is always the same. Search google groups for "reference"
or "locative".
--
__Pascal Bourguignon__ http://www.informatimago.com/
READ THIS BEFORE OPENING PACKAGE: According to certain suggested
versions of the Grand Unified Theory, the primary particles
constituting this product may decay to nothingness within the next
four hundred million years.
Pascal Bourguignon wrote:
> Eli Gottlieb <···········@gmail.com> writes:
>
>>That's what I mean by references. A variable is a reference to an
>>object in Lisp, but what about references to other variables? The
>>only form in which Lisp currently has those is instances of classes.
>
>
> Why don't you search in google groups? This is asked all the time and
> the answer is always the same. Search google groups for "reference"
> or "locative".
>
>
I've searched. Apparently references and locatives aren't a first-class
part of the language, because Lisp programmers feel that they are the
inferior C way of doing things and can usually be replaced with a
superior technique.
I missed the start of this thread so I apologize in advance if I'm way
off topic but... cl-containers has a double-linked list implementation.
--�
Gary Warren King
metabang.com
http://www.metabang.com/
Gary King wrote:
> I missed the start of this thread so I apologize in advance if I'm way
> off topic but... cl-containers has a double-linked list implementation.
Thank you for the reference. I was looking for something like this.
Mikalai.
>
> Here's some basic stuff based on that idea:
> <URL: http://rydis.no-ip.org:11147/src/dll.lisp >.
>
> No guarantees or anything, of course, but I think it worked a year
> or two ago, at least.
>
> ',mr
Thank you for the file. I'll look closer into it.
"Mikalai" <········@yahoo.com> writes:
> Can you point any good / standard implementation of doubly linked
> lists?
http://www.informatimago.com/develop/lisp
cvs -z3 -d ··················@cvs.informatimago.com:/usr/local/cvs/public/chrooted-cvs/cvs co common/common-lisp/dll.lisp
--
__Pascal Bourguignon__ http://www.informatimago.com/
In a World without Walls and Fences,
who needs Windows and Gates?