foldl 1.0.1 → 1.0.2
raw patch · 4 files changed
+126/−63 lines, 4 filesdep +primitivedep +vector
Dependencies added: primitive, vector
Files
- foldl.cabal +4/−2
- src/Control/Foldl.hs +102/−59
- src/Control/Foldl/ByteString.hs +10/−1
- src/Control/Foldl/Text.hs +10/−1
foldl.cabal view
@@ -1,5 +1,5 @@ Name: foldl-Version: 1.0.1+Version: 1.0.2 Cabal-Version: >=1.8.0.2 Build-Type: Simple License: BSD3@@ -23,7 +23,9 @@ Build-Depends: base >= 4 && < 5 , bytestring >= 0.9.2.1 && < 0.11,- text >= 0.11.2.0 && < 1.1+ primitive < 0.6 ,+ text >= 0.11.2.0 && < 1.1 ,+ vector >= 0.7 && < 0.11 Exposed-Modules: Control.Foldl, Control.Foldl.ByteString,
src/Control/Foldl.hs view
@@ -24,12 +24,6 @@ >>> L.fold ((,) <$> L.minimum <*> L.maximum) [1..10000000] (Just 1,Just 10000000) - You can also unpack the `Fold` type if you want to extract the individual- components of combined folds for use with your own customized folding- utilities:--> case ((/) <$> L.sum <*> L.genericLength) of-> L.Foldl step begin done -> ... -} {-# LANGUAGE ExistentialQuantification, RankNTypes #-}@@ -37,14 +31,11 @@ module Control.Foldl ( -- * Fold Types Fold(..)- , fold , FoldM(..)- , foldM - -- * Utilities- -- $utilities- , purely- , impurely+ -- * Folding+ , fold+ , foldM -- * Folds , mconcat@@ -72,16 +63,32 @@ , genericLength , genericIndex + -- * Container folds+ , list+ , vector++ -- * Utilities+ -- $utilities+ , purely+ , impurely+ , premap+ -- * Re-exports -- $reexports+ , module Control.Monad.Primitive , module Data.Foldable+ , module Data.Vector.Generic ) where import Control.Applicative (Applicative(pure, (<*>)),liftA2) import Control.Foldl.Internal (Maybe'(..), lazy, Either'(..), hush)+import Control.Monad.Primitive (PrimMonad) import Data.Foldable (Foldable) import qualified Data.Foldable as F import Data.Monoid (Monoid(mempty, mappend))+import Data.Vector.Generic (Vector)+import qualified Data.Vector.Generic as V+import qualified Data.Vector.Generic.Mutable as M import Prelude hiding ( head , last@@ -107,17 +114,6 @@ -} data Fold a b = forall x . Fold (x -> a -> x) x (x -> b) -{-| Apply a strict left 'Fold' to a 'Foldable' container-- Much slower than 'fold' on lists because 'Foldable' operations currently do- not trigger @build/foldr@ fusion--}-fold :: (Foldable f) => Fold a b -> f a -> b-fold (Fold step begin done) as = F.foldr step' done as begin- where- step' x k z = k $! step z x-{-# INLINE fold #-}- data Pair a b = Pair !a !b instance Functor (Fold a) where@@ -176,6 +172,13 @@ mappend = liftA2 mappend {-# INLINABLE mappend #-} +-- | Apply a strict left 'Fold' to a 'Foldable' container+fold :: (Foldable f) => Fold a b -> f a -> b+fold (Fold step begin done) as = F.foldr step' done as begin+ where+ step' x k z = k $! step z x+{-# INLINE fold #-}+ -- | Like 'fold', but monadic foldM :: (Foldable f, Monad m) => FoldM m a b -> f a -> m b foldM (FoldM step begin done) as0 = do@@ -187,41 +190,6 @@ k $! x' {-# INLINE foldM #-} -{- $utilities- 'purely' and 'impurely' allow you to write folds compatible with the @foldl@- library without incurring a @foldl@ dependency. Write your fold to accept- three parameters corresponding to the step function, initial- accumulator, and extraction function and then users can upgrade your- function to accept a 'Fold' or 'FoldM' using the 'purely' or 'impurely'- combinators.-- For example, the @pipes@ library implements a @foldM@ function in- @Pipes.Prelude@ with the following type:--> foldM-> :: (Monad m)-> => (x -> a -> m x) -> m x -> (x -> m b) -> Producer a m () -> m b-- @foldM@ is set up so that you can wrap it with 'impurely' to accept a- 'FoldM' instead:--> impurely foldM :: (Monad m) => FoldM m a b -> Producer a m () -> m b--}---- | Upgrade a fold to accept the 'Fold' type-purely :: (forall x . (x -> a -> x) -> x -> (x -> b) -> r) -> Fold a b -> r-purely f (Fold step begin done) = f step begin done-{-# INLINABLE purely #-}---- | Upgrade a monadic fold to accept the 'FoldM' type-impurely- :: (Monad m)- => (forall x . (x -> a -> m x) -> m x -> (x -> m b) -> r)- -> FoldM m a b- -> r-impurely f (FoldM step begin done) = f step begin done-{-# INLINABLE impurely #-}- -- | Fold all values within a container using 'mappend' and 'mempty' mconcat :: (Monoid a) => Fold a a mconcat = Fold mappend mempty id@@ -387,6 +355,81 @@ Right' a -> Just a {-# INLINABLE genericIndex #-} +-- | Fold all values into a list+list :: Fold a [a]+list = Fold (\x a -> x . (a:)) id ($ [])+{-# INLINABLE list #-}++maxChunkSize :: Int+maxChunkSize = 8 * 1024 * 1024++-- | Fold all values into a vector+vector :: (PrimMonad m, Vector v a) => FoldM m a (v a)+vector = FoldM step begin done+ where+ begin = do+ mv <- M.unsafeNew 10+ return (Pair mv 0)+ step (Pair mv idx) a = do+ let len = M.length mv+ mv' <- if (idx >= len)+ then M.unsafeGrow mv (min len maxChunkSize)+ else return mv+ M.unsafeWrite mv' idx a+ return (Pair mv' (idx + 1))+ done (Pair mv idx) = do+ v <- V.unsafeFreeze mv+ return (V.unsafeTake idx v)+{-# INLINABLE vector #-}++{- $utilities+ 'purely' and 'impurely' allow you to write folds compatible with the @foldl@+ library without incurring a @foldl@ dependency. Write your fold to accept+ three parameters corresponding to the step function, initial+ accumulator, and extraction function and then users can upgrade your+ function to accept a 'Fold' or 'FoldM' using the 'purely' or 'impurely'+ combinators.++ For example, the @pipes@ library implements a @foldM@ function in+ @Pipes.Prelude@ with the following type:++> foldM+> :: (Monad m)+> => (x -> a -> m x) -> m x -> (x -> m b) -> Producer a m () -> m b++ @foldM@ is set up so that you can wrap it with 'impurely' to accept a+ 'FoldM' instead:++> impurely foldM :: (Monad m) => FoldM m a b -> Producer a m () -> m b+-}++-- | Upgrade a fold to accept the 'Fold' type+purely :: (forall x . (x -> a -> x) -> x -> (x -> b) -> r) -> Fold a b -> r+purely f (Fold step begin done) = f step begin done+{-# INLINABLE purely #-}++-- | Upgrade a monadic fold to accept the 'FoldM' type+impurely+ :: (Monad m)+ => (forall x . (x -> a -> m x) -> m x -> (x -> m b) -> r)+ -> FoldM m a b+ -> r+impurely f (FoldM step begin done) = f step begin done+{-# INLINABLE impurely #-}++{-| @(premap f folder)@ returns a new 'Fold' where f is applied at each step+ @fold (premap f folder) list@ == @fold folder (map f list)@+-}+premap :: (a -> b) -> Fold b r -> Fold a r+premap f (Fold step begin done) = Fold step' begin done+ where+ step' x = step x . f+{-# INLINABLE premap #-}+ {- $reexports- @Data.Foldable@ re-exports the 'Foldable' type+ @Control.Monad.Primitive@ re-exports the 'PrimMonad' type class++ @Data.Foldable@ re-exports the 'Foldable' type class++ @Data.Vector.Generic@ re-exports the 'Vector' type class -}
src/Control/Foldl/ByteString.hs view
@@ -1,8 +1,11 @@ -- | Folds for byte streams module Control.Foldl.ByteString (+ -- * Folding+ fold+ -- * Folds- head+ , head , last , null , length@@ -29,10 +32,16 @@ import qualified Control.Foldl as L import Data.ByteString (ByteString) import qualified Data.ByteString as B+import qualified Data.ByteString.Lazy.Internal as Lazy import qualified Data.ByteString.Unsafe as BU import Data.Word (Word8) import Prelude hiding ( head, last, null, length, any, all, maximum, minimum, elem, notElem )++-- | Appply a strict left 'Fold' to a lazy bytestring+fold :: Fold ByteString a -> Lazy.ByteString -> a+fold (L.Fold step begin done) as = done (Lazy.foldlChunks step begin as)+{-# INLINABLE fold #-} {-| Get the first byte of a byte stream or return 'Nothing' if the stream is empty
src/Control/Foldl/Text.hs view
@@ -1,8 +1,11 @@ -- | Folds for text streams module Control.Foldl.Text (+ -- * Folding+ fold+ -- * Folds- head+ , head , last , null , length@@ -28,8 +31,14 @@ import qualified Control.Foldl as L import Data.Text (Text) import qualified Data.Text as T+import qualified Data.Text.Lazy as Lazy import Prelude hiding ( head, last, null, length, any, all, maximum, minimum, elem, notElem )++-- | Apply a strict left 'Fold' to lazy text+fold :: Fold Text a -> Lazy.Text -> a+fold (L.Fold step begin done) as = done (Lazy.foldlChunks step begin as)+{-# INLINABLE fold #-} {-| Get the first character of a text stream or return 'Nothing' if the stream is empty