DeepRead
Cover of Purely functional data structures

Purely functional data structures

Chris Okasaki · 1998

Programming and computer science › Functional programming languages

#198 most recommended

About the book

A monograph on designing and analyzing data structures that cannot be mutated, covering lists, queues, heaps, sorted sequences, and random-access structures built from persistent, immutable nodes. It is written for functional programmers and uses Standard ML throughout, with the algorithms and their running-time analysis developed in the same text. Purely functional data structures can match the efficiency of imperative ones, despite the usual belief that persistence forces a cost. Amortized bounds that are sound in an ephemeral setting can fail when old versions are reused, so Okasaki develops a separate analysis, and lazy evaluation with memoization is the tool that restores good bounds. The book presents techniques for building these structures, such as scheduling lazy computation, global rebuilding, and numerical representations modeled on binary arithmetic, and it treats the choice of data structure as a design problem that can be reasoned about systematically.

Written by Claude from what it knows of this book.

What Hacker News says 56% recommend · 1% critical

02040200720102015202020262010 peak · 26
This bookAverage book in Functional programming languages

In the commenters’ own words

What Open Library readers say 4.25 from 4 ratings

  1. 52
  2. 41
  3. 31
  4. 20
  5. 10
  • 27 want to read
  • 0 reading
  • 6 have read

Only 4 ratings: treat the average as a hint.

Open Library’s page for the book

What critics say, via Wikipedia

No Wikipedia article about this book yet, so no critics to quote.

Reddit communities — coming later

The threads it came up in

Details

First published
1998
ISBN
9780521663502
Editions known
10 at Open Library
Open Library
OL1863182W

Data structures (Computer science)Functional programming (computer science)Functional programming languagesLangages de programmation fonctionnelsStructures de données (Informatique)

Explore in the mosaic

Read next: its neighbours on the mosaic