acc 0.2 → 0.2.0.1
raw patch · 6 files changed
+382/−44 lines, 6 filesPVP: minor bump suggested
API additions: PVP suggests at least a minor version bump
API changes (from Hackage documentation)
+ Acc: fromReverseList :: [a] -> Acc a
Files
- README.md +90/−0
- acc.cabal +4/−1
- bench-results +188/−0
- bench/Main.hs +77/−9
- library/Acc.hs +17/−6
- library/Acc/NeAcc/Def.hs +6/−28
+ README.md view
@@ -0,0 +1,90 @@+# Summary++Data structure intended for accumulating a sequence of elements+for later traversal or folding.+A great basis for implementing many custom monoids,+most notably of the Builder pattern.++It shines with its Monoid instance,+which relieves the user from caring about from which side to append.+This is important because,+different data-structures exhibit very different performance depending on that.+Most notably List.+Acc on the other hand is neutral and performs well in all scenarios.++For such purposes it is common to use Seq or DList.+The benchmark results below show that Acc is a better fit.++# Benchmark results++These benchmarks compare the performance of acc vs. various other structures+as used for aggregation with intent of reduction.++In other words a two-step process of the following structure is measured as a whole:++1. Construct the measured data-structure using a particular method (cons, snoc, fromList)+2. Fold the data-structure into a final result (sum, length)++Following are the highlights from the benchmark results+grouped by the method of construction of the datastructure.++### Consing 1000 elements++```+acc 12.40 μs+list 18.70 μs+dlist 43.95 μs+sequence 27.54 μs+```++### Snocing 1000 elements++```+acc 17.02 μs+dlist 38.93 μs+sequence 27.15 μs+```++_No List here because it will blow up the memory._++### Construction from a list of 1000 elements++```+acc 13.27 μs+list 12.97 μs+dlist 27.57 μs+sequence 10.70 μs+```++### Appending chunks of 1000 elements 1000 times from left++```+acc 4.256 ms+list 553.7 ms+dlist 315.9 ms+sequence 10.05 ms+```++### Appending chunks of 1000 elements 1000 times from right++```+acc 4.305 ms+list 5.126 s+dlist 360.4 ms+sequence 7.209 ms+```++---++For complete results see [the dump](bench-results).++_Executed on an AWS c6i.2xlarge instance running Ubuntu._++## Conclusions++Given the preconditions of the benchmarks, the following can be concluded:++- Neither List or DList are suitable as monoidal structures, due to exponential performance degradation on appends from both sides+- Snocing and even consing Acc is better than all alternatives+- Acc performs better than Seq on both left- and right-appends (2-3x)+- Seq gets constructed from list faster than Acc (1.5x)
acc.cabal view
@@ -1,5 +1,5 @@ name: acc-version: 0.2+version: 0.2.0.1 synopsis: Sequence optimized for monoidal construction and folding description: Data structure intended for accumulating a sequence of elements@@ -19,6 +19,9 @@ license-file: LICENSE build-type: Simple cabal-version: >=1.10+extra-source-files:+ bench-results+ README.md source-repository head type: git
+ bench-results view
@@ -0,0 +1,188 @@+sum/cons/1/acc mean 44.27 ns ( +- 3.573 ns )+sum/cons/1/list mean 52.89 ns ( +- 709.0 ps )+sum/cons/1/dlist mean 111.9 ns ( +- 3.742 ns )+sum/cons/1/sequence mean 51.01 ns ( +- 183.2 ps )+sum/cons/10/acc mean 147.0 ns ( +- 417.8 ps )+sum/cons/10/list mean 181.8 ns ( +- 867.9 ps )+sum/cons/10/dlist mean 395.5 ns ( +- 3.609 ns )+sum/cons/10/sequence mean 207.6 ns ( +- 4.848 ns )+sum/cons/100/acc mean 1.208 μs ( +- 13.07 ns )+sum/cons/100/list mean 1.677 μs ( +- 9.983 ns )+sum/cons/100/dlist mean 3.179 μs ( +- 21.53 ns )+sum/cons/100/sequence mean 2.398 μs ( +- 50.80 ns )+sum/cons/1000/acc mean 12.40 μs ( +- 94.21 ns )+sum/cons/1000/list mean 18.70 μs ( +- 268.1 ns )+sum/cons/1000/dlist mean 43.95 μs ( +- 368.9 ns )+sum/cons/1000/sequence mean 27.54 μs ( +- 1.316 μs )+sum/snoc/1/acc mean 44.33 ns ( +- 124.2 ps )+sum/snoc/1/dlist mean 103.8 ns ( +- 809.8 ps )+sum/snoc/1/sequence mean 50.69 ns ( +- 346.4 ps )+sum/snoc/10/acc mean 163.3 ns ( +- 9.502 ns )+sum/snoc/10/dlist mean 343.9 ns ( +- 1.732 ns )+sum/snoc/10/sequence mean 203.9 ns ( +- 1.370 ns )+sum/snoc/100/acc mean 1.505 μs ( +- 8.679 ns )+sum/snoc/100/dlist mean 2.871 μs ( +- 32.63 ns )+sum/snoc/100/sequence mean 2.427 μs ( +- 20.72 ns )+sum/snoc/1000/acc mean 17.02 μs ( +- 183.3 ns )+sum/snoc/1000/dlist mean 38.93 μs ( +- 462.3 ns )+sum/snoc/1000/sequence mean 27.15 μs ( +- 444.2 ns )+sum/fromList/1/acc mean 41.77 ns ( +- 399.8 ps )+sum/fromList/1/list mean 39.01 ns ( +- 319.3 ps )+sum/fromList/1/dlist mean 87.06 ns ( +- 1.264 ns )+sum/fromList/1/sequence mean 37.22 ns ( +- 227.1 ps )+sum/fromList/10/acc mean 149.5 ns ( +- 17.93 ns )+sum/fromList/10/list mean 120.1 ns ( +- 919.1 ps )+sum/fromList/10/dlist mean 240.4 ns ( +- 1.824 ns )+sum/fromList/10/sequence mean 92.71 ns ( +- 656.2 ps )+sum/fromList/100/acc mean 1.247 μs ( +- 90.38 ns )+sum/fromList/100/list mean 1.194 μs ( +- 21.30 ns )+sum/fromList/100/dlist mean 1.834 μs ( +- 11.37 ns )+sum/fromList/100/sequence mean 894.5 ns ( +- 3.701 ns )+sum/fromList/1000/acc mean 13.27 μs ( +- 64.45 ns )+sum/fromList/1000/list mean 12.97 μs ( +- 170.1 ns )+sum/fromList/1000/dlist mean 27.57 μs ( +- 247.5 ns )+sum/fromList/1000/sequence mean 10.70 μs ( +- 123.5 ns )+sum/append/left/1/1/acc mean 35.97 ns ( +- 121.2 ps )+sum/append/left/1/1/list mean 62.45 ns ( +- 272.2 ps )+sum/append/left/1/1/dlist mean 105.4 ns ( +- 865.0 ps )+sum/append/left/1/1/sequence mean 43.22 ns ( +- 205.5 ps )+sum/append/left/1/10/acc mean 191.1 ns ( +- 1.043 ns )+sum/append/left/1/10/list mean 415.8 ns ( +- 2.104 ns )+sum/append/left/1/10/dlist mean 628.1 ns ( +- 5.932 ns )+sum/append/left/1/10/sequence mean 413.5 ns ( +- 1.709 ns )+sum/append/left/1/100/acc mean 1.792 μs ( +- 25.78 ns )+sum/append/left/1/100/list mean 4.119 μs ( +- 42.74 ns )+sum/append/left/1/100/dlist mean 5.884 μs ( +- 36.89 ns )+sum/append/left/1/100/sequence mean 4.822 μs ( +- 31.43 ns )+sum/append/left/1/1000/acc mean 18.33 μs ( +- 545.3 ns )+sum/append/left/1/1000/list mean 69.98 μs ( +- 1.293 μs )+sum/append/left/1/1000/dlist mean 86.36 μs ( +- 2.736 μs )+sum/append/left/1/1000/sequence mean 54.75 μs ( +- 272.2 ns )+sum/append/left/10/1/acc mean 66.08 ns ( +- 855.7 ps )+sum/append/left/10/1/list mean 198.0 ns ( +- 1.870 ns )+sum/append/left/10/1/dlist mean 257.7 ns ( +- 869.3 ps )+sum/append/left/10/1/sequence mean 81.51 ns ( +- 218.7 ps )+sum/append/left/10/10/acc mean 498.4 ns ( +- 1.440 ns )+sum/append/left/10/10/list mean 1.955 μs ( +- 16.94 ns )+sum/append/left/10/10/dlist mean 2.286 μs ( +- 137.1 ns )+sum/append/left/10/10/sequence mean 1.296 μs ( +- 6.863 ns )+sum/append/left/10/100/acc mean 4.807 μs ( +- 23.52 ns )+sum/append/left/10/100/list mean 31.14 μs ( +- 423.2 ns )+sum/append/left/10/100/dlist mean 32.48 μs ( +- 350.5 ns )+sum/append/left/10/100/sequence mean 15.17 μs ( +- 110.0 ns )+sum/append/left/10/1000/acc mean 48.59 μs ( +- 1.120 μs )+sum/append/left/10/1000/list mean 564.1 μs ( +- 50.59 μs )+sum/append/left/10/1000/dlist mean 524.4 μs ( +- 46.34 μs )+sum/append/left/10/1000/sequence mean 199.2 μs ( +- 921.1 ns )+sum/append/left/100/1/acc mean 365.5 ns ( +- 3.128 ns )+sum/append/left/100/1/list mean 1.753 μs ( +- 19.51 ns )+sum/append/left/100/1/dlist mean 1.852 μs ( +- 65.25 ns )+sum/append/left/100/1/sequence mean 559.4 ns ( +- 2.290 ns )+sum/append/left/100/10/acc mean 3.476 μs ( +- 20.41 ns )+sum/append/left/100/10/list mean 30.40 μs ( +- 6.729 μs )+sum/append/left/100/10/dlist mean 32.27 μs ( +- 528.0 ns )+sum/append/left/100/10/sequence mean 8.068 μs ( +- 8.548 ns )+sum/append/left/100/100/acc mean 34.92 μs ( +- 389.4 ns )+sum/append/left/100/100/list mean 819.3 μs ( +- 382.3 μs )+sum/append/left/100/100/dlist mean 603.5 μs ( +- 178.1 μs )+sum/append/left/100/100/sequence mean 122.4 μs ( +- 65.51 μs )+sum/append/left/100/1000/acc mean 351.5 μs ( +- 21.26 μs )+sum/append/left/100/1000/list mean 46.02 ms ( +- 9.988 ms )+sum/append/left/100/1000/dlist mean 20.05 ms ( +- 2.918 ms )+sum/append/left/100/1000/sequence mean 1.553 ms ( +- 1.077 ms )+sum/append/left/1000/1/acc mean 4.138 μs ( +- 83.44 ns )+sum/append/left/1000/1/list mean 44.38 μs ( +- 19.02 μs )+sum/append/left/1000/1/dlist mean 37.60 μs ( +- 12.52 μs )+sum/append/left/1000/1/sequence mean 13.45 μs ( +- 35.63 μs )+sum/append/left/1000/10/acc mean 34.12 μs ( +- 1.275 μs )+sum/append/left/1000/10/list mean 728.8 μs ( +- 337.6 μs )+sum/append/left/1000/10/dlist mean 681.9 μs ( +- 275.3 μs )+sum/append/left/1000/10/sequence mean 70.16 μs ( +- 16.57 μs )+sum/append/left/1000/100/acc mean 405.8 μs ( +- 13.34 μs )+sum/append/left/1000/100/list mean 48.14 ms ( +- 21.86 ms )+sum/append/left/1000/100/dlist mean 21.59 ms ( +- 3.849 ms )+sum/append/left/1000/100/sequence mean 741.6 μs ( +- 174.3 μs )+sum/append/left/1000/1000/acc mean 4.256 ms ( +- 241.8 μs )+sum/append/left/1000/1000/list mean 553.7 ms ( +- 46.81 ms )+sum/append/left/1000/1000/dlist mean 315.9 ms ( +- 24.05 ms )+sum/append/left/1000/1000/sequence mean 10.05 ms ( +- 5.712 ms )+sum/append/right/1/1/acc mean 67.70 ns ( +- 30.80 ns )+sum/append/right/1/1/list mean 67.06 ns ( +- 31.11 ns )+sum/append/right/1/1/dlist mean 192.3 ns ( +- 91.19 ns )+sum/append/right/1/1/sequence mean 67.56 ns ( +- 80.25 ns )+sum/append/right/1/10/acc mean 399.0 ns ( +- 338.4 ns )+sum/append/right/1/10/list mean 2.458 μs ( +- 3.916 μs )+sum/append/right/1/10/dlist mean 1.581 μs ( +- 2.157 μs )+sum/append/right/1/10/sequence mean 705.0 ns ( +- 292.5 ns )+sum/append/right/1/100/acc mean 2.764 μs ( +- 650.1 ns )+sum/append/right/1/100/list mean 141.7 μs ( +- 46.94 μs )+sum/append/right/1/100/dlist mean 9.531 μs ( +- 7.264 μs )+sum/append/right/1/100/sequence mean 7.380 μs ( +- 1.657 μs )+sum/append/right/1/1000/acc mean 27.99 μs ( +- 8.603 μs )+sum/append/right/1/1000/list mean 16.65 ms ( +- 8.541 ms )+sum/append/right/1/1000/dlist mean 121.3 μs ( +- 38.99 μs )+sum/append/right/1/1000/sequence mean 89.11 μs ( +- 33.58 μs )+sum/append/right/10/1/acc mean 90.50 ns ( +- 32.14 ns )+sum/append/right/10/1/list mean 265.4 ns ( +- 197.6 ns )+sum/append/right/10/1/dlist mean 448.2 ns ( +- 364.2 ns )+sum/append/right/10/1/sequence mean 79.49 ns ( +- 5.728 ns )+sum/append/right/10/10/acc mean 490.3 ns ( +- 1.691 ns )+sum/append/right/10/10/list mean 4.401 μs ( +- 76.30 ns )+sum/append/right/10/10/dlist mean 2.204 μs ( +- 13.22 ns )+sum/append/right/10/10/sequence mean 1.287 μs ( +- 15.71 ns )+sum/append/right/10/100/acc mean 4.709 μs ( +- 33.88 ns )+sum/append/right/10/100/list mean 464.6 μs ( +- 11.24 μs )+sum/append/right/10/100/dlist mean 33.91 μs ( +- 2.536 μs )+sum/append/right/10/100/sequence mean 15.30 μs ( +- 132.9 ns )+sum/append/right/10/1000/acc mean 47.88 μs ( +- 735.6 ns )+sum/append/right/10/1000/list mean 53.76 ms ( +- 1.138 ms )+sum/append/right/10/1000/dlist mean 512.0 μs ( +- 49.67 μs )+sum/append/right/10/1000/sequence mean 199.6 μs ( +- 698.3 ns )+sum/append/right/100/1/acc mean 360.4 ns ( +- 3.055 ns )+sum/append/right/100/1/list mean 1.180 μs ( +- 6.591 ns )+sum/append/right/100/1/dlist mean 1.855 μs ( +- 21.17 ns )+sum/append/right/100/1/sequence mean 562.0 ns ( +- 2.761 ns )+sum/append/right/100/10/acc mean 3.431 μs ( +- 14.79 ns )+sum/append/right/100/10/list mean 52.70 μs ( +- 488.1 ns )+sum/append/right/100/10/dlist mean 28.37 μs ( +- 541.3 ns )+sum/append/right/100/10/sequence mean 7.363 μs ( +- 74.71 ns )+sum/append/right/100/100/acc mean 34.06 μs ( +- 89.74 ns )+sum/append/right/100/100/list mean 4.775 ms ( +- 225.0 μs )+sum/append/right/100/100/dlist mean 416.1 μs ( +- 7.272 μs )+sum/append/right/100/100/sequence mean 80.12 μs ( +- 534.4 ns )+sum/append/right/100/1000/acc mean 342.3 μs ( +- 3.529 μs )+sum/append/right/100/1000/list mean 516.1 ms ( +- 3.341 ms )+sum/append/right/100/1000/dlist mean 18.03 ms ( +- 864.3 μs )+sum/append/right/100/1000/sequence mean 1.120 ms ( +- 75.73 μs )+sum/append/right/1000/1/acc mean 4.076 μs ( +- 39.54 ns )+sum/append/right/1000/1/list mean 22.16 μs ( +- 268.7 ns )+sum/append/right/1000/1/dlist mean 27.94 μs ( +- 450.0 ns )+sum/append/right/1000/1/sequence mean 5.783 μs ( +- 50.68 ns )+sum/append/right/1000/10/acc mean 33.62 μs ( +- 151.1 ns )+sum/append/right/1000/10/list mean 1.046 ms ( +- 90.84 μs )+sum/append/right/1000/10/dlist mean 450.8 μs ( +- 45.64 μs )+sum/append/right/1000/10/sequence mean 60.83 μs ( +- 262.3 ns )+sum/append/right/1000/100/acc mean 387.1 μs ( +- 29.71 μs )+sum/append/right/1000/100/list mean 64.56 ms ( +- 1.640 ms )+sum/append/right/1000/100/dlist mean 17.79 ms ( +- 329.9 μs )+sum/append/right/1000/100/sequence mean 636.2 μs ( +- 3.351 μs )+sum/append/right/1000/1000/acc mean 4.305 ms ( +- 114.3 μs )+sum/append/right/1000/1000/list mean 5.126 s ( +- 23.33 ms )+sum/append/right/1000/1000/dlist mean 360.4 ms ( +- 10.62 ms )+sum/append/right/1000/1000/sequence mean 7.209 ms ( +- 110.3 μs )+length/cons/1/acc mean 41.51 ns ( +- 349.4 ps )+length/cons/1/list mean 36.96 ns ( +- 219.8 ps )+length/cons/1/dlist mean 72.30 ns ( +- 305.6 ps )+length/cons/1/sequence mean 38.03 ns ( +- 714.3 ps )+length/cons/10/acc mean 140.0 ns ( +- 1.176 ns )+length/cons/10/list mean 92.01 ns ( +- 447.1 ps )+length/cons/10/dlist mean 251.4 ns ( +- 2.626 ns )+length/cons/10/sequence mean 148.1 ns ( +- 3.281 ns )+length/cons/100/acc mean 1.233 μs ( +- 13.49 ns )+length/cons/100/list mean 753.6 ns ( +- 2.182 ns )+length/cons/100/dlist mean 2.177 μs ( +- 147.5 ns )+length/cons/100/sequence mean 1.828 μs ( +- 203.0 ns )+length/cons/1000/acc mean 12.64 μs ( +- 37.79 ns )+length/cons/1000/list mean 7.923 μs ( +- 347.9 ns )+length/cons/1000/dlist mean 22.19 μs ( +- 819.1 ns )+length/cons/1000/sequence mean 21.56 μs ( +- 394.8 ns )
bench/Main.hs view
@@ -12,7 +12,7 @@ main = defaultMain [ bgroup "sum" $- [ onIntListByMagBench "cons" 3 $ \input ->+ [ onIntListByMagBench "cons" 4 $ \input -> [ reduceConstructBench "acc" input sum $ foldl' (flip Acc.cons) mempty, reduceConstructBench "list" input sum $@@ -22,7 +22,7 @@ reduceConstructBench "sequence" input sum $ foldl' (flip (Sequence.<|)) mempty ],- onIntListByMagBench "snoc" 3 $ \input ->+ onIntListByMagBench "snoc" 4 $ \input -> [ reduceConstructBench "acc" input sum $ foldl' (flip Acc.snoc) mempty, reduceConstructBench "dlist" input sum $@@ -30,15 +30,33 @@ reduceConstructBench "sequence" input sum $ foldl' (Sequence.|>) mempty ],- onIntListByMagBench "fromList" 3 $ \input ->+ onIntListByMagBench "fromList" 4 $ \input -> [ reduceConstructBench "acc" input sum $ fromList @(Acc.Acc Int), reduceConstructBench "list" input sum $ id, reduceConstructBench "dlist" input sum $ DList.fromList, reduceConstructBench "sequence" input sum $ Sequence.fromList+ ],+ bgroup "append" $+ [ bgroup "left" $+ onIntListByMagBenchList 4 $ \input ->+ onSizeByMagBenchList 4 $ \appendAmount ->+ [ appendLeftBench "acc" appendAmount (fromList @(Acc.Acc Int) input) sum,+ appendLeftBench "list" appendAmount input sum,+ appendLeftBench "dlist" appendAmount (DList.fromList input) sum,+ appendLeftBench "sequence" appendAmount (Sequence.fromList input) sum+ ],+ bgroup "right" $+ onIntListByMagBenchList 4 $ \input ->+ onSizeByMagBenchList 4 $ \appendAmount ->+ [ appendRightBench "acc" appendAmount (fromList @(Acc.Acc Int) input) sum,+ appendRightBench "list" appendAmount input sum,+ appendRightBench "dlist" appendAmount (DList.fromList input) sum,+ appendRightBench "sequence" appendAmount (Sequence.fromList input) sum+ ] ] ], bgroup "length" $- [ onIntListByMagBench "cons" 3 $ \input ->+ [ onIntListByMagBench "cons" 4 $ \input -> [ reduceConstructBench "acc" input length $ foldl' (flip Acc.cons) mempty, reduceConstructBench "list" input length $@@ -56,7 +74,7 @@ -- and reduction, ensuring that they don't get fused. {-# NOINLINE reduceConstructBench #-} reduceConstructBench ::- NFData reduction =>+ (NFData reduction, NFData a) => -- | Benchmark name. String -> -- | Input sample.@@ -67,8 +85,50 @@ ([a] -> intermediate) -> Benchmark reduceConstructBench name list reducer constructor =- bench name $ nf (reducer . constructor) list+ bench name $ nf (reducer . constructor) $!! list +-- |+-- Construct a benchmark that measures appending from the left side of a+-- preconstructed chunk of an intermediate representation.+{-# NOINLINE appendLeftBench #-}+appendLeftBench ::+ (NFData reduction, NFData intermediate, Monoid intermediate) =>+ -- | Benchmark name.+ String ->+ -- | How many appends.+ Int ->+ -- | Sample intermediate representation.+ intermediate ->+ -- | Reducer of the intermediate representation.+ (intermediate -> reduction) ->+ Benchmark+appendLeftBench name appendAmount chunk reducer =+ let input =+ replicate appendAmount chunk+ in reduceConstructBench name input reducer $+ foldl' (flip (<>)) mempty++-- |+-- Construct a benchmark that measures appending from the right side of a+-- preconstructed chunk of an intermediate representation.+{-# NOINLINE appendRightBench #-}+appendRightBench ::+ (NFData reduction, NFData intermediate, Monoid intermediate) =>+ -- | Benchmark name.+ String ->+ -- | How many appends.+ Int ->+ -- | Sample intermediate representation.+ intermediate ->+ -- | Reducer of the intermediate representation.+ (intermediate -> reduction) ->+ Benchmark+appendRightBench name appendAmount chunk reducer =+ let input =+ replicate appendAmount chunk+ in reduceConstructBench name input reducer $+ foldl' (<>) mempty+ onIntListByMagBench :: String -> Int -> ([Int] -> [Benchmark]) -> Benchmark onIntListByMagBench groupName amount benchmarks = onSizeByMagBench groupName amount $ \size ->@@ -76,8 +136,16 @@ onSizeByMagBench :: String -> Int -> (Int -> [Benchmark]) -> Benchmark onSizeByMagBench groupName amount benchmarks =- bgroup groupName $- take amount sizesByMagnitude <&> \size -> bgroup (show size) (benchmarks size)+ bgroup groupName $ onSizeByMagBenchList amount benchmarks +onIntListByMagBenchList :: Int -> ([Int] -> [Benchmark]) -> [Benchmark]+onIntListByMagBenchList amount benchmarks =+ onSizeByMagBenchList amount $ \size ->+ benchmarks $!! enumFromTo 0 size++onSizeByMagBenchList :: Int -> (Int -> [Benchmark]) -> [Benchmark]+onSizeByMagBenchList amount benchmarks =+ take amount sizesByMagnitude <&> \size -> bgroup (show size) (benchmarks size)+ sizesByMagnitude :: [Int]-sizesByMagnitude = [0 ..] <&> \magnitude -> 10 ^ (2 * magnitude)+sizesByMagnitude = [0 ..] <&> \magnitude -> 10 ^ magnitude
library/Acc.hs view
@@ -1,5 +1,6 @@ module Acc ( Acc,+ fromReverseList, cons, snoc, uncons,@@ -22,6 +23,9 @@ -- -- Appending and prepending is always \(\mathcal{O}(1)\). --+-- Another way to think about this data-structure+-- is as of a strict list with fast append and snoc.+-- -- To produce a single element 'Acc' use 'pure'. -- To produce a multielement 'Acc' use 'fromList'. -- To combine use '<|>' or '<>' and other 'Alternative' and 'Monoid'-related utils.@@ -152,10 +156,7 @@ instance IsList (Acc a) where type Item (Acc a) = a {-# INLINE [0] fromList #-}- fromList list =- case reverse list of- a : b -> TreeAcc (NeAcc.prependReverseList b (NeAcc.Leaf a))- _ -> EmptyAcc+ fromList = fromReverseList . reverse {-# INLINE [0] toList #-} toList = \case@@ -184,8 +185,7 @@ -- -- 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)\).+-- This means that calling 'uncons' on it will be \(\mathcal{O}(1)\). {-# INLINE uncons #-} uncons :: Acc a -> Maybe (a, Acc a) uncons =@@ -260,3 +260,14 @@ if from <= to then TreeAcc (NeAcc.appendEnumFromTo (succ from) to (NeAcc.Leaf from)) else EmptyAcc++-- |+-- Construct from list in reverse order.+--+-- This is more efficient than 'fromList',+-- which is actually defined as @fromReverseList . 'reverse'@.+{-# INLINE fromReverseList #-}+fromReverseList :: [a] -> Acc a+fromReverseList = \case+ a : b -> TreeAcc (NeAcc.prependReverseList b (NeAcc.Leaf a))+ _ -> EmptyAcc
library/Acc/NeAcc/Def.hs view
@@ -118,20 +118,13 @@ {-# INLINE [0] foldl' #-} foldl' :: (b -> a -> b) -> b -> NeAcc a -> b- foldl' step !acc =- \case- Branch a b ->- foldlOnBranch' step acc a b- Leaf a ->- step acc a+ foldl' step = build [] where- foldlOnBranch' :: (b -> a -> b) -> b -> NeAcc a -> NeAcc a -> b- foldlOnBranch' step acc a b =- case a of- Leaf c ->- foldl' step (step acc c) b- Branch c d ->- foldlOnBranch' step acc c (Branch d b)+ build stack !acc = \case+ Branch l r -> build (r : stack) acc l+ Leaf leaf -> case stack of+ tree : stack -> build stack (step acc leaf) tree+ _ -> step acc leaf {-# INLINE [0] foldMap #-} foldMap :: Monoid m => (a -> m) -> NeAcc a -> m@@ -166,21 +159,6 @@ case a of Leaf c -> foldMapTo' (acc <> map c) map b Branch c d -> foldMapToOnBranch' acc map c (Branch d b)-- {-# INLINE length #-}- length :: NeAcc a -> Int- length =- \case- Leaf _ -> 1- Branch l r -> go 0 l r- where- go n l r =- case l of- Leaf _ -> case succ n of- n -> case r of- Branch l r -> go n l r- Leaf _ -> succ n- Branch l lr -> go n l (Branch lr r) instance Traversable NeAcc where {-# INLINE [0] traverse #-}