binary-list 0.1.0.1 → 0.1.0.2

raw patch · 2 files changed

+34/−5 lines, 2 filesPVP ok

version bump matches the API change (PVP)

API changes (from Hackage documentation)

Files

• Data/BinaryList.hs +33/−4
• binary-list.cabal +1/−1

@@ -48,7 +48,6 @@  import Prelude hiding (length,lookup,replicate,head,last,zip,unzip,zipWith,reverse) import qualified Prelude-import Data.Bits ((.&.)) import Foreign.Storable (sizeOf) import Data.List (find) @@ -60,7 +59,7 @@         -- Given ListNode n l r:         --   * n >= 1.         --   * Both l and r have 2^(n-1) elements.-      | ListNode Int (BinList a) (BinList a)+      | ListNode {-# UNPACK #-} !Int (BinList a) (BinList a)         deriving Eq  -- | /O(1)/. Build a list with a single element.@@ -115,6 +114,11 @@   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 +{-# RULES+      "Data.BinaryList: fmap/replicate"+         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)@@ -135,6 +139,11 @@ reverse (ListNode n l r) = ListNode n (reverse r) (reverse l) reverse xs = xs +{-# RULES+      "Data.BinaryList: reverse/reverse"+         forall xs. reverse (reverse xs) = xs+  #-}+ ------------------------------ -- Transformations with tuples @@ -211,7 +220,7 @@ fromList :: [a] -> Maybe (BinList a) fromList xs = fmap (fromListBuilder xs) $ exponentInBasisTwo $ Prelude.length xs --- | /O(n)/. This functions builds a binary list from a linked list, assuming+-- | /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@@ -246,8 +255,28 @@ fromListWithDefault e xs =   let l = Prelude.length xs   in  case nextExponentOfTwo l of-        Just n -> fromListBuilder (xs ++ Prelude.replicate (2^n - l) e) n+        Just n -> fromListBuilderWithDefault e xs l n         _ -> 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 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)  -- | /O(n)/. Build a linked list from a binary list. toList :: BinList a -> [a]

@@ -1,5 +1,5 @@ name:                binary-list-version:             0.1.0.1+version:             0.1.0.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 provides with a