From: Greg Menke
Subject: Sharing of list elements in Common Lisp
Date:
Message-ID: <socxxmta.fsf@erols.com>
Hi,
I've a couple questions, if you wouldn't mind considering
them....
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? By same object, I mean
when c is deleted from one list, it disappears from the
other. It would also be desirable to preserve the linkage
even if the item moves in one or both lists.
Second, is it possible to record the position of
an item in a large list so the item may be efficently
retrieved?
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?
Thanks,
Gregm
In article <············@erols.com>, Greg Menke <······@erols.com> wrote:
>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? By same object, I mean
>when c is deleted from one list, it disappears from the
>other. It would also be desirable to preserve the linkage
>even if the item moves in one or both lists.
A list is a chain of cons cells, in which the cars point to the list
elements, and the cdrs point to the next cons in the chain. If two lists
share the same cons cell, they'll have the same tail. E.g.
(setq common-tail '(a b c)) -> (A B C)
(setq list1 (append '(1 2 3) common-tail)) -> (1 2 3 A B C)
(setq list2 (append '(5 6) common-tail)) -> (5 6 A B C)
(setq list1 (delete 'b list1)) -> (1 2 3 A C)
list2 -> (5 6 A C)
However,
(setq list1 (delete 'a list1)) -> (1 2 3 C)
list2 -> (5 6 A C)
To understand why this is, I suggest you draw a diagram showing all the
cons cells and their linkages, then watch what happens when DELETE relinks
the cdr chain to remove the element.
>Second, is it possible to record the position of
>an item in a large list so the item may be efficently
>retrieved?
The POSITION function will return the numeric position of an element of a
list. However, retrieving an item from a list by its numeric position is
not efficient -- it's O(n). Arrays should be used when efficient indexing
is required.
>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?
The MEMBER function returns the cons cell whose car contains the found
object.
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Don't bother cc'ing followups to me.
Greg Menke <······@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.
Kent M Pitman <······@world.std.com> writes:
Thanks to all who replied! I come from a C background with lots
of time spent with those style pointers- hence my misunderstanding
of how cons's work.
I'll keep at it...
Regards,
Gregm
From: Howard R. Stearns
Subject: Doing the impossible (Re: Sharing of list elements in Common Lisp)
Date:
Message-ID: <36AF6B94.EA52720@elwood.com>
Kent M Pitman wrote:
> ... 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.
> ...
I'm probably misremembering this....
Kent will remember the slogan at Symbolics to the effect of something
like, "We make the difficult things easy (and vice versa)".
I think I remember ICAD had a similar saying to the effect of, "We make
the impossible, possible (and vice versa)". (And to think that we
always tried to claim that ICAD was NOT an AI company!)
I think the sales department has something to do with my (probably
distored) memory on this.
In article <················@elwood.com>, "Howard R. Stearns" <······@elwood.com> wrote:
> Kent M Pitman wrote:
> > ... 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.
> > ...
>
> I'm probably misremembering this....
>
> Kent will remember the slogan at Symbolics to the effect of something
> like, "We make the difficult things easy (and vice versa)".
Make the easy things easy and the difficult things possible.
--
http://www.lavielle.com/~joswig
From: Kent M Pitman
Subject: Re: Doing the impossible (Re: Sharing of list elements in Common Lisp)
Date:
Message-ID: <sfwiuds9p6j.fsf@world.std.com>
······@lavielle.com (Rainer Joswig) writes:
> In article <················@elwood.com>, "Howard R. Stearns" <······@elwood.com> wrote:
>
> > Kent M Pitman wrote:
> > > ... 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.
> > > ...
> >
> > I'm probably misremembering this....
> >
> > Kent will remember the slogan at Symbolics to the effect of something
> > like, "We make the difficult things easy (and vice versa)".
>
> Make the easy things easy and the difficult things possible.
No, at Symbolics there was a poster of Zippy the Pinheads receding
into infinity with the subtitle "At Symbolics we make hard problems
easy--and vice versa" on someone's door. It wasn't an official
company policy. But there were days when it seemed pretty darned true
(in both cases).
From: Will Fitzgerald
Subject: Re: Doing the impossible (Re: Sharing of list elements in Common Lisp)
Date:
Message-ID: <78puqe$gd3@news.net-link.net>
I just received a copy of Harlequin LispWorks 4.1 Professional. On the
outside of the box, it says:
We solve the hard problems.
Apparently, they don't take a stance on easy problems.
From: Kelly Murray
Subject: Re: Doing the impossible (Re: Sharing of list elements in Common Lisp)
Date:
Message-ID: <36B0D42C.6BA16F04@IntelliMarket.Com>
I had a quote from Carl Mayes I put in my .sig a couple years ago:
"Those who can see the invisible, can do the impossible."
-Kelly Murray ···@intellimarket.com
Greg Menke <······@erols.com> writes:
< Hi,
<
< I've a couple questions, if you wouldn't mind considering
< them....
<
< 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? By same object, I mean
< when c is deleted from one list, it disappears from the
< other. It would also be desirable to preserve the linkage
< even if the item moves in one or both lists.
<
< Second, is it possible to record the position of
< an item in a large list so the item may be efficently
< retrieved?
<
< 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?
USER(1): (defvar *c* 'c)
*C*
USER(2): (defvar *list* (list 'a 'b *c*))
*LIST*
USER(3): *list*
(A B C)
USER(4): (setq *c* (list *c* 'd))
(C D)
USER(5): *list*
(A B C)
The variable `*c*' `points' to the object `c'.
USER(6): (setq *c* (nthcdr 2 *list*))
(C)
The variable `*c*' `points' to a place, the second cdr in `*list*'.
USER(7): *c*
(C)
USER(8): (setf (cdr *c*) 'd)
D
USER(9): *list*
(A B C . D)
USER(10):
Here is an example of a container with another container (a list with
a vector).
> (defvar *x* (vector 1 2 3))
*X*
> (setq *list* (list 1 2 *x*))
(1 2 #(1 2 3))
> *list*
(1 2 #(1 2 3))
> (setf (aref *x* 0) -1)
-1
> *list*
(1 2 #(-1 2 3))
Hope this helps some.