First, you'd still have optional mutability. Second, arrays are rather simple data structures, but ones where you often care about performance--small tight loops are common. Compare that to the data structure that eg holding your options and flags for the computation: you don't do much computation on that, but you have lots of invariants that you want to uphold---ie lots of code, but each bit executed roughly once, no tight loops.

I assume using some form of copy-on-write.

Naïve algorithms on immutable data structurs tend to have very bad worst case performance.