I wouldn't say lists should be replaced with trees, but adding a rich set of tree-based data structures to Lisp improves it substantially, in my view. To see w

I wouldn't say lists should be replaced with trees, but adding a rich set of tree-based data structures to Lisp improves it substantially, in my view. To see what I mean, have a look at my FSet functional collections package, which does exactly that: http://common-lisp.net/project/fset/ Unlike what the OP is suggesting, FSet doesn't expose the internal structure of its trees. Instead it wraps them in a rich set-theoretic interface.