binary-list 0.3.1.1 → 0.3.1.2

raw patch · 4 files changed

+42/−39 lines, 4 filesdep +binary-listdep +criteriondep +deepseqPVP ok

version bump matches the API change (PVP)

Dependencies added: binary-list, criterion, deepseq

API changes (from Hackage documentation)

Files

• Data/BinaryList.hs +10/−24
• Data/BinaryList/Internal.hs +1/−14
• bench/Main.hs +21/−0
• binary-list.cabal +10/−1

@@ -74,7 +74,7 @@ import Data.Monoid (mappend) import Data.Foldable (Foldable (..),toList) import Data.Traversable (Traversable (..))-import Control.Monad.Trans.State (evalState,get,modify)+import Control.Monad.Trans.State (StateT (..),evalState,get,modify)  -- | /O(1)/. Build a list with a single element. singleton :: a -> BinList a@@ -351,7 +351,9 @@ -- | /O(n)/. Build a binary list from a linked list. If the input list --   has length different from a power of two, it returns 'Nothing'. fromList :: [a] -> Maybe (BinList a)-fromList xs = fmap (fromListBuilder xs) $ exponentInBasisTwo $ Prelude.length xs+fromList xs = fmap builder . exponentInBasisTwo $ Prelude.length xs+  where+    builder l = evalState (replicateA l $ StateT $ \(h:t) -> pure (h,t)) xs  -- | /O(1)/. This is the last exponent that has power of two defined in the type 'Int'. --@@ -377,29 +379,13 @@ fromListWithDefault e xs =   let l = Prelude.length xs   in  case nextExponentOfTwo l of-        Just n -> fromListBuilderWithDefault e xs l n+        Just n ->+          evalState (replicateA n $ StateT $+             \ys -> pure $ case ys of+                      (h:t) -> (h,t)+                      [] -> (e,[])+               ) xs         _ -> error "fromListWithDefault: input list is too big."---- | /O(n)/. Build a binary list from any linked list, providing a default element---   to use when in need of completing elements to the next power of two,---   and the length index of the output binary list.-fromListBuilderWithDefault :: a -- ^ Default element-                           -> [a] -- ^ Input list-                           -> Int -- ^ Lenght of the input list-                           -> Int -- ^ Length index of the list expanded-                                  --   to the next power of two-                           -> BinList a-fromListBuilderWithDefault e = go-  where-    go [] _ n = replicate n e-    go xs _ 0 = ListEnd $ Prelude.head xs -- Hopefully we can avoid this case?-    go xs l n =-      let m = n - 1-          l' = 2^m-          (ys,zs) = splitAt l' xs-      in  if l <= l'-             then ListNode n (go xs l m) (replicate m e)-             else ListNode n (fromListBuilder ys m) (go zs (l - l') m)  ----------------------------- -- Show and Functor instances

@@ -1,9 +1,7 @@ --- | This module only contains the 'BinList' data type, with 'Show' and---   'Functor' instances, plus the 'fromListBuilder' function.+-- | This module only contains the 'BinList' data type. module Data.BinaryList.Internal   ( BinList (..)-  , fromListBuilder     ) where  -- | A binary list is a list containing a power of two elements.@@ -16,14 +14,3 @@         --   * Both l and r have 2^(n-1) elements.       | ListNode {-# UNPACK #-} !Int (BinList a) (BinList a)         deriving Eq---- | /O(n)/. This function builds a binary list from a linked list, assuming---   the length of the input list is a power of two.-fromListBuilder :: [a] -- ^ Input list-                -> Int -- ^ Length index of the input list-                -> BinList a-fromListBuilder [x] _ = ListEnd x-fromListBuilder xs  n =-  let m = n - 1 -- Length index of a single branch-      (l,r) = splitAt (2^m) xs-  in  ListNode n (fromListBuilder l m) (fromListBuilder r m)

@@ -0,0 +1,21 @@++import Data.BinaryList (BinList)+import qualified Data.BinaryList as BL++import Control.DeepSeq+import qualified Data.Foldable as F++import Criterion.Main++instance NFData a => NFData (BinList a) where+  rnf xs = F.foldl1 seq xs `seq` ()++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 "generate" $ nf (\i -> BL.generate i id) 10+      , bench "replicate" $ nf (\i -> BL.replicate i (0 :: Int)) 10+        ]+    ]

@@ -1,5 +1,5 @@ name:                binary-list-version:             0.3.1.1+version:             0.3.1.2 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@@ -25,3 +25,12 @@   type: git   location: git://github.com/Daniel-Diaz/binary-list.git +benchmark binary-list-bench+  type: exitcode-stdio-1.0+  hs-source-dirs: bench+  main-is: Main.hs+  build-depends: base == 4.*+               , binary-list+               , deepseq+               , criterion+  ghc-options: -O2