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

Majorinc, Kazimir skrev:
> Chris Laux wrote:
>> You could do (cons 'x ()) and would get (x). But I wouldn't call that
>> inserting per se. A list is just a chain of cons cells, so maybe you
>> have the wrong paradigm?
> Maybe.
> 
> Say x is my list and it is contained in other lists like y and z.
> 
>  > (define x (list 1))

(list 1) contructs the value

   (cons 1 empty)

The (define x ...) lets us refer to that value by the name x.

     x:
       (cons 1 empty)

Note: x is not a list. x is a name.

>  > (define y (list x))

Here (list x) constructs the value

    (cons (cons 1 empty) empty)

where the cons-cell (cons 1 empty) is the cons-cell to
which we refer to by the name x.

   y:       x:
     (cons   (cons 1 empty) empty)

> (define z (list x))

Now we construct yet another list:

    z:        x:
       (cons   (cons 1 empty)  empty)

Note that y and z share the cons-cell named x.

>  > x
> (1)

x refers to (cons 1 empty) which is printed (1).

>  > y
> ((1))

y refers to (cons (cons 1 empty) empty) which is printed ((1))

>  > z
> ((1))

Same reasoning here.

> 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

Now we construct the value (cons 2 empty).
The (set-rest! x (list 2)) first finds the cons-cell
associated with x. Then the rest-part is set to contain
the value (cons 2 empty)

That is,

   BEFORE       x:
                 (cons 1 empty)

      y:        x:
         (cons   (cons 1 empty) empty)

      z:        x:
         (cons   (cons 1 empty)  empty)


   AFTER        x:
                 (cons 1 (cons 2 empty))

      y:        x:
         (cons   (cons 2 (cons 2 empty)) empty)

      z:        x:
         (cons   (cons 3 (cons 2 empty))  empty)

> (1 2)
>  > y
> ((1 2))
>  > z
> ((1 2))

And that is what we observe here.

> 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)?

You can't. x is not a list. x refers to a value, which is either empty
or a cons-cell. empty is an atomic value that can't be changed. A
cons-cell is a compund value, that contains two other values (first and
rest). You can change which values the cons-cell contains.


What you can do however, is to make your own data definition for 
double-linked lists. Then you can insert elements into an empty list.


-- 
Jens Axel Søgaard