-- 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.2.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 -- | <math> The empty vector. empty :: Vector a -- | <math> Construct a vector with a single element. singleton :: a -> Vector a -- | <math> Append an element to the end of the vector. snoc :: Vector a -> a -> Vector a -- | <math> Construct a vector from a list fromList :: [a] -> Vector a -- | <math> Append two Vector instances -- -- 
--   append v1 v2
--
-- -- This operation is linear in the length of v2 (where -- length v1 == n and length v2 == m). append :: Vector a -> Vector a -> Vector a -- | <math> Test to see if the vector is empty. null :: Vector a -> Bool -- | <math> Get the length of the vector. length :: Vector a -> Int -- | <math> Bounds-checked indexing into a vector. index :: Vector a -> Int -> Maybe a -- | <math> Unchecked indexing into a vector. -- -- Out-of-bounds indexing might not even crash—it will usually just -- return nonsense values. -- -- Note: the actual lookup is not performed until the result is forced. -- This can cause a memory leak if the result of indexing is stored, -- unforced, after the rest of the vector becomes garbage. To avoid this, -- use unsafeIndexA or unsafeIndex# instead. unsafeIndex :: Vector a -> Int -> a -- | <math> Unchecked indexing into a vector in the context of an -- arbitrary Applicative functor. If the Applicative is -- "strict" (such as IO, (strict) ST s, (strict) -- StateT, or Maybe, but not Identity, -- ReaderT, etc.), then the lookup is performed before the next -- action. This avoids space leaks that can result from lazy uses of -- unsafeIndex. See the documentation for unsafeIndex# for -- a custom Applicative that can be especially useful in -- conjunction with this function. -- -- Note that out-of-bounds indexing might not even crash—it will usually -- just return nonsense values. unsafeIndexA :: Applicative f => Vector a -> Int -> f a -- | <math> Unchecked indexing into a vector. -- -- Note that out-of-bounds indexing might not even crash—it will usually -- just return nonsense values. -- -- This function exists mostly because there is not, as yet, a -- well-known, canonical, and convenient lifted unary tuple. So we -- instead offer an eager indexing function returning an unlifted -- unary tuple. Users who prefer to avoid such "low-level" features can -- do something like this: -- -- 
--   data Solo a = Solo a deriving Functor
--   instance Applicative Solo where
--     pure = Solo
--     liftA2 f (Solo a) (Solo b) = Solo (f a b)
--
-- -- Now -- -- 
--   unsafeIndexA :: Vector a -> Int -> Solo a
--
unsafeIndex# :: Vector a -> Int -> (# a #) -- | <math> Take n elements starting from the start of the -- Vector take :: Int -> Vector a -> Vector a -- | <math> Drop n elements starting from the start of the -- Vector drop :: Int -> Vector a -> Vector a -- | <math> Split the vector into two at the given index -- -- Note that this function strictly computes both result vectors (once -- the tuple itself is reduced to whnf) splitAt :: Int -> Vector a -> (Vector a, Vector a) -- | <math> 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
--
slice :: Int -> Int -> Vector a -> Vector a -- | <math> Drop any unused space in the vector -- -- NOTE: This is currently the identity shrink :: Vector a -> Vector a -- | <math> Update a single element at ix with new value -- elt in v. -- -- 
--   update ix elt v
--
update :: Int -> a -> Vector a -> Vector a -- | <math> 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. The updates are applied in order, so the last -- one at each index takes effegct. (//) :: Vector a -> [(Int, a)] -> Vector a -- | <math> Right fold over the vector foldr :: (a -> b -> b) -> b -> Vector a -> b -- | <math> Strict right fold over the vector. -- -- Note: Strict in the initial accumulator value. foldr' :: (a -> b -> b) -> b -> Vector a -> b -- | <math> Left fold over the vector. foldl :: (b -> a -> b) -> b -> Vector a -> b -- | <math> Strict left fold over the vector. -- -- Note: Strict in the initial accumulator value. foldl' :: (b -> a -> b) -> b -> Vector a -> b -- | <math> Map over the vector map :: (a -> b) -> Vector a -> Vector b -- | <math> Reverse a vector reverse :: Vector a -> Vector a -- | <math> Apply a predicate p to the vector, returning the longest -- prefix of elements that satisfy p. takeWhile :: (a -> Bool) -> Vector a -> Vector a -- | <math> Returns the longest suffix after takeWhile p v. dropWhile :: (a -> Bool) -> Vector a -> Vector a -- | <math> Filter according to the predicate. filter :: (a -> Bool) -> Vector a -> Vector a -- | <math> Return the elements that do and do not obey the predicate partition :: (a -> Bool) -> Vector a -> (Vector a, Vector a) instance GHC.Show.Show a => GHC.Show.Show (Data.Vector.Persistent.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.Semigroup (Data.Vector.Persistent.Vector a) 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) 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 Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Vector.Persistent.Vector_ a)