foldl 1.4.5 → 1.4.6

raw patch · 7 files changed

+190/−18 lines, 7 filesdep +doctestdep ~basedep ~profunctorsPVP: major bump suggested

API removals or changes: PVP suggests a major version bump

Dependencies added: doctest

Dependency ranges changed: base, profunctors

API changes (from Hackage documentation)

Files

• CHANGELOG.md +4/−0
• README.md +1/−1
• bench/benchmarks.hs +34/−0
• foldl.cabal +15/−6
• src/Control/Foldl.hs +108/−7
• src/Control/Scanl.hs +24/−4
• test/doctest.hs +4/−0

@@ -1,3 +1,7 @@+1.4.6++* Add `nest`/`predropWhile`/`drop`/`dropM`+ 1.4.5  * Increase upper bound on `containers`

@@ -1,4 +1,4 @@-# `foldl` v1.4.5+# `foldl`  Use this `foldl` library when you want to compute multiple folds over a collection in one pass over the data without space leaks.

@@ -1,3 +1,5 @@+{-# LANGUAGE BangPatterns #-}+ module Main (main) where  import Control.Foldl hiding (map)@@ -5,6 +7,7 @@ import qualified Data.List import Prelude hiding (length, sum) import qualified Prelude+import qualified Data.Foldable as Foldable  main :: IO () main = defaultMain@@ -36,5 +39,36 @@             , bench "Prelude.length" .                 whnf Prelude.length             ]+        , bgroup "sumAndLength" $ map ($ ns)+            [ bench "naive sumAndLength" .+                nf sumAndLength+            , bench "foldl' sumAndLength" .+                nf sumAndLength'+            , bench "strict pair sumAndLength" .+                nf sumAndLength_Pair+            , bench "foldl sumAndLength" .+                nf sumAndLength_foldl+            ]         ]   ]+++sumAndLength :: Num a => [a] -> (a, Int)+sumAndLength xs = (Prelude.sum xs, Prelude.length xs)++sumAndLength' :: Num a => [a] -> (a, Int)+sumAndLength' xs = Foldable.foldl' step (0, 0) xs+  where+    step (x, y) n = (x + n, y + 1)++data Pair a b = Pair !a !b++sumAndLength_Pair :: Num a => [a] -> (a, Int)+sumAndLength_Pair xs = done (Foldable.foldl' step (Pair 0 0) xs)+  where+    step (Pair x y) n = Pair (x + n) (y + 1)++    done (Pair x y) = (x, y)++sumAndLength_foldl :: Num a => [a] -> (a, Int)+sumAndLength_foldl = fold ((,) <$> sum <*> length)

@@ -1,5 +1,5 @@ Name: foldl-Version: 1.4.5+Version: 1.4.6 Cabal-Version: >=1.8.0.2 Build-Type: Simple License: BSD3@@ -27,16 +27,16 @@         base         >= 4.8      && < 5   ,         bytestring   >= 0.9.2.1  && < 0.11,         mwc-random   >= 0.13.1.0 && < 0.15,-        primitive                   < 0.7 ,+        primitive                   < 0.8 ,         text         >= 0.11.2.0 && < 1.3 ,         transformers >= 0.2.0.0  && < 0.6 ,         vector       >= 0.7      && < 0.13,         containers   >= 0.5.0.0  && < 0.7 ,         unordered-containers        < 0.3 ,-        hashable                    < 1.3 ,+        hashable                    < 1.4 ,         contravariant               < 1.6 ,-        semigroups   >= 0.17     && < 1.19,-        profunctors                 < 5.4 ,+        semigroups   >= 0.17     && < 1.20,+        profunctors                 < 5.6 ,         semigroupoids >= 1.0     && < 5.4 ,         comonad      >= 4.0      && < 6   ,         vector-builder              < 0.4@@ -58,4 +58,13 @@         base,         criterion,         foldl-    GHC-Options: -O2 -Wall -rtsopts+    GHC-Options: -O2 -Wall -rtsopts -rtsopts -with-rtsopts=-T++Test-Suite doctest+    Type: exitcode-stdio-1.0+    HS-Source-Dirs: test+    Main-Is: doctest.hs+    Build-Depends:+        base,+        doctest >= 0.16+    GHC-Options: -threaded

@@ -118,6 +118,9 @@     , premapM     , prefilter     , prefilterM+    , predropWhile+    , drop+    , dropM     , Handler     , handles     , foldOver@@ -130,6 +133,7 @@     , groupBy     , either     , eitherM+    , nest      -- * Re-exports     -- $reexports@@ -158,6 +162,7 @@ import Data.Vector.Generic.Mutable (MVector) import Data.Hashable (Hashable) import Data.Traversable+import Numeric.Natural (Natural) import System.Random.MWC (GenIO, createSystemRandom, uniformR) import Prelude hiding     ( head@@ -177,6 +182,7 @@     , lookup     , map     , either+    , drop     )  import qualified Data.Foldable               as F@@ -192,6 +198,22 @@ import qualified VectorBuilder.Vector import qualified Data.Semigroupoid +{- $setup++>>> import qualified Control.Foldl as L++>>> _2 f (x, y) = fmap (\i -> (x, i)) (f y)++>>> :{+>>> _Just = let maybeEither Nothing = Left Nothing+>>>             maybeEither (Just x) = Right x+>>>         in Control.Foldl.Optics.prism Just maybeEither+>>> :}++>>> both f (x, y) = (,) <$> f x <*> f y++-}+ {-| Efficient representation of a left fold that preserves the fold's step     function, initial accumulator, and extraction function @@ -493,7 +515,11 @@         k $! x' {-# INLINE foldM #-} --- | Convert a strict left 'Fold' into a scan+{-| Convert a strict left 'Fold' into a scan++    >>> L.scan L.length [1..5]+    [0,1,2,3,4,5]+-} scan :: Fold a b -> [a] -> [b] scan (Fold step begin done) as = foldr cons nil as begin   where@@ -504,6 +530,9 @@ {-| Convert a `Fold` into a prescan for any `Traversable` type      \"Prescan\" means that the last element of the scan is not included++    >>> L.prescan L.length [1..5]+    [0,1,2,3,4] -} prescan :: Traversable t => Fold a b -> t a -> t b prescan (Fold step begin done) as = bs@@ -518,6 +547,9 @@ {-| Convert a `Fold` into a postscan for any `Traversable` type      \"Postscan\" means that the first element of the scan is not included++    >>> L.postscan L.length [1..5]+    [1,2,3,4,5] -} postscan :: Traversable t => Fold a b -> t a -> t b postscan (Fold step begin done) as = bs@@ -1092,12 +1124,12 @@  {-| @(premap f folder)@ returns a new 'Fold' where f is applied at each step -> fold (premap f folder) list = fold folder (map f list)+> fold (premap f folder) list = fold folder (List.map f list) ->>> fold (premap Sum mconcat) [1..10]+>>> fold (premap Sum L.mconcat) [1..10] Sum {getSum = 55} ->>> fold mconcat (map Sum [1..10])+>>> fold L.mconcat (List.map Sum [1..10]) Sum {getSum = 55}  > premap id = id@@ -1151,7 +1183,7 @@     step' x a = if f a then step x a else x {-# INLINABLE prefilter #-} -{-| @(prefilterM f folder)@ returns a new 'Fold' where the folder's input is used+{-| @(prefilterM f folder)@ returns a new 'FoldM' where the folder's input is used   only when the input satisfies a monadic predicate f.  > foldM (prefilterM p folder) list = foldM folder (filter p list)@@ -1164,6 +1196,66 @@       if use then step x a else return x {-# INLINABLE prefilterM #-} +{-| Transforms a 'Fold' into one which ignores elements+    until they stop satisfying a predicate++> fold (predropWhile p folder) list = fold folder (dropWhile p list)++>>> fold (predropWhile (>5) Control.Foldl.sum) [10,9,5,9]+14+-}+predropWhile :: (a -> Bool) -> Fold a r -> Fold a r+predropWhile f (Fold step begin done) = Fold step' begin' done'+  where+    step' (Pair dropping x) a = if dropping && f a+      then Pair True x+      else Pair False (step x a)+    begin' = Pair True begin+    done' (Pair _ state) = done state+{-# INLINABLE predropWhile #-}++{-| @(drop n folder)@ returns a new 'Fold' that ignores the first @n@ inputs but+otherwise behaves the same as the original fold.++> fold (drop n folder) list = fold folder (Data.List.genericDrop n list)++>>> L.fold (L.drop 3 L.sum) [10, 20, 30, 1, 2, 3]+6++>>> L.fold (L.drop 10 L.sum) [10, 20, 30, 1, 2, 3]+0+-}++drop :: Natural -> Fold a b -> Fold a b+drop n (Fold step begin done) = Fold step' begin' done'+  where+    begin'          = (n, begin)+    step' (0,  s) x = (0, step s x)+    step' (n', s) _ = (n' - 1, s)+    done' (_,  s)   = done s+{-# INLINABLE drop #-}++{-| @(dropM n folder)@ returns a new 'FoldM' that ignores the first @n@ inputs but+otherwise behaves the same as the original fold.++> foldM (dropM n folder) list = foldM folder (Data.List.genericDrop n list)++>>> L.foldM (L.dropM 3 (L.generalize L.sum)) [10, 20, 30, 1, 2, 3]+6++>>> L.foldM (L.dropM 10 (L.generalize L.sum)) [10, 20, 30, 1, 2, 3]+0+-}++dropM :: Monad m => Natural -> FoldM m a b -> FoldM m a b+dropM n (FoldM step begin done) = FoldM step' begin' done'+  where+    begin'          = fmap (\s  -> (n, s))  begin+    step' (0,  s) x = fmap (\s' -> (0, s')) (step s x)+    step' (n', s) _ = return (n' - 1, s)+    done' (_,  s)   = done s+{-# INLINABLE dropM #-}+ {-| A handler for the upstream input of a `Fold`      Any lens, traversal, or prism will type-check as a `Handler`@@ -1188,7 +1280,7 @@ >>> fold (handles (filtered even) sum) [1..10] 30 ->>> fold (handles _2 mconcat) [(1,"Hello "),(2,"World"),(3,"!")]+>>> fold (handles _2 L.mconcat) [(1,"Hello "),(2,"World"),(3,"!")] "Hello World!"  > handles id = id@@ -1303,7 +1395,7 @@ >>> fold (handles (filtered even) sum) [1..10] 30 ->>> foldM (handlesM (filtered even) (mapM_ print)) [1..10]+>>> foldM (handlesM (filtered even) (L.mapM_ print)) [1..10] 2 4 6@@ -1339,6 +1431,15 @@ eitherM :: Monad m => FoldM m a1 b1 -> FoldM m a2 b2 -> FoldM m (Either a1 a2) (b1, b2) eitherM l r = (,) <$> handlesM _Left l <*> handlesM _Right r {-# INLINABLE eitherM #-}++{-| Nest a fold in an applicative.+-}+nest :: Applicative f => Fold a b -> Fold (f a) (f b)+nest (Fold s i e) =+    Fold (\xs as -> liftA2 s xs as)+         (pure i)+         (\xs -> fmap e xs)+{-# INLINABLE nest #-}  {- $reexports     @Control.Monad.Primitive@ re-exports the 'PrimMonad' type class

@@ -1,12 +1,32 @@-{-| This module provides efficient and streaming left map-with-accumulator that you can combine-    using 'Applicative' style.+{-| This module provides efficient and streaming left map-with-accumulator that+    you can combine using 'Applicative' style.      Import this module qualified to avoid clashing with the Prelude:  >>> import qualified Control.Scanl as SL -    Use 'scan' to apply a 'Fold' to a list (or other 'Traversable' structures) from left to right,-    and 'scanr' to do so from right to left.+    Use 'scan' to apply a 'Fold' to a list (or other 'Traversable' structures)+    from left to right, and 'scanr' to do so from right to left.++    Note that the `Scan` type does not supersede the `Fold` type nor does the+    `Fold` type supersede the `Scan` type.  Each type has a unique advantage.++    For example, `Scan`s can be chained end-to-end:++    > (>>>) :: Scan a b -> Scan b c -> Scan a c++    In other words, `Scan` is an instance of the `Category` typeclass.++    `Fold`s cannot be chained end-to-end++    Vice versa, `Fold`s can produce a result even when fed no input:++    > extract :: Fold a b -> b++    In other words, `Fold` is an instance of the `Comonad` typeclass.++    A `Scan`s cannot produce any output until provided with at least one+    input. -}  {-# LANGUAGE CPP                       #-}

@@ -0,0 +1,4 @@+import Test.DocTest++main :: IO ()+main = doctest ["-isrc", "src/Control/Foldl.hs", "src/Control/Scanl.hs"]