Definitely. But unless special care is taken, these will use (normally) more space, and potentially more time. I think Chris Osaki did a bunch of work on functional data structures for handling immutability efficiently (still less efficiently) and that some of this was implemented in Clojure.