Purely Functional Data Structures

Citation

Okasaki, C. (1998). Purely Functional Data Structures. Cambridge University Press.

Chapter Summary

The book is about 230 pages with eleven chapters and an appendix containing Haskell source code. It shares its title, and several chapter titles, with the author's 1996 Carnegie Mellon doctoral thesis. Its premise is that most textbook data structures assume an imperative language, while structures for Standard ML, Haskell or Scheme must work without assignment and must keep earlier versions of a structure usable after an update. The book presents design techniques so that readers can build their own functional structures, alongside both classical structures (the publisher names red-black trees and binomial queues) and many that were developed for functional languages. Code is given in Standard ML and Haskell.

Chapter 1: Introduction

The opening chapter sets out the contrast between functional and imperative data structures. Destructive updates are a handicap for functional design, and persistence is an extra requirement, since functional data structures keep every version. The chapter also fixes terminology, because "data structure" has several related meanings.

Chapter 2: Persistence

This chapter deals with persistent versus ephemeral data structures: a persistent structure supports multiple versions after updates, while an ephemeral one allows only the latest. It sets up the idea that functional programs use persistence as a matter of course, and it prepares the later difficulty of combining persistence with amortized analysis.

Chapter 3: Some Familiar Data Structures in a Functional Setting

Before introducing new techniques, the book re-examines familiar structures in a functional language, showing what changes when updates cannot be destructive.

Chapter 4: Lazy Evaluation

The chapter introduces lazy evaluation: delaying an expression until its value is needed, then caching the result (memoization). It presents a notation for adding suspensions to a strict language such as Standard ML, with streams as the first application. Strict and lazy evaluation each matter for the analysis: strict languages can describe worst-case structures but not amortized ones, and lazy languages the reverse.

Chapters 5–6: Fundamentals of Amortization; Amortization and Persistence via Lazy Evaluation

Chapter 5 presents the fundamentals of amortization, the technique of bounding the average cost of operations. Chapter 6 is the foundation of the book: traditional amortization fails when old versions of a structure remain in use, and lazy evaluation (through memoization) reconciles amortization with persistence. The author's methods for analysing the cost of lazy structures, including the banker's and physicist's methods, are illustrated on queues and on bottom-up mergesort with sharing.

Chapter 7: Eliminating Amortization

Here the book shows how a worst-case bound can often be derived from an amortized structure by systematically scheduling the premature execution of lazy components. Real-time queues, with constant-time operations in the worst case, are the main example.

Chapter 8: Lazy Rebuilding

Lazy rebuilding is a lazy variant of global rebuilding. It is simpler but gives amortized rather than worst-case bounds; combined with the scheduling of Chapter 7, worst-case bounds are recovered. Batched rebuilding, global rebuilding and double-ended queues (deques) are the context.

Chapter 9: Numerical Representations

A design technique built on an analogy with number systems: choosing a variant of binary numbers in which adding or subtracting one takes constant time guides the design of insertion and deletion. The chapter covers positional number systems, binary random-access lists, binomial heaps, and segmented and skew binary numbers.

Chapter 10: Data-Structural Bootstrapping

Bootstrapping comes in two flavours: structural decomposition, in which unbounded solutions are built from bounded ones, and structural abstraction, in which efficient solutions are built from inefficient ones. The applications include queues, lists with efficient catenation and heaps with efficient merging.

Chapter 11: Implicit Recursive Slowdown

The final technical chapter is a lazy variant of Kaplan and Tarjan's recursive slowdown. It is simpler but amortized, with worst-case bounds recoverable by scheduling, and yields implicit queues, deques and catenable double-ended queues.

Appendix A: Haskell Source Code

An appendix of about twenty pages gives the Haskell versions of the programs, followed by a bibliography of about ten pages and an index.

Key Concepts

Chapters 1–4: Persistence and Laziness

• Persistent and ephemeral structures: whether old versions remain available after an update.
• Lazy evaluation and memoization: delaying a computation and caching its result.
• Strict versus lazy: the two evaluation orders and what each lets one express about cost.

Chapters 5–8: Amortization

• Amortization: bounding the cost of a sequence of operations rather than each one.
• Banker's and physicist's methods: two ways of analysing amortized cost of lazy structures.
• Scheduling: running lazy work early to recover worst-case bounds.
• Lazy rebuilding: spreading the rebuilding of a structure across subsequent operations.

Chapters 9–11: Design Techniques

• Numerical representations: structures designed in analogy with number systems.
• Structural decomposition and structural abstraction: the two forms of bootstrapping.
• Implicit recursive slowdown: a lazy form of recursive slowdown that gives queues and deques.

Critical Analysis

Strengths

• A clear point of view. The publisher's description frames the book as data structures from the point of view of functional languages, with design techniques for building new ones, rather than as a catalogue.
• Method plus examples. Each of the later chapters is built around a general technique (lazy rebuilding, numerical representations, bootstrapping, implicit recursive slowdown) illustrated with concrete structures such as queues, deques, heaps and random-access lists.
• Two languages. Source code is given in Standard ML in the text and in Haskell in an appendix, and most of the programs adapt to other functional languages.
• Reviewer's verdict. Computing Reviews called it important for presenting data structures from the functional point of view, a handy reference for professional functional programmers, with well-structured, readable programs set off in boxes; it also noted that C and Java programmers should find the structures straightforward to implement.
• Self-study use. The publisher states that it can be used as a tutorial or for self-study as well as a reference.

Limitations

• Tied to evaluation order. The author notes that programmers in languages that are entirely strict or entirely lazy can use some, but not all, of the structures, because several rely on both kinds of evaluation.
• Language limits. Some recursive structures are hard to express in Standard ML (the author mentions polymorphic recursion and recursive modules), so the text sometimes uses pseudo-code and then shows the conversion to legal code.
• Short and specialised. With 232 pages, the book is written for programmers who already work in functional languages; it is not an introduction to a functional language or to data structures in general.
• Date. The book first appeared in 1998, so readers should check newer literature for later developments.

Where It Fits in the Course

Most of the other books in this course present imperative structures. Grokking Algorithms and A Common-Sense Guide to Data Structures and Algorithms are plain-language first introductions with code in Python and other languages; Data Structures and Algorithms in Java is a second-course textbook that builds each structure from an abstract data type; Open Data Structures gives precise interfaces, full implementations and running-time proofs, free online; and Advanced Data Structures is a graduate-level treatment with C implementations and references to the research literature.

Okasaki's book is a complement to these, not a replacement. Read it after a standard data-structures course and some experience with a functional language, when you want to know how to get comparable bounds without mutation, or how amortized analysis survives persistence.

How to Use This Book

The book is for readers with a data-structures course behind them and working knowledge of a functional language such as Standard ML, OCaml or Haskell; familiarity with amortized analysis helps.

A practical plan:

• Core: Chapters 2–4 for persistence and laziness, then Chapter 6, the pivotal chapter on amortization with persistence.
• Techniques: Chapters 7–8 (scheduling and lazy rebuilding), then whichever of Chapters 9–11 matches your interest. Chapter 9 is the most self-contained.
• Optional: Chapter 5 if you need to refresh amortization; Chapter 11 as the most advanced.
• Code: implement at least the queue and one heap in your own language, including tests of persistent use, and compare the Standard ML and Haskell versions.