Purely functional data structures

About the book

Chris Okasaki's Purely Functional Data Structures examines how classic structures behave when every operation returns a new version and leaves the old one intact. The setting is a language without destructive assignment, so an insert or delete cannot overwrite memory in place. That single constraint reshapes the analysis: amortized bounds computed by charging work to saved state no longer hold when a caller can revisit an earlier version.

The book works through structures such as stacks, queues, heaps, search trees and random-access lists under that rule, pairing implementations with cost arguments. Its central technical theme is how to recover acceptable bounds without mutation, often by making the cost of an operation explicit in its type or by designing lazy evaluation carefully. Okasaki wrote it as a researcher addressing a gap in the literature, and the treatment is mathematical rather than tutorial.

Readers should expect a text that argues through definitions, invariants and proofs of running time, with code serving the analysis rather than standing alone as a library.

How to read it

Approach the book as a series of arguments, not a cookbook. Each structure arrives with a claim about cost, and the interesting part is the reasoning that justifies it. Read the definitions closely and check the invariants yourself; the proofs are short but they carry the load.

The difficulty sits in the amortized and persistent analysis, especially where lazy evaluation enters. Readers without comfort in discrete math or complexity notation will move slowly. Work the examples with a functional language at hand if possible, and expect to reread sections on debt and scheduling more than once.

Who it suits

Programmers who already write functional code and want to understand why certain structures are chosen will find the reasoning directly useful. Students of programming languages and algorithms will get a disciplined model of cost analysis under persistence. Implementers of immutable collections in any language can use the designs and their bounds as a reference. Readers wanting a gentle introduction to functional programming should look elsewhere first.

Reading considerations

The book assumes fluency with mathematical notation and with at least one functional language, and its examples are tied to the conventions of its era. Later work has extended and reworked some of the material, so treat the bounds as a starting framework to test against current implementations rather than a final word.