-- 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 <a>shrink</a>ing the
--   slice. This seems like a reasonable tradeoff, and, I believe, mirrors
--   the behavior of the vector library.
--   
--   Highlights:
--   
--   <ul>
--   <li>O(1) append element, indexing, updates, length, and slicing</li>
--   <li>Reasonably compact representation</li>
--   </ul>
@package persistent-vector
@version 0.1.0.0


-- | 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 <tt>i</tt> elements of the vector.
--   
--   Note that this is just a wrapper around slice and the resulting slice
--   retains references that are inaccessible. Use <a>shrink</a> if this is
--   undesirable.
take :: Int -> Vector a -> Vector a

-- | O(1) Drop <tt>i</tt> 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 <tt>v</tt> of length <tt>length</tt> starting
--   at index <tt>start</tt>. The returned vector may have fewer than
--   <tt>length</tt> 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.
--   
--   <pre>
--   slice start length v
--   </pre>
--   
--   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 <a>shrink</a> on the return value of <a>slice</a> 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 <tt>ix</tt> with new value
--   <tt>elt</tt> in <tt>v</tt>.
--   
--   <pre>
--   update ix elt v
--   </pre>
update :: Int -> a -> Vector a -> Vector a

-- | O(n) Bulk update.
--   
--   <pre>
--   v // updates
--   </pre>
--   
--   For each (index, element) pair in <tt>updates</tt>, modify <tt>v</tt>
--   such that the <tt>index</tt>th position of <tt>v</tt> is
--   <tt>element</tt>. Indices in <tt>updates</tt> that are not in
--   <tt>v</tt> 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)
instance Show a => Show (Vector a)
instance NFData a => NFData (Vector a)
instance Traversable Vector
instance Monoid (Vector a)
instance Functor Vector
instance Foldable Vector
instance Ord a => Ord (Vector a)
instance Eq a => Eq (Vector a)