Account Options

  1. Sign in
The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Google Groups Home
« Groups Home
comp.lang.lisp
+ new post
About this group
Subscribe to this group
This is a Usenet group - learn more
Message from discussion Sharing of list elements in Common Lisp
The group you are posting to is a Usenet group. Messages posted to this group will make your email address visible to anyone on the Internet.
Your reply message has not been sent.
Your post was successful
 
From:
To:
Cc:
Followup To:
Add Cc | Add Followup-to | Edit Subject
Subject:
Validation:
For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon. Listen and type the numbers you hear
 
Kent M Pitman  
View profile  
 More options Jan 27 1999, 3:00 am
Newsgroups: comp.lang.lisp
From: Kent M Pitman <pit...@world.std.com>
Date: 1999/01/27
Subject: Re: Sharing of list elements in Common Lisp
Print | View thread | Show original | Report this message | Find messages by this author

Greg Menke <nos...@erols.com> writes:

Barry already answered this and nothing he said is false,
but I have a different take on the nature of your question
so consider this "additional data".

> In Common Lisp, is it possible to have a list item shared
> in 2 or more lists; ie:
> lista -> (a b c d)
> listb -> (1 c 2 3)
> where c is the same object?

Yes.  This is not a property just of Lisp, by the way, but of any
system which allows you to have pointers to objects with identity.
In Lisp, everything is a pointer, and everything is an object
with identity, so we don't use the word pointer except for
emphasis--it is not, as in other languages, the introduction of
an indirection.  Conceptually, all objects are indirect to start
with.  As such, both of the above lists contain pointers to an
abstract object (a symbol) c.

> By same object, I mean
> when c is deleted from one list, it disappears from the
> other.

This question is ill-formed.  Deletion has nothing to do with
an object, it has to do with the container to the object.  The
containers being different objects, it cannot be the case that
deletion from one implies deletion from the other.  If you
literally shared the two container objects, of course, it could be.
For example:
 (setq list0 '(b c d))
 (setq list1 (cons 'a list0))
 (setq list2 (cons 'a list0))
Now both list1 and list2 have c in them, but if you delete c
from list0 it will also disappear from list1 and list2, but only
because lists are recursive data structures and secretly the tail
of list1 and the tail of list2 are the same object as list0.  But
if the objects were distinct, as in
 (setq list3 (cons 'a (copy-list list0)))
then you would find that deleting c from list3 had no effect on
list0 (or on list1 or list2).

> It would also be desirable to preserve the linkage
> even if the item moves in one or both lists.

The linkage is preserved when you manipulate a list.  Lists are
about the object pointers in them, not about the recursive
nature of those object pointers.

Note that copy-list does not copy c.  for example,
 (setf (get 'c 'some-property) 'hello)
 (setq list4 (cons 'a (copy-list list0)))
 (get (third list4) 'some-property) => hello
The list has been copied, but not the object.

The same is true of lists, which are objects.  copy-list copies
the backbone of a list, it does not descend objects.  Consider:
 (setq item (cons 'hello 'there))
 (setq listx (list 'hi item 'howdy))
 (setq listy (copy-list list1))
 (setf (cdr item) 'sailor)
 item => (hello . sailor)
 listx => (hi (hello . sailor) howdy)
 listy => (hi (hello . sailor) howdy)
 (setq listx (delete item listx))
 listx => (hi howdy)
 listy => (hi howdy)
 item => (hello . sailor)

> Second, is it possible to record the position of
> an item in a large list so the item may be efficently
> retrieved?

Lisp is capable of implementing whatever storage structures any other
language can implement.  The question you're asking is about
philosophy and/or about algorithms.  It is not about Lisp.  That
doesn't make it a bad question.  But, if it helps, a good rule of
thumb is that if it's something that's possible in general, Lisp can
do it, and if it's something that is not possible in general, Lisp
can't do it.

There is some question of what you mean by "position" here.  There is
no real concept of a position in a list as an integer, since the list
might be a shared tail of fome other list, and the same object will
have different positions in the lists.  If you store the positions in
the list, you might as well just store the objects.  Also, lists are
sequential access, so knowing the position as an integer won't get you
to it any faster than searching.  You could have elements have
backpointers to the cons cell holding them, but then you have to have
one backpointer for each such containing list.  In some cases that may
be worth it, but in others not.  You could use arrays instead of
lists, and then sequential access can give way to indexed access.  You
can, for example, make the position in the list a property of the
object.  But then if you remove it, you have to decide whether to
leave the sibling objects in place (which can be done in efficient
time, but with inefficiency of space because you now have an element
that is empty) or else you can decide to move the sibling objects, and
update all their positions (which loses time--but if the accesses are
often and then updates are seldom, that can be ok).  None of what I
have said in this paragraph is just about lisp--any language would
have the exact same set of problems, which is why things like this are
usually taught in algorithms classes.  But Lisp can give you a
concrete way of feeling and articulating these limitations and
strengths of the world we live in.

> Third, is it possible to get a "handle" or pointer to a
> list item which is independent of its position, or presence
> in some other list?

Yes, and I've illustrated some above.  But you should think about
what you want to do that for because the answer is more specific
to different situations.  Is the position for lookup? If so, you
don't need a list at all if you already have the object.   Since
it is a pointer, you can modify it directly and all lists containing
it will see the update.  Is the position for addition/deletion of
siblings?  In this case, you may want backpointers to the cons
cell holding but you also may want a tree of some kind, not just
a linear list.  (It may be implemented with lists.)  Are the
positions for things that are finitely enumerable?  For example,
a list of the shift-keys on a character?  Perhaps a bit table would
be a better representation.  

The key thing to see in your question is that an object is itself
a pointer or handle to itself.  They are the same in Lisp.  So
you don't need to talk about lists to have that.  To the extent
that you do talk about lists, then you are talking only about
the list.  There is nothing in (A B C) which is not either A, or
B, or C (independent of the list) or else the container which
is ([ place for anything] [place for anything] [place for anything])
and if we'r talking about A,B,C we're not talking about the list
and vice versa.  So when you talk about "a pointer to an element
independent of its presence in other objects" you're just talking
about A (or B or C).  If you're talking about "a pointer to the
position" you're just talking about the list, independent of A
(or B or C).  You can implement other structures by other
representations or by other operators that do more bookkeeping,
but a list is just what I've said and nothing more.

Good luck.
 --Kent

p.s. Disclaimer: I didn't try any of the examples above.
     If they don't perform as advertised, it's probably a typo.


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Create a group - Google Groups - Google Home - Terms of Service - Privacy Policy
©2013 Google