Fully Persistent Lists with Catenation

Abstract:

In this paper we consider the problem of efficiently implementing a set of side-effect-free procedures for manipulating lists. These procedures are:
makelist(d): Create and return a new list of length 1 whose first and only element is d.
first(X): Return the first element of list X.
pop(X): Return a new list that is the same as list X with its first element deleted. This operation does not effect X.
catenate(X,Y ): Return a new list that is the result of catenating list X and list Y , with X first, followed by Y (X and Y may be the same list). This operation has no effect on X or Y .
We show how to implement these operations so that makelist(d) runs in constant time and consumes constant space, and catenate(X,Y ) runs in time (and consumes space) proportional to log log k, where k is the number of list operations done up to the time of the catenation. All of these time and space bounds are amortized over the sequence of operations.