Guest User

Untitled

a guest
Aug 17th, 2018
69
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.50 KB | None | 0 0
  1. How can I ensure amortized O(n) concatenation from Data.Vector?
  2. import Data.Vector((++),Vector)
  3. import Prelude hiding ((++))
  4. import Control.Monad.State.Strict
  5.  
  6. data App = S (Vector Int)
  7.  
  8. add :: Vector Int -> State App ()
  9. add v1 = modify (S v2 -> S (v2 ++ v1))
  10.  
  11. add v1 = do
  12. S v2 <- get
  13. let v3 = runST $ do
  14. m1 <- unsafeThaw v2
  15. m2 <- unsafeGrow m1 (length v1)
  16. -- copy contents of v1 behind contents of v2
  17. unsafeFreeze m2
  18. put (S v3)
Add Comment
Please, Sign In to add comment