That line of research exists, but it's different from persistent data structures. The search term is "reversible computing", and the main idea is that you never erase bits because that would irreversibly increase entropy. One difference is that persistent data structures allow access to past states in O(1), while reversible computing requires you to spend time on uncomputing. Right now it's mostly a curiosity because it requires hardware that doesn't exist, so I'd be wary of using it as a foundation of CS. It might well become important in the future though, due to lower energy requirements.
Bringing a snowflake back to its previous shape after it has melted?
Of course, we don't have time symmetry in the equations anyway because of the weak force. But because the weak force is weak//doesn't matter much for the physics of many systems, we can often write the equations of physics as a time-symmetric term which essentially decides the motion plus a very small time-asymmetric term. So we can deal with the small term using techniques like perturbation theory, and use time symmetry for the rest.
Could you expand on what you mean here? I've expected for a while that there was going to be something non-time-reversal-symmetric with the weak force, on the basis of parity violation (space-reversal doesn't give you the same equations) plus relativity (space and time are the same thing, at least kind of). But getting there directly from parity violation might require a faster-than-light frame of reference to observe it from, which is... let's just say it's experimentally difficult.
How does the weak force break time symmetry?
If the universe is externally a pure value, it doesn't matter to us on the inside. The universe is impure from our point of view.
Also, a pure data structure doesn't just imply that you have a puddle of water that you can put back together into a snowflake; it practically (that is, in practice, not in the colloquial sense of the term) implies that you have both at the same time. When I'm working with pure data structures I don't have to laboriously translate back and forth, I have them both in hand. This is partially because pure data structures simply have no concept of time at all in them. And you can't save this argument by claiming you can transform them back and forth at will, because as I mentioned, no, you can not. Common sense can be clad with solid mathematical arguments here; you can not, in our real universe, ever do that, so even the superficially appealing theoretical answer must give way to a more sophisticated and correct theoretical analysis in which in fact you can't reverse arbitrary transforms in practice. (You can do it at a small scale for small numbers of qubits. You can do it for a constrained number of qubits specially set up and isolated for just such an occasion, aka "quantum computer".... and note how hard even that is, we've still not managed to isolate very many qubits at a time that way! But you can not do it in general.)
Whether an entity external to our universe could do it is something you'd have to take up with them.
gettimeofday requires IO, so the computation would depend on dynamic inputs, but that doesn't make it impure. If the program knows how long one of its computations took, that's only because an oracle (outer layer of abstraction) told it.
> Another problem with seeing purity as fundamental is that our physical reality isn't a persistent data structure
I like this line of reasoning, but would take the opposite conclusion. The universe is symmetric with respect to time, and indeed, information is conserved. Past states aren't easily accessible, but they have not been erased. This sounds like a fine working definition for persistent data structures.
> there's a strong suspicion that the (pure) type signature of runST has no pure implementation
Interesting, thanks for bringing it up!