Racket now has all manner of purely functional data structures (Okasaki and Bagwell) available as a library on Planet:

http://planet.plt-scheme.org/package-source/krhari/pfds.plt/...