binary-list 0.3.2.1 → 0.3.3.0

raw patch · 4 files changed

+117/−9 lines, 4 filesdep +phantom-statePVP ok

version bump matches the API change (PVP)

Dependencies added: phantom-state

API changes (from Hackage documentation)

Files

• Data/BinaryList.hs +99/−5
• Data/BinaryList/Serialize.hs +2/−1
• bench/Main.hs +14/−2
• binary-list.cabal +2/−1

@@ -40,6 +40,7 @@   , replicateA   , replicateAR   , generate+  , generateM     -- * Queries   , lengthIndex   , length@@ -59,13 +60,21 @@   , zip , unzip   , zipWith     -- * Lists+    -- ** From list   , fromList   , fromListWithDefault+    -- ** To list+  , toListFilter+  , toListSegment+    -- * Others+  , traverseSegment     -- * Example: Radix-2 FFT     -- $fft   ) where -import Prelude hiding ( length,lookup,replicate,head,last,zip,unzip,zipWith,reverse,foldr1,take,map )+import Prelude hiding ( length,lookup,replicate,head,last+                      , zip,unzip,zipWith,reverse,foldr1+                      , take,map,foldr ) import qualified Prelude import Foreign.Storable (sizeOf) import Data.List (find)@@ -76,8 +85,10 @@ import Data.Monoid (mappend) import Data.Foldable (Foldable (..),toList) import Data.Traversable (Traversable (..))-import Control.Monad.Trans.State (StateT (..),evalState,get,modify)+import Control.Monad.Trans.State (StateT (..),evalStateT,evalState,get,modify)+import Control.Monad.Trans.Class (lift) import Data.Functor.Identity (Identity (..))+import Control.Applicative.PhantomState  -- | /O(1)/. Build a list with a single element. singleton :: a -> BinList a@@ -176,6 +187,11 @@ generate :: Int -> (Int -> a) -> BinList a generate l f = evalState (replicateA l $ fmap f get <* modify (+1)) 0 +-- | Like 'generate', but the generator function returns a value in a 'Monad'.+--   Therefore, the result is as well contained in a 'Monad'.+generateM :: (Applicative m, Monad m) => Int -> (Int -> m a) -> m (BinList a)+generateM l f = evalStateT (replicateA l $ (get >>= lift . f) <* modify (+1)) 0+ -- | /O(log n)/. Get the first element of a binary list. head :: BinList a -> a head (ListNode _ l _) = head l@@ -384,8 +400,88 @@                       (h:t) -> (h,t)                       [] -> (e,[])                ) xs-        _ -> error "fromListWithDefault: input list is too big."+        _ -> error "[binary-list] fromListWithDefault: input list is too big." +{-# INLINE toListFilter #-}++-- | /O(n)/. Create a list from the elements of a binary list matching a given+--   condition.+toListFilter :: (a -> Bool) -> BinList a -> [a]+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.+toListSegment :: Int -> Int -> BinList a -> [a]+{-# 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 ()+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 ()+traverseSegmentFromTo f = go+  where+    go s e (ListNode n l r) =+      let k = 2^(n-1)+      in  if s >= k+             -- Sublist is contained in right portion+             then go (s - k) (e - k) r+             else if e < k+                     -- Sublist is contained in left portion+                     then go s e l+                     -- Sublist is divided in both portions+                     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 ()+traverseSegmentFrom f = go+  where+    go s (ListNode n l r) =+      let k = 2^(n-1)+      in  if s >= k+             -- Sublist is contained in right portion+             then go (s - k) r+             -- Sublist is divided in both portions, but right+             -- portion is taken entirely+             else go s l *> traverseFull f r+    go _ (ListEnd x) = f x++{-# INLINE traverseSegmentTo #-}++traverseSegmentTo :: Applicative f => (a -> f ()) -> Int -> BinList a -> f ()+traverseSegmentTo f = go+  where+    go e (ListNode n l r) =+      let k = 2^(n-1)+      in  if e < k+             -- Sublist is contained in left portion+             then go e l+             -- Sublist is divided in both portions, but left+             -- portion is taken entirely+             else traverseFull f l *> go (e - k) r+    go _ (ListEnd x) = f x++{-# INLINE traverseFull #-}++traverseFull :: Applicative f => (a -> f ()) -> BinList a -> f ()+traverseFull f = go+  where+    go (ListEnd x) = f x+    go (ListNode _ l r) = go l *> go r++------------------------------------------------+------------------------------------------------+ ----------------------------- -- Show and Functor instances @@ -457,7 +553,5 @@ >       in  fromJust $ >             BL.append (BL.zipWith (+) evensfft oddsfft) >                       (BL.zipWith (-) evensfft oddsfft)--  -}

@@ -52,7 +52,7 @@ --   If you foresee reading only a part of the list, either --   at its beginning or end, an appropiate choice of direction --   will allow you to avoid decoding the full list.-data Direction = FromLeft | FromRight deriving Eq+data Direction = FromLeft | FromRight deriving (Eq,Show)  -- | A binary list encoded, ready to be written in a file or be --   sent over a network. It can be directly translated to a@@ -103,6 +103,7 @@                | FinalResult (BinList a) ByteString                  -- | A decoding error, with an error message and the remaining input.                | DecodingError String ByteString+                 deriving Show  -- | Get the final result of a decoding process, unless it returned an error, in which --   case this error is returned as a 'String'.

@@ -2,20 +2,32 @@ import Data.BinaryList (BinList) import qualified Data.BinaryList as BL +import Control.Applicative import Control.DeepSeq import qualified Data.Foldable as F +-- criterion import Criterion.Main  instance NFData a => NFData (BinList a) where   rnf xs = F.foldl1 seq xs `seq` () +list1024 :: [Int]+list1024 = [1..1024]++list513 :: [Int]+list513 = [1..513]++blist1024 :: BinList Int+blist1024 = BL.generate 10 id+ main :: IO () main = defaultMain   [ bgroup "1024"-      [ bench "fromList" $ nf (\i -> BL.fromList [1..i]) (1024 :: Int)-      , bench "fromListWithDefault" $ nf (\i -> BL.fromListWithDefault 0 [1..i]) (513 :: Int)+      [ bench "fromList" $ nf (\i -> const BL.fromList i $ list1024) 0+      , bench "fromListWithDefault" $ nf (\i -> BL.fromListWithDefault i 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.2.1+version:             0.3.3.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,@@ -30,6 +30,7 @@   other-modules:       Data.BinaryList.Internal   build-depends:       base == 4.*, bytestring, binary >= 0.6.4.0                ,       transformers >= 0.3.0.0+               ,       phantom-state >= 0.2   default-language:    Haskell2010   ghc-options:         -Wall -fno-warn-orphans