yoklov, for some reason I can't reply directly. There are a few common lisp libraries of persistent, immutable data structures that perform well. This one is implemented most closely to Clojure's: https://github.com/ks/X.FDATATYPES . This one has been around for a long time and is quite stable: http://common-lisp.net/project/fset/Site/index.html .
