
Purely functional data structures
Chris Okasaki · 1998
Programming and computer science › Functional programming languages
#198 most recommended
Hacker News
209
mentions by 155 people · top 2% of 15,732 books
Open Library
4.25★★★★★★★★★★
4 ratings · 27 want to read
Wikipedia
—
No article yet
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
In the commenters’ own words
Depending on your level of programming ability, one algorithm a day, IMHO, is completely doable. A number of comments and suggestions say that one per day is…
> The effects of methods that are called by other methods will be concealed, so at the calling site, you'll have no idea that the high-level API `do_stuff` is…
What Open Library readers say 4.25 from 4 ratings
- 52
- 41
- 31
- 20
- 10
- 27 want to read
- 0 reading
- 6 have read
Only 4 ratings: treat the average as a hint.
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
- Ask HN: Which book are you reading these days?
- Ask HN: What language-agnostic programming books should I read?
- What are you reading?
- Ask HN: The book that did it for you in math and/or CS?
- Ask HN: Which books have made you a better thinker and problem solver?
- Ask HN: What are the most fundamental books on computer science?
- Ask HN: Most interesting, mildly impractical, well-written books on software?
- Ask HN: What books had the greatest effect on how you structure your code?
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)
Read next: its neighbours on the mosaic
Pearls of functional algorithm designBird, Richard · 2010 · recommended by 17 people · 7 people recommended both
Structure and Interpretation of Computer ProgramsHarold Abelson · 1984 · recommended by 347 people · 12 people recommended both
Modern compiler designDick Grune · 2000 · recommended by 12 people · 3 people recommended both
Let Over LambdaDoug Hoyte · 2008 · recommended by 66 people · 6 people recommended both
Learn You a Haskell for Great Good!Miran Lipovača · 2011 · recommended by 237 people · 10 people recommended both
The craft of PrologRichard A. O'Keefe · 1990 · recommended by 18 people · 4 people recommended both
The art of computer programmingDonald Knuth · 1968 · recommended by 336 people · 9 people recommended both
Programming Language PragmaticsMichael L. Scott · 1999 · recommended by 31 people · 3 people recommended both
Real World HaskellBryan O'Sullivan · 2008 · recommended by 122 people · 5 people recommended both
Introduction to AlgorithmsThomas H. Cormen · 1990 · recommended by 274 people · 7 people recommended both
Modern compiler implementation in MLAndrew W. Appel · 1997 · recommended by 24 people · 3 people recommended both
The algorithm design manualSteven S. Skiena · 1998 · recommended by 195 people · 8 people recommended both
Compiling with ContinuationsAndrew W. Appel · 1992 · recommended by 19 people · 3 people recommended both
On LISPPaul Graham · 1993 · recommended by 192 people · 8 people recommended both
The reasoned schemerDaniel P. Friedman · 2005 · recommended by 45 people · 3 people recommended both
Practical Common LispPeter Seibel · 2005 · recommended by 218 people · 7 people recommended both
Engineering a compilerKeith D. Cooper · 2004 · recommended by 39 people · 3 people recommended both
How to Design ProgramsMatthias Felleisen · 2001 · recommended by 277 people · 8 people recommended both
Lisp in Small PiecesChristian Queinnec · 1996 · recommended by 101 people · 5 people recommended both
The little MLerMatthias Felleisen · 1998 · recommended by 6 people · 2 people recommended both
The Practice of ProgrammingBrian W. Kernighan · 1999 · recommended by 90 people · 4 people recommended both
Essentials of programming languagesDaniel P. Friedman · 1992 · recommended by 43 people · 3 people recommended both
Concepts, techniques, and models of computer programmingPeter Van Roy · 2004 · recommended by 70 people · 4 people recommended both
Paradigms of Artificial IntelligencePeter Norvig · 1991 · recommended by 63 people · 3 people recommended both