acc 0.1.0.1 → 0.1.0.2

raw patch · 4 files changed

+137/−3 lines, 4 filesPVP: minor bump suggested

API additions: PVP suggests at least a minor version bump

API changes (from Hackage documentation)

Files

• acc.cabal +2/−2
• library/Acc.hs +76/−0
• library/Acc/BinTree1.hs +54/−1
• test/Main.hs +5/−0

@@ -1,5 +1,5 @@ name: acc-version: 0.1.0.1+version: 0.1.0.2 synopsis: Sequence optimized for monoidal construction and folding description:   Data structure intended for accumulating a sequence of elements@@ -7,7 +7,7 @@   Useful for implementing all kinds of builders on top.   .   The benchmarks show that for the described use-case it-  is on average 2 times faster than 'Data.DList.DList' and 'Data.Sequence.Seq',+  is on average 2 times faster than 'DList' and 'Seq',   is on par with list when you always prepend elements and   is exponentially faster than list when you append. homepage: https://github.com/nikita-volkov/acc

@@ -2,6 +2,10 @@ module Acc (   Acc,+  cons,+  snoc,+  uncons,+  unsnoc, ) where @@ -67,6 +71,12 @@         BinTree1.foldr' step acc a       EmptyAcc ->         acc+  foldl step acc =+    \ case+      TreeAcc a ->+        BinTree1.foldl step acc a+      EmptyAcc ->+        acc   foldl' step acc =     \ case       TreeAcc a ->@@ -138,3 +148,69 @@ instance Show a => Show (Acc a) where   show =     show . toList++{-|+Prepend an element.+-}+cons :: a -> Acc a -> Acc a+cons a =+  \ case+    TreeAcc tree ->+      TreeAcc (BinTree1.Branch (BinTree1.Leaf a) tree)+    EmptyAcc ->+      TreeAcc (BinTree1.Leaf a)++{-|+Extract the first element.++The produced accumulator will lack the extracted element+and will have the underlying tree rebalanced towards the beginning.+This means that calling 'uncons' on it will be \(\mathcal{O}(1)\) and+'unsnoc' will be \(\mathcal{O}(n)\).+-}+uncons :: Acc a -> Maybe (a, Acc a)+uncons =+  \ case+    TreeAcc tree ->+      case tree of+        BinTree1.Branch l r ->+          case BinTree1.unconsTo r l of+            (res, newTree) ->+              Just (res, TreeAcc newTree)+        BinTree1.Leaf res ->+          Just (res, EmptyAcc)+    EmptyAcc ->+      Nothing++{-|+Append an element.+-}+snoc :: a -> Acc a -> Acc a+snoc a =+  \ case+    TreeAcc tree ->+      TreeAcc (BinTree1.Branch tree (BinTree1.Leaf a))+    EmptyAcc ->+      TreeAcc (BinTree1.Leaf a)++{-|+Extract the last element.++The produced accumulator will lack the extracted element+and will have the underlying tree rebalanced towards the end.+This means that calling 'unsnoc' on it will be \(\mathcal{O}(1)\) and+'uncons' will be \(\mathcal{O}(n)\).+-}+unsnoc :: Acc a -> Maybe (a, Acc a)+unsnoc =+  \ case+    TreeAcc tree ->+      case tree of+        BinTree1.Branch l r ->+          case BinTree1.unsnocTo l r of+            (res, newTree) ->+              Just (res, TreeAcc newTree)+        BinTree1.Leaf res ->+          Just (res, EmptyAcc)+    EmptyAcc ->+      Nothing

@@ -8,12 +8,17 @@   foldMap',   foldr,   foldr',+  foldl,   foldl',   traverse,+  uncons,+  unconsTo,+  unsnoc,+  unsnocTo, ) where -import Acc.Prelude hiding (ap, foldM, foldl', foldr, foldr', foldMap, foldMap', traverse)+import Acc.Prelude hiding (ap, foldM, foldl, foldl', foldr, foldr', foldMap, foldMap', traverse) import qualified Acc.Prelude as Prelude  @@ -68,6 +73,22 @@     Leaf c -> foldr' step (step c acc) a     Branch c d -> foldrOnBranch' step acc (Branch a c) d +foldl :: (b -> a -> b) -> b -> BinTree1 a -> b+foldl step acc =+  \ case+    Branch a b ->+      foldlOnBranch step acc a b+    Leaf a ->+      step acc a++foldlOnBranch :: (b -> a -> b) -> b -> BinTree1 a -> BinTree1 a -> b+foldlOnBranch step acc a b =+  case b of+    Leaf c ->+      step (foldl step acc a) c+    Branch c d ->+      foldlOnBranch step acc (Branch a c) d+ foldl' :: (b -> a -> b) -> b -> BinTree1 a -> b foldl' step !acc =   \ case@@ -152,3 +173,35 @@   \ case     b : c -> fromList1To (Branch leftTree (Leaf a)) b c     _ -> Branch leftTree (Leaf a)++uncons :: BinTree1 a -> (a, Maybe (BinTree1 a))+uncons =+  \ case+    Branch l r ->+      fmap Just (unconsTo r l)+    Leaf a ->+      (a, Nothing)++unconsTo :: BinTree1 a -> BinTree1 a -> (a, BinTree1 a)+unconsTo buff =+  \ case+    Branch l r ->+      unconsTo (Branch r buff) l+    Leaf a ->+      (a, buff)++unsnoc :: BinTree1 a -> (a, Maybe (BinTree1 a))+unsnoc =+  \ case+    Branch l r ->+      fmap Just (unsnocTo l r)+    Leaf a ->+      (a, Nothing)++unsnocTo :: BinTree1 a -> BinTree1 a -> (a, BinTree1 a)+unsnocTo buff =+  \ case+    Branch l r ->+      unsnocTo (Branch l buff) r+    Leaf a ->+      (a, buff)

@@ -25,6 +25,11 @@           toList acc'         in list === list'     ,+    testProperty "foldl" $+      \ (acc :: Acc Int) ->+        foldl (flip (:)) [] acc ===+        foldl (flip (:)) [] (toList acc)+    ,     testProperty "foldl'" $       \ (acc :: Acc Int) ->         foldl' (flip (:)) [] acc ===