so far I've only found vector and sequences, but neither of those could replace an element of a list in O(1). Such data structure would of course violate the immutable character of Haskells structures, but maybe there still exist some dirty implementation? Every feedback is welcom.
1 Answers
As you suggest yourself – I'm also pretty sure a safe, purely-functional update in O(1) is not possible. What is possible is in O(log n) with a tree-like implementation; for instance, instead of [a] you could use Data.Map.Map Int a with a contiguous region of indices. Also, it is possible to do a batch update of k ≤ n elements in a list or vector, in only O(n) instead of the O(k·n) it would take to manually insert them one-by-one. Check out //.
If none of that is fast enough for you, then yes, you will need to go into the dark realm of mutability. Fortunately, Haskell offers a good safety armour and flashlight for such journeys: the ST monad. The way it works is, you wrap the entire region where you need to do mutable updates in runST. Inside that region, you use MVectors, which support O(1) mutable element updates, much like you could in an imperative language. But thanks to a type-system trick, runST ensures that all these side-effects stay confined to within the local scope.
Related