Having spent a good amount of time doing production FP, and then taking what I learned into imperative work, I rarely find myself doing this. In the real world, what we usually want is the result of adding to a list or changing a value in a map. But also in the real world, we rarely want to consider whether we've affected other things that supplied that list or map (which they generally would prefer we did not do).
> Typically functional programming languages use linked lists to make h::t efficient but if you need performance characteristics of arrays and good performance/low GC you are going to have a lot impedance mismatch with the typical functional programming patterns based on built in lists.
I can't speak for the wide variety of FP languages out there, but it sounds like you've been exposed to languages with a poor set of data structures. Clojure, for example, provides a wealth of great immutable/persistent data structures that provide the semantics you'd want and perform really well.