Chris Okasaki's PhD thesis on purely functional data structures (pdf)

[amichail]

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

[nostrademons]

Also available in extended dead-tree form: http://www.amazon.com/Purely-Functional-Structures-Chris-Okasaki/dp/0521663504

I highly recommend the book if you're implementing or using a functional programming language. There're lots of data structures that aren't mentioned at all in traditional imperative-language textbooks. Some of them even have decent performance.