nonempty-vector 0.1.0.0 → 0.2.0.0
raw patch · 8 files changed
+892/−108 lines, 8 filesdep +doctestdep −hedgehogdep −nonempty-vectorbuild-type:Customsetup-changed
Dependencies added: doctest
Dependencies removed: hedgehog, nonempty-vector
Files
- CHANGELOG.md +14/−0
- README.md +4/−0
- Setup.hs +6/−0
- nonempty-vector.cabal +18/−12
- src/Data/Vector/NonEmpty.hs +792/−28
- src/Data/Vector/NonEmpty/Mutable.hs +51/−6
- test/NEVectorTests.hs +0/−62
- test/doctests.hs +7/−0
CHANGELOG.md view
@@ -1,5 +1,19 @@ # Revision history for nonempty-vector +## 0.2.0.0++* Remove naughty `Generic`, and `Alternative` instances as they can construct empty `NonEmptyVector`s++* Handwritten `Read` and `Read1` instances with safe cons++* Added `uncons`, `unsnoc`, `replicate1`, `generate1`, `iterateN1`, `unsafeCreate`, `unsafeCreateT`, `unfoldr1`, `unfoldr1N`, `unfoldr1M`, `unfoldr1NM`,++* Added `unsafeFromList`, `unsafeFromVector`, and `fromNonEmptyN1`++* Add `ifilterM`++* Add doctests for all new functions + many familiar ones+ ## 0.1.0.0 * Remove `MonadFail` instance for the sake of backcompat with LTS < 13
README.md view
@@ -7,3 +7,7 @@ There are no external dependencies that are not already in `base`. ++### Motivation++Every "container" in the Haskell ecosystem features a [non-empty variant](https://hackage.haskell.org/package/nonempty-containers), including the venerable [list](https://hackage.haskell.org/package/semigroups), aside from `vector`. Many (including myself) use `vector` for its incredible performance characteristics achieved over many years by the CLC and authors of the library. But many of us also want to adhere to the principle of least power, and not have to worry about whether `head` or `tail` (for example) are safe. This package addresses both of the previous points. No new pointer indirection is exposed by this library except at construction (and even then - `unsafe` constructors are supplied), with as much reuse of `vector`'s library as possible to make sure asymptotics stay the same.
+ Setup.hs view
@@ -0,0 +1,6 @@+module Main where++import Distribution.Extra.Doctest (defaultMainWithDoctests)++main :: IO ()+main = defaultMainWithDoctests "doctests"
nonempty-vector.cabal view
@@ -1,6 +1,6 @@-cabal-version: 2.0+cabal-version: 1.24 name: nonempty-vector-version: 0.1.0.0+version: 0.2.0.0 synopsis: Non-empty vectors description: Performant non-empty mutable and immutable vectors. These vectors strive to implement@@ -13,7 +13,7 @@ maintainer: emilypi@cohomolo.gy copyright: (c) 2019 Emily Pillmore category: Data-build-type: Simple+build-type: Custom extra-source-files: CHANGELOG.md README.md@@ -26,6 +26,13 @@ location: https://github.com/emilypi/nonempty-vector.git +custom-setup+ setup-depends:+ base >=4.9 && <5+ , Cabal+ , cabal-doctest++ library exposed-modules: Data.Vector.NonEmpty , Data.Vector.NonEmpty.Mutable@@ -41,15 +48,14 @@ ghc-options: -Wall -test-suite nonempty-vector-tests+test-suite doctests default-language: Haskell2010 type: exitcode-stdio-1.0- hs-source-dirs: test- main-is: NEVectorTests.hs- ghc-options: -Wall -threaded -rtsopts -with-rtsopts=-N+ main-is: doctests.hs - build-depends: base >=4.9 && <5- , nonempty-vector- , hedgehog >=0.6 && <1.1- , semigroups >=0.17 && <0.20- , vector >=0.12 && <0.13+ build-depends: base >=4.9 && <5+ , doctest++ hs-source-dirs: test+ ghc-options: -Wall -threaded+ x-doctest-options: --fast
src/Data/Vector/NonEmpty.hs view
@@ -1,9 +1,8 @@+{-# LANGUAGE CPP #-} {-# LANGUAGE DeriveDataTypeable #-}-{-# LANGUAGE DeriveGeneric #-} {-# LANGUAGE GeneralizedNewtypeDeriving #-} {-# LANGUAGE NoImplicitPrelude #-} {-# LANGUAGE Rank2Types #-}-{-# LANGUAGE TypeFamilies #-} -- | -- Module : Data.Vector.NonEmpty -- Copyright : (c) 2019 Emily Pillmore@@ -59,25 +58,35 @@ , headM, lastM, indexM, unsafeIndexM -- ** Extracting subvectors (slicing)-, tail, slice, init, take, drop, splitAt+, tail, slice, init, take, drop+, uncons, unsnoc, splitAt , unsafeSlice, unsafeTake, unsafeDrop -- * Construction -- ** Initialization-, singleton, replicate, generate-, iterateN+, singleton+, replicate, replicate1+, generate, generate1+, iterateN, iterateN1 -- ** Monad Initialization-, replicateM, generateM, iterateNM-, create, createT+, replicateM, replicate1M+, generateM, generate1M+, iterateNM, iterateN1M+, create, unsafeCreate+, createT, unsafeCreateT -- ** Unfolding-, unfoldr, unfoldrN, unfoldrM, unfoldrNM+, unfoldr, unfoldr1+, unfoldrN, unfoldr1N+, unfoldrM, unfoldr1M+, unfoldrNM, unfoldr1NM , constructN, constructrN -- ** Enumeration-, enumFromN, enumFromStepN+, enumFromN, enumFromN1+, enumFromStepN, enumFromStepN1 , enumFromTo, enumFromThenTo -- ** Concatenation@@ -89,10 +98,12 @@ -- * Conversion -- ** To/from non-empty lists-, toNonEmpty, fromNonEmpty, fromNonEmptyN+, toNonEmpty, fromNonEmpty+, fromNonEmptyN, fromNonEmptyN1+, unsafeFromList -- ** To/from vector-, toVector, fromVector+, toVector, fromVector, unsafeFromVector -- ** To/from list , toList, fromList, fromListN@@ -139,7 +150,8 @@ -- * Working with predicates -- ** Filtering-, filter, ifilter, uniq, mapMaybe, imapMaybe, filterM+, uniq, mapMaybe, imapMaybe+, filter, ifilter, filterM, ifilterM , takeWhile, dropWhile -- * Partitioning@@ -174,12 +186,13 @@ ) where -import Prelude (Bool, Eq, Ord, Read, Show(..), Num, Enum, (.), Ordering)+import Prelude ( Bool, Eq, Ord, Show(..), Num, Enum+ , (.), Ordering, max, uncurry, snd) import Control.Applicative import Control.DeepSeq hiding (force)-import Control.Monad (Monad)+import Control.Monad (Monad, return) import Control.Monad.ST import Control.Monad.Zip (MonadZip) @@ -187,7 +200,7 @@ import Data.Foldable (Foldable) import qualified Data.Foldable as Foldable import Data.Functor-import Data.Functor.Classes+import Data.Functor.Classes (Eq1, Ord1, Show1, Read1(..)) import Data.Int import Data.List.NonEmpty (NonEmpty(..)) import qualified Data.List.NonEmpty as NonEmpty@@ -200,9 +213,23 @@ import qualified Data.Vector.Generic as G import Data.Vector.Mutable (MVector) -import GHC.Generics+import GHC.Read +import qualified Text.Read as Read ++-- $setup+-- >>> import Prelude (Int, String, ($), (.), (+), (<), const)+-- >>> import Data.Bool+-- >>> import Data.Eq+-- >>> import qualified Prelude as P+-- >>> import qualified Data.Vector as V+-- >>> import Data.List.NonEmpty (NonEmpty(..))+-- >>> import qualified Data.List.NonEmpty as NEL+-- >>> :set -XTypeApplications+-- >>> :set -XScopedTypeVariables++ -- | 'NonEmptyVector' is a thin wrapper around 'Vector' that -- witnesses an API requiring non-empty construction, -- initialization, and generation of non-empty vectors by design.@@ -214,17 +241,39 @@ newtype NonEmptyVector a = NonEmptyVector { _neVec :: V.Vector a } deriving- ( Eq, Ord, Read- , Eq1, Ord1, Show1, Read1- , Data, Typeable, Generic, NFData+ ( Eq, Ord+ , Eq1, Ord1, Show1+ , Data, Typeable, NFData , Functor, Applicative, Monad- , MonadZip, Alternative+ , MonadZip , Semigroup ) instance Show a => Show (NonEmptyVector a) where show (NonEmptyVector v) = show v +instance Read a => Read (NonEmptyVector a) where+ readPrec = do+ as <- Read.readPrec+ if Foldable.null as+ then Read.pfail+ else return (unsafeFromList as)++instance Read1 NonEmptyVector where+#if __GLASGOW_HASKELL__ > 802+ liftReadPrec _ rl = do+ l <- rl+ if Foldable.null l+ then Read.pfail+ else return (unsafeFromList l)+#else+ liftReadsPrec _ r _ s = do+ (as, s') <- r s+ if Foldable.null as+ then []+ else return (unsafeFromList as, s')+#endif+ instance Foldable NonEmptyVector where foldMap f = Foldable.foldMap f . _neVec @@ -236,6 +285,9 @@ -- | /O(1)/ Length. --+-- >>> length $ unsafeFromList [1..10]+-- 10+-- length :: NonEmptyVector a -> Int length = V.length . _neVec {-# INLINE length #-}@@ -243,6 +295,10 @@ -- | /O(1)/ First element. Since head is gauranteed, bounds checks -- are bypassed by deferring to 'unsafeHead'. --+--+-- >>> head $ unsafeFromList [1..10]+-- 1+-- head :: NonEmptyVector a -> a head = V.unsafeHead . _neVec {-# INLINE head #-}@@ -250,18 +306,33 @@ -- | /O(1)/ Last element. Since a last element is gauranteed, bounds checks -- are bypassed by deferring to 'unsafeLast'. --+--+-- >>> last $ unsafeFromList [1..10]+-- 10+-- last :: NonEmptyVector a -> a last = V.unsafeLast . _neVec {-# INLINE last #-} -- | /O(1)/ Indexing. --+--+-- >>> (unsafeFromList [1..10]) ! 0+-- 1+-- (!) :: NonEmptyVector a -> Int -> a (!) (NonEmptyVector as) n = as V.! n {-# INLINE (!) #-} -- | /O(1)/ Safe indexing. --+--+-- >>> (unsafeFromList [1..10]) !? 0+-- Just 1+--+-- >>> (unsafeFromList [1..10]) !? 11+-- Nothing+-- (!?) :: NonEmptyVector a -> Int -> Maybe a (NonEmptyVector as) !? n = as V.!? n {-# INLINE (!?) #-}@@ -282,6 +353,10 @@ -- -- See 'V.indexM' for more details --+--+-- >>> indexM @[] (unsafeFromList [1..10]) 3+-- [4]+-- indexM :: Monad m => NonEmptyVector a -> Int -> m a indexM (NonEmptyVector v) n = V.indexM v n {-# INLINE indexM #-}@@ -293,6 +368,10 @@ -- Note that this function defers to 'unsafeHeadM' since head is -- gauranteed to be safe by construction. --+--+-- >>> headM @[] (unsafeFromList [1..10])+-- [1]+-- headM :: Monad m => NonEmptyVector a -> m a headM (NonEmptyVector v) = V.unsafeHeadM v {-# INLINE headM #-}@@ -303,6 +382,10 @@ -- Note that this function defers to 'unsafeHeadM' since a last element is -- gauranteed. --+--+-- >>> lastM @[] (unsafeFromList [1..10])+-- [10]+-- lastM :: Monad m => NonEmptyVector a -> m a lastM (NonEmptyVector v) = V.unsafeLastM v {-# INLINE lastM #-}@@ -321,14 +404,44 @@ -- vector returned may be empty (i.e. input was a singleton), this function -- returns a normal 'Vector' --+--+-- >>> tail (unsafeFromList [1..10])+-- [2,3,4,5,6,7,8,9,10]+-- tail :: NonEmptyVector a -> Vector a tail = V.unsafeTail . _neVec {-# INLINE tail #-} +-- | /O(1)/ Yield a slice of a non-empty vector without copying at+-- the @0@th and @1@st indices.+--+--+-- >>> uncons (unsafeFromList [1..10])+-- (1,[2,3,4,5,6,7,8,9,10])+--+uncons :: NonEmptyVector a -> (a, Vector a)+uncons v = (head v, tail v)+{-# INLINE uncons #-}++-- | /O(1)/ Yield a slice of a non-empty vector without copying at+-- the @n-1@th and @nth@ indices+--+--+-- >>> unsnoc (unsafeFromList [1..10])+-- ([1,2,3,4,5,6,7,8,9],10)+--+unsnoc :: NonEmptyVector a -> (Vector a, a)+unsnoc v = (init v, last v)+{-# INLINE unsnoc #-}+ -- | /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 0 3 (unsafeFromList [1..10])+-- [1,2,3]+-- slice :: Int -> Int -> NonEmptyVector a -> Vector a slice i n = V.slice i n . _neVec @@ -336,51 +449,78 @@ -- vector returned may be empty (i.e. input was a singleton), this function -- returns a normal 'Vector' --+--+-- >>> init (unsafeFromList [1..3])+-- [1,2]+-- init :: NonEmptyVector a -> Vector a init = V.unsafeInit . _neVec+{-# INLINE init #-} -- | /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 2 (unsafeFromList [1..3])+-- [1,2]+-- take :: Int -> NonEmptyVector a -> Vector a take n = V.take n . _neVec+{-# INLINE take #-} -- | /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 2 (unsafeFromList [1..3])+-- [3]+-- drop :: Int -> NonEmptyVector a -> Vector a drop n = V.drop n . _neVec+{-# INLINE drop #-} -- | /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 2 (unsafeFromList [1..3])+-- ([1,2],[3])+-- splitAt :: Int -> NonEmptyVector a -> (Vector a, Vector a) splitAt n = V.splitAt n . _neVec+{-# INLINE splitAt #-} -- | /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 unsafeSlice i n = V.unsafeSlice i n . _neVec+{-# INLINE unsafeSlice #-} -- | /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 unsafeTake n = V.unsafeTake n . _neVec+{-# INLINE unsafeTake #-} -- | /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 unsafeDrop n = V.unsafeDrop n . _neVec+{-# INLINE unsafeDrop #-} -- ---------------------------------------------------------------------- -- -- Construction -- | /O(1)/ Non-empty vector with exactly one element --+--+-- >>> singleton "a"+-- ["a"]+-- singleton :: a -> NonEmptyVector a singleton = NonEmptyVector . V.singleton {-# INLINE singleton #-}@@ -390,27 +530,113 @@ -- -- When given a index n <= 0, then 'Nothing' is returned, otherwise 'Just'. --+--+-- >>> replicate 3 "a"+-- Just ["a","a","a"]+--+-- >>> replicate 0 "a"+-- Nothing+-- replicate :: Int -> a -> Maybe (NonEmptyVector a) replicate n a = fromVector (V.replicate n a) {-# INLINE replicate #-} +-- | /O(n)/ Non-empty vector of the given length with the same value in+-- each position.+--+-- This variant takes @max n 1@ for the supplied length parameter.+--+--+-- >>> replicate1 3 "a"+-- ["a","a","a"]+--+-- >>> replicate1 0 "a"+-- ["a"]+--+-- >>> replicate1 (-1) "a"+-- ["a"]+--+replicate1 :: Int -> a -> NonEmptyVector a+replicate1 n a = unsafeFromVector (V.replicate (max n 1) a)+{-# INLINE replicate1 #-}+ -- | /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'. --+--+-- >>> let f 0 = "a"; f _ = "k"; f :: Int -> String+--+-- >>> generate 1 f+-- Just ["a"]+--+-- >>> generate 0 f+-- Nothing+--+-- >>> generate 2 f+-- Just ["a","k"]+-- generate :: Int -> (Int -> a) -> Maybe (NonEmptyVector a) generate n f = fromVector (V.generate n f) {-# INLINE generate #-} +-- | /O(n)/ Construct a vector of the given length by applying the function to+-- each index.+--+-- This variant takes @max n 1@ for the supplied length parameter.+--+--+-- >>> let f 0 = "a"; f _ = "k"; f :: Int -> String+--+-- >>> generate1 2 f+-- ["a","k"]+--+-- >>> generate1 0 f+-- ["a"]+--+-- >>> generate1 (-1) f+-- ["a"]+--+generate1 :: Int -> (Int -> a) -> NonEmptyVector a+generate1 n f = unsafeFromVector (V.generate (max n 1) f)+{-# INLINE generate1 #-}+ -- | /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 3 (+1) 0+-- Just [0,1,2]+--+-- >>> iterateN 0 (+1) 0+-- Nothing+--+-- >>> iterateN (-1) (+1) 0+-- Nothing+-- iterateN :: Int -> (a -> a) -> a -> Maybe (NonEmptyVector a) iterateN n f a = fromVector (V.iterateN n f a) {-# INLINE iterateN #-} +-- | /O(n)/ Apply function n times to value. Zeroth element is original value.+--+-- This variant takes @max n 1@ for the supplied length parameter.+--+--+-- >>> iterateN1 3 (+1) 0+-- [0,1,2]+--+-- >>> iterateN1 0 (+1) 0+-- [0]+--+-- >>> iterateN1 (-1) (+1) 0+-- [0]+--+iterateN1 :: Int -> (a -> a) -> a -> NonEmptyVector a+iterateN1 n f a = unsafeFromVector (V.iterateN (max n 1) f a)+{-# INLINE iterateN1 #-}+ -- ---------------------------------------------------------------------- -- -- Monadic Initialization @@ -419,43 +645,163 @@ -- -- When given a index n <= 0, then 'Nothing' is returned, otherwise 'Just'. --+--+-- >>> replicateM @Maybe 3 (Just "a")+-- Just (Just ["a","a","a"])+--+-- >>> replicateM @Maybe 3 Nothing+-- Nothing+--+-- >>> replicateM @Maybe 0 (Just "a")+-- Just Nothing+--+-- >>> replicateM @Maybe (-1) (Just "a")+-- Just Nothing+-- replicateM :: Monad m => Int -> m a -> m (Maybe (NonEmptyVector a)) replicateM n a = fmap fromVector (V.replicateM n a) {-# INLINE replicateM #-} +-- | /O(n)/ Execute the monadic action the given number of times and store+-- the results in a vector.+--+-- This variant takes @max n 1@ for the supplied length parameter.+--+--+-- >>> replicate1M @Maybe 3 (Just "a")+-- Just ["a","a","a"]+--+-- >>> replicate1M @Maybe 3 Nothing+-- Nothing+--+-- >>> replicate1M @Maybe 0 (Just "a")+-- Just ["a"]+--+-- >>> replicate1M @Maybe (-1) (Just "a")+-- Just ["a"]+--+replicate1M :: Monad m => Int -> m a -> m (NonEmptyVector a)+replicate1M n a = fmap unsafeFromVector (V.replicateM (max n 1) a)+{-# INLINE replicate1M #-}+ -- | /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 3 (\i -> if i P.< 1 then ["a"] else ["b"])+-- [Just ["a","b","b"]]+--+-- >>> generateM @[] @Int 3 (const [])+-- []+--+-- >>> generateM @[] @Int 0 (const [1])+-- [Nothing]+--+-- >>> generateM @Maybe @Int (-1) (const Nothing)+-- Just Nothing+-- generateM :: Monad m => Int -> (Int -> m a) -> m (Maybe (NonEmptyVector a)) generateM n f = fmap fromVector (V.generateM n f) {-# INLINE generateM #-} +-- | /O(n)/ Construct a vector of the given length by applying the monadic+-- action to each index+--+-- This variant takes @max n 1@ for the supplied length parameter.+--+-- >>> generate1M 3 (\i -> if i P.< 1 then Just "a" else Just "b")+-- Just ["a","b","b"]+--+-- >>> generate1M 3 (const [])+-- []+--+-- >>> generate1M 0 (const $ Just 1)+-- Just [1]+--+-- >>> generate1M (-1) (const Nothing)+-- Nothing+--+generate1M :: Monad m => Int -> (Int -> m a) -> m (NonEmptyVector a)+generate1M n f = fmap unsafeFromVector (V.generateM (max n 1) f)+{-# INLINE generate1M #-}+ -- | /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 @Maybe 3 return "a"+-- Just (Just ["a","a","a"])+--+-- >>> iterateNM @Maybe 3 (const Nothing) "a"+-- Nothing+--+-- >>> iterateNM @Maybe 0 return "a"+-- Just Nothing+-- iterateNM :: Monad m => Int -> (a -> m a) -> a -> m (Maybe (NonEmptyVector a)) iterateNM n f a = fmap fromVector (V.iterateNM n f a) {-# INLINE iterateNM #-} +-- | /O(n)/ Apply monadic function n times to value. Zeroth element is+-- original value.+--+-- This variant takes @max n 1@ for the supplied length parameter.+--+--+-- >>> iterateN1M @Maybe 3 return "a"+-- Just ["a","a","a"]+--+-- >>> iterateN1M @Maybe 3 (const Nothing) "a"+-- Nothing+--+-- >>> iterateN1M @Maybe 0 return "a"+-- Just ["a"]+--+-- >>> iterateN1M @Maybe (-1) return "a"+-- Just ["a"]+--+iterateN1M :: Monad m => Int -> (a -> m a) -> a -> m (NonEmptyVector a)+iterateN1M n f a = fmap unsafeFromVector (V.iterateNM (max n 1) f a)+{-# INLINE iterateN1M #-}+ -- | Execute the monadic action and freeze the resulting non-empty vector. -- create :: (forall s. ST s (MVector s a)) -> Maybe (NonEmptyVector a) create p = fromVector (G.create p) {-# INLINE create #-} +-- | Execute the monadic action and freeze the resulting non-empty vector,+-- bypassing emptiness checks.+--+-- The onus is on the caller to guarantee the created vector is non-empty.+--+unsafeCreate :: (forall s. ST s (MVector s a)) -> NonEmptyVector a+unsafeCreate p = unsafeFromVector (G.create p)+{-# INLINE unsafeCreate #-}+ -- | 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))-{-# INLINE createT #-} createT p = fmap fromVector (G.createT p)+{-# INLINE createT #-} +-- | Execute the monadic action and freeze the resulting non-empty vector.+--+-- The onus is on the caller to guarantee the created vector is non-empty.+--+unsafeCreateT+ :: Traversable t+ => (forall s. ST s (t (MVector s a)))+ -> t (NonEmptyVector a)+unsafeCreateT p = fmap unsafeFromVector (G.createT p)+{-# INLINE unsafeCreateT #-}+ -- ---------------------------------------------------------------------- -- -- Unfolding @@ -467,10 +813,34 @@ -- If an unfold does not create meaningful values, 'Nothing' is -- returned. Otherwise, 'Just' containing a non-empty vector is returned. --+--+-- >>> unfoldr (\b -> case b of "a" -> Just ("a", "b"); _ -> Nothing) "a"+-- Just ["a"]+--+-- >>> unfoldr (const Nothing) "a"+-- Nothing+-- unfoldr :: (b -> Maybe (a, b)) -> b -> Maybe (NonEmptyVector a) unfoldr f b = fromVector (V.unfoldr f b) {-# INLINE unfoldr #-} +-- | /O(n)/ Construct a non-empty vector by repeatedly applying the+-- generator function to a seed and a first element.+--+-- This variant of 'unfoldr' guarantees the resulting vector is non-+-- empty by supplying an initial element @a@.+--+--+-- >>> unfoldr1 (\b -> case b of "a" -> Just ("a", "b"); _ -> Nothing) "first" "a"+-- ["first","a"]+--+-- >>> unfoldr1 (const Nothing) "first" "a"+-- ["first"]+--+unfoldr1 :: (b -> Maybe (a, b)) -> a -> b -> NonEmptyVector a+unfoldr1 f a b = cons a (unsafeFromVector (V.unfoldr f b))+{-# INLINE unfoldr1 #-}+ -- | /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@@ -479,10 +849,47 @@ -- If an unfold does not create meaningful values, 'Nothing' is -- returned. Otherwise, 'Just' containing a non-empty vector is returned. --+--+-- >>> unfoldrN 3 (\b -> Just (b+1, b+1)) 0+-- Just [1,2,3]+--+-- >>> unfoldrN 3 (const Nothing) 0+-- Nothing+--+-- >>> unfoldrN 0 (\b -> Just (b+1, b+1)) 0+-- Nothing+-- unfoldrN :: Int -> (b -> Maybe (a, b)) -> b -> Maybe (NonEmptyVector a) unfoldrN n f b = fromVector (V.unfoldrN n f b) {-# INLINE unfoldrN #-} +-- | /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.+--+-- This variant of 'unfoldrN' guarantees the resulting vector is non-+-- empty by supplying an initial element @a@.+--+--+-- >>> unfoldr1N 3 (\b -> Just (b+1, b+1)) 0 0+-- [0,1,2,3]+--+-- >>> unfoldr1N 3 (const Nothing) 0 0+-- [0]+--+-- >>> unfoldr1N 0 (\b -> Just (b+1, b+1)) 0 0+-- [0]+--+unfoldr1N+ :: Int+ -> (b -> Maybe (a, b))+ -> a+ -> b+ -> NonEmptyVector a+unfoldr1N n f a b = cons a (unsafeFromVector (V.unfoldrN n f b))+{-# INLINE unfoldr1N #-}+ -- | /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.@@ -490,21 +897,63 @@ -- 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))+unfoldrM+ :: Monad m+ => (b -> m (Maybe (a, b)))+ -> b+ -> m (Maybe (NonEmptyVector a)) unfoldrM f b = fmap fromVector (V.unfoldrM f b) {-# INLINE unfoldrM #-} -- | /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.+--+-- This variant of 'unfoldrM' guarantees the resulting vector is non-+-- empty by supplying an initial element @a@.+--+unfoldr1M+ :: Monad m+ => (b -> m (Maybe (a, b)))+ -> a+ -> b+ -> m (NonEmptyVector a)+unfoldr1M f a b = fmap (cons a . unsafeFromVector) (V.unfoldrM f b)+{-# INLINE unfoldr1M #-}++-- | /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))+unfoldrNM+ :: Monad m+ => Int+ -> (b -> m (Maybe (a, b)))+ -> b+ -> m (Maybe (NonEmptyVector a)) unfoldrNM n f b = fmap fromVector (V.unfoldrNM n f b) {-# INLINE unfoldrNM #-} +-- | /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.+--+-- This variant of 'unfoldrNM' guarantees the resulting vector is non-+-- empty by supplying an initial element @a@.+--+unfoldr1NM+ :: Monad m+ => Int+ -> (b -> m (Maybe (a, b)))+ -> a+ -> b+ -> m (NonEmptyVector a)+unfoldr1NM n f a b = fmap (cons a . unsafeFromVector) (V.unfoldrNM n f b)+{-# INLINE unfoldr1NM #-}+ -- | /O(n)/ Construct a non-empty vector with n elements by repeatedly applying the -- generator function to the already constructed part of the vector. --@@ -539,6 +988,14 @@ enumFromN a n = fromVector (V.enumFromN a n) {-# INLINE enumFromN #-} +-- | /O(n)/ Yield a non-emptyvector of length @max n 1@ containing the+-- values x, x+1 etc. This operation is usually more efficient than+-- 'enumFromTo'.+--+enumFromN1 :: Num a => a -> Int -> NonEmptyVector a+enumFromN1 a n = unsafeFromVector (V.enumFromN a (max n 1))+{-# INLINE enumFromN1 #-}+ -- | /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'.@@ -550,6 +1007,14 @@ enumFromStepN a0 a1 n = fromVector (V.enumFromStepN a0 a1 n) {-# INLINE enumFromStepN #-} +-- | /O(n)/ Yield a non-empty vector of length @max n 1@ containing the+-- values x, x+y, x+y+y etc. This operations is usually more efficient than+-- 'enumFromThenTo'.+--+enumFromStepN1 :: Num a => a -> a -> Int -> NonEmptyVector a+enumFromStepN1 a0 a1 n = unsafeFromVector (V.enumFromStepN a0 a1 (max n 1))+{-# INLINE enumFromStepN1 #-}+ -- | /O(n)/ Enumerate values from x to y. -- -- If an enumeration does not use meaningful indices, 'Nothing' is returned,@@ -579,18 +1044,27 @@ -- | /O(n)/ Prepend an element --+-- >>> cons 1 (unsafeFromList [2,3])+-- [1,2,3]+-- cons :: a -> NonEmptyVector a -> NonEmptyVector a cons a (NonEmptyVector as) = NonEmptyVector (V.cons a as) {-# INLINE cons #-} -- | /O(n)/ Append an element --+-- >>> snoc (unsafeFromList [1,2]) 3+-- [1,2,3]+-- snoc :: NonEmptyVector a -> a -> NonEmptyVector a snoc (NonEmptyVector as) a = NonEmptyVector (V.snoc as a) {-# INLINE snoc #-} -- | /O(m+n)/ Concatenate two non-empty vectors --+-- >>> (unsafeFromList [1..3]) ++ (unsafeFromList [4..6])+-- [1,2,3,4,5,6]+-- (++) :: NonEmptyVector a -> NonEmptyVector a -> NonEmptyVector a NonEmptyVector v ++ NonEmptyVector v' = NonEmptyVector (v <> v') {-# INLINE (++) #-}@@ -600,6 +1074,9 @@ -- If list is empty, 'Nothing' is returned, otherwise 'Just' -- containing the concatenated non-empty vectors --+-- >>> concat [(unsafeFromList [1..3]), (unsafeFromList [4..6])]+-- Just [1,2,3,4,5,6]+-- concat :: [NonEmptyVector a] -> Maybe (NonEmptyVector a) concat [] = Nothing concat (a:as) = Just (concat1 (a :| as))@@ -607,6 +1084,9 @@ -- | O(n) Concatenate all non-empty vectors in a non-empty list. --+-- >>> concat1 ((unsafeFromList [1..3]) :| [(unsafeFromList [4..6])])+-- [1,2,3,4,5,6]+-- concat1 :: NonEmpty (NonEmptyVector a) -> NonEmptyVector a concat1 = NonEmptyVector . Foldable.foldl' go V.empty where@@ -618,12 +1098,18 @@ -- | /O(n)/ Convert a non-empty vector to a non-empty list. --+-- >>> toNonEmpty (unsafeFromList [1..3])+-- 1 :| [2,3]+-- toNonEmpty :: NonEmptyVector a -> NonEmpty a toNonEmpty = NonEmpty.fromList . V.toList . _neVec {-# INLINE toNonEmpty #-} -- | O(n) Convert from a non-empty list to a non-empty vector. --+-- >>> fromNonEmpty (1 :| [2,3])+-- [1,2,3]+-- fromNonEmpty :: NonEmpty a -> NonEmptyVector a fromNonEmpty = NonEmptyVector . V.fromList . Foldable.toList {-# INLINE fromNonEmpty #-}@@ -634,13 +1120,40 @@ -- Returns 'Nothing' if indices are <= 0, otherwise 'Just' containing -- the non-empty vector. --+-- >>> fromNonEmptyN 3 (1 :| [2..5])+-- Just [1,2,3]+--+-- >>> fromNonEmptyN 0 (1 :| [2..5])+-- Nothing+-- fromNonEmptyN :: Int -> NonEmpty a -> Maybe (NonEmptyVector a)-fromNonEmptyN n as = fromVector (V.fromListN n (Foldable.toList as))+fromNonEmptyN n a = fromVector (V.fromListN n (Foldable.toList a)) {-# INLINE fromNonEmptyN #-} +-- | O(n) Convert from the first n-elements of a non-empty list to a+-- non-empty vector. This is a safe version of `fromNonEmptyN` which+-- takes @max n 1@ of the first n-elements of the non-empty list.+--+--+-- >>> fromNonEmptyN1 3 (1 :| [2..5])+-- [1,2,3]+--+-- >>> fromNonEmptyN1 0 (1 :| [2..5])+-- [1]+--+fromNonEmptyN1 :: Int -> NonEmpty a -> NonEmptyVector a+fromNonEmptyN1 n = unsafeFromVector+ . V.fromListN (max n 1)+ . Foldable.toList+{-# INLINE fromNonEmptyN1 #-}+ -- | /O(1)/ Convert from a non-empty vector to a vector. ---toVector :: NonEmptyVector a -> V.Vector a+--+-- >>> let nev :: NonEmptyVector Int = unsafeFromList [1..3] in toVector nev+-- [1,2,3]+--+toVector :: NonEmptyVector a -> Vector a toVector = _neVec {-# INLINE toVector #-} @@ -649,27 +1162,79 @@ -- If the vector is empty, then 'Nothing' is returned, -- otherwise 'Just' containing the non-empty vector. ---fromVector :: V.Vector a -> Maybe (NonEmptyVector a)+-- >>> fromVector $ V.fromList [1..3]+-- Just [1,2,3]+--+-- >>> fromVector $ V.fromList []+-- Nothing+--+fromVector :: Vector a -> Maybe (NonEmptyVector a) fromVector v = if V.null v then Nothing else Just (NonEmptyVector v) {-# INLINE fromVector #-} +-- | /O(1)/ Convert from a vector to a non-empty vector without+-- checking bounds.+--+-- /Warning/: the onus is on the user to ensure that their vector+-- is not empty, otherwise all bets are off!+--+--+-- >>> unsafeFromVector $ V.fromList [1..3]+-- [1,2,3]+--+unsafeFromVector :: Vector a -> NonEmptyVector a+unsafeFromVector = NonEmptyVector+{-# INLINE unsafeFromVector #-}+ -- | /O(n)/ Convert from a non-empty vector to a list. --+--+-- >>> let nev :: NonEmptyVector Int = unsafeFromList [1..3] in toList nev+-- [1,2,3]+-- toList :: NonEmptyVector a -> [a] toList = V.toList . _neVec {-# INLINE toList #-} -- | /O(n)/ Convert from a list to a non-empty vector. --+--+-- >>> fromList [1..3]+-- Just [1,2,3]+--+-- >>> fromList []+-- Nothing+-- fromList :: [a] -> Maybe (NonEmptyVector a) fromList = fromVector . V.fromList {-# INLINE fromList #-} +-- | /O(n)/ Convert from a list to a non-empty vector.+--+-- /Warning/: the onus is on the user to ensure that their vector+-- is not empty, otherwise all bets are off!+--+-- >>> unsafeFromList [1..3]+-- [1,2,3]+--+unsafeFromList :: [a] -> NonEmptyVector a+unsafeFromList = unsafeFromVector . V.fromList+{-# INLINE unsafeFromList #-}+ -- | /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 3 [1..5]+-- Just [1,2,3]+--+-- >>> fromListN 3 []+-- Nothing+--+-- >>> fromListN 0 [1..5]+-- Nothing+-- fromListN :: Int -> [a] -> Maybe (NonEmptyVector a) fromListN n as = fromVector (V.fromListN n as) {-# INLINE fromListN #-}@@ -690,6 +1255,12 @@ -- | /O(m+n)/ For each pair (i,a) from the list, replace the non-empty vector -- element at position i by a. --+-- >>> unsafeFromList [1..3] // [(2,4)]+-- [1,2,4]+--+-- >>> unsafeFromList [1..3] // []+-- [1,2,3]+-- (//) :: NonEmptyVector a -> [(Int, a)] -> NonEmptyVector a NonEmptyVector v // us = NonEmptyVector (v V.// us) {-# INLINE (//) #-}@@ -697,6 +1268,12 @@ -- | O(m+n) For each pair (i,a) from the vector of index/value pairs, -- replace the vector element at position i by a. --+-- >>> unsafeFromList [1..3] `update` V.fromList [(2,4)]+-- [1,2,4]+--+-- >>> unsafeFromList [1..3] `update` V.empty+-- [1,2,3]+-- update :: NonEmptyVector a -> Vector (Int, a) -> NonEmptyVector a update (NonEmptyVector v) v' = NonEmptyVector (V.update v v') {-# INLINE update #-}@@ -705,6 +1282,13 @@ -- corresponding value a from the value vector, replace the element of -- the initial vector at position i by a. --+--+-- >>> update_ (unsafeFromList [1..3]) (V.fromList [2]) (V.fromList [4])+-- [1,2,4]+--+-- >>> update_ (unsafeFromList [1..3]) V.empty V.empty+-- [1,2,3]+-- update_ :: NonEmptyVector a -> Vector Int -> Vector a -> NonEmptyVector a update_ (NonEmptyVector v) is as = NonEmptyVector (V.update_ v is as) {-# INLINE update_ #-}@@ -733,6 +1317,13 @@ -- | /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 (+) (unsafeFromList [1..3]) [(2,10)]+-- [1,2,13]+--+-- >>> accum (+) (unsafeFromList [1..3]) []+-- [1,2,3]+-- accum :: (a -> b -> a) -- ^ accumulating function @f@@@ -748,6 +1339,12 @@ -- | /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 (+) (unsafeFromList [1..3]) (V.fromList [(2,10)])+-- [1,2,13]+--+-- >>> accumulate (+) (unsafeFromList [1..3]) V.empty+-- [1,2,3]+-- accumulate :: (a -> b -> a) -- ^ accumulating function @f@@@ -757,13 +1354,18 @@ -- ^ vector of index/value pairs (of length @n@) -> NonEmptyVector a accumulate f (NonEmptyVector v) u = NonEmptyVector (V.accumulate f v u)- {-# INLINE accumulate #-} -- | /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_ (+) (unsafeFromList [1..3]) (V.fromList [2]) (V.fromList [10])+-- [1,2,13]+--+-- >>> accumulate_ (+) (unsafeFromList [1..3]) V.empty V.empty+-- [1,2,3]+-- accumulate_ :: (a -> b -> a) -- ^ accumulating function @f@@@ -827,6 +1429,9 @@ -- | /O(n)/ Reverse a non-empty vector --+-- >>> reverse $ unsafeFromList [1..3]+-- [3,2,1]+-- reverse :: NonEmptyVector a -> NonEmptyVector a reverse = NonEmptyVector . V.reverse . _neVec {-# INLINE reverse #-}@@ -835,6 +1440,9 @@ -- @i@ of the non-empty index vector by @xs'!'i@. This is equivalent to -- @'map' (xs'!') is@ but is often much more efficient. --+-- >>> backpermute (unsafeFromList [1..3]) (unsafeFromList [2,0])+-- [3,1]+-- backpermute :: NonEmptyVector a -> NonEmptyVector Int -> NonEmptyVector a backpermute (NonEmptyVector v) (NonEmptyVector i) = NonEmptyVector (V.backpermute v i)@@ -869,6 +1477,9 @@ -- | /O(n)/ Pair each element in a vector with its index. --+-- >>> indexed $ unsafeFromList ["a","b","c"]+-- [(0,"a"),(1,"b"),(2,"c")]+-- indexed :: NonEmptyVector a -> NonEmptyVector (Int, a) indexed = NonEmptyVector . V.indexed . _neVec {-# INLINE indexed #-}@@ -878,6 +1489,9 @@ -- | /O(n)/ Map a function over a non-empty vector. --+-- >>> map (+1) $ unsafeFromList [1..3]+-- [2,3,4]+-- map :: (a -> b) -> NonEmptyVector a -> NonEmptyVector b map f = NonEmptyVector . V.map f . _neVec {-# INLINE map #-}@@ -885,12 +1499,18 @@ -- | /O(n)/ Apply a function to every element of a non-empty vector and -- its index. --+-- >>> imap (\i a -> if i == 2 then a+1 else a+0) $ unsafeFromList [1..3]+-- [1,2,4]+-- imap :: (Int -> a -> b) -> NonEmptyVector a -> NonEmptyVector b imap f = NonEmptyVector . V.imap f . _neVec {-# INLINE imap #-} -- | Map a function over a vector and concatenate the results. --+-- >>> concatMap (\a -> unsafeFromList [a,a]) (unsafeFromList [1,2,3])+-- [1,1,2,2,3,3]+-- concatMap :: (a -> NonEmptyVector b) -> NonEmptyVector a@@ -904,6 +1524,12 @@ -- | /O(n)/ Apply the monadic action to all elements of the non-empty -- vector, yielding non-empty vector of results. --+-- >>> mapM Just (unsafeFromList [1..3])+-- Just [1,2,3]+--+-- >>> mapM (const Nothing) (unsafeFromList [1..3])+-- Nothing+-- mapM :: Monad m => (a -> m b) -> NonEmptyVector a -> m (NonEmptyVector b) mapM f = fmap NonEmptyVector . V.mapM f . _neVec {-# INLINE mapM #-}@@ -911,6 +1537,12 @@ -- | /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 (\i a -> if i == 1 then Just a else Just 0) (unsafeFromList [1..3])+-- Just [0,2,0]+--+-- >>> imapM (\_ _ -> Nothing) (unsafeFromList [1..3])+-- Nothing+-- imapM :: Monad m => (Int -> a -> m b)@@ -922,6 +1554,12 @@ -- | /O(n)/ Apply the monadic action to all elements of a non-empty vector -- and ignore the results. --+-- >>> mapM_ (const $ Just ()) (unsafeFromList [1..3])+-- Just ()+--+-- >>> mapM_ (const Nothing) (unsafeFromList [1..3])+-- Nothing+-- mapM_ :: Monad m => (a -> m b) -> NonEmptyVector a -> m () mapM_ f = V.mapM_ f . _neVec {-# INLINE mapM_ #-}@@ -929,6 +1567,14 @@ -- | /O(n)/ Apply the monadic action to every element of a non-emptpy -- vector and its index, ignoring the results --+-- >>> imapM_ (\i a -> if i == 1 then P.print a else P.putStrLn "0") (unsafeFromList [1..3])+-- 0+-- 2+-- 0+--+-- >>> imapM_ (\_ _ -> Nothing) (unsafeFromList [1..3])+-- Nothing+-- imapM_ :: Monad m => (Int -> a -> m b) -> NonEmptyVector a -> m () imapM_ f = V.imapM_ f . _neVec {-# INLINE imapM_ #-}@@ -956,6 +1602,9 @@ -- | /O(min(m,n))/ Zip two non-empty vectors with the given function. --+-- >>> zipWith (+) (unsafeFromList [1..3]) (unsafeFromList [1..3])+-- [2,4,6]+-- zipWith :: (a -> b -> c) -> NonEmptyVector a@@ -969,6 +1618,7 @@ -- | Zip three non-empty vectors with the given function. --+-- zipWith3 :: (a -> b -> c -> d) -> NonEmptyVector a@@ -1126,7 +1776,8 @@ f' = _neVec f {-# INLINE izipWith6 #-} --- | /O(min(n,m))/ Elementwise pairing of non-empty vector elements.+-- | /O(min(n,m))/ Elementwise pairing of non-empty vector elements. This is a special case+-- of 'zipWith' where the function argument is '(,)' -- zip :: NonEmptyVector a -> NonEmptyVector b -> NonEmptyVector (a, b) zip a b = NonEmptyVector (V.zip a' b')@@ -1350,6 +2001,12 @@ -- -- If no elements satisfy the predicate, the resulting vector may be empty. --+-- >>> filter (\a -> if a == 2 then False else True) (unsafeFromList [1..3])+-- [1,3]+--+-- >>> filter (const False) (unsafeFromList [1..3])+-- []+-- filter :: (a -> Bool) -> NonEmptyVector a -> Vector a filter f = V.filter f . _neVec {-# INLINE filter #-}@@ -1359,6 +2016,12 @@ -- -- If no elements satisfy the predicate, the resulting vector may be empty. --+-- >>> ifilter (\i a -> if a == 2 || i == 0 then False else True) (unsafeFromList [1..3])+-- [3]+--+-- >>> ifilter (\_ _ -> False) (unsafeFromList [1..3])+-- []+-- ifilter :: (Int -> a -> Bool) -> NonEmptyVector a@@ -1370,6 +2033,15 @@ -- -- If no elements satisfy the predicate, the resulting vector may be empty. --+-- >>> filterM (\a -> if a == 2 then Just False else Just True) (unsafeFromList [1..3])+-- Just [1,3]+--+-- >>> filterM (\a -> if a == 2 then Nothing else Just True) (unsafeFromList [1..3])+-- Nothing+--+-- >>> filterM (const $ Just False) (unsafeFromList [1..3])+-- Just []+-- filterM :: Monad m => (a -> m Bool)@@ -1378,8 +2050,38 @@ filterM f = V.filterM f . _neVec {-# INLINE filterM #-} +-- | /O(n)/ Drop elements that do not satisfy the monadic predicate that is+-- a function of index and value.+--+-- If no elements satisfy the predicate, the resulting vector may be empty.+--+-- TODO: this should be a more efficient function in `vector`.+--+-- >>> ifilterM (\i a -> if a == 2 || i == 0 then Just False else Just True) (unsafeFromList [1..3])+-- Just [3]+--+-- >>> ifilterM (\i a -> if a == 2 || i == 0 then Nothing else Just True) (unsafeFromList [1..3])+-- Nothing+--+-- >>> ifilterM (\_ _ -> Just False) (unsafeFromList [1..3])+-- Just []+--+ifilterM+ :: Monad m+ => (Int -> a -> m Bool)+ -> NonEmptyVector a+ -> m (Vector a)+ifilterM f = fmap (V.map snd)+ . V.filterM (uncurry f)+ . V.indexed+ . _neVec+{-# INLINE ifilterM #-}+ -- | /O(n)/ Drop repeated adjacent elements. --+-- >>> uniq $ unsafeFromList [1,1,2,2,3,3,1]+-- [1,2,3,1]+-- uniq :: Eq a => NonEmptyVector a -> NonEmptyVector a uniq = NonEmptyVector . V.uniq . _neVec {-# INLINE uniq #-}@@ -1388,6 +2090,9 @@ -- -- If no elements satisfy the predicate, the resulting vector may be empty. --+-- >>> mapMaybe (\a -> if a == 2 then Nothing else Just a) (unsafeFromList [1..3])+-- [1,3]+-- mapMaybe :: (a -> Maybe b) -> NonEmptyVector a@@ -1399,6 +2104,9 @@ -- -- If no elements satisfy the predicate, the resulting vector may be empty. --+-- >>> imapMaybe (\i a -> if a == 2 || i == 2 then Nothing else Just a) (unsafeFromList [1..3])+-- [1]+-- imapMaybe :: (Int -> a -> Maybe b) -> NonEmptyVector a@@ -1411,6 +2119,9 @@ -- -- If no elements satisfy the predicate, the resulting vector may be empty. --+-- >>> takeWhile (/= 3) (unsafeFromList [1..3])+-- [1,2]+-- takeWhile :: (a -> Bool) -> NonEmptyVector a -> Vector a takeWhile f = V.takeWhile f . _neVec {-# INLINE takeWhile #-}@@ -1420,6 +2131,9 @@ -- -- If all elements satisfy the predicate, the resulting vector may be empty. --+-- >>> dropWhile (/= 3) (unsafeFromList [1..3])+-- [3]+-- dropWhile :: (a -> Bool) -> NonEmptyVector a -> Vector a dropWhile f = V.dropWhile f . _neVec {-# INLINE dropWhile #-}@@ -1436,6 +2150,9 @@ -- If all or no elements satisfy the predicate, one of the resulting vectors -- may be empty. --+-- >>> partition (< 3) (unsafeFromList [1..5])+-- ([1,2],[3,4,5])+-- partition :: (a -> Bool) -> NonEmptyVector a -> (Vector a, Vector a) partition f = V.partition f . _neVec {-# INLINE partition #-}@@ -1461,6 +2178,9 @@ -- If all or no elements satisfy the predicate, one of the resulting vectors -- may be empty. --+-- >>> span (== 1) (unsafeFromList [1,1,2,3,1])+-- ([1,1],[2,3,1])+-- span :: (a -> Bool) -> NonEmptyVector a -> (Vector a, Vector a) span f = V.span f . _neVec {-# INLINE span #-}@@ -1471,6 +2191,9 @@ -- If all or no elements satisfy the predicate, one of the resulting vectors -- may be empty. --+-- >>> break (== 2) (unsafeFromList [1,1,2,3,1])+-- ([1,1],[2,3,1])+-- break :: (a -> Bool) -> NonEmptyVector a -> (Vector a, Vector a) break f = V.break f . _neVec {-# INLINE break #-}@@ -1480,6 +2203,11 @@ -- | /O(n)/ Check if the non-empty vector contains an element --+-- >>> elem 1 $ unsafeFromList [1..3]+-- True+-- >>> elem 4 $ unsafeFromList [1..3]+-- False+-- elem :: Eq a => a -> NonEmptyVector a -> Bool elem a = V.elem a . _neVec {-# INLINE elem #-}@@ -1487,6 +2215,12 @@ -- | /O(n)/ Check if the non-empty vector does not contain an element -- (inverse of 'elem') --+-- >>> notElem 1 $ unsafeFromList [1..3]+-- False+--+-- >>> notElem 4 $ unsafeFromList [1..3]+-- True+-- notElem :: Eq a => a -> NonEmptyVector a -> Bool notElem a = V.notElem a . _neVec {-# INLINE notElem #-}@@ -1494,6 +2228,12 @@ -- | /O(n)/ Yield 'Just' the first element matching the predicate or -- 'Nothing' if no such element exists. --+-- >>> find (< 2) $ unsafeFromList [1..3]+-- Just 1+--+-- >>> find (< 0) $ unsafeFromList [1..3]+-- Nothing+-- find :: (a -> Bool) -> NonEmptyVector a -> Maybe a find f = V.find f . _neVec {-# INLINE find #-}@@ -1501,6 +2241,12 @@ -- | /O(n)/ Yield 'Just' the index of the first element matching the -- predicate or 'Nothing' if no such element exists. --+-- >>> findIndex (< 2) $ unsafeFromList [1..3]+-- Just 0+--+-- >>> findIndex (< 0) $ unsafeFromList [1..3]+-- Nothing+-- findIndex :: (a -> Bool) -> NonEmptyVector a -> Maybe Int findIndex f = V.findIndex f . _neVec {-# INLINE findIndex #-}@@ -1508,6 +2254,12 @@ -- | /O(n)/ Yield the indices of elements satisfying the predicate in -- ascending order. --+-- >>> findIndices (< 3) $ unsafeFromList [1..3]+-- [0,1]+--+-- >>> findIndices (< 0) $ unsafeFromList [1..3]+-- []+-- findIndices :: (a -> Bool) -> NonEmptyVector a -> Vector Int findIndices f = V.findIndices f . _neVec {-# INLINE findIndices #-}@@ -1516,12 +2268,24 @@ -- element or 'Nothing' if the non-empty vector does not contain the -- element. This is a specialised version of 'findIndex'. --+-- >>> elemIndex 1 $ unsafeFromList [1..3]+-- Just 0+--+-- >>> elemIndex 0 $ unsafeFromList [1..3]+-- Nothing+-- elemIndex :: Eq a => a -> NonEmptyVector a -> Maybe Int elemIndex a = V.elemIndex a . _neVec {-# INLINE elemIndex #-} -- | /O(n)/ Yield the indices of all occurences of the given element in -- ascending order. This is a specialised version of 'findIndices'.+--+-- >>> elemIndices 1 $ unsafeFromList [1,2,3,1]+-- [0,3]+--+-- >>> elemIndices 0 $ unsafeFromList [1..3]+-- [] -- elemIndices :: Eq a => a -> NonEmptyVector a -> Vector Int elemIndices a = V.elemIndices a . _neVec
src/Data/Vector/NonEmpty/Mutable.hs view
@@ -30,10 +30,13 @@ , overlaps -- ** Conversions-, fromMVector, toMVector+, fromMVector, toMVector, unsafeFromMVector -- ** Initialisation-, new, unsafeNew, replicate, replicateM, clone+, new, new1, unsafeNew+, replicate, replicate1+, replicateM, replicate1M+, clone -- ** Growing , grow, unsafeGrow@@ -53,7 +56,7 @@ ) where -import Prelude (Bool, Int, Ord, (.))+import Prelude (Bool, Int, Ord, (.), max) import Control.Monad.Primitive @@ -76,9 +79,10 @@ { _nemVec :: MVector s a } deriving (Typeable) --- | NonEmptyMVector parametrized by 'PrimState'+-- | 'NonEmptyMVector' parametrized by 'PrimState' type NonEmptyIOVector = NonEmptyMVector RealWorld--- | NonEmptyMVector parametrized by 'ST'++-- | 'NonEmptyMVector' parametrized by 'ST' type NonEmptySTVector s = NonEmptyMVector s -- ---------------------------------------------------------------------- --@@ -177,10 +181,19 @@ toMVector :: NonEmptyMVector s a -> MVector s a toMVector = _nemVec +-- | Convert a mutable vector to a non-empty mutable vector+--+-- /Warning:/ this function is unsafe and can result in empty non-empty+-- mutable vectors. If you call this function, the onus is on you to+-- make sure the mutable vector being converted is not empty.+--+unsafeFromMVector :: MVector s a -> NonEmptyMVector s a+unsafeFromMVector = NonEmptyMVector+{-# INLINE unsafeFromMVector #-}+ -- ---------------------------------------------------------------------- -- -- Initialisation --- | -- | Create a mutable vector of the given length. -- new@@ -190,6 +203,16 @@ new = fmap fromMVector . M.new {-# INLINE new #-} +-- | Create a mutable vector of the given length which is+-- @max n 1@.+--+new1+ :: PrimMonad m+ => Int+ -> m (NonEmptyMVector (PrimState m) a)+new1 n = fmap unsafeFromMVector (M.new (max n 1))+{-# INLINE new1 #-}+ -- | Create a mutable vector of the given length. The memory is not initialized. -- unsafeNew@@ -210,6 +233,17 @@ replicate n a = fmap fromMVector (M.replicate n a) {-# INLINE replicate #-} +-- | Create a mutable vector of the length @max n 1@ for a given length,+-- and fill it with an initial value.+--+replicate1+ :: PrimMonad m+ => Int+ -> a+ -> m (NonEmptyMVector (PrimState m) a)+replicate1 n a = fmap unsafeFromMVector (M.replicate (max n 1) a)+{-# INLINE replicate1 #-}+ -- | 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. --@@ -220,6 +254,17 @@ -> m (Maybe (NonEmptyMVector (PrimState m) a)) replicateM n a = fmap fromMVector (M.replicateM n a) {-# INLINE replicateM #-}++-- | Create a mutable vector of the length @max n 1@ for a given length,+-- and fill it with values produced by repeatedly executing the monadic action.+--+replicate1M+ :: PrimMonad m+ => Int+ -> m a+ -> m (Maybe (NonEmptyMVector (PrimState m) a))+replicate1M n a = fmap fromMVector (M.replicateM (max n 1) a)+{-# INLINE replicate1M #-} -- | Create a copy of a mutable vector. --
− test/NEVectorTests.hs
@@ -1,62 +0,0 @@-{-# LANGUAGE OverloadedStrings #-}-{-# LANGUAGE RankNTypes #-}--- |--- Module : Main (tests)--- Copyright : 2019 (c) Emily Pillmore--- License : BSD------ Maintainer : Emily Pillmore <emilypi@cohomolo.gy>--- Stability : Experimental--- Portability : TypeFamilies----module Main-( main-) where---import Data.Functor-import Data.Maybe-import Data.Vector (Vector)-import Data.Vector.NonEmpty (NonEmptyVector)-import qualified Data.Vector.NonEmpty as NEV--import Hedgehog-import qualified Hedgehog.Range as Range--import qualified Hedgehog.Internal.Gen as Gen---main :: IO ()-main = void $ checkParallel $ Group "NonEmptyVector constructor"- [ ("prop_reverse", prop_reverse)- , ("prop_from_to_list", prop_from_to_list)- , ("prop_from_to_vec", prop_from_to_vec)- ]--genList :: Gen [Int]-genList = Gen.list (Range.linear 1 100) Gen.enumBounded--genNEV :: Gen (NonEmptyVector Int)-genNEV = fmap (fromJust . NEV.fromList) genList--genV :: Gen (Vector Int)-genV = NEV.toVector <$> genNEV--prop_reverse :: Property-prop_reverse = property $ do- t <- forAll genNEV- NEV.reverse (NEV.reverse t) === t--prop_from_to_list :: Property-prop_from_to_list = property $ do- t <- forAll $ genNEV- u <- forAll $ genList- NEV.fromList (NEV.toList t) === Just t- fmap NEV.toList (NEV.fromList u) === Just u--prop_from_to_vec :: Property-prop_from_to_vec = property $ do- t <- forAll $ genNEV- u <- forAll $ genV- NEV.fromVector (NEV.toVector t) === Just t- fmap NEV.toVector (NEV.fromVector u) === Just u
+ test/doctests.hs view
@@ -0,0 +1,7 @@+module Main where++import Build_doctests (flags, pkgs, module_sources)+import Test.DocTest (doctest)++main :: IO ()+main = doctest $ flags ++ pkgs ++ module_sources