At the lowest levels, the pattern can be reversed: you provide a nice functional shell around a little bit of imperative core (e.g. implementing "map" with a loop).
ST is exactly the same sort of thing junke was talking about, except it also uses the type system to ensure the imperative core doesn't leak into the outside world.
I think the grandparent comment boils down to saying "there's no known persistent data structure with O(1) random access for read and write". Whether you need such a structure (for a cache, histogram, frame buffer, etc.) is up to you.
Some functional languages allow transient data structures (via something like ST or uniqueness types), so you can match the performance of any imperative algorithm at the cost of ugly code.
> Note also that all of this discusses only asymptotic running times. Many techniques for implementing purely functional data structures give you a certain amount of constant factor slowdown, due to extra bookkeeping necessary for them to work, and implementation details of the language in question. The benefits of purely functional data structures may outweigh these constant factor slowdowns, so you will generally need to make trade-offs based on the problem in question.
Hash tables are a big example. You can implement pure associative arrays, and they have some nice benefits, but the best functional implementations still have much poorer asymptotic performance than a basic hash table.
Pure data structures also tend to include a lot of extra pointers. That can create a lot of overhead. A pure list of 32-bit integers will need either 4 or 8 bytes of overhead (depending on whether you're running 32 or 64 bit) for every item stored. A resizable array just needs whatever empty space it preallocates, plus the occasional memcpy when it needs to add capacity. Also locality of reference and all that fun stuff.
Another example: Caching of results, transparent to the user of your function. If your function is otherwise pure you can simply use its parameter and hash them for a key to your result index. Examples where I've used this: Caching of regex results, replacing file reads with modification date polls and read from cache if not changed..
I was disappointed to learn that Quicksort implemented functionally is almost always much much slower than if implemented procedurally, to the point that functional langs use other sorts such as mergesort. What makes it extra annoying is that Quicksort implemented functionally is so damn elegant!
Neural networks are a good example where mutable structures are the only realistic choice. You're dealing with fully connected networks of millions of nodes, each of which needs to be updated multiple times for each layer at every pass.
Yes, but the domain of your computer memory is surprisingly disjoint from the domain of your business logic, and that's really what matters here.
Consider a counter-example, where calling a functional method that takes an object and creates a copy with a new field updated (a classic pattern for introducing immutability to a mutable environment). What if internally the constructor calls a log call or increments a shared resource tally?
Not unreasonable, but in a functional context an update now has weird side effects that creates misleading results.
CakeML, a Standard ML subset, can compile to ASM with mathematical proof of correctness. You know your ASM will be what you expected it to be. There's also tools like QuickCheck, QuickSpec, and SPARK that can automate lots of analysis. Tons of work like this in compilers and static analysis with smart people always improving them.
Good chance your business logic will not be handled that well. So, good to structure it in a way to facilitate easy analysis or optimization by tools that currently exist or are in development. You get long-term benefits.
But the abstraction there is a lot more battle-hardened than your business logic at $COMPANY. Not that compiler bugs never happen, but it's comparatively quite rare.
Combining the two ideas
Transient imperative logic in the core (5%), Functional mantle (90%), Side-effecting imperative crust (5%).