I was interested how common data structures were implemented in FP languages and decided to read Purely Functional Data Structures by Chris Okasaki. I can’t say that I understood all parts of this book, especially the last chapters. But reading and solving exercises from the book gave me some thoughts. And I guess I got more than enough answers to almost all my questions about functional data structures.
Also a good thing in this book — all examples are in SML and Haskell. And reading examples in SML is a more pleasure than reading them in C or Java, at least for me.