binary-list 0.2.0.4 → 0.3.0.0

raw patch · 3 files changed

+81/−53 lines, 3 filesdep +transformersPVP ok

version bump matches the API change (PVP)

Dependencies added: transformers

API changes (from Hackage documentation)

Files

• Data/BinaryList.hs +57/−33
• Data/BinaryList/Serialize.hs +22/−19
• binary-list.cabal +2/−1

@@ -3,7 +3,9 @@ --   This data structure is efficient for some computations like: -- -- * Splitting a list in half.+-- -- * Appending two lists of the same length.+-- -- * Extracting an element from the list. -- --   All the functions exported are total except for 'fromListWithDefault'.@@ -16,6 +18,10 @@ -- > import Data.BinaryList (BinList) -- > import qualified Data.BinaryList as BL --+--   Remember that binary lists are an instance of the 'Foldable' and 'Traversable'+--   classes. If you are missing a function here, look for functions using those+--   instances.+-- module Data.BinaryList (     -- * Type     BinList@@ -23,14 +29,14 @@   , singleton   , append   , replicate+  , replicateA+  , replicateAR     -- * Queries   , lengthIndex   , length   , lookup   , head   , last-  , minimum-  , maximum     -- * Decontruction   , split   , fold@@ -45,17 +51,18 @@     -- * Lists   , fromList   , fromListWithDefault-  , toList   ) where -import Prelude hiding ( length,lookup,replicate,head,last,zip,unzip,zipWith,reverse-                      , minimum, maximum-                        )+import Prelude hiding ( length,lookup,replicate,head,last,zip,unzip,zipWith,reverse,foldr1 ) import qualified Prelude import Foreign.Storable (sizeOf) import Data.List (find) import Data.BinaryList.Internal-+import Control.Applicative (Applicative (..),(<$>))+import Control.Applicative.Backwards+import Data.Monoid (mappend)+import Data.Foldable (Foldable (..),toList)+import Data.Traversable (Traversable (..))  -- | /O(1)/. Build a list with a single element. singleton :: a -> BinList a@@ -104,21 +111,40 @@ -- | /O(log n)/. Calling @replicate n x@ builds a binary list with --   @2^n@ occurences of @x@. replicate :: Int -> a -> BinList a-replicate 0 x = ListEnd x-replicate n x =-  let b = replicate (n-1) x -- Both branches of the binary list-  in  ListNode n b b -- Note that both branches are the same shared object+replicate n x = go n+  where+    go 0 = ListEnd x+    go i = let b = go (i-1) -- Both branches of the binary list+           in  ListNode i b b -- Note that both branches are the same shared object  {-# RULES       "Data.BinaryList: fmap/replicate"-         forall f n x. fmap f (replicate n x) = replicate n (f x)+         forall f n x . fmap f (replicate n x) = replicate n (f x)   #-} --- | Fold a binary list using an operator.-fold :: (a -> a -> a) -> BinList a -> a-fold f (ListNode _ l r) = f (fold f l) (fold f r)-fold _ (ListEnd x) = x+-- | Calling @replicateA n f@ builds a binary list collecting the results of+--   executing @2^n@ times the applicative action @f@.+replicateA :: Applicative f => Int -> f a -> f (BinList a)+replicateA n f = go n+  where+    go 0 = ListEnd <$> f+    go i = let b = go (i-1)+           in  ListNode <$> pure i <*> b <*> b +-- | The same as 'replicateA', but the actions are executed in reversed order.+replicateAR :: Applicative f => Int -> f a -> f (BinList a)+replicateAR n = forwards . replicateA n . Backwards++{-# RULES+      "Data.BinaryList: fmap reverse/replicateA"+         forall i f . fmap reverse (replicateA  i f) = replicateAR i f+  #-}++{-# RULES+      "Data.BinaryList: fmap reverse/replicateAR"+         forall i f . fmap reverse (replicateAR i f) = replicateA  i f+  #-}+ -- | /O(log n)/. Get the first element of a binary list. head :: BinList a -> a head (ListNode _ l _) = head l@@ -139,16 +165,6 @@          forall xs. reverse (reverse xs) = xs   #-} --- | /O(n)/. Retrieves the minimum element of a binary list.-minimum :: Ord a => BinList a -> a-minimum (ListEnd x) = x-minimum (ListNode _ l r) = min (minimum l) (minimum r)---- | /O(n)/. Retrieves the maximum element of a binary list.-maximum :: Ord a => BinList a -> a-maximum (ListEnd x) = x-maximum (ListNode _ l r) = max (maximum l) (maximum r)- ------------------------------ -- Transformations with tuples @@ -273,13 +289,6 @@              then ListNode n (go xs l m) (replicate m e)              else ListNode n (fromListBuilder ys m) (go zs (l - l') m) --- | /O(n)/. Build a linked list from a binary list.-toList :: BinList a -> [a]-toList = go []-  where-    go xs (ListNode _ l r) = go (go xs r) l-    go xs (ListEnd x) = x : xs- ----------------------------- -- Show and Functor instances @@ -289,3 +298,18 @@ instance Functor BinList where   fmap f (ListNode n l r) = ListNode n (fmap f l) (fmap f r)   fmap f (ListEnd x) = ListEnd $ f x++instance Foldable BinList where+  -- Folding+  foldr1 f = go+    where+      go (ListEnd x) = x+      go (ListNode _ l r) = f (go l) (go r)+  --+  fold = foldr1 mappend+  foldl1 = foldr1+  foldMap f = fold . fmap f++instance Traversable BinList where+  sequenceA (ListEnd f) = ListEnd <$> f+  sequenceA (ListNode n l r) = ListNode <$> pure n <*> sequenceA l <*> sequenceA r

@@ -19,7 +19,8 @@    , encodedFromByteString    ) where -import Prelude hiding (reverse)+import Prelude hiding (foldr,foldl)+import Data.Foldable (foldr,foldl) -- Binary lists import Data.BinaryList.Internal import Data.BinaryList@@ -29,8 +30,6 @@ import Data.Binary.Get -- Bytestrings import Data.ByteString.Lazy (ByteString)--- Utils-import Control.Monad (replicateM)  -- | Encode a binary list using the 'Binary' instance of --   its elements.@@ -72,8 +71,8 @@ encodeBinList :: (a -> Put) -> Direction -> BinList a -> EncodedBinList encodeBinList f d xs = EncodedBinList d (lengthIndex xs) $   if d == FromLeft-     then runPut $ foldr (\x y -> f x >> y) (return ()) $ toList xs-     else runPut $ foldl (\y x -> f x >> y) (return ()) $ toList xs+     then runPut $ foldr (\x y -> f x >> y) (return ()) xs+     else runPut $ foldl (\y x -> f x >> y) (return ()) xs  -- | A binary list decoded, from where you can extract a binary list. If the --   decoding process fails in some point, you still will be able to retrieve@@ -119,16 +118,23 @@     Left (r,_,err) -> DecodingError err r     Right (r,_,x) -> go r (ListEnd x)   where-    -- | To avoid looking at the direction in each recursive step,-    --   we provide a function to append newly read data with the-    --   accumulated binary list depending on the direction. Since the-    --   new data is of the same size as the accumulated binary list,-    --   we can append them safely just by using 'ListNode'.+    -- | Function to get binary trees using the supplied 'Get' value.+    --   The order of the elements depends on the encoding direction.     --+    -- getBinList :: Int -> Get (BinList a)+    getBinList =+       case d of+         FromLeft -> \i -> replicateA  i f+         _        -> \i -> replicateAR i f++    -- | Function to append two binary lists of given length index,+    --   where the order of appending depends on the encoding+    --   direction.+    --     -- recAppend :: Int -> BinList a -> BinList a -> BinList a-    recAppend i = case d of-       FromLeft    -> ListNode (i+1)-       _ -> \xs ys -> ListNode (i+1) (reverse ys) xs+    recAppend = case d of+       FromLeft -> \i ->        ListNode (i+1)+       _        -> \i -> flip $ ListNode (i+1)      -- | Recursive decoding function.     --@@ -143,14 +149,11 @@               -- Otherwise, we read another chunk of data of the same size of               -- the already decoded data, prepending the accumulated data as               -- a partial result.-              else PartialResult xs $ case runGetOrFail (replicateM (2^i) f) input of+              else PartialResult xs $ case runGetOrFail (getBinList i) input of                      -- In case of error, we return a decoding error.                      Left (r,_,err) -> DecodingError err r-                     Right (r,_,list) ->-                       let -- Otherwise, we build a new binary list with the collected-                           -- new data.-                           ys = fromListBuilder list i-                           -- The new list is appended with the accumulated list and fed+                     Right (r,_,ys) ->+                       let -- The new list is appended with the accumulated list and fed                            -- to the next recursion step.                        in  go r $ recAppend i xs ys 

@@ -1,5 +1,5 @@ name:                binary-list-version:             0.2.0.4+version:             0.3.0.0 synopsis:            Lists of size length a power of two. description:         Some algorithmic problems work only when the input list                      has length a power of two. This library provides with a@@ -17,6 +17,7 @@   exposed-modules:     Data.BinaryList, Data.BinaryList.Serialize   other-modules:       Data.BinaryList.Internal   build-depends:       base == 4.*, bytestring, binary >= 0.6.4.0+               ,       transformers >= 0.3.0.0   default-language:    Haskell2010   ghc-options:         -Wall -fno-warn-orphans