Reasoning about pure functional data structures in the absence of laziness isn't that difficult, any more than the many mutable data structures that have copying/rebuilding/rebalancing that takes place only sometimes. The benefit of pure functional data structures is most visible when there is some kind of sharing -- concurrency of some kind -- in which case, reasoning about side effects becomes more difficult.

There are good approaches to handling in-place array update and similar operations in pure functional programming (the ST monad, for example), it's just not the default. As long as the side effect is somehow accounted for in the return value, referential transparency is maintained; we might say the return value is there to help us reason about side effects.