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