rrb-vector 0.2.0.0 → 0.2.0.1
raw patch · 7 files changed
+43/−21 lines, 7 filesdep ~deepseqdep ~primitive
Dependency ranges changed: deepseq, primitive
Files
- CHANGELOG.md +6/−1
- rrb-vector.cabal +11/−3
- src/Data/RRBVector/Internal.hs +12/−14
- src/Data/RRBVector/Internal/Array.hs +4/−1
- test/Arbitrary.hs +3/−0
- test/Main.hs +0/−2
- test/Properties.hs +7/−0
CHANGELOG.md view
@@ -1,5 +1,9 @@-# 0.2.0.0+# 0.2.0.1 - October 2023 +* Support `primitive-0.9` and `deepseq-1.5`++# 0.2.0.0 - February 2023+ * Add `map'` & `unzipWith` * Make `zip` & `unzip` more strict * Make all functions strict in the index@@ -7,6 +11,7 @@ * Implement `ifoldMap` in the `FoldableWithIndex` instance * Implement `fail` in the `Monad` instance * Add `Shift`, `Tree` and unidirectional pattern synonyms for `Vector` and `Tree` to `Data.RRBVector.Internal.Debug`+* Support `primitive-0.8` * Test typeclass laws
rrb-vector.cabal view
@@ -1,5 +1,5 @@ name: rrb-vector-version: 0.2.0.0+version: 0.2.0.1 synopsis: Efficient RRB-Vectors description: An RRB-Vector is an efficient sequence data structure.@@ -22,7 +22,15 @@ CHANGELOG.md README.md cabal-version: 2.0-tested-with: GHC == 8.4.4, GHC == 8.6.5, GHC == 8.8.4, GHC == 8.10.7, GHC == 9.0.2, GHC == 9.2.5, GHC == 9.4.4+tested-with:+ GHC == 8.4.4+ GHC == 8.6.5+ GHC == 8.8.4+ GHC == 8.10.7+ GHC == 9.0.2+ GHC == 9.2.8+ GHC == 9.4.7+ GHC == 9.6.3 source-repository head type: git@@ -38,7 +46,7 @@ Data.RRBVector.Internal.Array Data.RRBVector.Internal.Buffer Data.RRBVector.Internal.IntRef- build-depends: base >= 4.11 && < 5, deepseq ^>= 1.4.3, indexed-traversable ^>= 0.1, primitive >= 0.7 && < 0.9+ build-depends: base >= 4.11 && < 5, deepseq >= 1.4.3 && < 1.6, indexed-traversable ^>= 0.1, primitive >= 0.7 && < 0.10 ghc-options: -O2 -Wall -Wno-name-shadowing -Werror=missing-methods -Werror=missing-fields default-language: Haskell2010
src/Data/RRBVector/Internal.hs view
@@ -30,7 +30,11 @@ , zip, zipWith, unzip, unzipWith ) where +#if !(MIN_VERSION_base(4,18,0)) import Control.Applicative (Alternative, liftA2)+#else+import Control.Applicative (Alternative)+#endif import qualified Control.Applicative import Control.DeepSeq import Control.Monad (when, MonadPlus)@@ -46,6 +50,7 @@ import Data.List.NonEmpty (NonEmpty(..)) import Data.Maybe (fromMaybe) import Data.Semigroup+ import qualified GHC.Exts as Exts import GHC.Stack (HasCallStack) import Prelude hiding (replicate, lookup, map, take, drop, splitAt, head, last, reverse, zip, zipWith, unzip)@@ -143,7 +148,7 @@ computeSizes !sh arr | isBalanced = Balanced arr | otherwise = runST $ do- sizes <- newPrimArray (length arr)+ sizes <- newPrimArray len let loop acc i | i < len = let size = treeSize (down sh) (A.index arr i)@@ -556,22 +561,12 @@ zipWith :: (a -> b -> c) -> Vector a -> Vector b -> Vector c zipWith f v1 v2 = fromList $ List.zipWith f (toList v1) (toList v2) --- TODO: unzip = unzipWith id -- | \(O(n)\). Unzip a vector of pairs. -- -- >>> unzip (fromList [(1, "a"), (2, "b"), (3, "c")]) -- (fromList [1,2,3],fromList ["a","b","c"]) unzip :: Vector (a, b) -> (Vector a, Vector b)-unzip Empty = (Empty, Empty)-unzip (Root size sh tree) = case unzipTree tree of- (!left, !right) -> (Root size sh left, Root size sh right)- where- unzipTree (Balanced arr) = case A.unzipWith unzipTree arr of- (!left, !right) -> (Balanced left, Balanced right)- unzipTree (Unbalanced arr sizes) = case A.unzipWith unzipTree arr of- (!left, !right) -> (Unbalanced left sizes, Unbalanced right sizes)- unzipTree (Leaf arr) = case A.unzipWith id arr of- (!left, !right) -> (Leaf left, Leaf right)+unzip = Exts.inline unzipWith id -- | \(O(n)\). Unzip a vector with a function. --@@ -623,7 +618,7 @@ | n >= size = v | otherwise = normalize $ Root n sh (takeTree (n - 1) sh tree) --- | \(O(\log n)\). The vector without the first @i@ elements+-- | \(O(\log n)\). The vector without the first @i@ elements. -- If @i@ is negative, the whole vector is returned. If the vector contains less than @i@ elements, the empty vector is returned. drop :: Int -> Vector a -> Vector a drop !_ Empty = Empty@@ -645,11 +640,14 @@ !right = normalize $ Root (size - n) sh (dropTree n sh tree) in (left, right) --- | \(O(\log n)\). Insert an element at the given index.+-- | \(O(\log n)\). Insert an element at the given index, shifting the rest of the vector over.+-- If the index is negative, add the element to the left end of the vector.+-- If the index is bigger than or equal to the length of the vector, add the element to the right end of the vector. insertAt :: Int -> a -> Vector a -> Vector a insertAt i x v = let (left, right) = splitAt i v in (left |> x) >< right -- | \(O(\log n)\). Delete the element at the given index.+-- If the index is out of range, return the original vector. deleteAt :: Int -> Vector a -> Vector a deleteAt i v = let (left, right) = splitAt (i + 1) v in take i left >< right
src/Data/RRBVector/Internal/Array.hs view
@@ -1,4 +1,5 @@ {-# LANGUAGE BangPatterns #-}+{-# LANGUAGE CPP #-} {-# LANGUAGE MagicHash #-} {-# LANGUAGE RankNTypes #-} {-# LANGUAGE UnboxedTuples #-}@@ -28,7 +29,9 @@ , freeze, thaw ) where -import Control.Applicative (Applicative(liftA2))+#if !(MIN_VERSION_base(4,18,0))+import Control.Applicative (liftA2)+#endif import Control.DeepSeq (NFData(..)) import Control.Monad (when) import Control.Monad.ST
test/Arbitrary.hs view
@@ -1,8 +1,11 @@+{-# LANGUAGE CPP #-} {-# LANGUAGE FlexibleInstances #-} module Arbitrary where +#if !(MIN_VERSION_base(4,18,0)) import Control.Applicative (liftA2)+#endif import Data.Foldable (toList) import Test.Tasty.QuickCheck
test/Main.hs view
@@ -1,5 +1,3 @@-{-# LANGUAGE BangPatterns #-}- import Test.Tasty import Test.Tasty.QuickCheck
test/Properties.hs view
@@ -1,8 +1,12 @@+{-# LANGUAGE CPP #-}+ module Properties ( properties ) where +#if !(MIN_VERSION_base(4,18,0)) import Control.Applicative (liftA2)+#endif import Data.Foldable (Foldable(..)) import Data.List (uncons) import Data.Proxy (Proxy(..))@@ -119,12 +123,15 @@ ] , testGroup "insertAt" [ testProperty "inserts an element" $ \v i x -> toList (V.insertAt i x v) === insertAtList i x (toList v)+ , testProperty "prepends for negative indices" $ \v (Negative i) x -> V.insertAt i x v === x V.<| v+ , testProperty "appends for too large indices" $ \v x -> forAll (arbitrary `suchThat` (> length v)) $ \i -> V.insertAt i x v === v V.|> x , testProperty "satisfies `insertAt 0 x v = x <| v`" $ \v x -> V.insertAt 0 x v === x V.<| v , testProperty "satisfies `insertAt (length v) x v = v |> x`" $ \v x -> V.insertAt (length v) x v === v V.|> x ] , testGroup "deleteAt" [ testProperty "deletes an element" $ \v (NonNegative i) -> toList (V.deleteAt i v) === deleteAtList i (toList v) , testProperty "returns the vector for negative indices" $ \v (Negative i) -> V.deleteAt i v === v+ , testProperty "returns the vector for too large indices" $ \v -> forAll (arbitrary `suchThat` (>= length v)) $ \i -> V.deleteAt i v === v , testProperty "satisfies `deleteAt 0 v = drop 1 v`" $ \v -> V.deleteAt 0 v === V.drop 1 v , testProperty "satisfies `deleteAt (length v - 1) v = take (length v - 1) v`" $ \v -> V.deleteAt (length v - 1) v === V.take (length v - 1) v ]