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.
If you read introductory functional programming material, you will agree they are full of h::t style pattern matching and default list types in ocaml, haskell and scala are simple linked lists (I sadly haven't tried Clojure yet). I'm open to the possibility of advanced patterns with other data structures overcoming some of these problems that I'm not very familiar with but that's what I mean with impedance mismatch, you will need to step away a bit from the clean elegant patterns of "everything is recursion+pattern matching on lists" of typical FP teaching.
Do you? I don't. I've written loads and loads of production code that never did this. I know it never did it because I wrote it in Haskell and never used an IORef or STRef!