"Purely Functional Data Structures" by Chris Okasaki [pdf]

http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf

by Stasyan • 16 years ago

55 12 16 years ago

cs.cmu.edu

ionfish2• 16 years ago

Okasaki's book of the same name, based on his thesis, is one of my favourites—I'd recommend it to all programmers, not just those doing a lot of functional programming. The explanations are lucid and insightful, and the book is full of helpful diagrams and example code. The sample code is in Standard ML, but there's an appendix with Haskell versions of all the main data structures discussed in the book.

andrewcooke3• 16 years ago

it's worth clarifying that the book has a bit more (textual) content than the thesis.

ionfish2• 16 years ago

I should have made that clearer. By "based on" I meant that it builds on, clarifies and extends his thesis (in my experience, books based on theses often fail to do this).

how_gauche• 16 years ago

A true classic!

camccann• 16 years ago

For any Haskell users out there, the Edison library (see here: http://www.cs.princeton.edu/~rdockins/edison/home/ ) provides implementations of various data structures based on what's described in Okasaki's thesis.

I seem to recall a similar library existing for F# but I couldn't find a link, sorry.

dschobel• 16 years ago

I first learned about this book from Yegge's blog (back when he was still at amazon) where he wrote:

"We've been studying the available research, and all roads lead to the same set of conclusions, one of which is that Functional Programming is going to be a necessity in this new world. It's a foregone conclusion.

And that, in a roundabout way, brings me to this book by Chris Okasaki. It is absolutely unique. It's the world's first textbook on purely functional data structures — i.e., data structures with no side-effects. I'm not going to explain in this blog why this is such an important topic for Amazon and distributed computing in general, but I will point you to the book in the hopes that you are also interested in finding a solution."

http://steve.yegge.googlepages.com/ten-challenges

rads• 16 years ago

I came across a library for persistent data structures in Ruby yesterday: http://github.com/harukizaemon/hamster

Deestan• 16 years ago

Just bought this book in hardcover last month; I can't recommend it enough.

Be sure to also check out Chris Okasaki's functional programming blog: http://okasaki.blogspot.com/

silentbicycle• 16 years ago

Note, this isn't the book, it's his thesis. The book (which is great) expands upon it.

FWIW, its code is in SML, with some Haskell translations in the appendix. I haven't used SML, but know OCaml, and haven't had any problems reading it.

andrewcooke3• 16 years ago

i wrote a review of this (well, the book) for /. many years ago - http://books.slashdot.org/books/04/02/19/2257203.shtml

it's probably a bit basic for experienced programmers - in particular "functional programming" needs a lot less explanation these days - but if you want some simple background it might help.

telemachos• 16 years ago

From Okasaki's blog:

Sales were steady but trending downward, until 2004, when a book review by Andrew Cooke appeared on Slashdot. After that, sales doubled and have stayed at that level for several years. Of course, I can't be sure this increase was because of Slashdot, but it seems likely. Thanks, Andrew!

http://okasaki.blogspot.com/2008/02/ten-years-of-purely-func...

andrewcooke3• 16 years ago

heh; i hadn't seen that - thanks. :)

"Purely Functional Data Structures" by Chris Okasaki [pdf]

Related Stories