"Purely Functional Data Structures" by Chris Okasaki [pdf] (opens in new tab)

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.

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.

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/

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 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

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.

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

A true classic!