> And it does map so well onto the underlying reality of fundamentally mutable hardware. It maps well to the abstraction provided by the hardware. In reality w

> And it does map so well onto the underlying reality of fundamentally mutable hardware. It maps well to the abstraction provided by the hardware. In reality we know that modern architectures are executing instructions out-of-order for efficiencies' sake and that data-accesses are not necessarily sequential either. And we haven't even considered multiple-core processors that are so common these days! As Bird points out in his book, when one looks close enough there are cases where the logarithmic gap between the imperative vs. functional approach disappears. And further, with register targeting and stuff it's not often true that recursive calls are less efficient than their imperative counterparts anymore... although I suppose historically this could be why, at least for small arrays, imperative programmers could assume constant-time indexing and updating. I'm not nearly as versed in functional programming as I'd like to be. I was raised on C and algorithms were always described in terms of procedures to me where the proofs took quite a bit of work to follow. However as I learn more about algorithm design in functional programming and functional data structures I can't help but notice that the proofs are much easier to follow while sometimes the solution seems quite alien and I wonder if that's because of my heritage of thinking operationally rather than by calculation. I've often been surprised to learn that many of my assumptions about the logarithmic complexity of functional algorithms are not always there!