[plt-scheme] How to insert an element in empty list?

On Sun, 2007-08-12 at 23:11 +0200, jerzy.karczmarczuk at info.unicaen.fr
wrote:
> Majorinc, Kazimir writes: 
> 
> ...
> > > x
> > (1)
> > > y
> > ((1))
> > > z
> > ((1)) 
> > 
> > Now, when I insert an element in x, the lists y and z (and possibly many 
> > others) automatically change in the same time. 
> > 
> > > (set-rest! x (list 2))
> > > x
> > (1 2)
> > > y
> > ((1 2))
> > > z
> > ((1 2))
> > > 
> > 
> > It is  normal because y and z actually contain that same list. How can I 
> > make it work the same way if x is initially empty list (not list with one 
> > element)?
> 
> The action you call "insertion" is a physical modification of the relevant
> structure, the changing of one, or both fields of a 'dotted pair'. But the
> empty list is simply an irreducible constant, no way to modify it, since it
> has no internal structure: there were LISPs where NIL was just zero, and
> the atom NIL *was* the empty list. Modifying zero could be harmful for
> your health... 
> 
> In your case you must replace x by something else, in y and z. 

A fairly common technique is to use a so-called "headed list",
consisting of a list with a dummy first element.  The list is "empty"
when the tail of the headed list is empty, you add to the front by
inserting a fresh cons containing the new item between the head and the
first "real" member (or nil if it is "empty"), etc.  This way you need
not treat the empty structure as a special case so code is simplified.

 -- Bill Wood