Of course I agree that calling such data structures immutable is more precise, but it's still in contrast to both imperative programming and imperative data structures. In particular every single functional language (including the purest of the pure) fairly heavily use immutable array based structures in one way or other. So if functional programming requires only using data structures with structural sharing, there are no functional programming languages.