Taylor R Campbell wrote:
> What space usage are random-access lists guaranteed to exhibit?
> Growth order and constant factors are both interesting -- growth order
> to specify in the SRFI, and constant factors to satisfy my curiosity.

Representing a random-access list of n elements takes O(n) space, just
as with sequential lists.

A random-access list is a forest of complete binary trees.  The forest
contains at most log n trees, and the space of each tree is proportional
to the number of elements it contains.  If you represent binary trees
using pairs [*], then it takes m-1 pairs to represent a complete binary
tree with m elements.  The forest can be represented as a list, and thus
takes a pair per tree, which is at most log n.  So the overall space
consumption need not be more than n + log n.  My implementation stores
the size of each tree in the forest making it n + 2 * log n.

Does this answer your question satisfactorily?  (I will respond to the
benchmark question separately).

David

[*] With the caveat that these pairs be distinguishable from any kind of
data you wish to store in a random-access list, hence my use of records.