@device(postscript)
@libraryfile(Mathematics10)
@libraryfile(Accents)
@style(fontfamily=timesroman,fontscale=11)
@pagefooting(immediate, left "@c<Technical Report 1996>",
center "@c<Computer Science>",
right "@c<Carnegie Mellon>")
@heading(Purely Functional Data Structures)
@heading(CMU-CS-96-177)
@center(@b(Chris Okasaki))
@center(September 1996 - Ph.D. Thesis)
@center(FTP: Unavailable)
@blankspace(1)
@begin(text)

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
@i(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 @i(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.

@blankspace(2line)
@begin(transparent,size=10)
@b(Keywords:@ )@c<Functional programming, data structures, lazy evaluation,
amortization>
@end(transparent)
@blankspace(1line)
@end(text)
@flushright(@b[(164 pages)])