-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/

-- | Composable, streaming, and efficient left folds
--   
--   This library provides strict left folds that stream in constant
--   memory, and you can combine folds using Applicative style to
--   derive new folds. Derived folds still traverse the container just once
--   and are often as efficient as hand-written folds.
@package foldl
@version 1.2.5

-- | This module provides efficient and streaming left folds that you can
--   combine using Applicative style.
--   
--   Import this module qualified to avoid clashing with the Prelude:
--   
--   
--   >>> import qualified Control.Foldl as L
--   
--   
--   Use fold to apply a Fold to a list:
--   
--   
--   >>> L.fold L.sum [1..100]
--   5050
--   
--   
--   Folds are Applicatives, so you can combine them using
--   Applicative combinators:
--   
--   
--   >>> import Control.Applicative
--   
--   >>> let average = (/) <$> L.sum <*> L.genericLength
--   
--   
--   Taking the sum, the sum of squares, ..., upto the sum of x^5
--   
--   
--   >>> import Data.Traversable
--   
--   >>> let powerSums = sequenceA [L.premap (^n) L.sum | n <- [1..5]]
--   
--   >>> L.fold powerSums [1..10]
--   [55,385,3025,25333,220825]
--   
--   
--   These combined folds will still traverse the list only once, streaming
--   efficiently over the list in constant space without space leaks:
--   
--   
--   >>> L.fold average [1..10000000]
--   5000000.5
--   
--   >>> L.fold ((,) <$> L.minimum <*> L.maximum) [1..10000000]
--   (Just 1,Just 10000000)
--   
--   
--   You might want to try enabling the -flate-dmd-anal flag when
--   compiling executables that use this library to further improve
--   performance.
module Control.Foldl

-- | Efficient representation of a left fold that preserves the fold's step
--   function, initial accumulator, and extraction function
--   
--   This allows the Applicative instance to assemble derived folds
--   that traverse the container only once
--   
--   A 'Fold a b' processes elements of type a and results in
--   a value of type b.
data Fold a b

-- | Fold   step   initial   extract
Fold :: (x -> a -> x) -> x -> (x -> b) -> Fold a b

-- | Like Fold, but monadic.
--   
--   A 'FoldM m a b' processes elements of type a and results
--   in a monadic value of type m b.
data FoldM m a b

-- | FoldM   step   initial   extract
FoldM :: (x -> a -> m x) -> (m x) -> (x -> m b) -> FoldM m a b

-- | Apply a strict left Fold to a Foldable container
fold :: Foldable f => Fold a b -> f a -> b

-- | Like fold, but monadic
foldM :: (Foldable f, Monad m) => FoldM m a b -> f a -> m b

-- | Convert a strict left Fold into a scan
scan :: Fold a b -> [a] -> [b]

-- | Convert a Fold into a prescan for any Traversable type
--   
--   "Prescan" means that the last element of the scan is not included
prescan :: Traversable t => Fold a b -> t a -> t b

-- | Convert a Fold into a postscan for any Traversable type
--   
--   "Postscan" means that the first element of the scan is not included
postscan :: Traversable t => Fold a b -> t a -> t b

-- | Fold all values within a container using mappend and
--   mempty
mconcat :: Monoid a => Fold a a

-- | Convert a "foldMap" to a Fold
foldMap :: Monoid w => (a -> w) -> (w -> b) -> Fold a b

-- | Get the first element of a container or return Nothing if the
--   container is empty
head :: Fold a (Maybe a)

-- | Get the last element of a container or return Nothing if the
--   container is empty
last :: Fold a (Maybe a)

-- | Get the last element of a container or return a default value if the
--   container is empty
lastDef :: a -> Fold a a

-- | Return the last N elements
lastN :: Int -> Fold a [a]

-- | Returns True if the container is empty, False otherwise
null :: Fold a Bool

-- | Return the length of the container
length :: Fold a Int

-- | Returns True if all elements are True, False
--   otherwise
and :: Fold Bool Bool

-- | Returns True if any element is True, False
--   otherwise
or :: Fold Bool Bool

-- | (all predicate) returns True if all elements satisfy
--   the predicate, False otherwise
all :: (a -> Bool) -> Fold a Bool

-- | (any predicate) returns True if any element satisfies
--   the predicate, False otherwise
any :: (a -> Bool) -> Fold a Bool

-- | Computes the sum of all elements
sum :: Num a => Fold a a

-- | Computes the product of all elements
product :: Num a => Fold a a

-- | Compute a numerically stable arithmetic mean of all elements
mean :: Fractional a => Fold a a

-- | Compute a numerically stable (population) variance over all elements
variance :: Fractional a => Fold a a

-- | Compute a numerically stable (population) standard deviation over all
--   elements
std :: Floating a => Fold a a

-- | Computes the maximum element
maximum :: Ord a => Fold a (Maybe a)

-- | Computes the maximum element with respect to the given comparison
--   function
maximumBy :: (a -> a -> Ordering) -> Fold a (Maybe a)

-- | Computes the minimum element
minimum :: Ord a => Fold a (Maybe a)

-- | Computes the minimum element with respect to the given comparison
--   function
minimumBy :: (a -> a -> Ordering) -> Fold a (Maybe a)

-- | (elem a) returns True if the container has an element
--   equal to a, False otherwise
elem :: Eq a => a -> Fold a Bool

-- | (notElem a) returns False if the container has an
--   element equal to a, True otherwise
notElem :: Eq a => a -> Fold a Bool

-- | (find predicate) returns the first element that satisfies the
--   predicate or Nothing if no element satisfies the predicate
find :: (a -> Bool) -> Fold a (Maybe a)

-- | (index n) returns the nth element of the container,
--   or Nothing if the container has an insufficient number of
--   elements
index :: Int -> Fold a (Maybe a)

-- | (lookup a) returns the element paired with the first matching
--   item, or Nothing if none matches
lookup :: Eq a => a -> Fold (a, b) (Maybe b)

-- | (elemIndex a) returns the index of the first element that
--   equals a, or Nothing if no element matches
elemIndex :: Eq a => a -> Fold a (Maybe Int)

-- | (findIndex predicate) returns the index of the first element
--   that satisfies the predicate, or Nothing if no element
--   satisfies the predicate
findIndex :: (a -> Bool) -> Fold a (Maybe Int)

-- | Pick a random element, using reservoir sampling
random :: FoldM IO a (Maybe a)

-- | Pick several random elements, using reservoir sampling
randomN :: Vector v a => Int -> FoldM IO a (Maybe (v a))

-- | Converts an effectful function to a fold. Specialized version of
--   sink.
mapM_ :: Monad m => (a -> m ()) -> FoldM m a ()

-- | Converts an effectful function to a fold
--   
--   
--   sink (f <> g) = sink f <> sink g -- if `(&lt;&gt;)` is commutative
--   sink mempty = mempty
--   
sink :: (Monoid w, Monad m) => (a -> m w) -> FoldM m a w

-- | Like length, except with a more general Num return value
genericLength :: Num b => Fold a b

-- | Like index, except with a more general Integral argument
genericIndex :: Integral i => i -> Fold a (Maybe a)

-- | Fold all values into a list
list :: Fold a [a]

-- | Fold all values into a list, in reverse order
revList :: Fold a [a]

-- | O(n log n). Fold values into a list with duplicates removed,
--   while preserving their first occurrences
nub :: Ord a => Fold a [a]

-- | O(n^2). Fold values into a list with duplicates removed, while
--   preserving their first occurrences
eqNub :: Eq a => Fold a [a]

-- | Fold values into a set
set :: Ord a => Fold a (Set a)

-- | Fold values into a hash-set
hashSet :: (Eq a, Hashable a) => Fold a (HashSet a)

-- | Fold pairs into a map.
map :: Ord a => Fold (a, b) (Map a b)

-- | Fold pairs into a hash-map.
hashMap :: (Eq a, Hashable a) => Fold (a, b) (HashMap a b)

-- | Fold all values into a vector
vector :: (PrimMonad m, Vector v a) => FoldM m a (v a)

-- | Upgrade a fold to accept the Fold type
purely :: (forall x. (x -> a -> x) -> x -> (x -> b) -> r) -> Fold a b -> r

-- | Upgrade a more traditional fold to accept the Fold type
purely_ :: (forall x. (x -> a -> x) -> x -> x) -> Fold a b -> b

-- | Upgrade a monadic fold to accept the FoldM type
impurely :: (forall x. (x -> a -> m x) -> m x -> (x -> m b) -> r) -> FoldM m a b -> r

-- | Upgrade a more traditional monadic fold to accept the FoldM
--   type
impurely_ :: Monad m => (forall x. (x -> a -> m x) -> m x -> m x) -> FoldM m a b -> m b

-- | Generalize a Fold to a FoldM
--   
--   
--   generalize (pure r) = pure r
--   
--   generalize (f <*> x) = generalize f <*> generalize x
--   
generalize :: Monad m => Fold a b -> FoldM m a b

-- | Simplify a pure FoldM to a Fold
--   
--   
--   simplify (pure r) = pure r
--   
--   simplify (f <*> x) = simplify f <*> simplify x
--   
simplify :: FoldM Identity a b -> Fold a b

-- | Shift a FoldM from one monad to another with a morphism such as
--   lift or liftIO; the effect is the same as
--   hoist.
hoists :: (forall x. m x -> n x) -> FoldM m a b -> FoldM n a b

-- | Allows to continue feeding a FoldM even after passing it to a
--   function that closes it.
--   
--   For pure Folds, this is provided by the Comonad
--   instance.
duplicateM :: Applicative m => FoldM m a b -> FoldM m a (FoldM m a b)

-- | _Fold1 step returns a new Fold using just a step
--   function that has the same type for the accumulator and the element.
--   The result type is the accumulator type wrapped in Maybe. The
--   initial accumulator is retrieved from the Foldable, the result
--   is None for empty containers.
_Fold1 :: (a -> a -> a) -> Fold a (Maybe a)

-- | (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 Sum mconcat) [1..10]
--   Sum {getSum = 55}
--   
--   
--   
--   >>> fold mconcat (map Sum [1..10])
--   Sum {getSum = 55}
--   
--   
--   
--   premap id = id
--   
--   premap (f . g) = premap g . premap f
--   
--   
--   
--   premap k (pure r) = pure r
--   
--   premap k (f <*> x) = premap k f <*> premap k x
--   
premap :: (a -> b) -> Fold b r -> Fold a r

-- | (premapM f folder) returns a new FoldM where f is
--   applied to each input element
--   
--   
--   foldM (premapM f folder) list = foldM folder (map f list)
--   
--   
--   
--   premapM id = id
--   
--   premapM (f . g) = premap g . premap f
--   
--   
--   
--   premapM k (pure r) = pure r
--   
--   premapM k (f <*> x) = premapM k f <*> premapM k x
--   
premapM :: (a -> b) -> FoldM m b r -> FoldM m a r

-- | A handler for the upstream input of a Fold
--   
--   Any lens, traversal, or prism will type-check as a Handler
type Handler a b = forall x. (b -> Const (Dual (Endo x)) b) -> a -> Const (Dual (Endo x)) a

-- | (handles t folder) transforms the input of a Fold
--   using a lens, traversal, or prism:
--   
--   
--   handles _1       :: Fold a r -> Fold (a, b) r
--   handles _Left    :: Fold a r -> Fold (Either a b) r
--   handles traverse :: Traversable t => Fold a r -> Fold (t a) r
--   handles folded   :: Foldable    t => Fold a r -> Fold (t a) r
--   
--   
--   
--   >>> fold (handles traverse sum) [[1..5],[6..10]]
--   55
--   
--   
--   
--   >>> fold (handles (traverse.traverse) sum) [[Nothing, Just 2, Just 7],[Just 13, Nothing, Just 20]]
--   42
--   
--   
--   
--   >>> fold (handles (filtered even) sum) [1..10]
--   30
--   
--   
--   
--   >>> fold (handles _2 mconcat) [(1,"Hello "),(2,"World"),(3,"!")]
--   "Hello World!"
--   
--   
--   
--   handles id = id
--   
--   handles (f . g) = handles f . handles g
--   
--   
--   
--   handles t (pure r) = pure r
--   
--   handles t (f <*> x) = handles t f <*> handles t x
--   
handles :: Handler a b -> Fold b r -> Fold a r

-- | (foldOver f folder xs) folds all values from a Lens,
--   Traversal, Prism or Fold with the given folder
--   
--   
--   >>> foldOver (_Just . both) L.sum (Just (2, 3))
--   5
--   
--   
--   
--   >>> foldOver (_Just . both) L.sum Nothing
--   0
--   
--   
--   
--   L.foldOver f folder xs == L.fold folder (xs^..f)
--   
--   
--   
--   L.foldOver (folded.f) folder == L.fold (handles f folder)
--   
--   
--   
--   L.foldOver folded == L.fold
--   
foldOver :: Handler s a -> Fold a b -> s -> b

-- | 
--   instance Monad m => Monoid (EndoM m a) where
--       mempty = EndoM return
--       mappend (EndoM f) (EndoM g) = EndoM (f <=< g)
--   
newtype EndoM m a
EndoM :: (a -> m a) -> EndoM m a
[appEndoM] :: EndoM m a -> a -> m a

-- | A Handler for the upstream input of FoldM
--   
--   Any lens, traversal, or prism will type-check as a HandlerM
type HandlerM m a b = forall x. (b -> Const (Dual (EndoM m x)) b) -> a -> Const (Dual (EndoM m x)) a

-- | (handlesM t folder) transforms the input of a FoldM
--   using a lens, traversal, or prism:
--   
--   
--   handlesM _1       :: FoldM m a r -> FoldM (a, b) r
--   handlesM _Left    :: FoldM m a r -> FoldM (Either a b) r
--   handlesM traverse :: Traversable t => FoldM m a r -> FoldM m (t a) r
--   handlesM folded   :: Foldable    t => FoldM m a r -> FoldM m (t a) r
--   
--   
--   handlesM obeys these laws:
--   
--   
--   handlesM id = id
--   
--   handlesM (f . g) = handlesM f . handlesM g
--   
--   
--   
--   handlesM t (pure r) = pure r
--   
--   handlesM t (f <*> x) = handlesM t f <*> handlesM t x
--   
handlesM :: HandlerM m a b -> FoldM m b r -> FoldM m a r

-- | (foldOverM f folder xs) folds all values from a Lens,
--   Traversal, Prism or Fold monadically with the given folder
--   
--   
--   L.foldOverM (folded.f) folder == L.foldM (handlesM f folder)
--   
--   
--   
--   L.foldOverM folded == L.foldM
--   
foldOverM :: Monad m => HandlerM m s a -> FoldM m a b -> s -> m b

-- | 
--   folded :: Foldable t => Fold (t a) a
--   
--   handles folded :: Foldable t => Fold a r -> Fold (t a) r
--   
folded :: (Contravariant f, Applicative f, Foldable t) => (a -> f a) -> (t a -> f (t a))

-- | 
--   >>> fold (handles (filtered even) sum) [1..10]
--   30
--   
--   
--   
--   >>> foldM (handlesM (filtered even) (mapM_ print)) [1..10]
--   2
--   4
--   6
--   8
--   10
--   
filtered :: Monoid m => (a -> Bool) -> (a -> m) -> a -> m
instance GHC.Base.Functor (Control.Foldl.Fold a)
instance Data.Profunctor.Unsafe.Profunctor Control.Foldl.Fold
instance Control.Comonad.Comonad (Control.Foldl.Fold a)
instance GHC.Base.Applicative (Control.Foldl.Fold a)
instance GHC.Base.Monoid b => GHC.Base.Monoid (Control.Foldl.Fold a b)
instance GHC.Num.Num b => GHC.Num.Num (Control.Foldl.Fold a b)
instance GHC.Real.Fractional b => GHC.Real.Fractional (Control.Foldl.Fold a b)
instance GHC.Float.Floating b => GHC.Float.Floating (Control.Foldl.Fold a b)
instance GHC.Base.Monad m => GHC.Base.Functor (Control.Foldl.FoldM m a)
instance GHC.Base.Monad m => GHC.Base.Applicative (Control.Foldl.FoldM m a)
instance GHC.Base.Monad m => Data.Profunctor.Unsafe.Profunctor (Control.Foldl.FoldM m)
instance (GHC.Base.Monoid b, GHC.Base.Monad m) => GHC.Base.Monoid (Control.Foldl.FoldM m a b)
instance (GHC.Base.Monad m, GHC.Num.Num b) => GHC.Num.Num (Control.Foldl.FoldM m a b)
instance (GHC.Base.Monad m, GHC.Real.Fractional b) => GHC.Real.Fractional (Control.Foldl.FoldM m a b)
instance (GHC.Base.Monad m, GHC.Float.Floating b) => GHC.Float.Floating (Control.Foldl.FoldM m a b)
instance GHC.Base.Monad m => GHC.Base.Monoid (Control.Foldl.EndoM m a)

-- | Folds for byte streams
module Control.Foldl.ByteString

-- | Apply a strict left Fold to a lazy bytestring
fold :: Fold ByteString a -> ByteString -> a

-- | Apply a strict monadic left FoldM to a lazy bytestring
foldM :: Monad m => FoldM m ByteString a -> ByteString -> m a

-- | Get the first byte of a byte stream or return Nothing if the
--   stream is empty
head :: Fold ByteString (Maybe Word8)

-- | Get the last byte of a byte stream or return Nothing if the
--   byte stream is empty
last :: Fold ByteString (Maybe Word8)

-- | Returns True if the byte stream is empty, False
--   otherwise
null :: Fold ByteString Bool

-- | Return the length of the byte stream in bytes
length :: Num n => Fold ByteString n

-- | (any predicate) returns True if any byte satisfies the
--   predicate, False otherwise
any :: (Word8 -> Bool) -> Fold ByteString Bool

-- | (all predicate) returns True if all bytes satisfy the
--   predicate, False otherwise
all :: (Word8 -> Bool) -> Fold ByteString Bool

-- | Computes the maximum byte
maximum :: Fold ByteString (Maybe Word8)

-- | Computes the minimum byte
minimum :: Fold ByteString (Maybe Word8)

-- | (elem w8) returns True if the byte stream has a byte
--   equal to w8, False otherwise
elem :: Word8 -> Fold ByteString Bool

-- | (notElem w8) returns False if the byte stream has a
--   byte equal to w8, True otherwise
notElem :: Word8 -> Fold ByteString Bool

-- | (find predicate) returns the first byte that satisfies the
--   predicate or Nothing if no byte satisfies the predicate
find :: (Word8 -> Bool) -> Fold ByteString (Maybe Word8)

-- | (index n) returns the nth byte of the byte stream,
--   or Nothing if the stream has an insufficient number of bytes
index :: Integral n => n -> Fold ByteString (Maybe Word8)

-- | (elemIndex w8) returns the index of the first byte that
--   equals w8, or Nothing if no byte matches
elemIndex :: Num n => Word8 -> Fold ByteString (Maybe n)

-- | (findIndex predicate) returns the index of the first byte
--   that satisfies the predicate, or Nothing if no byte satisfies
--   the predicate
findIndex :: Num n => (Word8 -> Bool) -> Fold ByteString (Maybe n)

-- | count w8 returns the number of times w8 appears
count :: Num n => Word8 -> Fold ByteString n

-- | Combine all the strict ByteString chunks to build a lazy
--   ByteString
lazy :: Fold ByteString ByteString

-- | Folds for text streams
module Control.Foldl.Text

-- | Apply a strict left Fold to lazy text
fold :: Fold Text a -> Text -> a

-- | Apply a strict monadic left FoldM to lazy text
foldM :: Monad m => FoldM m Text a -> Text -> m a

-- | Get the first character of a text stream or return Nothing if
--   the stream is empty
head :: Fold Text (Maybe Char)

-- | Get the last character of a text stream or return Nothing if
--   the text stream is empty
last :: Fold Text (Maybe Char)

-- | Returns True if the text stream is empty, False
--   otherwise
null :: Fold Text Bool

-- | Return the length of the text stream in characters
length :: Num n => Fold Text n

-- | (any predicate) returns True if any character
--   satisfies the predicate, False otherwise
any :: (Char -> Bool) -> Fold Text Bool

-- | (all predicate) returns True if all characters satisfy
--   the predicate, False otherwise
all :: (Char -> Bool) -> Fold Text Bool

-- | Computes the maximum character
maximum :: Fold Text (Maybe Char)

-- | Computes the minimum character
minimum :: Fold Text (Maybe Char)

-- | (elem c) returns True if the text stream has a
--   character equal to c, False otherwise
elem :: Char -> Fold Text Bool

-- | (notElem c) returns False if the text stream has a
--   character equal to c, True otherwise
notElem :: Char -> Fold Text Bool

-- | (find predicate) returns the first character that satisfies
--   the predicate or Nothing if no character satisfies the
--   predicate
find :: (Char -> Bool) -> Fold Text (Maybe Char)

-- | (index n) returns the nth character of the text
--   stream, or Nothing if the stream has an insufficient number of
--   characters
index :: Integral n => n -> Fold Text (Maybe Char)

-- | (elemIndex c) returns the index of the first character that
--   equals c, or Nothing if no character matches
elemIndex :: Num n => Char -> Fold Text (Maybe n)

-- | (findIndex predicate) returns the index of the first
--   character that satisfies the predicate, or Nothing if no
--   character satisfies the predicate
findIndex :: Num n => (Char -> Bool) -> Fold Text (Maybe n)

-- | (count c) returns the number of times c appears
count :: Num n => Char -> Fold Text n

-- | Combine all the strict Text chunks to build a lazy Text
lazy :: Fold Text Text
