binary-list 0.3.1.2 → 0.3.2.0

raw patch · 3 files changed

+72/−20 lines, 3 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Data/BinaryList.hs +49/−14
• Data/BinaryList/Serialize.hs +21/−5
• binary-list.cabal +2/−1

@@ -61,6 +61,8 @@     -- * Lists   , fromList   , fromListWithDefault+    -- * Example: Radix-2 FFT+    -- $fft   ) where  import Prelude hiding ( length,lookup,replicate,head,last,zip,unzip,zipWith,reverse,foldr1,take,map )@@ -75,6 +77,7 @@ import Data.Foldable (Foldable (..),toList) import Data.Traversable (Traversable (..)) import Control.Monad.Trans.State (StateT (..),evalState,get,modify)+import Data.Functor.Identity (Identity (..))  -- | /O(1)/. Build a list with a single element. singleton :: a -> BinList a@@ -135,20 +138,6 @@ takeEnd k xs@(ListNode n _ r) = if k >= n then xs else takeEnd k r takeEnd _ xs = xs --- | /O(log n)/. Calling @replicate n x@ builds a binary list with---   @2^n@ occurences of @x@.-replicate :: Int -> a -> BinList a-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: map/replicate"-         forall f n x . map f (replicate n x) = replicate n (f 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)@@ -172,6 +161,16 @@          forall i f . map reverse (replicateAR i f) = replicateA  i f   #-} +-- | /O(log n)/. Calling @replicate n x@ builds a binary list with+--   @2^n@ occurences of @x@.+replicate :: Int -> a -> BinList a+replicate n = runIdentity . replicateA n . Identity++{-# RULES+      "Data.BinaryList: map/replicate"+         forall f n x . map f (replicate n x) = replicate n (f x)+  #-}+ -- | /O(n)/. Build a binary list with the given length index (see 'lengthIndex') --   by applying a function to each index. generate :: Int -> (Int -> a) -> BinList a@@ -426,3 +425,39 @@ instance Traversable BinList where   sequenceA (ListEnd f) = ListEnd <$> f   sequenceA (ListNode n l r) = ListNode <$> pure n <*> sequenceA l <*> sequenceA r++-----------------------------+-- Example: Radix-2 FFT++{- $fft++This is an example demonstrating the use of binary lists to calculate the Discrete+Fourier Transform of complex vectors with the Radix-2 Fast Fourier Transform algorithm.++> import Data.BinaryList (BinList)+> import qualified Data.BinaryList as BL+> +> import Data.Complex+> import Data.Maybe (fromJust)+> +> i :: Complex Double+> i = 0 :+ 1+> +> fft :: BinList (Complex Double) -> BinList (Complex Double)+> fft xs =+>   case BL.disjoinPairs xs of+>     Nothing -> xs+>     Just ps ->+>       let (evens,odds) = BL.unzip ps+>           n = BL.lengthIndex xs - 1+>           q = negate $ pi * i / fromIntegral (2^n)+>           twiddles = BL.generate n $ \k -> exp $ q * fromIntegral k+>           oddsfft = BL.zipWith (*) twiddles $ fft odds+>           evensfft = fft evens+>       in  fromJust $+>             BL.append (BL.zipWith (+) evensfft oddsfft)+>                       (BL.zipWith (-) evensfft oddsfft)++++-}

@@ -13,14 +13,14 @@    , DecodedBinList (..)    , Decoded (..)    , fromDecoded+   , toDecoded    , decodeBinList      -- ** ByteString translations    , encodedToByteString    , encodedFromByteString    ) where -import Prelude hiding (foldr,foldl)-import Data.Foldable (foldr,foldl)+import Data.Foldable (traverse_) -- Binary lists import Data.BinaryList.Internal import Data.BinaryList@@ -29,7 +29,9 @@ import Data.Binary.Put import Data.Binary.Get -- Bytestrings-import Data.ByteString.Lazy (ByteString)+import Data.ByteString.Lazy (ByteString,empty)+-- Backwards Applicative+import Control.Applicative.Backwards  -- | Encode a binary list using the 'Binary' instance of --   its elements.@@ -71,8 +73,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 ()) xs-     else runPut $ foldl (\y x -> f x >> y) (return ()) xs+     then runPut $ traverse_ f xs+     else runPut $ forwards $ traverse_ (Backwards . f) 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@@ -108,6 +110,20 @@ fromDecoded (PartialResult _ d) = fromDecoded d fromDecoded (FinalResult xs _) = Right xs fromDecoded (DecodingError err _) = Left err++-- | Break a list down to sublists of order 1, 2, 4, 8, ..., 2^k.+--   The result is stored in a 'Decoded' value. Obviously, the output+--   will not have a decoding error.+toDecoded :: BinList a -> Decoded a+toDecoded xs =+  case split xs of+    Right (l,_) -> go l $ FinalResult xs empty+    _ -> FinalResult xs empty+  where+    go ys d =+      case split ys of+        Right (l,_) -> go l $ PartialResult ys d+        _ -> PartialResult ys d  -- | Decode an encoded binary list. --   The result is given as a 'DecodedBinList' value, which can then be

@@ -1,5 +1,5 @@ name:                binary-list-version:             0.3.1.2+version:             0.3.2.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 implements a@@ -26,6 +26,7 @@   location: git://github.com/Daniel-Diaz/binary-list.git  benchmark binary-list-bench+  default-language: Haskell2010   type: exitcode-stdio-1.0   hs-source-dirs: bench   main-is: Main.hs