sharing list structure

sharing list structure

[Joe Corneli]

I'm not sure how to do the following:

 I have a list A, that grows, shrinks, and changes.

 I want to have a list B that includes list A within
 its list structure, along with other things, and that
 automatically keeps the "A" part of itself in synch
 with A.

If this was C, I think what I guess what I would say I want is a
"pointer to A".

But the elisp manual says --

   A note to C programmers: in Lisp, we do not distinguish between
   "holding" a value and "pointing to" the value, because pointers in
    Lisp are implicit.

So I guess what I want is an "implicit pointer" to A.


Looking at the box diagrams in the manual, it seemed to me that
everything would be taken care of if I used "setcdr" to build the list
B.  But that didn't quite work:

(progn
  (setq A '(1 2 3))
  (setq B (list 'foo))
  (setcdr B A)
  (setq A (append A (list 4)))
  B)
;=> (foo 1 2 3)

If I handle A with kid gloves, then B comes out right:

(progn
  (setq A '(1 2 3))
  (setq B (list 'foo))
  (setcdr B A)
  (setcdr (nthcdr 2 A) (list 4))
  B)
;=>(foo 1 2 3 4)

But is this the only way to go?  If it was possible, I would like to
set things up so that I could do anything I wanted to do to A, and
have B simply reflect that value at the end.

Is there a way to accomplish this?  And if it can't be done with
list structure alone, what other suggestions can you make?

Re: sharing list structure

[Denis Bueno]

On Thu, 24 Mar 2005 17:48:57 -0600, Joe Corneli
<jcorneli@math.utexas.edu> wrote:
> 
> I'm not sure how to do the following:

*snip*

> 
> So I guess what I want is an "implicit pointer" to A.
> 
> Looking at the box diagrams in the manual, it seemed to me that
> everything would be taken care of if I used "setcdr" to build the list
> B.  But that didn't quite work:
> 
> (progn
>   (setq A '(1 2 3))
>   (setq B (list 'foo))
>   (setcdr B A)
>   (setq A (append A (list 4)))
>   B)
> ;=> (foo 1 2 3)

The `append' doesn't alter the structure of the list A.

  (defvar *foo* (list 1 2 3))
  (append *foo* (list 4 5 6))
  *foo* => (1 2 3)

Hence, the result of append doesn't alter A's structure.

> If I handle A with kid gloves, then B comes out right:
> 
> (progn
>   (setq A '(1 2 3))
>   (setq B (list 'foo))
>   (setcdr B A)
>   (setcdr (nthcdr 2 A) (list 4))
>   B)
> ;=>(foo 1 2 3 4)

(setcdr (nthcdr ...) ...) _does_ alter A's structure. And thus it works.

> But is this the only way to go?  If it was possible, I would like to
> set things up so that I could do anything I wanted to do to A, and
> have B simply reflect that value at the end.

You can do "anything you want" with A, as long as any function you run
on A destructively modifies A. If it doesn't, then there's no way for
B to reflect the change.

So, just restrict yourself to destructive operations on A - like
setcdr, setcar, etc. - and you'll be set. Just note that A will always
have to be the "tail" part of B.

I.e. something like 

  B: (1 2 3 4 5 6)
  A: (3 4) ; a sublist of B

won't work, just because of the nature of lisp lists.

-- 
Denis Bueno
PGP: http://pgp.mit.edu:11371/pks/lookup?search=0xA1B51B4B&op=index

Re: sharing list structure

[Joe Corneli]

   > 
   > So I guess what I want is an "implicit pointer" to A.
   > 
   > Looking at the box diagrams in the manual, it seemed to me that
   > everything would be taken care of if I used "setcdr" to build the list
   > B.  But that didn't quite work:
   > 
   > (progn
   >   (setq A '(1 2 3))
   >   (setq B (list 'foo))
   >   (setcdr B A)
   >   (setq A (append A (list 4)))
   >   B)
   > ;=> (foo 1 2 3)

   The `append' doesn't alter the structure of the list A.

     (defvar *foo* (list 1 2 3))
     (append *foo* (list 4 5 6))
     *foo* => (1 2 3)

   Hence, the result of append doesn't alter A's structure.


Note the `setq' above, which make it look an awful lot like the
structure of A *is* being modified.  I mean, it comes out as a
different list --

(progn
  (setq A '(1 2 3))
  (setq B (list 'foo))
  (setcdr B A)
  (setq A (append A (list 4)))
  A)
;=> (1 2 3 4)

   > But is this the only way to go?  If it was possible, I would like to
   > set things up so that I could do anything I wanted to do to A, and
   > have B simply reflect that value at the end.

   You can do "anything you want" with A, as long as any function you run
   on A destructively modifies A. If it doesn't, then there's no way for
   B to reflect the change.

   So, just restrict yourself to destructive operations on A - like
   setcdr, setcar, etc. - and you'll be set. Just note that A will always
   have to be the "tail" part of B.

OK, I think I've got the idea now.  But still, I'm surprised that `setq'
is not among the list of "destructive functions".  What's that about?

Re: sharing list structure

[Denis Bueno]

On Thu, 24 Mar 2005 18:27:28 -0600, Joe Corneli
<jcorneli@math.utexas.edu> wrote:
>    The `append' doesn't alter the structure of the list A.
> 
>      (defvar *foo* (list 1 2 3))
>      (append *foo* (list 4 5 6))
>      *foo* => (1 2 3)
> 
>    Hence, the result of append doesn't alter A's structure.
> 
> Note the `setq' above, which make it look an awful lot like the
> structure of A *is* being modified.  I mean, it comes out as a
> different list --

The setq modifies what the value of the symbol A is - it's destructive
in that sense. After the setq, instead of being (1 2 3), A's value to
the list (1 2 3 4). But it's a different list (in memory) from its
former value.

>    So, just restrict yourself to destructive operations on A - like
>    setcdr, setcar, etc. - and you'll be set. Just note that A will always
>    have to be the "tail" part of B.
> 
> OK, I think I've got the idea now.  But still, I'm surprised that `setq'
> is not among the list of "destructive functions".  What's that about?

Like I said, the difference is in just _what_ it's destructively
modifying. In the case above, it destructively modifies the value of
the symbol A (see `symbol-value'), not the structure of the list whose
head cons cell is the value of the symbol A (which is just a more
precise way of saying "the list A").


-- 
Denis Bueno
PGP: http://pgp.mit.edu:11371/pks/lookup?search=0xA1B51B4B&op=index

Re: sharing list structure

[rgb]

Joe Corneli wrote:
> I'm not sure how to do the following:
>
>  I have a list A, that grows, shrinks, and changes.
>
>  I want to have a list B that includes list A within
>  its list structure, along with other things, and that
>  automatically keeps the "A" part of itself in synch
>  with A.
>
There will certainly be some kid gloves involved because most of
the normal things you might want to do with A are destructive or
subversive to any pointer B might hold.  The reason is, B is a
symbol in an obarray that points to a list element.  That list
element might have a CDR which points to the same list element
that A points to but a change to A list can never cause the
pointer held by some element in list B to change. So any
operation involving setq A will very likely cause the
corresponding pointer in list B to point to an obsolete location.

> Is there a way to accomplish this?  And if it can't be done with
> list structure alone, what other suggestions can you make?

I'm pretty sure this is not what you are looking for since
the position of the contents of B within list A is fixed.

(defmacro a+b () '`(,@A ,@B))  ;or any number of similar things
(setq A '(a b c d))
(setq B '(1 2 3 4))
(a+b)
  => (a b c d 1 2 3 4)
(setq a '(w x y z))
(setq b '(9 8 7 6))
(a+b)
  => (w x y z 9 8 7 6)

To be honest, I can't think of a way to do what it seems you
want in *any* language.  But maybe I don't really understand.

Re: sharing list structure

[Thien-Thi Nguyen]

Joe Corneli <jcorneli@math.utexas.edu> writes:

> OK, I think I've got the idea now.  But still, I'm
> surprised that `setq' is not among the list of
> "destructive functions".  What's that about?

setq changes a symbol's value to a new value.

a symbol and its value are two different concepts.

the "destructiveness" of a function does not refer
to the binding between a symbol and its value, but
rather how the cdr of a pair is treated.

check out gnugo.el, which uses tail-pointer style
extensively.  also: reverse:nreverse::append:nconc
(more or less, pedants be damned).

thi

Re: sharing list structure

[Joe Corneli]

   > I'm not sure how to do the following:
   >
   >  I have a list A, that grows, shrinks, and changes.
   >
   >  I want to have a list B that includes list A within
   >  its list structure, along with other things, and that
   >  automatically keeps the "A" part of itself in synch
   >  with A.
   >
   There will certainly be some kid gloves involved because most of
   the normal things you might want to do with A are destructive or
   subversive to any pointer B might hold.  The reason is, B is a
   symbol in an obarray that points to a list element.  That list
   element might have a CDR which points to the same list element
   that A points to but a change to A list can never cause the
   pointer held by some element in list B to change. So any
   operation involving setq A will very likely cause the
   corresponding pointer in list B to point to an obsolete location.


Well, I might be able to get by with using destructive functions to
modify list A.  It might be worth giving it a shot as an
exercise...  and if it works, so much the better.

   > Is there a way to accomplish this?  And if it can't be done with
   > list structure alone, what other suggestions can you make?

   I'm pretty sure this is not what you are looking for since
   the position of the contents of B within list A is fixed.

   (defmacro a+b () '`(,@A ,@B))  ;or any number of similar things
   (setq A '(a b c d))
   (setq B '(1 2 3 4))
   (a+b)
     => (a b c d 1 2 3 4)
   (setq a '(w x y z))
   (setq b '(9 8 7 6))
   (a+b)
     => (w x y z 9 8 7 6)


I think that you're right that this isn't quite like what I'm after.

Let me describe the situation a bit better more... hopefully the
details won't be overwhelming.

I have two lists, H and F, and they both grow, shrink, and otherwise
change.  But, actually, I have several pairs of lists like this, H1,
F1, H2, F2, etc., and at any given point in time, exactly one matched
pair is to be assigned to H and F,

  H := Hk
  F := Fk

However, I'm not just handed the H1 F1, ..., Hn Fn, rather, I wish to
build up the collection from H's and F's over time.  Thus, sometimes I
also wish to run

  Hj := H
  Fj := F

The data structure that I think ought to be capable of handling all of
this would be a list B that contains

 ((title1, H1, F1), (title2, H2, F2), ..., (titlen, Hn, Fn))

This imposes an order on the of pairs Hk, Fk, and can be used at any
give point in time to select the kth pair, or to do the assignment
above, or just to manage all of this data.  Of course, the list B
can't have a fixed length in this set-up, since new Hk, Fk pairs may
appear, or old ones deleted.

   To be honest, I can't think of a way to do what it seems you
   want in *any* language.

Hopefully now that I've described the situation a bit more precisely
it will be clear that it could be done with pointers:

  \|
  -> (V  V  V)
      T1 H1 F1
  -> (V  V  V)
      T2 H2 F2
   ...........

The vertical dimension here is dynamic, and there is a 3rd dimension
that is also dynamic, and it would be a pain to code it, I think, but
it seems manageable.  You'll have to forgive the quaint drawing style;
I fear it mainly will illustrate my lack of C programming sense.

Re: sharing list structure

[rgb]

> The data structure that I think ought to be capable of handling all
of
> this would be a list B that contains
>
>  ((title1, H1, F1), (title2, H2, F2), ..., (titlen, Hn, Fn))
>

Well I'm not sure now if you're re-explaining the problem for my
benefit or showing me you've found the answer.  Because the above
(with commas removed) seems to be a perfectly useable answer.


(setq all-my-lists
  '((key1 (h1a h1b h1c ...) (f1a f1b f1c ...))
    (key2 (h2a h2b h2c ...) (f2a f2b f2c ...))
     ...))

It should't be too hard to write some functions that mannage a
set of nested lists such as that in whatever way is convenient to
your application.

For example:

(setq all '((a (h1 h2 h3)(f1 f2 f3))       ;test data
            (b (ha hb hc)(fa fb fc))))

(defun get^h (key index)
  "get h[index] value within KEY list"
  (nth index (cadr (assoc key all))))

(get^h 'b 2)
hc

(defun delete^h (key index)
  "remove h[index] value from KEY list."
  (if (< 0 index)
      ;; the car of the list is not affected so just change the list
      ;; I used (nth 1 ...) rather than (cadr ...) so it's more obvious
      ;; how this could have a 3rd argument and not just access h.
      (setcdr (nthcdr (1- index) (nth 1 (assoc key all)))
              (nthcdr (1+ index) (nth 1 (assoc key all))))
    ;; when the car changes the outer list holding it must change
    (setcar (cdr (assoc key all))
            (nthcdr 1 (cadr (assoc key all))))))

(get^h 'a 1)
h2
(delete^h 'a 1)
(get^h 'a 1)
h3

(defun insert^h (key index value)
  "insert a new h value at h[index] value from KEY list."
  (if (< 0 index)
      (setcdr (nthcdr (1- index) (nth 1 (assoc key all)))
              (cons value (nthcdr index (nth 1 (assoc key all)))))
    (setcar (nthcdr 1 (assoc key all))
            (cons value (nthcdr index (nth 1 (assoc key all)))))))

(insert^h 'a 1 'h4)
(get^h 'a 1)
h4
(get^h 'a 2)
h3

Replace is more of the same...

Re: sharing list structure

[rgb]

rgb wrote:
> > The data structure that I think ought to be capable of handling all
> of
> > this would be a list B that contains
> >
> >  ((title1, H1, F1), (title2, H2, F2), ..., (titlen, Hn, Fn))
> >
>
> Well I'm not sure now if you're re-explaining the problem for my
> benefit or showing me you've found the answer.  Because the above
> (with commas removed) seems to be a perfectly useable answer.
>
>
> (setq all-my-lists
>   '((key1 (h1a h1b h1c ...) (f1a f1b f1c ...))
>     (key2 (h2a h2b h2c ...) (f2a f2b f2c ...))
>      ...))
>
> It should't be too hard to write some functions that mannage a
> set of nested lists such as that in whatever way is convenient to
> your application.
>
> For example:
>
> (setq all '((a (h1 h2 h3)(f1 f2 f3))       ;test data
>             (b (ha hb hc)(fa fb fc))))
>
> (defun get^h (key index)
>   "get h[index] value within KEY list"
>   (nth index (cadr (assoc key all))))
>
> (get^h 'b 2)
> hc
>
> (defun delete^h (key index)
>   "remove h[index] value from KEY list."
>   (if (< 0 index)
>       ;; the car of the list is not affected so just change the list
>       ;; I used (nth 1 ...) rather than (cadr ...) so it's more
obvious
>       ;; how this could have a 3rd argument and not just access h.
>       (setcdr (nthcdr (1- index) (nth 1 (assoc key all)))
>               (nthcdr (1+ index) (nth 1 (assoc key all))))
>     ;; when the car changes the outer list holding it must change
>     (setcar (cdr (assoc key all))
>             (nthcdr 1 (cadr (assoc key all))))))

Naturally this needs a bit more code like probably bounds checking
but as an example to get started with...

Re: sharing list structure

[Joe Corneli]

  Well I'm not sure now if you're re-explaining the problem for my
  benefit or showing me you've found the answer.

Mostly it was just for my benefit... I'm so selfish;) - but 
I appreciate your code suggestions!  I'll take a look at the
whole collection again when I'm feeling fresh.  Thanks all...
for your help with this & other questions today!

Re: sharing list structure

[Stefan Monnier]

> OK, I think I've got the idea now.  But still, I'm surprised that `setq'
> is not among the list of "destructive functions".  What's that about?

You're right: `setq' is also destructive.  But it's slightly different (the
difference has to do with the notion of "pointer aliasing").

In Scheme destructive operations are traditionally named with a "!" suffix,
so `setq' is actually called `set!'.

As for me, I'd rather get rid of `setq' and `set!' altogether.
That's basically what SSA does behind the scenes ;-)


        Stefan