Purely functional data structures
by Chris Okasaki · first published 1998
56% recommend43% neutral1% critical
Why HN recommends it
Fun, in-depth tour of persistent, immutable data structures and how to design and analyze functional algorithms, with exercises. Suits programmers curious about functional programming, even those new to it.
Summarised by Claude from recommending comments
Affiliate links. As an Amazon Associate I earn from qualifying purchases.
Mentions per year
What Hacker News says
Related books
2011–2024Pearls of functional algorithm design
Bird, Richard
Recommended by 17 · mentioned by 2217 recommend · 22 mention17 recommend · 2217 recommend
2008–2026Real World Haskell
Bryan O'Sullivan, John Goerzen, Don Stewart
Recommended by 122 · mentioned by 208122 recommend · 208 mention122 recommend · 208122 recommend
2007–2026The algorithm design manual
Steven S. Skiena
Recommended by 195 · mentioned by 265195 recommend · 265 mention195 recommend · 265195 recommend
2007–2026Introduction to Algorithms
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Recommended by 274 · mentioned by 712274 recommend · 712 mention274 recommend · 712274 recommend
2016–2021Advanced data structures
Peter Brass
Recommended by 3 · mentioned by 33 recommend · 3 mention3 recommend · 33 recommend
2008–2024Feynman lectures on computation
Richard Phillips Feynman
Recommended by 17 · mentioned by 2417 recommend · 24 mention17 recommend · 2417 recommend
2010–2025Prolog and natural-language analysis
Fernando C. N. Pereira, Stuart M. Shieber
Recommended by 6 · mentioned by 86 recommend · 8 mention6 recommend · 86 recommend
2008–2025Discrete Mathematics and Its Applications
Kenneth H. Rosen
Recommended by 14 · mentioned by 1914 recommend · 19 mention14 recommend · 1914 recommend
…Computer Programs, Abelson and Sussman - Algorithms, Sedgewick, Wayne - Introduction to Automata Theory, Languages, and Computation, Hopcroft, Motwani, Ullman Lesser known, but incredibly fun books: - Purely Functional Data Structures, Chris Okasaki - The Reasoned Schemer, Friedman, Byrd, Kiselyov (or a good Prolog book). After learning the foundations, you could branch out to a subfield that interests you. (Or as Frank Zappa has…
on “Ask HN: How to best acquire theoretical computer science knowledge?” ↗I expected Purely Functional Data Structures by Chris Okasaki to be on this list. I would recommend it but more importantly I've seen many people who know a lot more about functional programming recommend it. It is probably a bit more useful for…
on “Erik Meijer’s suggestions for further reading in functional programming” ↗I highly recommend Purely Functional Data Structures by Chris Okasaki. It really opened my mind when I was starting out in functional programming. Highly relevant to many modern problems.
on “Binomial Heap in OCaml” ↗…post. There are many good resources on this. I've referenced a few below. Of course there are many more. [1] https://www.amazon.com/Pearls-Functional-Algorithm-Design-Ri... [2] https://www.amazon.com/Purely-Functional-Data-Structures-Oka... [3] https://www.amazon.com/Algorithm-Design-Haskell-Richard-Bird... [4] https://www.amazon.com/Structure-Interpretation-Computer-Pro...
on “Two Vexing Problems in Functional Programming” ↗…little of this out on my own, but it's still really cool.) Incidentally, there's apparently a deep connection between number systems and tree structures. You can read more about it in Chris Okasaki's Purely Functional Data Structures. Apparently, every number system corresponds to a data structure. For example, Peano arithmetic = linked lists, binary numbers = binary trees, fibonacci numbers = binomial heaps, etc. There's a short…
on “PG: What's your current take on reddit's comment system?” ↗…you could develop your intuitions about data structure design trade-offs and what makes them behave the ways they do. After I learned OCaml, a lot of data structure design seemed obvious. Also, read _Purely Functional Data Structures_ by Chris Okasaki. Unlike (say) CLRS (http://mitpress.mit.edu/algorithms/), it's even a pretty short book.
on “Web Programming Is Hard ” ↗You should read the introduction to Chris Okasaki's "Purely Functional Data Structures". It says there may be higher lower bounds for some problems in functional programming languages, although it's often possible to come up with something that is as fast. I interpret that as it can require…
on “Functional Languages 101: What’s All the Fuss About?” ↗Purely functional data structures by Chris Okasaki Let Over Lambda forgot by whom https://www.youtube.com/watch?v=0nbkaYsR94c Not technically a book, but watch it anyway.
on “Ask HN: What language-agnostic programming books should I read?” ↗…other degree either. But I guess I'm just grumpy, because the book came with high praise. To be more constructive: Sedgewick's Algorithms is good for implementations in imperative languages. Okasaki's Purely Functional Data Structures is a nice introduction to some algorithms and data structures suitable in a purely functional setting. He also addresses laziness. And finally for the theory, Schrijver's "Combinatorial Optimization:…
on “The Algorithm Design Manual (2008)” ↗Allow me to disagree. Chris Okasaki's thesis, "Purely Functional Data Structures" is That Good for the field of functional programming. There are other exemplary papers, like Godel's incompleteness theorem, Cantor's diagonal argument, or Einstein's statement of special relativity.…
on “No Paper Is That Good” ↗…either time or space complexity. I believe I learned about using a fuel parameter in an old Edward Yang blog post (http://ezyang.com/) but I don't have a direct link. Jeff Okasaki's well known book "Purely Functional Data Structures" (highly recommended) does some complexity analyses of operations on functional data structures. They're not formalized but maybe they could be.
on “Functional Algorithms, Verified” ↗…magical number seven, plus or minus two: Some limits on our capacity for processing information." (this might be pushing it, but maybe the original case for managing complexity) [16] Chris Okasaki. 1998 "Purely Functional Data Structures." (how to design functional algorithms) [17] John C. Reynolds 1975. "User-defined types and procedural data structures as complementary approaches to data abstraction." (the fundamental abstract data…
on “Ask HN: CS papers for software architecture and design?” ↗> FP's greatest drawback, which is the copying of large data structures I guess you made that one up on the spot. Go read about "Purely Functional Data Structures" http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf or have a look at Haskells Data.Map implementation for another example.
on “Why Haskell is beyond ready for Prime Time” ↗You can read the thesis that later became "Purely Functional Data Structures" for free online: http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf It's a great read even for those who don't yet have experience with functional programming.
on “Books that influenced Clojure” ↗…At the same time, anything that adds to the list won't interfere with other code that is holding a reference to the same list, or even accessing it concurrently. Probably the best way to learn about purely functional data structures is from the book of the same name by Chris Okasaki.
on “Functional programming explained ... IRC-style” ↗