I think, though, that this case really highlights the extent to which Knuth's quote gets used in a much wider context than he intended. In the context he was e

I think, though, that this case really highlights the extent to which Knuth's quote gets used in a much wider context than he intended. In the context he was explicitly talking about micro-optimization, not large-scale performance-impacting decisions. The use of the word "prematurely" combined with the tendency to forget the context of that quote means it takes on connotations of implying that if you do something for performance from the get-go, that's bad. That just ain't so; sometimes you really do know what you're doing, and know that one option won't be workable and other one will. Choice of data structures is a case where this often happens. If you know up front that you're going to need O(1) random access and replacement, and O(1) typical case and O(N) worst case appending, and that persistence is not necessary, then you already know you want a mutable list. In that case starting with a persistent equivalent and planning to rework things later is likely just a waste of time and, assuming you're doing this at work, money.