R help - Mar 2006 - linear lists, creation, insertion, deletion, traversal *someone?*

Hi,

In a second try I will ask this list to give me some useful pointers.

Linear lists, as described e.g. by N.Wirth in "Algorithms and Data
Structures", seem not to be implemented in S/R, although in lisp we have 
cons, car, cdr.

Nevertheless I want to implement an algorithm using such linear lists, 
porting a trusted program to R (S). I need:

(from Modula/Oberon)
	pSC* = POINTER TO SC;
	SC* = RECORD	Next*: pSC; ......
...     END;

# generate and fill a linked list:
VAR   p, pA, Kol: pSC;
	NEW( Kol);
	pA := Kol;
	while () {
		NEW( p );
		pA.Next := p;
		pA := p;
		...
	}

Mapping this list management to R's list() is possible, but may not be 
so transparent. Insertions and deletions from a list may be more convoluted.

Does anybody have experience in this? I could not find any reference in
R resources, also the Blue Book is mute here.

Thank you
Christian
-- 
Dr. Christian W. Hoffmann,
Swiss Federal Research Institute WSL
Mathematics + Statistical Computing
Zuercherstrasse 111
CH-8903 Birmensdorf, Switzerland

Tel +41-44-7392-277  (office)   -111(exchange)
Fax +41-44-7392-215  (fax)
christian.hoffmann at wsl.ch
http://www.wsl.ch/staff/christian.hoffmann

International Conference 5.-7.6.2006 Ekaterinburg Russia
"Climate changes and their impact on boreal and temperate forests"
http://ecoinf.uran.ru/conference/

On 3/1/2006 8:09 AM, Christian Hoffmann wrote:
> Hi,
> 
> In a second try I will ask this list to give me some useful pointers.
> 
> Linear lists, as described e.g. by N.Wirth in "Algorithms and Data
> Structures", seem not to be implemented in S/R, although in lisp we
have
> cons, car, cdr.
They are in R as "pairlists" (see ?pairlist), and are used internally,
but are rarely used at the R level; I'd suggest avoiding them.

One other problem with that style of programming is that there is 
(almost) no way to have a pointer or reference to an object.  (The 
"almost" refers to the fact that you can have references to 
environments, and could wrap objects in environments to make references 
to objects, but this is cumbersome and you probably want to avoid it.)

> 
> Nevertheless I want to implement an algorithm using such linear lists, 
> porting a trusted program to R (S). I need:
> 
> (from Modula/Oberon)
> 	pSC* = POINTER TO SC;
> 	SC* = RECORD	Next*: pSC; ......
> ...     END;
> 
> # generate and fill a linked list:
> VAR   p, pA, Kol: pSC;
> 	NEW( Kol);
> 	pA := Kol;
> 	while () {
> 		NEW( p );
> 		pA.Next := p;
> 		pA := p;
> 		...
> 	}
> 
> Mapping this list management to R's list() is possible, but may not be 
> so transparent. Insertions and deletions from a list may be more
convoluted.
Insertions and deletions are relatively easy; the difficult part comes 
in doing the things that involve references, like your pA.Next above. 
You'll need to use vector indexing instead, e.g. you could translate the 
code above to

Kol <- list()
repeat {
    p <- new_pSC;
    Kol <- c(Kol, p)
    ...
}

and then refer to objects in the list as Kol[[i]], to the tail of the 
list as Kol[i:length(Kol)], etc.  (Note the distinction between [[ ]] 
and [ ]:  single brackets give a list, double brackets extract an 
element from the list.)  Remember that each of these makes a *copy* of 
the object; saying

x <- Kol[[2]]
x <- newvalue

has no effect on x.

Duncan Murdoch
> 
> Does anybody have experience in this? I could not find any reference in
> R resources, also the Blue Book is mute here.
> 
> Thank you
> Christian

Christian Hoffmann <christian.hoffmann <at> wsl.ch> writes:
> 
> Hi,
> 
> In a second try I will ask this list to give me some useful pointers.
   [There is a general problem with the list, because of its
volunteer nature: easy questions and questions that catch peoples'
attention get answered.  Others don't.  I saw your initial question
but wasn't sufficiently clear on the distinction between "linear
lists" and lists as implemented in R to know what you needed that
an R list() couldn't do ... and I don't have Wirth on my shelf
and didn't have time to go look for a copy.]
 
> Linear lists, as described e.g. by N.Wirth in "Algorithms and Data
> Structures", seem not to be implemented in S/R, although in lisp we
have
> cons, car, cdr.
  cons would seem to be roughly equivalent to c() (except
that you have to make sure that the arguments are lists:
c("pine",list("fir","oak","maple"))
won't work, you have
to do
c(list("pine"),list("fir","oak","maple"))).
   car(x) is x[1]
   cdr(x) is x[-1]
> Nevertheless I want to implement an algorithm using such linear lists, 
> porting a trusted program to R (S). I need:
> 
> (from Modula/Oberon)
> 	pSC* = POINTER TO SC;
> 	SC* = RECORD	Next*: pSC; ......
> ...     END;
> 
> # generate and fill a linked list:
> VAR   p, pA, Kol: pSC;
> 	NEW( Kol);
> 	pA := Kol;
> 	while () {
> 		NEW( p );
> 		pA.Next := p;
> 		pA := p;
> 		...
> 	}
> 
> Mapping this list management to R's list() is possible, but may not be 
> so transparent. Insertions and deletions from a list may be more
convoluted.
   I don't know Modula.  What determines the length of the
list you are constructing here?  It looks like this is more
or less analogous to a while() { mylist <- c(mylist,newelement) }
(although there are probably more efficient ways to do it)

   Setting a list element to NULL deletes it; you can also use
negative indexing to drop one or more elements from a list.
  (pages 28 and 29 of "introduction to R"
   I don't know offhand if there's a simple way to modify
a list by inserting an element into the middle, bumping
up all the other indices; R deals much more with indices
than with pointer references.  If you wanted to insert
an element between items w and w+1 you could say
newlist <- c(oldlist[1:w],newelement,oldlist[(w+1):length(oldlist)])
but I appreciate that this may not be what you're looking
for.

Christian Hoffmann wrote:
> Hi,
> 
> In a second try I will ask this list to give me some useful pointers.
> 
> Linear lists, as described e.g. by N.Wirth in "Algorithms and Data
> Structures", seem not to be implemented in S/R, although in lisp we
have
> cons, car, cdr.
> 
This has been discussed on the list a (long) time ago, so you can
search the archives. I remember L Tierney opined they should be
implementes as a (S4) class.

Kjetil
> Nevertheless I want to implement an algorithm using such linear lists, 
> porting a trusted program to R (S). I need:
> 
> (from Modula/Oberon)
> 	pSC* = POINTER TO SC;
> 	SC* = RECORD	Next*: pSC; ......
> ...     END;
> 
> # generate and fill a linked list:
> VAR   p, pA, Kol: pSC;
> 	NEW( Kol);
> 	pA := Kol;
> 	while () {
> 		NEW( p );
> 		pA.Next := p;
> 		pA := p;
> 		...
> 	}
> 
> Mapping this list management to R's list() is possible, but may not be 
> so transparent. Insertions and deletions from a list may be more
convoluted.
> 
> Does anybody have experience in this? I could not find any reference in
> R resources, also the Blue Book is mute here.
> 
> Thank you
> Christian

Christian Hoffmann <christian.hoffmann <at> wsl.ch> writes:
> 
> Hi,
> 
> In a second try I will ask this list to give me some useful pointers.
> 
> Linear lists, as described e.g. by N.Wirth in "Algorithms and Data
> Structures", seem not to be implemented in S/R, although in lisp we
have
> cons, car, cdr.
> 
[snip description of ops on linked list]
> Mapping this list management to R's list() is possible, but may not be 
> so transparent. Insertions and deletions from a list may be more
convoluted.
> 
If the linked list you are using will be large and involve lots of manipulation,
you might want to store and implement it in C. 

But if you do it in native R ...

You might use new.env(hash=TRUE) to create an environment() as the linked-list.

It would contain one object that contains the name of (serving as the pointer
to) the first node. (or it would contain NULL or FALSE if the linked-list was of
length zero.)

Each node would be a list() with two components: the value and the name of (i.e.
the pointer to) the next element. 

To add a node you would create a name that is unique (within the environment at
least), use assign() once to place the new node in the environment and once more
to rewrite the preceeding nodes pointer to contain the name of the new node.

Initialize and add data to a linked list:
> linklist <- new.env(hash=TRUE)
> assign('start',FALSE,envir=linklist)
> for (i in 1:10000 ){
+ assign(as.character(i), list( ptr=get('start',linklist),
value=rnorm(1) ),
+ envir=linklist)
+ assign('start',as.character(i), envir=linklist )
+ }
> get("501",linklist) # example of one node
$ptr
[1] "500"

$value
[1] -0.7022237

Of course, you would write a function to do those two assignments.

To delete a node you would use assign() to reset the pointer from the previous
to the succeeding node, then rm() to delete the defunct node.
> to.delete <- get("501", linklist)$ptr
> assign( "501", list(ptr = get( to.delete, linklist )$ptr, 
+ val = get("501", linklist)$val ), linklist )
> rm( list=to.delete, envir=linklist )
> get("501",linklist)
$ptr
[1] "499"

$val
[1] -0.7022237
>
> Does anybody have experience in this? I could not find any reference in
> R resources, also the Blue Book is mute here.
> 
> Thank you
> Christian