Considering the performance implications of a full commitment to immutable data structures, I think Rust does a pretty good job here.

Dynamic arrays / vectors / slices or whatever you want to call them are probably the most important or fundamental non-plain-old-data data structure, and in a purely immutable environment these are essentially impossible (or have awful performance characteristics).