From hin-tak.leung at cimr.cam.ac.uk  Tue Oct  2 18:32:18 2007
From: hin-tak.leung at cimr.cam.ac.uk (Hin-Tak Leung)
Date: Tue, 02 Oct 2007 17:32:18 +0100
Subject: [Rd] pairlist objects
In-Reply-To: <1191292109.4701accd24217@webmail.fhcrc.org>
References: <1191292109.4701accd24217@webmail.fhcrc.org>
Message-ID: <47027292.6010808@cimr.cam.ac.uk>

?list has a little bit of information. As far as I know, historically,
the more inefficient one (pairlist()) came first, where R inherits its
structure and implementation from LISP ; list() came later as a new 
implementation of a list-like object which is more efficient and faster
in various manner (e.g. addressing the (n)th elements in the middle,
and overall storage size). So these days most list-like stuff within R
is done as list()'s rather than pairlist()'s.

Internally, a pairlist() in R is implemented as a recursive binary
tree (LISTSXP), where one branch of the first node consists of the
first elements, its
attributes, and the other branch consists of a daughter node which
consists of the 2nd element as its one branch, etc. Walking such a tree
is slow and its storage requirement is a bit larger than list().

Internally, a list() in R is a VECSXP, which is a one-dimensional 
structure, plus some attributes storing the names of the elements, etc.
It is a bit more efficient in terms of storage (a 1-D structure vs a 
recursive binary tree), and also in random addressing of its elements -
e.g. you can jump to the (n)th element without walking the 1st to the 
(n-1)th elements.

This is my understanding, no doubt the R core team has more and better 
way to say about this.

a list() is not of class vector (despite the implementation in C being a 
VECSXP) - a vector in R is a 1-D structure where all the elements are of 
the same type/mode, which a list() is not.

hpages at fhcrc.org wrote:
> Hi,
> 
> ?pairlist gives no explanation about what exactly is the difference
> between a pairlist and a list (except that a pairlist of length 0
> is 'NULL'). So, what's a pairlist?
> 
> class(.Options)
> [1] "pairlist"
> 
> Some strange things about the "pairlist" type:
> 
>   > showClass("pairlist")
>   Error in getClass(Class) : "pairlist" is not a defined class
> 
> Why the above doesn't work? It works for "list":
> 
>   > showClass("list")
> 
>   No Slots, prototype of class "list"
> 
>   Extends: "vector"
> 
>   > is.list(.Options)
>   [1] TRUE
> 
>   > is.vector(.Options)
>   [1] FALSE
> 
> This doesn't make sense! If 'x' is a list, then it should be considered
> a vector too.
> 
> Subsetting a pairlist with [] doesn't produce a pairlist: 
> 
>   > class(.Options[1:3])
>   [1] "list"
> 
> Yes, this one is documented, but still...
> 
> 
> Cheers,
> H.
> 
> ______________________________________________
> R-devel at r-project.org mailing list
> https://stat.ethz.ch/mailman/listinfo/r-devel



[Rd] pairlist objects
Hin-Tak Leung