binary-list 0.3.0.0 → 0.3.1.0

raw patch · 3 files changed

+101/−7 lines, 3 filesPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

API changes (from Hackage documentation)

Files

• Data/BinaryList.hs +98/−4
• Data/BinaryList/Serialize.hs +1/−1
• binary-list.cabal +2/−2

@@ -12,7 +12,7 @@ --   It is impossible for the user of this library to create a binary list --   whose length is /not/ a power of two. -----   Since many names in this module crashes with the names of some "Prelude"+--   Since many names in this module clash with the names of some "Prelude" --   functions, you probably want to import this module this way: -- -- > import Data.BinaryList (BinList)@@ -22,6 +22,14 @@ --   classes. If you are missing a function here, look for functions using those --   instances. --+--   Note that some functions like 'replicate', 'generate', or 'take', don't use+--   the length of the list as argument, but the exponent of its length expressed+--   as a power of two. Throughout this document, this is referred (perhaps improperly)+--   as the /length index/. For example, if the list has length 16, its length index+--   is 4 since 2^4 = 16. Therefore @replicate 4 0@ will create a list with 16 zeroes.+--   Keep this in mind when using this library. Note as well that this implies that+--   there is no need to check that the length argument is or is not a power of two.+-- module Data.BinaryList (     -- * Type     BinList@@ -31,15 +39,17 @@   , replicate   , replicateA   , replicateAR+  , generate     -- * Queries   , lengthIndex   , length   , lookup   , head   , last-    -- * Decontruction+    -- * Deconstruction   , split-  , fold+  , take+  , takeEnd     -- * Transformation   , reverse     -- * Tuples@@ -53,16 +63,18 @@   , fromListWithDefault   ) where -import Prelude hiding ( length,lookup,replicate,head,last,zip,unzip,zipWith,reverse,foldr1 )+import Prelude hiding ( length,lookup,replicate,head,last,zip,unzip,zipWith,reverse,foldr1,take ) import qualified Prelude import Foreign.Storable (sizeOf) import Data.List (find) import Data.BinaryList.Internal import Control.Applicative (Applicative (..),(<$>)) import Control.Applicative.Backwards+import Control.Arrow ((***)) import Data.Monoid (mappend) import Data.Foldable (Foldable (..),toList) import Data.Traversable (Traversable (..))+import Control.Monad.Trans.State (evalState,get,modify)  -- | /O(1)/. Build a list with a single element. singleton :: a -> BinList a@@ -80,6 +92,11 @@ length :: BinList a -> Int length = (2^) . lengthIndex +{-# RULES+       "Data.BinaryList: length equality"+         forall xs ys . length xs == length ys = lengthIndex xs == lengthIndex ys+  #-}+ -- | /O(log n)/. Lookup an element in the list by its index (starting from 0). --   If the index is out of range, 'Nothing' is returned. lookup :: BinList a -> Int -> Maybe a@@ -108,6 +125,16 @@ split (ListNode _ l r) = Right (l,r) split (ListEnd x) = Left x +-- | /O(log n)/. Calling @take n xs@ returns the first @min (2^n) (length xs)@ elements of @xs@.+take :: Int -> BinList a -> BinList a+take k xs@(ListNode n l _) = if k >= n then xs else take k l+take _ xs = xs++-- | /O(log n)/. Calling @takeEnd n xs@ returns the last @min (2^n) (length xs)@ elements of @xs@.+takeEnd :: Int -> BinList a -> BinList a+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@@ -145,6 +172,11 @@          forall i f . fmap reverse (replicateAR i f) = replicateA  i f   #-} +-- | /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+generate l f = evalState (replicateA l $ fmap f get <* modify (+1)) 0+ -- | /O(log n)/. Get the first element of a binary list. head :: BinList a -> a head (ListNode _ l _) = head l@@ -188,6 +220,54 @@ disjoinPairsNodes (ListNode n l r) = ListNode (n-1) (disjoinPairsNodes l) (disjoinPairsNodes r) disjoinPairsNodes _ = error "disjoinPairsNodes: bug. Please, report this with an example input." +{-# RULES+      "Data.BinaryList: disjoinPairs/joinPairs"+         forall xs . disjoinPairs (joinPairs xs) = Just xs+  #-}++{-# RULES+      "Data.BinaryList: disjoinPairs/fmap/joinPairs"+         forall f xs . disjoinPairs (fmap f (joinPairs xs)) = Just (fmap (f *** f) xs)+  #-}++pairBuilder :: (a -> (b,b)) -> BinList a -> BinList b+pairBuilder f = go+  where+    go (ListEnd x) = let (a,b) = f x in ListNode 1 (ListEnd a) (ListEnd b)+    go (ListNode n l r) = ListNode (n+1) (go l) (go r)++{-# RULES+      "Data.BinaryList: joinPairs/fmap"+         forall f xs . joinPairs (fmap f xs) = pairBuilder f xs+  #-}++zipAndJoin :: ((a,b) -> (c,c)) -> BinList a -> BinList b -> BinList c+zipAndJoin f = go+  where+    -- Recursion+    go xs@(ListNode n l r) ys@(ListNode n' l' r')+         -- If both lists have the same length, recurse assuming it+         -- to avoid comparisons.+       | n == n'   = ListNode (n+1) (goEquals l l') (goEquals r r')+         -- If the first list is larger, the second fits entirely in+         -- the left branch of the first.+       | n >  n'   = go l ys+         -- If the second list is larger, the first fits entirely in+         -- the left branch of the second.+       | otherwise = go xs l'+    go xs ys       = let (x,y) = f (head xs,head ys)+                     in  ListNode 1 (ListEnd x) (ListEnd y)+    -- Recursion assuming both lists have the same length+    goEquals (ListNode n l r) (ListNode _ l' r') =+                     ListNode (n+1) (goEquals l l') (goEquals r r')+    goEquals xs ys = let (x,y) = f (head xs,head ys)+                     in  ListNode 1 (ListEnd x) (ListEnd y)++{-# RULES+      "Data.BinaryList: pairBuilder/zip"+         forall f xs ys . pairBuilder f (zip xs ys) = zipAndJoin f xs ys+  #-}+ ------------------------ -- Zipping and Unzipping @@ -223,6 +303,20 @@   let (la,lb) = unzip l       (ra,rb) = unzip r   in  (ListNode n la ra, ListNode n lb rb)++unzipMap :: ((a,b) -> (c,d)) -> BinList (a,b) -> (BinList c,BinList d)+unzipMap f = go+  where+    go (ListEnd p) = ListEnd *** ListEnd $ f p+    go (ListNode n l r) =+      let (lc,ld) = go l+          (rc,rd) = go r+      in  (ListNode n lc rc, ListNode n ld rd)++{-# RULES+      "Data.BinaryList: unzip/fmap"+         forall f xs . unzip (fmap f xs) = unzipMap f xs+  #-}  ----------------------------- -- Transforming from/to lists

@@ -92,7 +92,7 @@ --   lists of increasing size, ending in either a decoding error or a final --   binary list. When this is the result of 'decodeBinList', it --   contains sublists of order 1, 2, 4, 8, ... up to the order of the total---   list (unless an error has been encountered first). This sublists are+--   list (unless an error has been encountered first). These sublists are --   either a section starting at the left, or a section starting at the right, --   depending on the 'Direction' of encoding. data Decoded a = -- | Partial binary list, and rest of decoded input.

@@ -1,8 +1,8 @@ name:                binary-list-version:             0.3.0.0+version:             0.3.1.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+                     has length a power of two. This library implements a                      data structure optimized for this. license:             BSD3 license-file:        LICENSE