I think you're referring to "association lists" which definitely predate clojure and are definitely a persistent data structure and very cool in their own right. However, their performance profile is pretty poor (i.e. O(n) lookups) and are therefore rarely used in modern lisp programming anymore, to the best of my knowledge.