This doesn't really explain why it has to be that way. I'm not really a fan of "it is because it is" design.
It doesn't seem like there's any particular reason that a state reconstruction algorithm needs to be more expensive than O(1). What kind of advantages does this design have that an append store wouldn't give?
Redux was built as an implementation of the Flux Architecture. In Flux, you have different "stores" for different types of data (such as a `UsersStore`, `PostsStore`, and `CommentsStore`). One of the key concepts of Redux is that instead of having separate stores for each type of data, you can have separate "reducer functions" that are responsible for initializing and updating those data sets, and write another function that combines all of them together into a single object state tree. So, the standard encouraged approach is that the root reducer function delegates the work of updating each "slice" in the state tree to smaller functions, and so on ad infinitum. That way, each individual slice reducer function can be written and understood in isolation.
My blog post "The Tao of Redux, Part 1 - Implementation and Intent" goes into a lot of detail on the history, design, and influences behind Redux [0], and Dan's post "You Might Not Need Redux" [1] talks about the tradeoffs that Redux asks you to make and the kinds of benefits you get in return.
Arrays end up being a bigger pain to deal with when updating.
If the User marks TODO item #17 as complete (or deletes it), you have to either dig through the state array looking for the TODO with the matching ID, which is O(n), right? I'm sure there are times an array is more conventient. These trade offs are in the redux docs.
And this is one of many reasons why Redux encourages you to normalize your state - you can retrieve any item with a couple simple direct lookups (such as `state.entities[type].byId[id]`), rather than mapping over an array comparing item IDs. Granted, O(n) array loops aren't likely to be a real perf issue until you hit fairly large values of N.
It doesn't seem like there's any particular reason that a state reconstruction algorithm needs to be more expensive than O(1). What kind of advantages does this design have that an append store wouldn't give?