FSet on Common-Lisp.net provides functional data structures as well. This library is also available in Quicklisp, so it's easier to install. And it looks very interesting.