acc 0.2.0.1 → 0.2.0.2
raw patch · 9 files changed
+204/−103 lines, 9 filesdep +criteriondep −QuickCheckdep −gaugedep −tasty-hunitdep ~deepseqdep ~rerebasedep ~semigroupoidssetup-changedPVP: minor bump suggested
API additions: PVP suggests at least a minor version bump
Dependencies added: criterion
Dependencies removed: QuickCheck, gauge, tasty-hunit
Dependency ranges changed: deepseq, rerebase, semigroupoids
API changes (from Hackage documentation)
+ Acc: unsnoc :: Acc a -> Maybe (a, Acc a)
Files
- README.md +13/−13
- Setup.hs +0/−2
- acc.cabal +161/−44
- bench/Main.hs +4/−5
- library/Acc.hs +3/−3
- library/Acc/NeAcc.hs +0/−1
- library/Acc/NeAcc/Def.hs +19/−27
- library/Acc/Prelude.hs +0/−2
- test/Main.hs +4/−6
README.md view
@@ -5,25 +5,25 @@ A great basis for implementing many custom monoids, most notably of the Builder pattern. -It shines with its Monoid instance,+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.+Most notably linked 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.+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+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)+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.@@ -45,7 +45,7 @@ sequence 27.15 μs ``` -_No List here because it will blow up the memory._+_No list here because it will blow up the memory._ ### Construction from a list of 1000 elements @@ -84,7 +84,7 @@ 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)+- 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)
− Setup.hs
@@ -1,2 +0,0 @@-import Distribution.Simple-main = defaultMain
acc.cabal view
@@ -1,6 +1,7 @@-name: acc-version: 0.2.0.1-synopsis: Sequence optimized for monoidal construction and folding+cabal-version: 3.0+name: acc+version: 0.2.0.2+synopsis: Sequence optimized for monoidal construction and folding description: Data structure intended for accumulating a sequence of elements for later traversal or folding.@@ -10,66 +11,182 @@ 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-bug-reports: https://github.com/nikita-volkov/acc/issues-author: Nikita Volkov <nikita.y.volkov@mail.ru>-maintainer: Nikita Volkov <nikita.y.volkov@mail.ru>-copyright: (c) 2020 Nikita Volkov-license: MIT-license-file: LICENSE-build-type: Simple-cabal-version: >=1.10++homepage: https://github.com/nikita-volkov/acc+bug-reports: https://github.com/nikita-volkov/acc/issues+author: Nikita Volkov <nikita.y.volkov@mail.ru>+maintainer: Nikita Volkov <nikita.y.volkov@mail.ru>+copyright: (c) 2020 Nikita Volkov+license: MIT+license-file: LICENSE extra-source-files: bench-results README.md source-repository head- type: git+ type: git location: git://github.com/nikita-volkov/acc.git library- hs-source-dirs: library- default-extensions: BangPatterns, ConstraintKinds, DataKinds, DefaultSignatures, DeriveDataTypeable, DeriveFoldable, DeriveFunctor, DeriveGeneric, DeriveTraversable, EmptyDataDecls, FlexibleContexts, FlexibleInstances, FunctionalDependencies, GADTs, GeneralizedNewtypeDeriving, InstanceSigs, LambdaCase, LiberalTypeSynonyms, MagicHash, MultiParamTypeClasses, MultiWayIf, NoImplicitPrelude, NoMonomorphismRestriction, OverloadedStrings, PatternGuards, ParallelListComp, QuasiQuotes, RankNTypes, RecordWildCards, ScopedTypeVariables, StandaloneDeriving, StrictData, TemplateHaskell, TupleSections, TypeApplications, TypeFamilies, TypeOperators, UnboxedTuples, ViewPatterns- default-language: Haskell2010+ hs-source-dirs: library+ default-extensions:+ NoImplicitPrelude+ NoMonomorphismRestriction+ BangPatterns+ ConstraintKinds+ DataKinds+ DefaultSignatures+ DeriveDataTypeable+ DeriveFoldable+ DeriveFunctor+ DeriveGeneric+ DeriveTraversable+ EmptyDataDecls+ FlexibleContexts+ FlexibleInstances+ FunctionalDependencies+ GADTs+ GeneralizedNewtypeDeriving+ InstanceSigs+ LambdaCase+ LiberalTypeSynonyms+ MagicHash+ MultiParamTypeClasses+ MultiWayIf+ OverloadedStrings+ ParallelListComp+ PatternGuards+ QuasiQuotes+ RankNTypes+ RecordWildCards+ ScopedTypeVariables+ StandaloneDeriving+ StrictData+ TemplateHaskell+ TupleSections+ TypeApplications+ TypeFamilies+ TypeOperators+ UnboxedTuples+ ViewPatterns++ default-language: Haskell2010 exposed-modules: Acc Acc.NeAcc+ other-modules: Acc.NeAcc.Def Acc.Prelude+ build-depends:- base >=4.13 && <5,- deepseq >=1.4 && <1.5,- semigroupoids >=5.3 && <6+ base >=4.13 && <5+ , deepseq >=1.4 && <2+ , semigroupoids >=5.3 && <7 benchmark bench- type: exitcode-stdio-1.0- hs-source-dirs: bench- main-is: Main.hs- default-extensions: BangPatterns, ConstraintKinds, DataKinds, DefaultSignatures, DeriveDataTypeable, DeriveFoldable, DeriveFunctor, DeriveGeneric, DeriveTraversable, EmptyDataDecls, FlexibleContexts, FlexibleInstances, FunctionalDependencies, GADTs, GeneralizedNewtypeDeriving, InstanceSigs, LambdaCase, LiberalTypeSynonyms, MagicHash, MultiParamTypeClasses, MultiWayIf, NoImplicitPrelude, NoMonomorphismRestriction, OverloadedStrings, PatternGuards, ParallelListComp, QuasiQuotes, RankNTypes, RecordWildCards, ScopedTypeVariables, StandaloneDeriving, StrictData, TemplateHaskell, TupleSections, TypeApplications, TypeFamilies, TypeOperators, UnboxedTuples, ViewPatterns- default-language: Haskell2010+ type: exitcode-stdio-1.0+ hs-source-dirs: bench+ main-is: Main.hs+ default-extensions:+ NoImplicitPrelude+ NoMonomorphismRestriction+ BangPatterns+ ConstraintKinds+ DataKinds+ DefaultSignatures+ DeriveDataTypeable+ DeriveFoldable+ DeriveFunctor+ DeriveGeneric+ DeriveTraversable+ EmptyDataDecls+ FlexibleContexts+ FlexibleInstances+ FunctionalDependencies+ GADTs+ GeneralizedNewtypeDeriving+ InstanceSigs+ LambdaCase+ LiberalTypeSynonyms+ MagicHash+ MultiParamTypeClasses+ MultiWayIf+ OverloadedStrings+ ParallelListComp+ PatternGuards+ QuasiQuotes+ RankNTypes+ RecordWildCards+ ScopedTypeVariables+ StandaloneDeriving+ StrictData+ TemplateHaskell+ TupleSections+ TypeApplications+ TypeFamilies+ TypeOperators+ UnboxedTuples+ ViewPatterns++ default-language: Haskell2010 ghc-options:- -O2- -threaded- "-with-rtsopts=-N"- -rtsopts- -funbox-strict-fields+ -O2 -threaded -with-rtsopts=-N -rtsopts -funbox-strict-fields+ build-depends:- acc,- gauge >=0.2.5 && <0.3,- rerebase >=1.9 && <2+ acc+ , criterion >=1.6 && <2+ , rerebase >=1.19 && <2 test-suite test- type: exitcode-stdio-1.0- hs-source-dirs: test- default-extensions: BangPatterns, ConstraintKinds, DataKinds, DefaultSignatures, DeriveDataTypeable, DeriveFoldable, DeriveFunctor, DeriveGeneric, DeriveTraversable, EmptyDataDecls, FlexibleContexts, FlexibleInstances, FunctionalDependencies, GADTs, GeneralizedNewtypeDeriving, InstanceSigs, LambdaCase, LiberalTypeSynonyms, MagicHash, MultiParamTypeClasses, MultiWayIf, NoImplicitPrelude, NoMonomorphismRestriction, OverloadedStrings, PatternGuards, ParallelListComp, QuasiQuotes, RankNTypes, RecordWildCards, ScopedTypeVariables, StandaloneDeriving, StrictData, TemplateHaskell, TupleSections, TypeApplications, TypeFamilies, TypeOperators, UnboxedTuples, ViewPatterns- default-language: Haskell2010- main-is: Main.hs+ type: exitcode-stdio-1.0+ hs-source-dirs: test+ default-extensions:+ NoImplicitPrelude+ NoMonomorphismRestriction+ BangPatterns+ ConstraintKinds+ DataKinds+ DefaultSignatures+ DeriveDataTypeable+ DeriveFoldable+ DeriveFunctor+ DeriveGeneric+ DeriveTraversable+ EmptyDataDecls+ FlexibleContexts+ FlexibleInstances+ FunctionalDependencies+ GADTs+ GeneralizedNewtypeDeriving+ InstanceSigs+ LambdaCase+ LiberalTypeSynonyms+ MagicHash+ MultiParamTypeClasses+ MultiWayIf+ OverloadedStrings+ ParallelListComp+ PatternGuards+ QuasiQuotes+ RankNTypes+ RecordWildCards+ ScopedTypeVariables+ StandaloneDeriving+ StrictData+ TemplateHaskell+ TupleSections+ TypeApplications+ TypeFamilies+ TypeOperators+ UnboxedTuples+ ViewPatterns++ default-language: Haskell2010+ main-is: Main.hs build-depends:- acc,- QuickCheck >=2.8.1 && <3,- quickcheck-instances >=0.3.11 && <0.4,- rerebase >=1.9 && <2,- tasty >=0.12 && <2,- tasty-hunit >=0.9 && <0.11,- tasty-quickcheck >=0.9 && <0.11+ acc+ , quickcheck-instances >=0.3.11 && <0.4+ , rerebase >=1.9 && <2+ , tasty >=0.12 && <2+ , tasty-quickcheck >=0.9 && <0.11
bench/Main.hs view
@@ -2,13 +2,12 @@ import qualified Acc import qualified Data.DList as DList-import qualified Data.Foldable as Foldable import qualified Data.Sequence as Sequence-import qualified Data.Vector as Vector-import Gauge-import Gauge.Main+import Criterion+import Criterion.Main import Prelude +main :: IO () main = defaultMain [ bgroup "sum" $@@ -148,4 +147,4 @@ take amount sizesByMagnitude <&> \size -> bgroup (show size) (benchmarks size) sizesByMagnitude :: [Int]-sizesByMagnitude = [0 ..] <&> \magnitude -> 10 ^ magnitude+sizesByMagnitude = [0 :: Int ..] <&> \magnitude -> 10 ^ magnitude
library/Acc.hs view
@@ -4,6 +4,7 @@ cons, snoc, uncons,+ unsnoc, toNonEmpty, toNeAcc, enumFromTo,@@ -13,7 +14,6 @@ import qualified Acc.NeAcc as NeAcc import qualified Acc.NeAcc.Def as NeAcc import Acc.Prelude hiding (enumFromTo, toNonEmpty)-import qualified Data.Foldable as Foldable import qualified Data.Semigroup.Foldable as Foldable1 -- |@@ -43,7 +43,7 @@ = EmptyAcc | TreeAcc !(NeAcc.NeAcc a) -instance NFData a => NFData (Acc a) where+instance (NFData a) => NFData (Acc a) where rnf = \case TreeAcc tree -> rnf tree EmptyAcc -> ()@@ -165,7 +165,7 @@ _ -> [] -instance Show a => Show (Acc a) where+instance (Show a) => Show (Acc a) where show = show . toList
library/Acc/NeAcc.hs view
@@ -4,4 +4,3 @@ where import Acc.NeAcc.Def-import Acc.Prelude
library/Acc/NeAcc/Def.hs view
@@ -11,7 +11,6 @@ where import Acc.Prelude hiding (foldM)-import qualified Acc.Prelude as Prelude -- | -- Non-empty accumulator.@@ -21,11 +20,11 @@ = Leaf a | Branch !(NeAcc a) !(NeAcc a) -instance Show a => Show (NeAcc a) where+instance (Show a) => Show (NeAcc a) where show = show . toList -instance NFData a => NFData (NeAcc a) where+instance (NFData a) => NFData (NeAcc a) where rnf = \case Leaf a -> rnf a Branch l r -> seq (rnf l) (rnf r)@@ -65,21 +64,14 @@ instance Foldable NeAcc where {-# INLINEABLE [0] foldr #-} foldr :: (a -> b -> b) -> b -> NeAcc a -> b- foldr step acc =- peel []+ foldr step =+ go [] where- peel layers =- \case- Leaf a ->- step a (unpeel layers)- Branch l r ->- peel (r : layers) l- unpeel =- \case- h : t ->- peel t h- _ ->- acc+ go stack next = \case+ Branch l r -> go (r : stack) next l+ Leaf a -> step a $ case stack of+ tree : stack -> go stack next tree+ [] -> next {-# INLINE [0] foldr' #-} foldr' :: (a -> b -> b) -> b -> NeAcc a -> b@@ -127,7 +119,7 @@ _ -> step acc leaf {-# INLINE [0] foldMap #-}- foldMap :: Monoid m => (a -> m) -> NeAcc a -> m+ foldMap :: (Monoid m) => (a -> m) -> NeAcc a -> m foldMap map = peel where@@ -145,16 +137,16 @@ map a <> peel buff {-# INLINE [0] foldMap' #-}- foldMap' :: Monoid m => (a -> m) -> NeAcc a -> m+ foldMap' :: (Monoid m) => (a -> m) -> NeAcc a -> m foldMap' = foldMapTo' mempty where- foldMapTo' :: Monoid m => m -> (a -> m) -> NeAcc a -> m+ foldMapTo' :: (Monoid m) => m -> (a -> m) -> NeAcc a -> m foldMapTo' !acc map = \case Branch a b -> foldMapToOnBranch' acc map a b Leaf a -> acc <> map a- foldMapToOnBranch' :: Monoid m => m -> (a -> m) -> NeAcc a -> NeAcc a -> m+ foldMapToOnBranch' :: (Monoid m) => m -> (a -> m) -> NeAcc a -> NeAcc a -> m foldMapToOnBranch' acc map a b = case a of Leaf c -> foldMapTo' (acc <> map c) map b@@ -162,7 +154,7 @@ instance Traversable NeAcc where {-# INLINE [0] traverse #-}- traverse :: Applicative f => (a -> f b) -> NeAcc a -> f (NeAcc b)+ traverse :: (Applicative f) => (a -> f b) -> NeAcc a -> f (NeAcc b) traverse map = \case Branch a b ->@@ -170,7 +162,7 @@ Leaf a -> Leaf <$> map a where- traverseOnBranch :: Applicative f => (a -> f b) -> NeAcc a -> NeAcc a -> f (NeAcc b)+ traverseOnBranch :: (Applicative f) => (a -> f b) -> NeAcc a -> NeAcc a -> f (NeAcc b) traverseOnBranch map a b = case a of Leaf c ->@@ -180,7 +172,7 @@ instance Foldable1 NeAcc where {-# INLINE [0] fold1 #-}- fold1 :: Semigroup m => NeAcc m -> m+ fold1 :: (Semigroup m) => NeAcc m -> m fold1 = \case Branch l r ->@@ -189,7 +181,7 @@ a {-# INLINE [0] foldMap1 #-}- foldMap1 :: Semigroup m => (a -> m) -> NeAcc a -> m+ foldMap1 :: (Semigroup m) => (a -> m) -> NeAcc a -> m foldMap1 f = \case Branch l r ->@@ -250,13 +242,13 @@ Leaf a -> cont a r -foldM :: Monad m => (a -> b -> m a) -> a -> NeAcc b -> m a+foldM :: (Monad m) => (a -> b -> m a) -> a -> NeAcc b -> m a foldM step !acc = \case Branch a b -> foldMOnBranch step acc a b Leaf a -> step acc a where- foldMOnBranch :: Monad m => (a -> b -> m a) -> a -> NeAcc b -> NeAcc b -> m a+ foldMOnBranch :: (Monad m) => (a -> b -> m a) -> a -> NeAcc b -> NeAcc b -> m a foldMOnBranch step acc a b = case a of Leaf c -> step acc c >>= \acc' -> foldM step acc' b
library/Acc/Prelude.hs view
@@ -28,7 +28,6 @@ import Data.Function as Exports hiding (id, (.)) import Data.Functor as Exports import Data.Functor.Alt as Exports hiding (many, optional, some)-import Data.Functor.Apply as Exports import Data.Functor.Compose as Exports import Data.IORef as Exports import Data.Int as Exports@@ -69,7 +68,6 @@ import System.Mem as Exports import System.Mem.StableName as Exports import System.Timeout as Exports-import Text.ParserCombinators.ReadP as Exports (ReadP, ReadS, readP_to_S, readS_to_P) import Text.ParserCombinators.ReadPrec as Exports (ReadPrec, readP_to_Prec, readPrec_to_P, readPrec_to_S, readS_to_Prec) import Text.Printf as Exports (hPrintf, printf) import Text.Read as Exports (Read (..), readEither, readMaybe)
test/Main.hs view
@@ -1,16 +1,14 @@+{-# OPTIONS_GHC -Wno-orphans #-} module Main where import Acc import qualified Data.List.NonEmpty as NonEmpty-import GHC.Exts (fromList)-import qualified Test.QuickCheck as QuickCheck-import Test.QuickCheck.Instances+import Test.QuickCheck.Instances () import Test.Tasty-import Test.Tasty.HUnit import Test.Tasty.QuickCheck-import Test.Tasty.Runners import Prelude hiding (assert) +main :: IO () main = defaultMain $ testGroup@@ -55,7 +53,7 @@ === NonEmpty.nonEmpty (toList acc) ] -instance Arbitrary a => Arbitrary (Acc a) where+instance (Arbitrary a) => Arbitrary (Acc a) where arbitrary = accGen arbitrary