Purely Functional Data Structures
📜 Abstract
When a C programmer needs an efficient data structure for a particular problem, he or she can often simply look one up in any of a number of good textbooks or handbooks. Unfortunately, programmers in functional languages such as Standard ML or Haskell do not have this luxury. Although some data structures designed for imperative languages such as C can be quite easily adapted to a functional setting, most cannot, usually because they depend in crucial ways on assignments, which are disallowed, or at least discouraged, in functional languages. To address this imbalance, we describe several techniques for designing functional data structures, and numerous original data structures based on these techniques, including multiple variations of lists, queues, double-ended queues, and heaps, many supporting more exotic features such as random access or efficient catenation. In addition, we expose the fundamental role of lazy evaluation in amortized functional data structures. Traditional methods of amortization break down when old versions of a data structure, not just the most recent, are available for further processing. This property is known as persistence, and is taken for granted in functional languages. On the surface, persistence and amortization appear to be incompatible, but we show how lazy evaluation can be used to resolve this conflict, yielding amortized data structures that are efficient even when used persistently. Turning this relationship between lazy evaluation and amortization around, the notion of amortization also provides the first practical techniques for analyzing the time requirements of non-trivial lazy programs. Finally, our data structures offer numerous hints to programming language designers, illustrating the utility of combining strict and lazy evaluation in a single language, and providing non-trivial examples using polymorphic recursion and higher-order, recursive modules.
✨ Summary
Overview
This dissertation develops a general methodology for designing efficient data structures in purely functional languages, where destructive updates are unavailable and every updated value can remain accessible as an older version. The central objective is to obtain asymptotic performance comparable to imperative data structures while preserving persistence, structural sharing, and referential transparency.
The main conceptual contribution is the connection between lazy evaluation, memoization, amortization, and persistence. Conventional amortized analysis assumes that accumulated credits or potential are spent along a single future execution path. Persistence invalidates that assumption because one version may be reused by multiple future computations. Okasaki replaces accumulated savings with accumulated debt associated with unevaluated computations. Lazy evaluation with memoization ensures that expensive suspended work is performed at most once per shared suspension, while each logical future is charged conservatively for the work it may force.
The dissertation introduces two analysis techniques for lazy persistent structures:
- The banker’s method, which assigns debits to locations in a data structure and proves that debits are discharged before the associated suspended computations are forced.
- The physicist’s method, which uses a potential function representing an upper bound on outstanding suspended work.
These methods provide a practical framework for reasoning about the running time of non-trivial lazy programs without pretending that they are strict. The dissertation distinguishes unshared, shared, realized, and unrealized costs, making explicit which suspended computations contribute to actual execution time.
A second major contribution is scheduling, which converts many lazy amortized structures into worst-case structures. The approach incrementally forces suspended computations before they are demanded, preventing long cascades of forces. This yields real-time queues and deques and worst-case sortable collections. The dissertation therefore presents strict and lazy evaluation as complementary: laziness supports simple amortized structures, while controlled forcing supports predictable worst-case bounds.
The design techniques developed throughout the work include:
- Lazy rebuilding, which replaces expensive global rebuilding with suspended rebuilding computations and can be combined with scheduling.
- Numerical representations, which model collections after positional number systems. Binary, segmented-binary, and skew-binary representations lead to efficient random-access lists and heaps. In particular, skew-binary random-access lists support constant-time insertion, head, and tail operations with logarithmic lookup and update, while skew binomial heaps support constant-time insertion and logarithmic merge, minimum, and deletion operations.
- Data-structural bootstrapping, including structural decomposition for constructing unbounded structures from bounded ones and structural abstraction for deriving efficient join operations from efficient insertion operations. Applications include bootstrapped queues, catenable lists, and bootstrapped heaps.
- Implicit recursive slowdown, a lazy counterpart to recursive slowdown that represents partially completed restructuring implicitly as suspended computation. It yields persistent queues, deques, and catenable deques with strong amortized bounds.
The implementations cover queues, real-time queues, deques, catenable lists, catenable deques, random-access lists, heaps, and sortable collections. The accompanying complexity table demonstrates that purely functional implementations can achieve constant-time amortized or worst-case operations for several fundamental abstractions, while retaining persistence.
Influence
The dissertation was subsequently expanded into the 1998 Cambridge University Press book Purely Functional Data Structures, which has accumulated substantial citation activity; Cambridge reports 171 Crossref citations for the book version. (cambridge.org) Its techniques and examples became a standard reference point for subsequent work on persistent sequences, heaps, queues, lazy amortization, and functional data-structure design. Later research continues to develop high-performance purely functional collections, including compressed and parallel purely functional trees for sets, maps, and sequences. (arxiv.org)
The paper’s industry influence is clearest at the level of the broader persistent-data-structure model rather than through a documented direct implementation lineage. Clojure, for example, provides immutable persistent collections using structural sharing and specifies their performance guarantees for persistent use. Clojure’s official documentation does not, in the sources examined, directly attribute these implementations to Okasaki’s dissertation, so a direct causal claim would be unwarranted. (clojure.org)