Applicative-order languages don't support constant time array writes? If not, why not?

I'm reading Steven Skiena's "The Algorithm Design Manual", and in one of his War Stories on page 155 he states:

Efficiency is a great challenge in Mathematica, due to its applicative model of computation (it does not support constant-time write operations to arrays) and the overhead of interpretation (as opposed to compilation).

I've already read SICP so I'm familiar with the difference between applicative and normal-order languages (i.e. that normal-order languages delay evaluation of procedure arguments until they're needed, whereas applicative-order languages evaluate them as soon as the procedure is called). But Skiena's sentence above appears to link the idea of applicative-order languages with the idea of worse-than-constant-time array writes. I don't remember Abelson and Sussman mentioning this in their text, so this came as a surprise.

If true, what are the under-the-hood reasons for why applicative-order languages don't write to arrays in constant time? Why would the order of evaluation matter in determining array write time?

I'm also curious what the Big-O write performance is in this case, but I imagine that depends on the language implementation, so I'll skip that question unless there's a definitive answer.

In a purely functional language, such as Haskell, you apply functions to values and produce new values just as in mathematics. Like math, in such a language, variables are just names for values. If you say "let $x$ be $1$", then $x$ and $1$ are everywhere interchangeable. It makes no more sense to talk of "mutating" $x$ to be $2$ than it does to say to set $1$ to be $2$. For array this means that to "update" an array, you build a new array with the changes. Obviously, building an entire copy of an array except for the one entry you're changing is expensive. This is almost certainly the issue Skiena is referring to.