You’re assuming a stateful process that always updates a fixed reference, but there are other ways to model applications. E.g., stateless serverless functions like Next.js and AWS lambda use, or React pure function components.
In Redux or React component state, the render function gets called with the current state rather than holding a reference to a state tree which must be mutated.
Render gets trigered by state updates (as in a call to store.dispatch() or a useState setter which results in a new state).
Because we can assume immutability with Redux, selectors and pure components can both be safely memoized so that a call passing a reference to the last used state always returns a reference to the last result. The same is not true if you’re mutating state.
In other words, not only is it false that you always need mutation, we can also make some pretty interesting optimizations, like safely skipping all or part of a component tree rerender without needing to deeply dive into an object to see if something changed, indicating that a rerender is required.
With immutable state trees, a single === comparison against the previous state is all we need to determine if we need to rerender or recalculate a selector result. If you mutate any part of the state tree, that === compare won’t be able to detect the mutation, because === for objects only checks root state reference identity, not mutation.
Languages like Haskell take this to an extreme. Mutation is forbidden at the language level. You can’t even compile a program that mutates state in Haskell. Instead, mutation must be simulated with a state monad.
Clojure’s built-in data structures are also immutable. All the update operations return new objects rather than mutating the existing object in place. Memory is automatically optimized using trie data structures, which share references to common data branches in the previous and new objects.