-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | A persistent sequence based on array mapped tries -- -- This package provides persistent vectors based on array mapped tries. -- The implementation is based on the persistent vectors used in clojure, -- but in a Haskell-style API. The API is modeled after Data.Sequence -- from the containers library. -- -- Technically, the element-wise operations are O(log(n)), but the -- underlying tree cannot be more than 7 or 8 levels deep so this is -- effectively constant time. -- -- One change from the clojure implementation is that this version -- supports O(1) slicing, though it does cheat a little. Slices retain -- references to elements that cannot be indexed. These extra references -- (and the space they occupy) can be reclaimed by shrinking the -- slice. This seems like a reasonable tradeoff, and, I believe, mirrors -- the behavior of the vector library. -- -- Highlights: -- -- @package persistent-vector @version 0.1.0.3 -- | This is a port of the persistent vector from clojure to Haskell. It is -- spine-strict and lazy in the elements. -- -- The implementation is based on array mapped tries. The complexity -- bounds given are mostly O(1), but only if you are willing to accept -- that the tree cannot have height greater than 7 on 32 bit systems and -- maybe 8 on 64 bit systems. module Data.Vector.Persistent -- | Persistent vectors based on array mapped tries data Vector a -- | O(1) The empty vector empty :: Vector a -- | O(1) Construct a vector with a single element. singleton :: a -> Vector a -- | O(1) Append an element to the end of the vector. snoc :: Vector a -> a -> Vector a -- | O(n) Construct a vector from a list. fromList :: [a] -> Vector a -- | O(1) Test to see if the vector is empty. null :: Vector a -> Bool -- | O(1) Get the length of the vector. length :: Vector a -> Int -- | O(1) Bounds-checked indexing into a vector. index :: Vector a -> Int -> Maybe a -- | O(1) Unchecked indexing into a vector. -- -- Note that out-of-bounds indexing might not even crash - it will -- usually just return nonsense values. unsafeIndex :: Vector a -> Int -> a -- | O(1) Take the first i elements of the vector. -- -- Note that this is just a wrapper around slice and the resulting slice -- retains references that are inaccessible. Use shrink if this is -- undesirable. take :: Int -> Vector a -> Vector a -- | O(1) Drop i elements from the front of the vector. -- -- Note that this is just a wrapper around slice. drop :: Int -> Vector a -> Vector a -- | O(1) Split the vector at the given position. splitAt :: Int -> Vector a -> (Vector a, Vector a) -- | O(1) Return a slice of v of length length starting -- at index start. The returned vector may have fewer than -- length elements if the bounds are off on either side (the -- start is negative or length takes it past the end). -- -- A slice of negative or zero length is the empty vector. -- -- 
--   slice start length v
--
-- -- Note that a slice retains all of the references that the vector it is -- derived from has. They are not reachable via any traversals and are -- not counted towards its size, but this may lead to references living -- longer than intended. If is important to you that this not happen, -- call shrink on the return value of slice to drop unused -- space and references. slice :: Int -> Int -> Vector a -> Vector a -- | O(n) Force a sliced vector to drop any unneeded space and references. -- -- This is a no-op for an un-sliced vector. shrink :: Vector a -> Vector a -- | O(1) Update a single element at ix with new value -- elt in v. -- -- 
--   update ix elt v
--
update :: Int -> a -> Vector a -> Vector a -- | O(n) Bulk update. -- -- 
--   v // updates
--
-- -- For each (index, element) pair in updates, modify v -- such that the indexth position of v is -- element. Indices in updates that are not in -- v are ignored (//) :: Vector a -> [(Int, a)] -> Vector a -- | O(n) Right fold over the vector foldr :: (a -> b -> b) -> b -> Vector a -> b -- | O(n) Strict left fold over the vector foldl' :: (b -> a -> b) -> b -> Vector a -> b -- | O(n) Map over the vector map :: (a -> b) -> Vector a -> Vector b -- | O(n) Reverse a vector reverse :: Vector a -> Vector a -- | O(n) Filter according to the predicate filter :: (a -> Bool) -> Vector a -> Vector a -- | O(n) Return the elements that do and do not obey the predicate partition :: (a -> Bool) -> Vector a -> (Vector a, Vector a) -- | O(n) Apply a predicate p to the vector, returning the longest -- prefix of elements that satisfy p. takeWhile :: (a -> Bool) -> Vector a -> Vector a -- | O(n) Returns the longest suffix after takeWhile p v. dropWhile :: (a -> Bool) -> Vector a -> Vector a instance GHC.Show.Show a => GHC.Show.Show (Data.Vector.Persistent.Vector a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Vector.Persistent.Vector a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Vector.Persistent.Vector a) instance Data.Foldable.Foldable Data.Vector.Persistent.Vector instance GHC.Base.Functor Data.Vector.Persistent.Vector instance GHC.Base.Monoid (Data.Vector.Persistent.Vector a) instance Data.Traversable.Traversable Data.Vector.Persistent.Vector instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Vector.Persistent.Vector a)