-- Hoogle documentation, generated by Haddock -- See Hoogle, http://www.haskell.org/hoogle/ -- | Non-empty vectors -- -- Performant non-empty mutable and immutable vectors. These vectors -- strive to implement the common APIs seen in vector without any -- additional performance cost. @package nonempty-vector @version 0.1.0.0 -- | A library for non-empty boxed vectors (that is, polymorphic arrays -- capable of holding any Haskell value). Non-empty vectors come in two -- flavors: -- -- -- -- This library attempts to provide support for all standard -- Vector operations in the API, with some slight variation in -- types and implementation. For example, since head and -- foldr are always gauranteed to be over a non-empty -- Vector, it is safe to make use of the 'unsafe-*' Vector -- operations and semigroupal folds available in the API in lieu of the -- standard implementations. -- -- In contrast, some operations such as filter may "break out" of -- a NonEmptyVector due to the fact that there are no guarantees -- that may be made on the types of Bool-valued functions passed -- in, hence one could write the following: -- -- 
--   filter (const false) v
--
-- -- which always produces an empty vector. Thus, some operations must -- return either a Maybe containing a NonEmptyVector or a -- Vector whenever appropriate. Generally The former is used in -- initialization and generation operations, and the latter is used in -- iterative operations where the intent is not to create an instance of -- NonEmptyVector. -- -- Credit to Roman Leshchinskiy for the original Vector library upon -- which this is based. module Data.Vector.NonEmpty -- | NonEmptyVector is a thin wrapper around Vector that -- witnesses an API requiring non-empty construction, initialization, and -- generation of non-empty vectors by design. -- -- A newtype wrapper was chosen so that no new pointer indirection is -- introduced when working with Vectors, and all performance -- characteristics inherited from the Vector API still apply. data NonEmptyVector a -- | O(1) Length. length :: NonEmptyVector a -> Int -- | O(1) First element. Since head is gauranteed, bounds checks are -- bypassed by deferring to unsafeHead. head :: NonEmptyVector a -> a -- | O(1) Last element. Since a last element is gauranteed, bounds -- checks are bypassed by deferring to unsafeLast. last :: NonEmptyVector a -> a -- | O(1) Indexing. (!) :: NonEmptyVector a -> Int -> a -- | O(1) Safe indexing. (!?) :: NonEmptyVector a -> Int -> Maybe a -- | O(1) Unsafe indexing without bounds checking unsafeIndex :: NonEmptyVector a -> Int -> a -- | O(1) First element of a non-empty vector in a monad. -- -- See indexM for an explanation of why this is useful. -- -- Note that this function defers to unsafeHeadM since head is -- gauranteed to be safe by construction. headM :: Monad m => NonEmptyVector a -> m a -- | O(1) Last element of a non-empty vector in a monad. See -- indexM for an explanation of why this is useful. -- -- Note that this function defers to unsafeHeadM since a last -- element is gauranteed. lastM :: Monad m => NonEmptyVector a -> m a -- | O(1) Indexing in a monad. -- -- The monad allows operations to be strict in the non-empty vector when -- necessary. -- -- See indexM for more details indexM :: Monad m => NonEmptyVector a -> Int -> m a -- | O(1) Indexing in a monad without bounds checks. See indexM for -- an explanation of why this is useful. unsafeIndexM :: Monad m => NonEmptyVector a -> Int -> m a -- | O(1) Yield all but the first element without copying. Since the -- vector returned may be empty (i.e. input was a singleton), this -- function returns a normal Vector tail :: NonEmptyVector a -> Vector a -- | O(1) Yield a slice of the non-empty vector without copying it. -- The vector must contain at least i+n elements. Because this is not -- guaranteed, this function returns a Vector which could be empty slice :: Int -> Int -> NonEmptyVector a -> Vector a -- | O(1) Yield all but the last element without copying. Since the -- vector returned may be empty (i.e. input was a singleton), this -- function returns a normal Vector init :: NonEmptyVector a -> Vector a -- | O(1) Yield at the first n elements without copying. The -- non-empty vector may contain less than n elements in which case it is -- returned as a vector unchanged. take :: Int -> NonEmptyVector a -> Vector a -- | O(1) Yield all but the first n elements without copying. The -- non-empty vector may contain less than n elements in which case an -- empty vector is returned. drop :: Int -> NonEmptyVector a -> Vector a -- | O(1) Yield the first n elements paired with the remainder -- without copying. -- -- This function returns a pair of vectors, as one may slice a (0, n+1). splitAt :: Int -> NonEmptyVector a -> (Vector a, Vector a) -- | O(1) Yield a slice of the vector without copying. The vector -- must contain at least i+n elements but this is not checked. unsafeSlice :: Int -> Int -> NonEmptyVector a -> Vector a -- | O(1) Yield the first n elements without copying. The vector -- must contain at least n elements but this is not checked. unsafeTake :: Int -> NonEmptyVector a -> Vector a -- | O(1) Yield all but the first n elements without copying. The -- vector must contain at least n elements but this is not checked. unsafeDrop :: Int -> NonEmptyVector a -> Vector a -- | O(1) Non-empty vector with exactly one element singleton :: a -> NonEmptyVector a -- | O(n) Non-empty vector of the given length with the same value -- in each position. -- -- When given a index n <= 0, then Nothing is returned, -- otherwise Just. replicate :: Int -> a -> Maybe (NonEmptyVector a) -- | O(n) Construct a vector of the given length by applying the -- function to each index. -- -- When given a index n <= 0, then Nothing is returned, -- otherwise Just. generate :: Int -> (Int -> a) -> Maybe (NonEmptyVector a) -- | O(n) Apply function n times to value. Zeroth element is -- original value. -- -- When given a index n <= 0, then Nothing is returned, -- otherwise Just. iterateN :: Int -> (a -> a) -> a -> Maybe (NonEmptyVector a) -- | O(n) Execute the monadic action the given number of times and -- store the results in a vector. -- -- When given a index n <= 0, then Nothing is returned, -- otherwise Just. replicateM :: Monad m => Int -> m a -> m (Maybe (NonEmptyVector a)) -- | O(n) Construct a vector of the given length by applying the -- monadic action to each index -- -- When given a index n <= 0, then Nothing is returned, -- otherwise Just. generateM :: Monad m => Int -> (Int -> m a) -> m (Maybe (NonEmptyVector a)) -- | O(n) Apply monadic function n times to value. Zeroth element is -- original value. -- -- When given a index n <= 0, then Nothing is returned, -- otherwise Just. iterateNM :: Monad m => Int -> (a -> m a) -> a -> m (Maybe (NonEmptyVector a)) -- | Execute the monadic action and freeze the resulting non-empty vector. create :: (forall s. ST s (MVector s a)) -> Maybe (NonEmptyVector a) -- | Execute the monadic action and freeze the resulting non-empty vector. createT :: Traversable t => (forall s. ST s (t (MVector s a))) -> t (Maybe (NonEmptyVector a)) -- | O(n) Construct a non-empty vector by repeatedly applying the -- generator function to a seed. The generator function yields -- Just the next element and the new seed or Nothing if -- there are no more elements. -- -- If an unfold does not create meaningful values, Nothing is -- returned. Otherwise, Just containing a non-empty vector is -- returned. unfoldr :: (b -> Maybe (a, b)) -> b -> Maybe (NonEmptyVector a) -- | O(n) Construct a vector with at most n elements by repeatedly -- applying the generator function to a seed. The generator function -- yields Just the next element and the new seed or Nothing -- if there are no more elements. -- -- If an unfold does not create meaningful values, Nothing is -- returned. Otherwise, Just containing a non-empty vector is -- returned. unfoldrN :: Int -> (b -> Maybe (a, b)) -> b -> Maybe (NonEmptyVector a) -- | O(n) Construct a non-empty vector by repeatedly applying the -- monadic generator function to a seed. The generator function yields -- Just the next element and the new seed or Nothing if there are no more -- elements. -- -- If an unfold does not create meaningful values, Nothing is -- returned. Otherwise, Just containing a non-empty vector is -- returned. unfoldrM :: Monad m => (b -> m (Maybe (a, b))) -> b -> m (Maybe (NonEmptyVector a)) -- | O(n) Construct a non-empty vector by repeatedly applying the -- monadic generator function to a seed. The generator function yields -- Just the next element and the new seed or Nothing if there are no more -- elements. -- -- If an unfold does not create meaningful values, Nothing is -- returned. Otherwise, Just containing a non-empty vector is -- returned. unfoldrNM :: Monad m => Int -> (b -> m (Maybe (a, b))) -> b -> m (Maybe (NonEmptyVector a)) -- | O(n) Construct a non-empty vector with n elements by repeatedly -- applying the generator function to the already constructed part of the -- vector. -- -- If constructN does not create meaningful values, Nothing -- is returned. Otherwise, Just containing a non-empty vector is -- returned. constructN :: Int -> (Vector a -> a) -> Maybe (NonEmptyVector a) -- | O(n) Construct a vector with n elements from right to left by -- repeatedly applying the generator function to the already constructed -- part of the vector. -- -- If constructrN does not create meaningful values, -- Nothing is returned. Otherwise, Just containing a -- non-empty vector is returned. constructrN :: Int -> (Vector a -> a) -> Maybe (NonEmptyVector a) -- | O(n) Yield a non-emptyvector of the given length containing the -- values x, x+1 etc. This operation is usually more efficient than -- enumFromTo. -- -- If an enumeration does not use meaningful indices, Nothing is -- returned, otherwise, Just containing a non-empty vector. enumFromN :: Num a => a -> Int -> Maybe (NonEmptyVector a) -- | O(n) Yield a non-empty vector of the given length containing -- the values x, x+y, x+y+y etc. This operations is usually more -- efficient than enumFromThenTo. -- -- If an enumeration does not use meaningful indices, Nothing is -- returned, otherwise, Just containing a non-empty vector. enumFromStepN :: Num a => a -> a -> Int -> Maybe (NonEmptyVector a) -- | O(n) Enumerate values from x to y. -- -- If an enumeration does not use meaningful indices, Nothing is -- returned, otherwise, Just containing a non-empty vector. -- -- WARNING: This operation can be very inefficient. If at all -- possible, use enumFromN instead. enumFromTo :: Enum a => a -> a -> Maybe (NonEmptyVector a) -- | O(n) Enumerate values from x to y with a specific step z. -- -- If an enumeration does not use meaningful indices, Nothing is -- returned, otherwise, Just containing a non-empty vector. -- -- WARNING: This operation can be very inefficient. If at all -- possible, use enumFromStepN instead. enumFromThenTo :: Enum a => a -> a -> a -> Maybe (NonEmptyVector a) -- | O(n) Prepend an element cons :: a -> NonEmptyVector a -> NonEmptyVector a -- | O(n) Append an element snoc :: NonEmptyVector a -> a -> NonEmptyVector a -- | O(m+n) Concatenate two non-empty vectors (++) :: NonEmptyVector a -> NonEmptyVector a -> NonEmptyVector a -- | O(n) Concatenate all non-empty vectors in the list -- -- If list is empty, Nothing is returned, otherwise Just -- containing the concatenated non-empty vectors concat :: [NonEmptyVector a] -> Maybe (NonEmptyVector a) -- | O(n) Concatenate all non-empty vectors in a non-empty list. concat1 :: NonEmpty (NonEmptyVector a) -> NonEmptyVector a -- | O(n) Yield the argument but force it not to retain any extra -- memory, possibly by copying it. force :: NonEmptyVector a -> NonEmptyVector a -- | O(n) Convert a non-empty vector to a non-empty list. toNonEmpty :: NonEmptyVector a -> NonEmpty a -- | O(n) Convert from a non-empty list to a non-empty vector. fromNonEmpty :: NonEmpty a -> NonEmptyVector a -- | O(n) Convert from the first n-elements of a non-empty list to a -- non-empty vector. -- -- Returns Nothing if indices are <= 0, otherwise Just -- containing the non-empty vector. fromNonEmptyN :: Int -> NonEmpty a -> Maybe (NonEmptyVector a) -- | O(1) Convert from a non-empty vector to a vector. toVector :: NonEmptyVector a -> Vector a -- | O(1) Convert from a vector to a non-empty vector. -- -- If the vector is empty, then Nothing is returned, otherwise -- Just containing the non-empty vector. fromVector :: Vector a -> Maybe (NonEmptyVector a) -- | O(n) Convert from a non-empty vector to a list. toList :: NonEmptyVector a -> [a] -- | O(n) Convert from a list to a non-empty vector. fromList :: [a] -> Maybe (NonEmptyVector a) -- | O(n) Convert the first n elements of a list to a non-empty -- vector. -- -- If the list is empty or <= 0 elements are chosen, Nothing is -- returned, otherwise Just containing the non-empty vector fromListN :: Int -> [a] -> Maybe (NonEmptyVector a) -- | O(m+n) For each pair (i,a) from the list, replace the non-empty -- vector element at position i by a. (//) :: NonEmptyVector a -> [(Int, a)] -> NonEmptyVector a -- | O(m+n) For each pair (i,a) from the vector of index/value pairs, -- replace the vector element at position i by a. update :: NonEmptyVector a -> Vector (Int, a) -> NonEmptyVector a -- | O(m+min(n1,n2)) For each index i from the index vector and the -- corresponding value a from the value vector, replace the element of -- the initial vector at position i by a. update_ :: NonEmptyVector a -> Vector Int -> Vector a -> NonEmptyVector a -- | Same as '(//)' but without bounds checking. unsafeUpd :: NonEmptyVector a -> [(Int, a)] -> NonEmptyVector a -- | Same as update but without bounds checking. unsafeUpdate :: NonEmptyVector a -> Vector (Int, a) -> NonEmptyVector a -- | Same as update_ but without bounds checking. unsafeUpdate_ :: NonEmptyVector a -> Vector Int -> Vector a -> NonEmptyVector a -- | O(m+n) For each pair (i,b) from the non-empty list, -- replace the non-empty vector element a at position i -- by f a b. accum :: (a -> b -> a) -> NonEmptyVector a -> [(Int, b)] -> NonEmptyVector a -- | O(m+n) For each pair (i,b) from the vector of pairs, -- replace the non-empty vector element a at position i -- by f a b. accumulate :: (a -> b -> a) -> NonEmptyVector a -> Vector (Int, b) -> NonEmptyVector a -- | O(m+min(n1,n2)) For each index i from the index vector -- and the corresponding value b from the the value vector, -- replace the element of the initial non-empty vector at position -- i by f a b. accumulate_ :: (a -> b -> a) -> NonEmptyVector a -> Vector Int -> Vector b -> NonEmptyVector a -- | Same as accum but without bounds checking. unsafeAccum :: (a -> b -> a) -> NonEmptyVector a -> [(Int, b)] -> NonEmptyVector a -- | Same as accumulate but without bounds checking. unsafeAccumulate :: (a -> b -> a) -> NonEmptyVector a -> Vector (Int, b) -> NonEmptyVector a -- | Same as accumulate_ but without bounds checking. unsafeAccumulate_ :: (a -> b -> a) -> NonEmptyVector a -> Vector Int -> Vector b -> NonEmptyVector a -- | O(n) Reverse a non-empty vector reverse :: NonEmptyVector a -> NonEmptyVector a -- | O(n) Yield the non-empty vector obtained by replacing each -- element i of the non-empty index vector by -- xs!i. This is equivalent to map -- (xs!) is but is often much more efficient. backpermute :: NonEmptyVector a -> NonEmptyVector Int -> NonEmptyVector a -- | Same as backpermute but without bounds checking. unsafeBackpermute :: NonEmptyVector a -> NonEmptyVector Int -> NonEmptyVector a -- | Apply a destructive operation to a non-empty vector. The operation -- will be performed in place if it is safe to do so and will modify a -- copy of the non-empty vector otherwise. modify :: (forall s. MVector s a -> ST s ()) -> NonEmptyVector a -> NonEmptyVector a -- | O(n) Pair each element in a vector with its index. indexed :: NonEmptyVector a -> NonEmptyVector (Int, a) -- | O(n) Map a function over a non-empty vector. map :: (a -> b) -> NonEmptyVector a -> NonEmptyVector b -- | O(n) Apply a function to every element of a non-empty vector -- and its index. imap :: (Int -> a -> b) -> NonEmptyVector a -> NonEmptyVector b -- | Map a function over a vector and concatenate the results. concatMap :: (a -> NonEmptyVector b) -> NonEmptyVector a -> NonEmptyVector b -- | O(n) Apply the monadic action to all elements of the non-empty -- vector, yielding non-empty vector of results. mapM :: Monad m => (a -> m b) -> NonEmptyVector a -> m (NonEmptyVector b) -- | O(n) Apply the monadic action to every element of a non-empty -- vector and its index, yielding a non-empty vector of results. imapM :: Monad m => (Int -> a -> m b) -> NonEmptyVector a -> m (NonEmptyVector b) -- | O(n) Apply the monadic action to all elements of a non-empty -- vector and ignore the results. mapM_ :: Monad m => (a -> m b) -> NonEmptyVector a -> m () -- | O(n) Apply the monadic action to every element of a non-emptpy -- vector and its index, ignoring the results imapM_ :: Monad m => (Int -> a -> m b) -> NonEmptyVector a -> m () -- | O(n) Apply the monadic action to all elements of the non-empty -- vector, yielding a non0empty vector of results. -- -- Equivalent to flip mapM. forM :: Monad m => NonEmptyVector a -> (a -> m b) -> m (NonEmptyVector b) -- | O(n) Apply the monadic action to all elements of a non-empty -- vector and ignore the results. -- -- Equivalent to flip mapM_. forM_ :: Monad m => NonEmptyVector a -> (a -> m b) -> m () -- | O(min(m,n)) Zip two non-empty vectors with the given function. zipWith :: (a -> b -> c) -> NonEmptyVector a -> NonEmptyVector b -> NonEmptyVector c -- | Zip three non-empty vectors with the given function. zipWith3 :: (a -> b -> c -> d) -> NonEmptyVector a -> NonEmptyVector b -> NonEmptyVector c -> NonEmptyVector d -- | Zip four non-empty vectors with the given function. zipWith4 :: (a -> b -> c -> d -> e) -> NonEmptyVector a -> NonEmptyVector b -> NonEmptyVector c -> NonEmptyVector d -> NonEmptyVector e -- | Zip five non-empty vectors with the given function. zipWith5 :: (a -> b -> c -> d -> e -> f) -> NonEmptyVector a -> NonEmptyVector b -> NonEmptyVector c -> NonEmptyVector d -> NonEmptyVector e -> NonEmptyVector f -- | Zip six non-empty vectors with the given function. zipWith6 :: (a -> b -> c -> d -> e -> f -> g) -> NonEmptyVector a -> NonEmptyVector b -> NonEmptyVector c -> NonEmptyVector d -> NonEmptyVector e -> NonEmptyVector f -> NonEmptyVector g -- | O(min(m,n)) Zip two non-empty vectors with a function that also -- takes the elements' indices. izipWith :: (Int -> a -> b -> c) -> NonEmptyVector a -> NonEmptyVector b -> NonEmptyVector c -- | Zip three non-empty vectors and their indices with the given function. izipWith3 :: (Int -> a -> b -> c -> d) -> NonEmptyVector a -> NonEmptyVector b -> NonEmptyVector c -> NonEmptyVector d -- | Zip four non-empty vectors and their indices with the given function. izipWith4 :: (Int -> a -> b -> c -> d -> e) -> NonEmptyVector a -> NonEmptyVector b -> NonEmptyVector c -> NonEmptyVector d -> NonEmptyVector e -- | Zip five non-empty vectors and their indices with the given function. izipWith5 :: (Int -> a -> b -> c -> d -> e -> f) -> NonEmptyVector a -> NonEmptyVector b -> NonEmptyVector c -> NonEmptyVector d -> NonEmptyVector e -> NonEmptyVector f -- | Zip six non-empty vectors and their indices with the given function. izipWith6 :: (Int -> a -> b -> c -> d -> e -> f -> g) -> NonEmptyVector a -> NonEmptyVector b -> NonEmptyVector c -> NonEmptyVector d -> NonEmptyVector e -> NonEmptyVector f -> NonEmptyVector g -- | O(min(n,m)) Elementwise pairing of non-empty vector elements. zip :: NonEmptyVector a -> NonEmptyVector b -> NonEmptyVector (a, b) -- | Zip together three non-empty vectors. zip3 :: NonEmptyVector a -> NonEmptyVector b -> NonEmptyVector c -> NonEmptyVector (a, b, c) -- | Zip together four non-empty vectors. zip4 :: NonEmptyVector a -> NonEmptyVector b -> NonEmptyVector c -> NonEmptyVector d -> NonEmptyVector (a, b, c, d) -- | Zip together five non-empty vectors. zip5 :: NonEmptyVector a -> NonEmptyVector b -> NonEmptyVector c -> NonEmptyVector d -> NonEmptyVector e -> NonEmptyVector (a, b, c, d, e) -- | Zip together six non-empty vectors. zip6 :: NonEmptyVector a -> NonEmptyVector b -> NonEmptyVector c -> NonEmptyVector d -> NonEmptyVector e -> NonEmptyVector f -> NonEmptyVector (a, b, c, d, e, f) -- | O(min(m,n)) Zip the two non-empty vectors with the monadic -- action and yield a non-empty vector of results. zipWithM :: Monad m => (a -> b -> m c) -> NonEmptyVector a -> NonEmptyVector b -> m (NonEmptyVector c) -- | O(min(m,n)) Zip the two non-empty vectors with the monadic -- action and ignore the results. zipWithM_ :: Monad m => (a -> b -> m c) -> NonEmptyVector a -> NonEmptyVector b -> m () -- | O(min(m,n)) Zip the two non-empty vectors with a monadic action -- that also takes the element index and yield a vector of results. izipWithM :: Monad m => (Int -> a -> b -> m c) -> NonEmptyVector a -> NonEmptyVector b -> m (NonEmptyVector c) -- | O(min(m,n)) Zip the two non-empty vectors with a monadic action -- that also takes the element index and ignore the results. izipWithM_ :: Monad m => (Int -> a -> b -> m c) -> NonEmptyVector a -> NonEmptyVector b -> m () -- | O(min(m,n)) Unzip a non-empty vector of pairs. unzip :: NonEmptyVector (a, b) -> (NonEmptyVector a, NonEmptyVector b) -- | Unzip a non-empty vector of triples. unzip3 :: NonEmptyVector (a, b, c) -> (NonEmptyVector a, NonEmptyVector b, NonEmptyVector c) -- | Unzip a non-empty vector of quadruples. unzip4 :: NonEmptyVector (a, b, c, d) -> (NonEmptyVector a, NonEmptyVector b, NonEmptyVector c, NonEmptyVector d) -- | Unzip a non-empty vector of quintuples. unzip5 :: NonEmptyVector (a, b, c, d, e) -> (NonEmptyVector a, NonEmptyVector b, NonEmptyVector c, NonEmptyVector d, NonEmptyVector e) -- | Unzip a non-empty vector of sextuples. unzip6 :: NonEmptyVector (a, b, c, d, e, f) -> (NonEmptyVector a, NonEmptyVector b, NonEmptyVector c, NonEmptyVector d, NonEmptyVector e, NonEmptyVector f) -- | O(n) Drop elements that do not satisfy the predicate. -- -- If no elements satisfy the predicate, the resulting vector may be -- empty. filter :: (a -> Bool) -> NonEmptyVector a -> Vector a -- | O(n) Drop elements that do not satisfy the predicate which is -- applied to values and their indices. -- -- If no elements satisfy the predicate, the resulting vector may be -- empty. ifilter :: (Int -> a -> Bool) -> NonEmptyVector a -> Vector a -- | O(n) Drop repeated adjacent elements. uniq :: Eq a => NonEmptyVector a -> NonEmptyVector a -- | O(n) Drop elements when predicate returns Nothing -- -- If no elements satisfy the predicate, the resulting vector may be -- empty. mapMaybe :: (a -> Maybe b) -> NonEmptyVector a -> Vector b -- | O(n) Drop elements when predicate, applied to index and value, -- returns Nothing -- -- If no elements satisfy the predicate, the resulting vector may be -- empty. imapMaybe :: (Int -> a -> Maybe b) -> NonEmptyVector a -> Vector b -- | O(n) Drop elements that do not satisfy the monadic predicate. -- -- If no elements satisfy the predicate, the resulting vector may be -- empty. filterM :: Monad m => (a -> m Bool) -> NonEmptyVector a -> m (Vector a) -- | O(n) Yield the longest prefix of elements satisfying the -- predicate without copying. -- -- If no elements satisfy the predicate, the resulting vector may be -- empty. takeWhile :: (a -> Bool) -> NonEmptyVector a -> Vector a -- | O(n) Drop the longest prefix of elements that satisfy the -- predicate without copying. -- -- If all elements satisfy the predicate, the resulting vector may be -- empty. dropWhile :: (a -> Bool) -> NonEmptyVector a -> Vector a -- | O(n) Split the non-empty vector in two parts, the first one -- containing those elements that satisfy the predicate and the second -- one those that don't. The relative order of the elements is preserved -- at the cost of a sometimes reduced performance compared to -- unstablePartition. -- -- If all or no elements satisfy the predicate, one of the resulting -- vectors may be empty. partition :: (a -> Bool) -> NonEmptyVector a -> (Vector a, Vector a) -- | O(n) Split the non-empty vector in two parts, the first one -- containing those elements that satisfy the predicate and the second -- one those that don't. The order of the elements is not preserved but -- the operation is often faster than partition. -- -- If all or no elements satisfy the predicate, one of the resulting -- vectors may be empty. unstablePartition :: (a -> Bool) -> NonEmptyVector a -> (Vector a, Vector a) -- | O(n) Split the non-empty vector into the longest prefix of -- elements that satisfy the predicate and the rest without copying. -- -- If all or no elements satisfy the predicate, one of the resulting -- vectors may be empty. span :: (a -> Bool) -> NonEmptyVector a -> (Vector a, Vector a) -- | O(n) Split the vector into the longest prefix of elements that -- do not satisfy the predicate and the rest without copying. -- -- If all or no elements satisfy the predicate, one of the resulting -- vectors may be empty. break :: (a -> Bool) -> NonEmptyVector a -> (Vector a, Vector a) -- | O(n) Check if the non-empty vector contains an element elem :: Eq a => a -> NonEmptyVector a -> Bool -- | O(n) Check if the non-empty vector does not contain an element -- (inverse of elem) notElem :: Eq a => a -> NonEmptyVector a -> Bool -- | O(n) Yield Just the first element matching the predicate -- or Nothing if no such element exists. find :: (a -> Bool) -> NonEmptyVector a -> Maybe a -- | O(n) Yield Just the index of the first element matching -- the predicate or Nothing if no such element exists. findIndex :: (a -> Bool) -> NonEmptyVector a -> Maybe Int -- | O(n) Yield the indices of elements satisfying the predicate in -- ascending order. findIndices :: (a -> Bool) -> NonEmptyVector a -> Vector Int -- | O(n) Yield Just the index of the first occurence of the -- given element or Nothing if the non-empty vector does not -- contain the element. This is a specialised version of -- findIndex. elemIndex :: Eq a => a -> NonEmptyVector a -> Maybe Int -- | O(n) Yield the indices of all occurences of the given element -- in ascending order. This is a specialised version of -- findIndices. elemIndices :: Eq a => a -> NonEmptyVector a -> Vector Int -- | O(n) Left monoidal fold foldl :: (a -> b -> a) -> a -> NonEmptyVector b -> a -- | O(n) Left semigroupal fold foldl1 :: (a -> a -> a) -> NonEmptyVector a -> a -- | O(n) Strict Left monoidal fold foldl' :: (a -> b -> a) -> a -> NonEmptyVector b -> a -- | O(n) Strict Left semigroupal fold foldl1' :: (a -> a -> a) -> NonEmptyVector a -> a -- | O(n) Right monoidal fold foldr :: (a -> b -> b) -> b -> NonEmptyVector a -> b -- | O(n) Right semigroupal fold foldr1 :: (a -> a -> a) -> NonEmptyVector a -> a -- | O(n) Strict right monoidal fold foldr' :: (a -> b -> b) -> b -> NonEmptyVector a -> b -- | O(n) Strict right semigroupal fold foldr1' :: (a -> a -> a) -> NonEmptyVector a -> a -- | O(n) Left monoidal fold with function applied to each element -- and its index ifoldl :: (a -> Int -> b -> a) -> a -> NonEmptyVector b -> a -- | O(n) Strict left monoidal fold with function applied to each -- element and its index ifoldl' :: (a -> Int -> b -> a) -> a -> NonEmptyVector b -> a -- | O(n) Right monoidal fold with function applied to each element -- and its index ifoldr :: (Int -> a -> b -> b) -> b -> NonEmptyVector a -> b -- | O(n) strict right monoidal fold with function applied to each -- element and its index ifoldr' :: (Int -> a -> b -> b) -> b -> NonEmptyVector a -> b -- | O(n) Check if all elements satisfy the predicate. all :: (a -> Bool) -> NonEmptyVector a -> Bool -- | O(n) Check if any element satisfies the predicate. any :: (a -> Bool) -> NonEmptyVector a -> Bool -- | O(n) Check if all elements are True. and :: NonEmptyVector Bool -> Bool -- | O(n) Check if any element is True or :: NonEmptyVector Bool -> Bool -- | O(n) Compute the sum of the elements sum :: Num a => NonEmptyVector a -> a -- | O(n) Compute the produce of the elements product :: Num a => NonEmptyVector a -> a -- | O(n) Yield the maximum element of the non-empty vector. maximum :: Ord a => NonEmptyVector a -> a -- | O(n) Yield the maximum element of a non-empty vector according -- to the given comparison function. maximumBy :: (a -> a -> Ordering) -> NonEmptyVector a -> a -- | O(n) Yield the minimum element of the non-empty vector. minimum :: Ord a => NonEmptyVector a -> a -- | O(n) Yield the minimum element of the non-empty vector -- according to the given comparison function. minimumBy :: (a -> a -> Ordering) -> NonEmptyVector a -> a -- | O(n) Yield the index of the maximum element of the non-empty -- vector. maxIndex :: Ord a => NonEmptyVector a -> Int -- | O(n) Yield the index of the maximum element of the vector -- according to the given comparison function. maxIndexBy :: (a -> a -> Ordering) -> NonEmptyVector a -> Int -- | O(n) Yield the index of the minimum element of the non-empty -- vector. minIndex :: Ord a => NonEmptyVector a -> Int -- | O(n) Yield the index of the minimum element of the vector -- according to the given comparison function. minIndexBy :: (a -> a -> Ordering) -> NonEmptyVector a -> Int -- | O(n) Monadic fold foldM :: Monad m => (a -> b -> m a) -> a -> NonEmptyVector b -> m a -- | O(n) Strict monadic fold foldM' :: Monad m => (a -> b -> m a) -> a -> NonEmptyVector b -> m a -- | O(n) Monadic semigroupal fold fold1M :: Monad m => (a -> a -> m a) -> NonEmptyVector a -> m a -- | O(n) Strict monadic semigroupal fold fold1M' :: Monad m => (a -> a -> m a) -> NonEmptyVector a -> m a -- | O(n) Monadic fold that discards the result foldM_ :: Monad m => (a -> b -> m a) -> a -> NonEmptyVector b -> m () -- | O(n) Strict monadic fold that discards the result foldM'_ :: Monad m => (a -> b -> m a) -> a -> NonEmptyVector b -> m () -- | O(n) Monadic semigroupal fold that discards the result fold1M_ :: Monad m => (a -> a -> m a) -> NonEmptyVector a -> m () -- | O(n) Strict monadic semigroupal fold that discards the result fold1M'_ :: Monad m => (a -> a -> m a) -> NonEmptyVector a -> m () -- | O(n) Monadic fold (action applied to each element and its -- index) ifoldM :: Monad m => (a -> Int -> b -> m a) -> a -> NonEmptyVector b -> m a -- | O(n) Strict monadic fold (action applied to each element and -- its index) ifoldM' :: Monad m => (a -> Int -> b -> m a) -> a -> NonEmptyVector b -> m a -- | O(n) Monadic fold that discards the result (action applied to -- each element and its index) ifoldM_ :: Monad m => (a -> Int -> b -> m a) -> a -> NonEmptyVector b -> m () -- | O(n) Strict monadic fold that discards the result (action -- applied to each element and its index) ifoldM'_ :: Monad m => (a -> Int -> b -> m a) -> a -> NonEmptyVector b -> m () -- | Evaluate each action and collect the results sequence :: Monad m => NonEmptyVector (m a) -> m (NonEmptyVector a) -- | Evaluate each action and discard the results sequence_ :: Monad m => NonEmptyVector (m a) -> m () -- | O(n) Prescan prescanl :: (a -> b -> a) -> a -> NonEmptyVector b -> NonEmptyVector a -- | O(n) Prescan with strict accumulator prescanl' :: (a -> b -> a) -> a -> NonEmptyVector b -> NonEmptyVector a -- | O(n) Scan postscanl :: (a -> b -> a) -> a -> NonEmptyVector b -> NonEmptyVector a -- | O(n) Scan with a strict accumulator postscanl' :: (a -> b -> a) -> a -> NonEmptyVector b -> NonEmptyVector a -- | O(n) Haskell-style scan scanl :: (a -> b -> a) -> a -> NonEmptyVector b -> NonEmptyVector a -- | O(n) Haskell-style scan with strict accumulator scanl' :: (a -> b -> a) -> a -> NonEmptyVector b -> NonEmptyVector a -- | O(n) Semigroupal left scan scanl1 :: (a -> a -> a) -> NonEmptyVector a -> NonEmptyVector a -- | O(n) Strict semigroupal scan scanl1' :: (a -> a -> a) -> NonEmptyVector a -> NonEmptyVector a -- | O(n) Scan over a vector with its index iscanl :: (Int -> a -> b -> a) -> a -> NonEmptyVector b -> NonEmptyVector a -- | O(n) Scan over a vector with its index with strict accumulator iscanl' :: (Int -> a -> b -> a) -> a -> NonEmptyVector b -> NonEmptyVector a -- | O(n) Right-to-left prescan prescanr :: (a -> b -> b) -> b -> NonEmptyVector a -> NonEmptyVector b -- | O(n) Right-to-left prescan with strict accumulator prescanr' :: (a -> b -> b) -> b -> NonEmptyVector a -> NonEmptyVector b -- | O(n) Right-to-left scan postscanr :: (a -> b -> b) -> b -> NonEmptyVector a -> NonEmptyVector b -- | O(n) Right-to-left scan with strict accumulator postscanr' :: (a -> b -> b) -> b -> NonEmptyVector a -> NonEmptyVector b -- | O(n) Right-to-left Haskell-style scan scanr :: (a -> b -> b) -> b -> NonEmptyVector a -> NonEmptyVector b -- | O(n) Right-to-left Haskell-style scan with strict accumulator scanr' :: (a -> b -> b) -> b -> NonEmptyVector a -> NonEmptyVector b -- | O(n) Right-to-left Haskell-style semigroupal scan scanr1 :: (a -> a -> a) -> NonEmptyVector a -> NonEmptyVector a -- | O(n) Right-to-left Haskell-style semigroupal scan with strict -- accumulator scanr1' :: (a -> a -> a) -> NonEmptyVector a -> NonEmptyVector a -- | O(n) Right-to-left scan over a vector with its index iscanr :: (Int -> a -> b -> b) -> b -> NonEmptyVector a -> NonEmptyVector b -- | O(n) Right-to-left scan over a vector with its index and a -- strict accumulator iscanr' :: (Int -> a -> b -> b) -> b -> NonEmptyVector a -> NonEmptyVector b instance GHC.Base.Semigroup (Data.Vector.NonEmpty.NonEmptyVector a) instance GHC.Base.Alternative Data.Vector.NonEmpty.NonEmptyVector instance Control.Monad.Zip.MonadZip Data.Vector.NonEmpty.NonEmptyVector instance GHC.Base.Monad Data.Vector.NonEmpty.NonEmptyVector instance GHC.Base.Applicative Data.Vector.NonEmpty.NonEmptyVector instance GHC.Base.Functor Data.Vector.NonEmpty.NonEmptyVector instance Control.DeepSeq.NFData a => Control.DeepSeq.NFData (Data.Vector.NonEmpty.NonEmptyVector a) instance GHC.Generics.Generic (Data.Vector.NonEmpty.NonEmptyVector a) instance Data.Data.Data a => Data.Data.Data (Data.Vector.NonEmpty.NonEmptyVector a) instance Data.Functor.Classes.Read1 Data.Vector.NonEmpty.NonEmptyVector instance Data.Functor.Classes.Show1 Data.Vector.NonEmpty.NonEmptyVector instance Data.Functor.Classes.Ord1 Data.Vector.NonEmpty.NonEmptyVector instance Data.Functor.Classes.Eq1 Data.Vector.NonEmpty.NonEmptyVector instance GHC.Read.Read a => GHC.Read.Read (Data.Vector.NonEmpty.NonEmptyVector a) instance GHC.Classes.Ord a => GHC.Classes.Ord (Data.Vector.NonEmpty.NonEmptyVector a) instance GHC.Classes.Eq a => GHC.Classes.Eq (Data.Vector.NonEmpty.NonEmptyVector a) instance GHC.Show.Show a => GHC.Show.Show (Data.Vector.NonEmpty.NonEmptyVector a) instance Data.Foldable.Foldable Data.Vector.NonEmpty.NonEmptyVector instance Data.Traversable.Traversable Data.Vector.NonEmpty.NonEmptyVector -- | Non-empty mutable boxed vectors. module Data.Vector.NonEmpty.Mutable -- | NonEmptyMVector is a thin wrapper around MVector that -- witnesses an API requiring non-empty construction, initialization, and -- generation of non-empty vectors by design. -- -- A newtype wrapper was chosen so that no new pointer indirection is -- introduced when working with MVectors, and all performance -- characteristics inherited from the MVector API still apply. data NonEmptyMVector s a -- | NonEmptyMVector parametrized by PrimState type NonEmptyIOVector = NonEmptyMVector RealWorld -- | NonEmptyMVector parametrized by ST type NonEmptySTVector s = NonEmptyMVector s -- | Length of the mutable vector. length :: NonEmptyMVector s a -> Int -- | Yield a part of the mutable vector without copying. slice :: Int -> Int -> NonEmptyMVector s a -> MVector s a -- | Yield all but the last element without copying. init :: NonEmptyMVector s a -> MVector s a -- | Yield all but the first element without copying. tail :: NonEmptyMVector s a -> MVector s a -- | Yield at the first n elements without copying. take :: Int -> NonEmptyMVector s a -> MVector s a -- | Yield all but the first n elements without copying. drop :: Int -> NonEmptyMVector s a -> MVector s a -- | Yield the first n elements paired with the remainder without copying. splitAt :: Int -> NonEmptyMVector s a -> (MVector s a, MVector s a) -- | Yield a part of the mutable vector without copying it. No bounds -- checks are performed. unsafeSlice :: Int -> Int -> NonEmptyMVector s a -> MVector s a -- | Yield the first n elements without copying. The vector must contain at -- least n elements but this is not checked. unsafeTake :: Int -> NonEmptyMVector s a -> MVector s a -- | Yield all but the first n elements without copying. The vector must -- contain at least n elements but this is not checked. unsafeDrop :: Int -> NonEmptyMVector s a -> MVector s a -- | Check whether two vectors overlap. overlaps :: NonEmptyMVector s a -> NonEmptyMVector s a -> Bool -- | Convert a mutable vector to a non-empty mutable vector fromMVector :: MVector s a -> Maybe (NonEmptyMVector s a) -- | Convert a non-empty mutable vector to a mutable vector toMVector :: NonEmptyMVector s a -> MVector s a -- | | Create a mutable vector of the given length. new :: PrimMonad m => Int -> m (Maybe (NonEmptyMVector (PrimState m) a)) -- | Create a mutable vector of the given length. The memory is not -- initialized. unsafeNew :: PrimMonad m => Int -> m (Maybe (NonEmptyMVector (PrimState m) a)) -- | Create a mutable vector of the given length (0 if the length is -- negative) and fill it with an initial value. replicate :: PrimMonad m => Int -> a -> m (Maybe (NonEmptyMVector (PrimState m) a)) -- | Create a mutable vector of the given length (0 if the length is -- negative) and fill it with values produced by repeatedly executing the -- monadic action. replicateM :: PrimMonad m => Int -> m a -> m (Maybe (NonEmptyMVector (PrimState m) a)) -- | Create a copy of a mutable vector. clone :: PrimMonad m => NonEmptyMVector (PrimState m) a -> m (NonEmptyMVector (PrimState m) a) -- | Grow a vector by the given number of elements. The number must be -- positive. grow :: PrimMonad m => NonEmptyMVector (PrimState m) a -> Int -> m (NonEmptyMVector (PrimState m) a) -- | Grow a vector by the given number of elements. The number must be -- positive but this is not checked. unsafeGrow :: PrimMonad m => NonEmptyMVector (PrimState m) a -> Int -> m (NonEmptyMVector (PrimState m) a) -- | Reset all elements of the vector to some undefined value, clearing all -- references to external objects. This is usually a noop for unboxed -- vectors. clear :: PrimMonad m => NonEmptyMVector (PrimState m) a -> m () -- | Yield the element at the given position. read :: PrimMonad m => NonEmptyMVector (PrimState m) a -> Int -> m a -- | Replace the element at the given position. write :: PrimMonad m => NonEmptyMVector (PrimState m) a -> Int -> a -> m () -- | Modify the element at the given position. modify :: PrimMonad m => NonEmptyMVector (PrimState m) a -> (a -> a) -> Int -> m () -- | Swap the elements at the given positions. swap :: PrimMonad m => NonEmptyMVector (PrimState m) a -> Int -> Int -> m () -- | Yield the element at the given position. No bounds checks are -- performed. unsafeRead :: PrimMonad m => NonEmptyMVector (PrimState m) a -> Int -> m a -- | Replace the element at the given position. No bounds checks are -- performed. unsafeWrite :: PrimMonad m => NonEmptyMVector (PrimState m) a -> Int -> a -> m () -- | Modify the element at the given position. No bounds checks are -- performed. unsafeModify :: PrimMonad m => NonEmptyMVector (PrimState m) a -> (a -> a) -> Int -> m () -- | Swap the elements at the given positions. No bounds checks are -- performed. unsafeSwap :: PrimMonad m => NonEmptyMVector (PrimState m) a -> Int -> Int -> m () -- | Compute the next (lexicographically) permutation of given vector -- in-place. Returns False when input is the last permtuation nextPermutation :: (PrimMonad m, Ord e) => NonEmptyMVector (PrimState m) e -> m Bool -- | Set all elements of the vector to the given value. set :: PrimMonad m => NonEmptyMVector (PrimState m) a -> a -> m () -- | Copy a vector. The two vectors must have the same length and may not -- overlap. copy :: PrimMonad m => NonEmptyMVector (PrimState m) a -> NonEmptyMVector (PrimState m) a -> m () -- | Move the contents of a vector. The two vectors must have the same -- length. -- -- If the vectors do not overlap, then this is equivalent to copy. -- Otherwise, the copying is performed as if the source vector were -- copied to a temporary vector and then the temporary vector was copied -- to the target vector. move :: PrimMonad m => NonEmptyMVector (PrimState m) a -> NonEmptyMVector (PrimState m) a -> m () -- | Copy a vector. The two vectors must have the same length and may not -- overlap. This is not checked. unsafeCopy :: PrimMonad m => NonEmptyMVector (PrimState m) a -> NonEmptyMVector (PrimState m) a -> m () -- | Move the contents of a vector. The two vectors must have the same -- length, but this is not checked. -- -- If the vectors do not overlap, then this is equivalent to -- unsafeCopy. Otherwise, the copying is performed as if the -- source vector were copied to a temporary vector and then the temporary -- vector was copied to the target vector. unsafeMove :: PrimMonad m => NonEmptyMVector (PrimState m) a -> NonEmptyMVector (PrimState m) a -> m ()