I ordered another book today: Purely Functional Data Structures by Chris Okasaki.
I downloaded a PDF of his PhD thesis (PDF, 616K) and had a brief flick through. It looks as though some of the structures will be just what I need. One of the main differences (that I am aware of) between the thesis and the book is that the book includes the source code in both ML and Haskell, whereas the thesis only uses ML. The book will, therefore, be of a lot more use to me than the thesis and at less than $AU70, it’ll hardly break the bank.