But the paper that introduced the term 'persistent data structure' said they already existed in Lisp and gave the example of a persistent queue built by sharing the tail of an existing one with a new head?
A Lisp list is a persistent data structure.
> Scheme and CL have immutable data structures, but not persistent data structures.
And I said they do. You've said Clojure persistent data structure offer more. Ok, but I just said they existed in Lisp and they do.
First, conses are mutable so lists are persistent as long as they are used in a persistent way -- it has to be enforced through the codebase (and deps).
Second, lists big-O access/update costs are not as interesting as persistent maps and vectors.