binary-list 0.3.4.1 → 0.3.5.0

raw patch · 3 files changed

+39/−29 lines, 3 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Data/BinaryList.hs +36/−27
• bench/Main.hs +2/−1
• binary-list.cabal +1/−1

@@ -64,6 +64,7 @@     -- ** From list   , fromList   , fromListWithDefault+  , fromListSplit     -- ** To list   , toListFilter   , toListSegment@@ -86,7 +87,11 @@ import Data.Monoid (mappend) import Data.Foldable (Foldable (..),toList) import Data.Traversable (Traversable (..))-import Control.Monad.Trans.State (StateT (..),evalStateT,evalState,get,modify)+import Control.Monad.Trans.State+  ( StateT (..)+  , evalStateT ,evalState+  , runState+  , get ,modify ) import Control.Monad.Trans.Class (lift) import Data.Functor.Identity (Identity (..)) import Control.Applicative.PhantomState@@ -218,10 +223,9 @@ last (ListNode _ _ r) = last r last (ListEnd x) = x -{-# INLINE[2] reverse #-}- -- | /O(n)/. Reverse a binary list. reverse :: BinList a -> BinList a+{-# INLINE[2] reverse #-} reverse (ListNode n l r) = ListNode n (reverse r) (reverse l) reverse xs = xs @@ -233,22 +237,20 @@ ------------------------------ -- Transformations with tuples -{-# INLINE[1] joinPairs #-}- -- | /O(n)/. Transform a list of pairs into a flat list. The --   resulting list will have twice more elements than the --   original. joinPairs :: BinList (a,a) -> BinList a+{-# INLINE[1] joinPairs #-} joinPairs (ListEnd (x,y)) = ListNode 1 (ListEnd x) (ListEnd y) joinPairs (ListNode n l r) = ListNode (n+1) (joinPairs l) (joinPairs r) -{-# INLINE [1] disjoinPairs #-}- -- | /O(n)/. Opposite transformation of 'joinPairs'. It halves --   the number of elements of the input. As a result, when --   applied to a binary list with a single element, it returns --   'Nothing'. disjoinPairs :: BinList a -> Maybe (BinList (a,a))+{-# INLINE [1] disjoinPairs #-} disjoinPairs (ListEnd _) = Nothing disjoinPairs xs = Just $ disjoinPairsNodes xs @@ -267,11 +269,10 @@          forall f xs . disjoinPairs (map f (joinPairs xs)) = Just (map (f *** f) xs)   #-} -{-# INLINE[0] pairBuilder #-}- -- | Expression @pairBuilder f xs@ is equivalent to @joinPairs (map f xs)@, but does --   not build any intermediate structure. Used for rewriting rules. pairBuilder :: (a -> (b,b)) -> BinList a -> BinList b+{-# INLINE[0] pairBuilder #-} pairBuilder f = go   where     go (ListEnd x) = let (a,b) = f x in ListNode 1 (ListEnd a) (ListEnd b)@@ -335,16 +336,14 @@                      ListNode n (goEquals l l') (goEquals r r')     goEquals xs ys = ListEnd $ f (head xs) (head ys) -{-# INLINE zip #-}- -- | /O(n)/. Zip two binary lists in pairs. zip :: BinList a -> BinList b -> BinList (a,b)+{-# INLINE zip #-} zip = zipWith (,) -{-# INLINE[1] unzip #-}- -- | /O(n)/. Unzip a binary list of pairs. unzip :: BinList (a,b) -> (BinList a, BinList b)+{-# INLINE[1] unzip #-} unzip (ListEnd (x,y)) = (ListEnd x, ListEnd y) unzip (ListNode n l r) =   let (la,lb) = unzip l@@ -413,16 +412,31 @@         Just n ->           evalState (replicateA n $ StateT $              \ys -> pure $ case ys of-                      (h:t) -> (h,t)-                      [] -> (e,[])+                      (h:t) -> (h,t )+                      _     -> (e,[])                ) xs         _ -> error "[binary-list] fromListWithDefault: input list is too big." -{-# INLINE toListFilter #-}+-- | /O(n)/. Build a binary list from a linked list. It returns a binary list+--   with length @2 ^ n@ (where @n@ is the supplied 'Int' argument), and+--   the list of elements of the original list that were not used. If the+--   input list is shorter than @2 ^ n@, a default element will be used to+--   complete the binary list. This method for building binary lists is faster+--   than both 'fromList' and 'fromListWithDefault'.+fromListSplit :: a   -- ^ Default element+              -> Int -- ^ Length index+              -> [a] -- ^ Input list+              -> (BinList a, [a])+fromListSplit e n =+  runState $ replicateA n $ StateT $+    \xs -> pure $ case xs of+                    (h:t) -> (h,t )+                    _     -> (e,[])  -- | /O(n)/. Create a list from the elements of a binary list matching a given --   condition. toListFilter :: (a -> Bool) -> BinList a -> [a]+{-# INLINE toListFilter #-} toListFilter c = foldr (\x -> if c x then (x:) else id) []  -- | /O(n)/. Create a list extracting a sublist of elements from a binary list.@@ -430,19 +444,17 @@ {-# INLINE toListSegment #-} toListSegment s e xs = runPhantomState (traverseSegment (changeState . (:)) s e xs) [] -{-# INLINE traverseSegment #-}- -- | Apply an applicative action to every element in a segment of a binary list, from left to right. traverseSegment :: Applicative f => (a -> f ()) -> Int -> Int -> BinList a -> f ()+{-# INLINE traverseSegment #-} traverseSegment f s e xs   | s > e = pure ()   | e < 0 = pure ()   | s >= length xs = pure ()   | otherwise = traverseSegmentFromTo f (max 0 s) e xs -{-# INLINE traverseSegmentFromTo #-}- traverseSegmentFromTo :: Applicative f => (a -> f ()) -> Int -> Int -> BinList a -> f ()+{-# INLINE traverseSegmentFromTo #-} traverseSegmentFromTo f = go   where     go s e (ListNode n l r) =@@ -457,9 +469,8 @@                      else traverseSegmentFrom f s l *> traverseSegmentTo f (e - k) r     go _ _ (ListEnd x) = f x -{-# INLINE traverseSegmentFrom #-}- traverseSegmentFrom :: Applicative f => (a -> f ()) -> Int -> BinList a -> f ()+{-# INLINE traverseSegmentFrom #-} traverseSegmentFrom f = go   where     go s (ListNode n l r) =@@ -472,9 +483,8 @@              else go s l *> traverseFull f r     go _ (ListEnd x) = f x -{-# INLINE traverseSegmentTo #-}- traverseSegmentTo :: Applicative f => (a -> f ()) -> Int -> BinList a -> f ()+{-# INLINE traverseSegmentTo #-} traverseSegmentTo f = go   where     go e (ListNode n l r) =@@ -487,9 +497,8 @@              else traverseFull f l *> go (e - k) r     go _ (ListEnd x) = f x -{-# INLINE traverseFull #-}- traverseFull :: Applicative f => (a -> f ()) -> BinList a -> f ()+{-# INLINE traverseFull #-} traverseFull f = go   where     go (ListEnd x) = f x@@ -512,8 +521,8 @@  -} -{-# INLINE[1] map #-} map :: (a -> b) -> BinList a -> BinList b+{-# INLINE[1] map #-} map f = go   where     go (ListEnd x) = ListEnd (f x)

@@ -13,7 +13,7 @@   rnf xs = F.foldl1 seq xs `seq` ()  list1024 :: [Int]-list1024 = [1..1024]+list1024 = [1..1024] -- 2^10 = 1024  list513 :: [Int] list513 = [1..513]@@ -26,6 +26,7 @@   [ bgroup "1024"       [ bench "fromList" $ nf (\i -> const BL.fromList i $ list1024) 0       , bench "fromListWithDefault" $ nf (\i -> BL.fromListWithDefault i list513) 0+      , bench "fromListSplit" $ nf (\i -> BL.fromListSplit i 10 list513) 0       , bench "generate" $ nf (\i -> BL.generate i id) 10       , bench "replicate" $ nf (\i -> BL.replicate i (0 :: Int)) 10       , bench "toListSegment" $ nf (\e -> BL.toListSegment 256 e blist1024) 768

@@ -1,5 +1,5 @@ name:                binary-list-version:             0.3.4.1+version:             0.3.5.0 synopsis:            Lists of size length a power of two. description:         Implementation of lists whose number of elements is a                      power of two. Binary lists have this property by definition,