I have an application where it is efficient to use Vectors for one part of the code. However, during the computation I need to keep track of some of the elements. I have heard that you can get O(n) amortized concatenation from Data.Vectors (by the usual array growing trick) but I think that I am not doing it right. So lets say we have the following setup:
import Data.Vector((++),Vector)
import Prelude hiding ((++))
import Control.Monad.State.Strict
data App = S (Vector Int)
add :: Vector Int -> State App ()
add v1 = modify (\S v2 -> S (v2 ++ v1))
Does add run in amortized O(n) time in this case? If not, how can I make add do that (do I need to store an (forall s. MVector s Int) in the State?). Is there a more efficient way of implementing add?
I don't know the vector library well either, so I have to stick to general principles mostly. Benchmark it, run a sequence of adds similar to what you expect in your application and see what performance you get. If it's 'good enough', great, stick with the simple code. If not, before storing a (forall s. MVector s Int) in the state (which you can't directly, tuples can't hold forall-types, so you'd need to wrap it), try improving the add-behaviour by converting to mutable vectors and perform the concatenation there before freezing to get an immutable vector again, roughly
add v1 = do
S v2 <- get
let v3 = runST $ do
m1 <- unsafeThaw v2
m2 <- unsafeGrow m1 (length v1)
-- copy contents of v1 behind contents of v2
unsafeFreeze m2
put (S v3)
You may need to insert some strictness there. However, if unsafeGrow needs to copy, that will not guarantee amortized O(n) behaviour.
You can get amortized O(n) behaviour by