Clojure. The language is built around immutable data structures with the expected interface for maps and vectors, and the idiomatic list-churning we're both referring to is unified through the sequence abstraction. So switching from a vector to a map can often be as simple as switching constructors. Because they're immutable, every operation makes a "copy" but does so efficiently.

I don't have a lot of use for Clojure these days but I enjoyed working with it. Rich Hickey is a smart fella.