Purely Functional List Catenation in Constant Time, Revisited
Bob Tarjan, Princeton University
Dec 19, 2003, Wean 7220

Abstract:

A canonical problem that exposes both the power of purely
functional languages and the ease (or difficulty) of making data
structures persistent is that of implementing purely functional lists so
that insertion or deletion at either end of a list and list catenation
all take constant time. An intriguing aspect of this problem is that
lists of exponential size can be constructed in a linear number of
catenations. We describe a solution that builds on and simplifies
previous solutions. One component is a novel nested stack structure.