"Purely Functional Data Structures" by Chris Okasaki [pdf](cs.cmu.edu)
cs.cmu.edu
"Purely Functional Data Structures" by Chris Okasaki [pdf]
http://www.cs.cmu.edu/~rwh/theses/okasaki.pdf
12 comments
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.
it's worth clarifying that the book has a bit more (textual) content than the thesis.
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).
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.
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.
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...
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...
heh; i hadn't seen that - thanks. :)
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/
Be sure to also check out Chris Okasaki's functional programming blog: http://okasaki.blogspot.com/
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.
I seem to recall a similar library existing for F# but I couldn't find a link, sorry.
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
"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
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.
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.
I came across a library for persistent data structures in Ruby yesterday: http://github.com/harukizaemon/hamster
A true classic!