Hi,
I think I need destructive modification of lists. I want to modify a tree and want the subtrees to
keep their identity, thus I want to be able to destructively modify the whole thing.
Perhaps this is a wrong approach, perhaps I'm reinventing the wheel. Any pointers and hints very
welcome.
Here is what I am working on (all functions starting with n are destructive (all :))), the following
r is for recursive (shall work on a tree), further three letters 'ins' for insert, 'del' for delete,
'upd' for update):
(defun ndelcar (list)
(if (cdr list)
(progn
(rplaca list (cadr list))
(rplacd list (cddr list)))
(setf (nthcdr 0 list) nil)))
(defun ndelnth (n list)
(if (= n 0)
(ndelcar list)
(progn
(setf (nthcdr n list) (nthcdr (1+ n) list))
list)))
(defun ndelitem (item list)
(loop for p = (position item list) do
(if p
(setf list (ndelnth p list))
(return list))))
(defun nrdelitem (item tree)
(setf tree (ndelitem item tree))
(loop for i from 0 to (1- (length tree)) do
(when (consp (nth i tree))
(setf (nth i tree) (nrdelitem item (nth i tree)))))
tree)
(defun ninscar (item list)
(rplacd list (cons (car list) (cdr list)))
(rplaca list item))
(defun ninsnth (item n list)
(if (zerop n)
(ninscar item list)
(progn
(setf (nthcdr n list) (cons item (nthcdr n list)))
list)))
(defun ninsitem (new-item before-item list)
(let ((p (position before-item list)))
(when p (ninsnth new-item p list))))
(defun nupditem (new-item old-item list)
(loop for p = (position old-item list) do
(if p
(setf (nth p list) new-item)
(return)))
list)
Thanks
Andreas
"Andreas Thiele" <······@nospam.com> writes:
> I think I need destructive modification of lists. I want to modify a
> tree and want the subtrees to keep their identity, thus I want to
> be able to destructively modify the whole thing.
>
> Perhaps this is a wrong approach, perhaps I'm reinventing the
> wheel. Any pointers and hints very welcome.
>
> Here is what I am working on (all functions starting with n are
> destructive (all :))), the following r is for recursive (shall work
> on a tree), further three letters 'ins' for insert, 'del' for
> delete, 'upd' for update):
>
> (defun ndelcar (list) (if (cdr list) (progn (rplaca list (cadr
> list)) (rplacd list (cddr list))) (setf (nthcdr 0 list) nil)))
>
> (defun ndelnth (n list)
> (if (= n 0)
> (ndelcar list)
> (progn
> (setf (nthcdr n list) (nthcdr (1+ n) list))
> list)))
(delete-if (constantly t) list :start n :end (1+ n)) ; read below!
> (defun ndelitem (item list)
> (loop for p = (position item list) do
> (if p
> (setf list (ndelnth p list))
> (return list))))
(delete item list :count 1)
> (defun nrdelitem (item tree)
> (setf tree (ndelitem item tree))
> (loop for i from 0 to (1- (length tree)) do
> (when (consp (nth i tree))
> (setf (nth i tree) (nrdelitem item (nth i tree)))))
> tree)
> (defun ninscar (item list)
> (rplacd list (cons (car list) (cdr list)))
> (rplaca list item))
>
> (defun ninsnth (item n list)
> (if (zerop n)
> (ninscar item list)
> (progn
> (setf (nthcdr n list) (cons item (nthcdr n list)))
> list)))
>
> (defun ninsitem (new-item before-item list)
> (let ((p (position before-item list)))
> (when p (ninsnth new-item p list))))
>
> (defun nupditem (new-item old-item list)
> (loop for p = (position old-item list) do
> (if p
> (setf (nth p list) new-item)
> (return)))
> list)
(nsubstitute new-item old-item list :count 1)
How are you sure to never call (ndelnth 0 '(1)) ?
You need some more abstraction, to implement abstract data types.
For this, the first step would be to define constructor functions.
With CL destructive functions, when you delete the last element, there
remains no head CONS cell in the list to identify the list. The
solution is to allocate a list "header" object. This can be a cons, an
array, a structure, a CLOS object, it doesn't matter. But it must be
an object that won't be deleted even when the list is empty. If you
have this list header, then you can delete the last element of the
list and still keep the list identity: two different empty "lists" can
be distinguished, which is not the case with lisp lists (they are all
NIL).
Ok, now about DELETE, DELETE-IF, NSUBSTITUE and all the other CL
destructive functions: they are _not_ _mandated_ to be destructive.
This is only an option up to the implementation. Moreover, they are
not mandated to keep the identity of the list, that is the first cons
as first cons. Even if they are really destructinve, they could very
well shuffle the cons cells and return a different one than the first.
If you keep a list header, you can destruct or not destruct the cons
cells of the list, this doesn't matter, since you keep the identity
of the list by way of the header.
You need to implement your own really destructive functions only if
you want to spare copying the cons cells (only when you are optimizing!).
(make-tlist) --> tlist
(tlist-empty-p tlist) --> boolean
(tlist-length tlist) --> integer
(tlist-first tlist) --> item
(tlist-rest tlist) --> tlist ; makes a new tlist
(tlist-cons item tlist) --> tlist ; makes a new tlist
...
(tlist-ncons item tlist) --> tlist ; destructively cons item to the tlist
(tlist-nsnoc item tlist) --> tlist ; destructively append the item to the tlist
(tlist-concatenate tlist...) --> tlist ; makes a new tlist
(tlist-delete item tlist)
(tlist-delete-nth n tlist)
(tlist-from-list list) --> tlist
(tlist-to-list tlist) --> list
And similar with threes.
(make-ttree &key label children) --> ttree
(ttree-empty-p ttree)
(ttree-label ttree) --> object
(ttree-children ttree) --> tlist ; of children
(ttree-delete item ttree)
...
--
__Pascal Bourguignon__ http://www.informatimago.com/
PUBLIC NOTICE AS REQUIRED BY LAW: Any use of this product, in any
manner whatsoever, will increase the amount of disorder in the
universe. Although no liability is implied herein, the consumer is
warned that this process will ultimately lead to the heat death of
the universe.
"Pascal Bourguignon" <···@informatimago.com> schrieb im Newsbeitrag
···················@thalassa.informatimago.com...
> ...
Pascal,
thanks for your fast and helpful response. I was perfectly mislead. It was the first time I was
working with LispWorks capi:tree-view class and I did not immediately find the test function for
individual 'nodes'. So I thought when simply throwing in a syntax tree as Lisp list (into the
tree-view) I'd have to keep the 'nodes' (in this case sublists) eq when writing editing code.
Wrong - there is a test function.
> ...
>> (defun ndelitem (item list)
>> (loop for p = (position item list) do
>> (if p
>> (setf list (ndelnth p list))
>> (return list))))
>
> (delete item list :count 1)
(ndelitem item list) == (delete item list) but definitely modifies list.
While I was mislead, on the other hand I understood another tiny bit of Lisp. It is possible to
write functions which 'directly' manipulate cons cells. This is why I wrote these functions. I knew
that Lisps destructive functions are not mandated to be destructive and thus may not leave the first
cons cell intact. My functions try to this. Now I'm happy I don't need them :))
> ...
> How are you sure to never call (ndelnth 0 '(1)) ?
> ...
I didn't understand this at first. (ndelnth 0 '(1)) simply returns nil. - But - this is the point.
I loose the first cons cell and thus I loose the identity of the list (sublist).
This is the first time I wanted to manipulate individual nodes in a tree represented by a list.
Doesn't this reveal somehow 'a weak point' of Lisp? (Each time I want to access a tree node I have
to tranverse the whole tree.)
Fortunately in my case this is no performance issue I parse RTF files into a list. My primary
interest is running functions across the whole tree - not accessing individual 'nodes'. Even if I
wanted this I found a different simple solution. The tree-view is just a debbung aid to look into
real world RTF-Files.
Andreas
"Andreas Thiele" <······@nospam.com> writes:
>
> Doesn't this reveal somehow 'a weak point' of Lisp? (Each time I want
> to access a tree node I have to tranverse the whole tree.)
No. You can always retain a pointer to a particular tree node. You
then have direct access to that node.
If you want the nodes themselves to be destructively modifiable, you can
either use destructive list operations (remembering the caveat about not
being able to destructively eliminate the last remaining element of a
list). Or you could make up your tree out of DESTRUCT or CLOS
instances, and then modify their slots.
--
Thomas A. Russ, USC/Information Sciences Institute
"Thomas A. Russ" <···@sevak.isi.edu> schrieb im Newsbeitrag ····················@sevak.isi.edu...
> "Andreas Thiele" <······@nospam.com> writes:
>>
>> Doesn't this reveal somehow 'a weak point' of Lisp? (Each time I want
>> to access a tree node I have to tranverse the whole tree.)
>
> No. You can always retain a pointer to a particular tree node. You
> then have direct access to that node.
>
> If you want the nodes themselves to be destructively modifiable, you can
> either use destructive list operations (remembering the caveat about not
> being able to destructively eliminate the last remaining element of a
> list). Or you could make up your tree out of DESTRUCT or CLOS
> instances, and then modify their slots.
> ...
Thomas,
can you point me to a tiny 'pointer to a particular tree node' example?
Andreas
"Andreas Thiele" <······@nospam.com> writes:
> "Thomas A. Russ" <···@sevak.isi.edu> schrieb im Newsbeitrag ····················@sevak.isi.edu...
>> "Andreas Thiele" <······@nospam.com> writes:
>>>
>>> Doesn't this reveal somehow 'a weak point' of Lisp? (Each time I want
>>> to access a tree node I have to tranverse the whole tree.)
>>
>> No. You can always retain a pointer to a particular tree node. You
>> then have direct access to that node.
>>
>> If you want the nodes themselves to be destructively modifiable, you can
>> either use destructive list operations (remembering the caveat about not
>> being able to destructively eliminate the last remaining element of a
>> list). Or you could make up your tree out of DESTRUCT or CLOS
>> instances, and then modify their slots.
>> ...
>
> Thomas,
>
> can you point me to a tiny 'pointer to a particular tree node' example?
Here is one:
[618]> (second
(tree-children
(tree-make-tree
'root
(list (tree-make-tree
'left (list (tree-make-tree
'left-left
(list (tree-make-leaf 'lll) (tree-make-leaf 'llr)))
(tree-make-tree 'left-right (list (tree-make-leaf 'lrl)
(tree-make-leaf 'lrr)))))
(tree-make-tree
'right (list (tree-make-tree
'right-left
(list (tree-make-leaf 'rll) (tree-make-leaf 'rlr)))
(tree-make-tree 'right-right (list (tree-make-leaf 'rrl)
(tree-make-leaf 'rrr)))))))))
#S(ST :LABEL RIGHT
:CHILDREN
(#S(ST :LABEL RIGHT-LEFT :CHILDREN (RLL RLR))
#S(ST :LABEL RIGHT-RIGHT :CHILDREN (RRL RRR))))
[619]>
--
__Pascal Bourguignon__ http://www.informatimago.com/
Kitty like plastic.
Confuses for litter box.
Don't leave tarp around.
"Andreas Thiele" <······@nospam.com> writes:
> "Pascal Bourguignon" <···@informatimago.com> schrieb im Newsbeitrag ···················@thalassa.informatimago.com...
>> "Andreas Thiele" <······@nospam.com> writes:
>>> ...
>>> can you point me to a tiny 'pointer to a particular tree node' example?
>>
>> Here is one:
>>
>> [618]> (second
>> (tree-children
>> (tree-make-tree
>> 'root
>> (list (tree-make-tree
>> 'left (list (tree-make-tree
>> 'left-left
>> (list (tree-make-leaf 'lll) (tree-make-leaf 'llr)))
>> (tree-make-tree 'left-right (list (tree-make-leaf 'lrl)
>> (tree-make-leaf 'lrr)))))
>> (tree-make-tree
>> 'right (list (tree-make-tree
>> 'right-left
>> (list (tree-make-leaf 'rll) (tree-make-leaf 'rlr)))
>> (tree-make-tree 'right-right (list (tree-make-leaf 'rrl)
>> (tree-make-leaf 'rrr)))))))))
>> #S(ST :LABEL RIGHT
>> :CHILDREN
>> (#S(ST :LABEL RIGHT-LEFT :CHILDREN (RLL RLR))
>> #S(ST :LABEL RIGHT-RIGHT :CHILDREN (RRL RRR))))
>> [619]>
>> ...
>
> OK, my question was not precise. Where is the 'pointer'?
All lisp values are pointers!
(But possibly some fixnums and characters, and even, it's not sure,
but it doesn't matter because they're not mutable).
> Did Thomas mean something like:
>
> CL-USER 86 > (setf tree '(1 (2 3)))
> (1 (2 3))
>
> CL-USER 87 > (setf pointer (cdr tree))
> ((2 3))
>
> CL-USER 88 > (rplaca pointer 9)
> (9)
>
> CL-USER 89 > tree
> (1 9)
>
> when representing the tree as list?
Yes.
--
__Pascal Bourguignon__ http://www.informatimago.com/
CONSUMER NOTICE: Because of the "uncertainty principle," it is
impossible for the consumer to simultaneously know both the precise
location and velocity of this product.
On Wed, 22 Nov 2006 12:06:12 +0100,
"Andreas Thiele" <······@nospam.com> wrote:
>"Thomas A. Russ" <···@sevak.isi.edu> schrieb
>im Newsbeitrag ····················@sevak.isi.edu...
>>"Andreas Thiele" <······@nospam.com> writes:
>>> Doesn't this reveal somehow 'a weak point' of Lisp? (Each time I
>>> want to access a tree node I have to tranverse the whole tree.)
>>
>> No. You can always retain a pointer to a particular tree node. You
>> then have direct access to that node.
>>
>> If you want the nodes themselves to be destructively modifiable, you
>> can either use destructive list operations (remembering the caveat
>> about not being able to destructively eliminate the last remaining
>> element of a list). Or you could make up your tree out of DESTRUCT
>> or CLOS instances, and then modify their slots. ...
>
> Thomas,
> can you point me to a tiny 'pointer to a particular tree node'
> example?
As Pascal has already written, "all Lisp values are pointers". For
instance, try to understand why the last expression below evaluates to T.
CL-USER> (defparameter *foo* (list 1 2))
*FOO*
CL-USER> (defparameter *bar* (list 3 4))
*BAR*
CL-USER> *foo*
(1 2)
CL-USER> *bar*
(3 4)
CL-USER> (nconc (cdr *foo*) *bar*)
(2 3 4)
CL-USER> *foo*
(1 2 3 4)
CL-USER> *bar*
(3 4)
CL-USER> (defparameter *x* (cons *foo* *bar*))
*X*
CL-USER> (and (eq (cddar *X*) (cdr *X*))
(eq (cdr *X*) *bar*)
(eq (cddr *foo*) *bar*))
T
CL-USER>
If you try to 'visualize' what each symbol is bound to, you should 'see'
something like the following picture (in which each cons cell is
represented as a pair of 'boxes'):
+---+---+
| | |
*X* -----> | x | x |
| | | | |
+-|-+-|-+
| |
| `-------------------.
| |
v v
+---+---+ +---+---+ +---+---+ +---+---+
| | | | | | | | | | | N |
*FOO* ---> | 1 | x---->| 2 | x---->| 3 | x---->| 4 | I |
| | | | | | | | | | | L |
+---+---+ +---+---+ +---+---+ +---+---+
^
|
*BAR* -------------------------------'
So, there you have it. Exactly as Pascal said, "everything is a
pointer" :-)
- Giorgos
"Andreas Thiele" <······@nospam.com> writes:
>> ...
>> How are you sure to never call (ndelnth 0 '(1)) ?
>> ...
>
> I didn't understand this at first. (ndelnth 0 '(1)) simply returns
> nil. - But - this is the point. I loose the first cons cell and
> thus I loose the identity of the list (sublist).
>
> This is the first time I wanted to manipulate individual nodes in a
> tree represented by a list.
>
> Doesn't this reveal somehow 'a weak point' of Lisp? (Each time I
> want to access a tree node I have to tranverse the whole tree.)
"Lisp has no syntax. Lisp has no parentheses. Lisp as no list."
http://groups.google.com/group/comp.lang.lisp/msg/6ec4dab4a8d57f6e
Having no list datatype may be seen as a weakness, but on the other
hand, collapsing the CONS, LIST and (syntactic) TREE into one data
type allows to use the same functions on the three data types (long
before OOP was invented), and it allows to make "puns" that increase
the expressiveness of the language. Of course, in terms of software
engineering, it may not be a good idea. But in term of practical ease
of use, it's very nice.
--
__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.
"Andreas Thiele" <······@nospam.com> writes:
> Hi,
>
> (defun ndelcar (list)
> (if (cdr list)
> (progn
> (rplaca list (cadr list))
> (rplacd list (cddr list)))
> (setf (nthcdr 0 list) nil)))
This doesn't work for lists of length 1.
In my implementation (ACL 5.0.1), there isn't even a SETF function for
NTHCDR.
But even if that were solved it wouldn't work.
Try ndelcar on a list with only one element.
You will find that it is not, in fact, destructive.
Don't spend a lot of time tyring to solve this problem, for you cannot
destructively change a list to NIL, because the pointer to the head of
the list is not accessible inside the function call.
(It is often a good idea to test your code before posting it.)
--
Thomas A. Russ, USC/Information Sciences Institute
"Thomas A. Russ" <···@sevak.isi.edu> schrieb im Newsbeitrag ····················@sevak.isi.edu...
> "Andreas Thiele" <······@nospam.com> writes:
>
>> Hi,
>>
>> (defun ndelcar (list)
>> (if (cdr list)
>> (progn
>> (rplaca list (cadr list))
>> (rplacd list (cddr list)))
>> (setf (nthcdr 0 list) nil)))
>
> This doesn't work for lists of length 1.
> In my implementation (ACL 5.0.1), there isn't even a SETF function for
> NTHCDR.
>
> But even if that were solved it wouldn't work.
> Try ndelcar on a list with only one element.
> You will find that it is not, in fact, destructive.
>
> Don't spend a lot of time tyring to solve this problem, for you cannot
> destructively change a list to NIL, because the pointer to the head of
> the list is not accessible inside the function call.
>
> (It is often a good idea to test your code before posting it.)
>
>
> --
> Thomas A. Russ, USC/Information Sciences Institute
Ooops!
I don't remember why I thought there is a SETF for nthcdr.
You are right it is not in the specs.
In my Lisp the following happens:
CL-USER 7 > (ndelcar '(0 1 2))
(1 2)
CL-USER 8 > (ndelcar '(0 1))
(1)
CL-USER 9 > (ndelcar '(0))
NIL
So I use nthcdr in an implementation specific way.
Fortunately the whole thread is academic. I already abandoned this approach.
I was only interested if it is possible to _modify_ a given list.
Now I think this is not a lispy approach, it is more OO like.
Fortunately again I don't need OO I can work on a list representing
my source tree with ease.
Andreas