Functional programming is a well established programming paradigm and is becoming increasingly popular, even in industrial and commercial applications. Data structures used in functional languages are principally persistent, that is, they preserve previous versions of themselves when modified. The goal of this work is to broaden the theory of persistent data structures and devise efficient implementations of data structures to be used in functional languages.
Arrays are without any question the most frequently used data structure. Despite being conceptually very simple, no persistent array with constant time access operation exists. We describe a simplified implementation of a fully persistent array with asymptotically optimal amortized complexity Θ(log log n) and especially a nearly optimal worst-case implementation. Additionally, we show how to effectively perform a garbage collection on a persistent array.
The most efficient data structures are not necessarily based on asymptotically best structures. On that account, we also focus on data structure implementations in the purely functional language Haskell and improve the standard Haskell data structure library considerably.
The thesis is available online.
There are also various attachments available for download: attachment A.1 of the thesis (code generating Figure 7.3); benchmarks from Chapters 6, 7, 8; version 0.5.2.1 of the Haskell containers package with full commit history.