-- 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.4.18

-- | 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 Foldl
--   
--   
--   Use fold to apply a Fold to a list:
--   
--   
--   >>> Foldl.fold Foldl.sum [1..100]
--   5050
--   
--   
--   Folds are Applicatives, so you can combine them using
--   Applicative combinators:
--   
--   
--   >>> import Control.Applicative
--   
--   >>> let average = (/) <$> Foldl.sum <*> Foldl.genericLength
--   
--   
--   … or you can use do notation if you enable the
--   ApplicativeDo language extension:
--   
--   
--   >>> :set -XApplicativeDo
--   
--   >>> let average = do total <- Foldl.sum; count <- Foldl.genericLength; return (total / count)
--   
--   
--   … or you can use the fact that the Fold type implements
--   Num to do this:
--   
--   
--   >>> let average = Foldl.sum / Foldl.genericLength
--   
--   
--   These combined folds will still traverse the list only once, streaming
--   efficiently over the list in constant space without space leaks:
--   
--   
--   >>> Foldl.fold average [1..10000000]
--   5000000.5
--   
--   >>> Foldl.fold ((,) <$> Foldl.minimum <*> Foldl.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 :: Type -> Type) a b

-- | FoldM   step   initial   extract
FoldM :: (x -> a -> m x) -> m x -> (x -> m b) -> FoldM (m :: Type -> Type) 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
--   
--   
--   >>> Foldl.scan Foldl.length [1..5]
--   [0,1,2,3,4,5]
--   
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
--   
--   
--   >>> Foldl.prescan Foldl.length [1..5]
--   [0,1,2,3,4]
--   
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
--   
--   
--   >>> Foldl.postscan Foldl.length [1..5]
--   [1,2,3,4,5]
--   
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)

-- | Given a Fold, produces a Map which applies that fold to
--   each a separated by key k.
--   
--   
--   >>> fold (foldByKeyMap Control.Foldl.sum) [("a",1), ("b",2), ("b",20), ("a",10)]
--   fromList [("a",11),("b",22)]
--   
foldByKeyMap :: Ord k => Fold a b -> Fold (k, a) (Map k b)

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

-- | Given a Fold, produces a HashMap which applies that fold
--   to each a separated by key k.
--   
--   
--   >>> List.sort (HashMap.toList (fold (foldByKeyHashMap Control.Foldl.sum) [("a",1), ("b",2), ("b",20), ("a",10)]))
--   [("a",11),("b",22)]
--   
foldByKeyHashMap :: (Hashable k, Eq k) => Fold a b -> Fold (k, a) (HashMap k b)

-- | Fold all values into a vector
vector :: Vector v a => Fold a (v a)

-- | Fold all values into a vector
--   
--   This is more efficient than vector but is impure
vectorM :: forall (m :: Type -> Type) v a. (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 :: forall (m :: Type -> Type) a b. 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

-- | Lift a monadic value to a FoldM; works like lift.
--   
--   
--   lifts . pure = pure
--   
lifts :: Monad m => m b -> FoldM m 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 :: forall (m :: Type -> Type) a b. 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 (List.map f list)
--   
--   
--   
--   >>> fold (premap Sum Foldl.mconcat) [1..10]
--   Sum {getSum = 55}
--   
--   
--   
--   >>> fold Foldl.mconcat (List.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
--   
--   
--   premapM return = 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 :: Monad m => (a -> m b) -> FoldM m b r -> FoldM m a r

-- | (postmapM f folder) returns a new FoldM where f is
--   applied to the final value.
--   
--   
--   postmapM pure = id
--   
--   postmapM (f >=> g) = postmapM g . postmapM f
--   
--   
--   
--   postmapM k (pure r) = lifts (k r)
--   
postmapM :: Monad m => (a -> m r) -> FoldM m x a -> FoldM m x r

-- | (prefilter f folder) returns a new Fold where the
--   folder's input is used only when the input satisfies a predicate f
--   
--   This can also be done with handles (handles (filtered
--   f)) but prefilter does not need you to depend on a lens
--   library.
--   
--   
--   fold (prefilter p folder) list = fold folder (filter p list)
--   
--   
--   
--   >>> fold (prefilter (>5) Control.Foldl.sum) [1..10]
--   40
--   
--   
--   
--   >>> fold Control.Foldl.sum (filter (>5) [1..10])
--   40
--   
prefilter :: (a -> Bool) -> Fold a r -> Fold a r

-- | (prefilterM f folder) returns a new FoldM where the
--   folder's input is used only when the input satisfies a monadic
--   predicate f.
prefilterM :: Monad m => (a -> m Bool) -> FoldM m a r -> FoldM m a r

-- | 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

-- | (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)
--   
--   
--   
--   >>> Foldl.fold (Foldl.drop 3 Foldl.sum) [10, 20, 30, 1, 2, 3]
--   6
--   
--   
--   
--   >>> Foldl.fold (Foldl.drop 10 Foldl.sum) [10, 20, 30, 1, 2, 3]
--   0
--   
drop :: Natural -> Fold a b -> Fold a b

-- | (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)
--   
--   
--   
--   >>> Foldl.foldM (Foldl.dropM 3 (Foldl.generalize Foldl.sum)) [10, 20, 30, 1, 2, 3]
--   6
--   
--   
--   
--   >>> Foldl.foldM (Foldl.dropM 10 (Foldl.generalize Foldl.sum)) [10, 20, 30, 1, 2, 3]
--   0
--   
dropM :: forall (m :: Type -> Type) a b. Monad m => Natural -> FoldM m a b -> FoldM m a b

-- | 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 Foldl.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) Foldl.sum (Just (2, 3))
--   5
--   
--   
--   
--   >>> foldOver (_Just . both) Foldl.sum Nothing
--   0
--   
--   
--   
--   Foldl.foldOver f folder xs == Foldl.fold folder (xs^..f)
--   
--   
--   
--   Foldl.foldOver (folded . f) folder == Foldl.fold (handles f folder)
--   
--   
--   
--   Foldl.foldOver folded == Foldl.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 :: Type -> Type) a
EndoM :: (a -> m a) -> EndoM (m :: Type -> Type) a
[appEndoM] :: EndoM (m :: Type -> Type) 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 :: Type -> Type) 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 :: forall (m :: Type -> Type) a b r. 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
--   
--   
--   Foldl.foldOverM (folded . f) folder == Foldl.foldM (handlesM f folder)
--   
--   
--   
--   Foldl.foldOverM folded == Foldl.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) (Foldl.mapM_ print)) [1..10]
--   2
--   4
--   6
--   8
--   10
--   
filtered :: Monoid m => (a -> Bool) -> (a -> m) -> a -> m

-- | Perform a Fold while grouping the data according to a specified
--   group projection function. Returns the folded result grouped as a map
--   keyed by the group.
groupBy :: Ord k => (a -> k) -> Fold a b -> Fold a (Map k b)

-- | Combine two folds into a fold over inputs for either of them.
either :: Fold a1 b1 -> Fold a2 b2 -> Fold (Either a1 a2) (b1, b2)

-- | Combine two monadic folds into a fold over inputs for either of them.
eitherM :: forall (m :: Type -> Type) a1 b1 a2 b2. Monad m => FoldM m a1 b1 -> FoldM m a2 b2 -> FoldM m (Either a1 a2) (b1, b2)

-- | Nest a fold in an applicative.
nest :: Applicative f => Fold a b -> Fold (f a) (f b)

-- | RealWorld is deeply magical. It is primitive, but it is
--   not unlifted (hence ptrArg). We never manipulate
--   values of type RealWorld; it's only used in the type system, to
--   parameterise State#.
data RealWorld

-- | Class of monads which can perform primitive state-transformer actions.
class Monad m => PrimMonad (m :: Type -> Type)

-- | The Foldable class represents data structures that can be reduced to a
--   summary value one element at a time. Strict left-associative folds are
--   a good fit for space-efficient reduction, while lazy right-associative
--   folds are a good fit for corecursive iteration, or for folds that
--   short-circuit after processing an initial subsequence of the
--   structure's elements.
--   
--   Instances can be derived automatically by enabling the
--   DeriveFoldable extension. For example, a derived instance for
--   a binary tree might be:
--   
--   
--   {-# LANGUAGE DeriveFoldable #-}
--   data Tree a = Empty
--               | Leaf a
--               | Node (Tree a) a (Tree a)
--       deriving Foldable
--   
--   
--   A more detailed description can be found in the Overview
--   section of Data.Foldable#overview.
--   
--   For the class laws see the Laws section of
--   Data.Foldable#laws.
class Foldable (t :: Type -> Type)
class MVector Mutable v a => Vector (v :: Type -> Type) a
type family Mutable (v :: Type -> Type) = (mv :: Type -> Type -> Type) | mv -> v
instance GHC.Internal.Base.Applicative (Control.Foldl.Fold a)
instance GHC.Internal.Base.Applicative m => GHC.Internal.Base.Applicative (Control.Foldl.FoldM m a)
instance Data.Profunctor.Choice.Choice Control.Foldl.Fold
instance Data.Profunctor.Closed.Closed Control.Foldl.Fold
instance Control.Comonad.Comonad (Control.Foldl.Fold a)
instance Data.Profunctor.Sieve.Cosieve Control.Foldl.Fold []
instance Data.Profunctor.Strong.Costrong Control.Foldl.Fold
instance Data.Functor.Extend.Extend (Control.Foldl.Fold a)
instance GHC.Internal.Base.Monad m => Data.Functor.Extend.Extend (Control.Foldl.FoldM m a)
instance GHC.Internal.Float.Floating b => GHC.Internal.Float.Floating (Control.Foldl.Fold a b)
instance (GHC.Internal.Base.Monad m, GHC.Internal.Float.Floating b) => GHC.Internal.Float.Floating (Control.Foldl.FoldM m a b)
instance GHC.Internal.Real.Fractional b => GHC.Internal.Real.Fractional (Control.Foldl.Fold a b)
instance (GHC.Internal.Base.Monad m, GHC.Internal.Real.Fractional b) => GHC.Internal.Real.Fractional (Control.Foldl.FoldM m a b)
instance GHC.Internal.Base.Functor (Control.Foldl.Fold a)
instance GHC.Internal.Base.Functor m => GHC.Internal.Base.Functor (Control.Foldl.FoldM m a)
instance GHC.Internal.Base.Monad m => GHC.Internal.Base.Monoid (Control.Foldl.EndoM m a)
instance GHC.Internal.Base.Monoid b => GHC.Internal.Base.Monoid (Control.Foldl.Fold a b)
instance (GHC.Internal.Base.Monoid b, GHC.Internal.Base.Monad m) => GHC.Internal.Base.Monoid (Control.Foldl.FoldM m a b)
instance GHC.Internal.Num.Num b => GHC.Internal.Num.Num (Control.Foldl.Fold a b)
instance (GHC.Internal.Base.Monad m, GHC.Internal.Num.Num b) => GHC.Internal.Num.Num (Control.Foldl.FoldM m a b)
instance Data.Profunctor.Unsafe.Profunctor Control.Foldl.Fold
instance GHC.Internal.Base.Functor m => Data.Profunctor.Unsafe.Profunctor (Control.Foldl.FoldM m)
instance GHC.Internal.Base.Monad m => GHC.Internal.Base.Semigroup (Control.Foldl.EndoM m a)
instance GHC.Internal.Base.Semigroup b => GHC.Internal.Base.Semigroup (Control.Foldl.Fold a b)
instance (GHC.Internal.Base.Semigroup b, GHC.Internal.Base.Monad m) => GHC.Internal.Base.Semigroup (Control.Foldl.FoldM m a b)
instance Data.Semigroupoid.Semigroupoid Control.Foldl.Fold

-- | 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

-- | The Foldable class represents data structures that can be reduced to a
--   summary value one element at a time. Strict left-associative folds are
--   a good fit for space-efficient reduction, while lazy right-associative
--   folds are a good fit for corecursive iteration, or for folds that
--   short-circuit after processing an initial subsequence of the
--   structure's elements.
--   
--   Instances can be derived automatically by enabling the
--   DeriveFoldable extension. For example, a derived instance for
--   a binary tree might be:
--   
--   
--   {-# LANGUAGE DeriveFoldable #-}
--   data Tree a = Empty
--               | Leaf a
--               | Node (Tree a) a (Tree a)
--       deriving Foldable
--   
--   
--   A more detailed description can be found in the Overview
--   section of Data.Foldable#overview.
--   
--   For the class laws see the Laws section of
--   Data.Foldable#laws.
class Foldable (t :: Type -> Type)

-- | 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

-- | 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 :: Type -> Type) a b

-- | A space efficient, packed, unboxed Unicode text type.
data Text

-- | This module provides a Fold1 type that is a "non-empty" analog
--   of the Fold type, meaning that it requires at least one input
--   element in order to produce a result
--   
--   This module does not provide all of the same utilities as the
--   Control.Foldl module. Instead, this module only provides the
--   utilities which can make use of the non-empty input guarantee (e.g.
--   head). For all other utilities you can convert them from the
--   equivalent Fold using fromFold.
--   
--   Import this module qualified to avoid clashing with the Prelude:
--   
--   
--   >>> import qualified Control.Foldl.NonEmpty as Foldl1
--   
--   
--   Use fold1 to apply a Fold1 to a non-empty list:
--   
--   
--   >>> Foldl1.fold1 Foldl1.last (1 :| [2..10])
--   10
--   
module Control.Foldl.NonEmpty

-- | A Fold1 is like a Fold except that it consumes at least
--   one input element
data Fold1 a b
Fold1 :: (a -> Fold a b) -> Fold1 a b

-- | Fold1_ is an alternative to the Fold1 constructor if
--   you need to explicitly work with an initial, step and extraction
--   function.
--   
--   Fold1_ is similar to the Fold constructor, which
--   also works with an initial, step and extraction function. However,
--   note that Fold takes the step function as the first argument
--   and the initial accumulator as the second argument, whereas
--   Fold1_ takes them in swapped order:
--   
--   Fold1_   initial   step   extract
--   
--   While Fold resembles foldl, Fold1_ resembles
--   foldlMap1.
pattern Fold1_ :: forall a b x. () => (a -> x) -> (x -> a -> x) -> (x -> b) -> Fold1 a b

-- | Apply a strict left Fold1 to a NonEmpty list
fold1 :: Foldable1 f => Fold1 a b -> f a -> b

-- | Promote any Fold to an equivalent Fold1
fromFold :: Fold a b -> Fold1 a b

-- | Promote any Fold1 to an equivalent Fold
toFold :: Fold1 a b -> Fold a (Maybe b)

-- | Fold all values within a non-empty container using (<>)
sconcat :: Semigroup a => Fold1 a a

-- | Get the first element of a non-empty container
head :: Fold1 a a

-- | Get the last element of a non-empty container
last :: Fold1 a a

-- | Computes the maximum element
maximum :: Ord a => Fold1 a a

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

-- | Computes the minimum element
minimum :: Ord a => Fold1 a a

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

-- | Fold all values within a non-empty container into a NonEmpty
--   list
nonEmpty :: Fold1 a (NonEmpty a)

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

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

-- | (premap f folder) returns a new Fold1 where f is
--   applied at each step
--   
--   
--   Foldl1.fold1 (premap f folder) list = Foldl1.fold1 folder (NonEmpty.map f list)
--   
--   
--   
--   >>> Foldl1.fold1 (premap Sum Foldl1.sconcat) (1 :| [2..10])
--   Sum {getSum = 55}
--   
--   
--   
--   >>> Foldl1.fold1 Foldl1.sconcat $ NonEmpty.map Sum (1 :| [2..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) -> Fold1 b r -> Fold1 a r

-- | 
--   instance Monad m => Semigroup (FromMaybe m a) where
--       mappend (FromMaybe f) (FromMaybe g) = FromMaybeM (f . Just . g)
--   
newtype FromMaybe b
FromMaybe :: (Maybe b -> b) -> FromMaybe b
[appFromMaybe] :: FromMaybe b -> Maybe b -> b

-- | A handler for the upstream input of a Fold1
--   
--   This is compatible with van Laarhoven optics as defined in the lens
--   package. Any lens, fold1 or traversal1 will type-check as a
--   Handler1.
type Handler1 a b = forall x. () => b -> Const Dual FromMaybe x b -> a -> Const Dual FromMaybe x a

-- | (handles t folder) transforms the input of a Fold1
--   using a Lens, Traversal1, or Fold1 optic:
--   
--   
--   handles _1        :: Fold1 a r -> Fold1 (a, b) r
--   handles traverse1 :: Traversable1 t => Fold1 a r -> Fold1 (t a) r
--   handles folded1   :: Foldable1    t => Fold1 a r -> Fold1 (t a) r
--   
--   
--   
--   >>> Foldl1.fold1 (handles traverse1 Foldl1.nonEmpty) $ (1 :| [2..4]) :| [ 5 :| [6,7], 8 :| [9,10] ]
--   1 :| [2,3,4,5,6,7,8,9,10]
--   
--   
--   
--   >>> Foldl1.fold1 (handles _2 Foldl1.sconcat) $ (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 :: Handler1 a b -> Fold1 b r -> Fold1 a r

-- | (foldOver f folder xs) folds all values from a Lens,
--   Traversal1 or Fold1 optic with the given folder
--   
--   
--   >>> foldOver (_2 . both1) Foldl1.nonEmpty (1, (2, 3))
--   2 :| [3]
--   
--   
--   
--   Foldl1.foldOver f folder xs == Foldl1.fold1 folder (xs ^.. f)
--   
--   
--   
--   Foldl1.foldOver (folded1 . f) folder == Foldl1.fold1 (Foldl1.handles f folder)
--   
--   
--   
--   Foldl1.foldOver folded1 == Foldl1.fold1
--   
foldOver :: Handler1 s a -> Fold1 a b -> s -> b

-- | 
--   handles folded1 :: Foldable1 t => Fold1 a r -> Fold1 (t a) r
--   
folded1 :: (Contravariant f, Apply f, Foldable1 t) => (a -> f a) -> t a -> f (t a)

-- | Nest a fold in an Apply.
nest :: Apply f => Fold1 a b -> Fold1 (f a) (f b)
instance GHC.Internal.Base.Applicative (Control.Foldl.NonEmpty.Fold1 a)
instance GHC.Internal.Control.Arrow.ArrowChoice Control.Foldl.NonEmpty.Fold1
instance GHC.Internal.Control.Arrow.Arrow Control.Foldl.NonEmpty.Fold1
instance GHC.Internal.Control.Category.Category Control.Foldl.NonEmpty.Fold1
instance Data.Profunctor.Choice.Choice Control.Foldl.NonEmpty.Fold1
instance Data.Profunctor.Closed.Closed Control.Foldl.NonEmpty.Fold1
instance Data.Profunctor.Sieve.Cosieve Control.Foldl.NonEmpty.Fold1 GHC.Internal.Base.NonEmpty
instance Data.Functor.Extend.Extend (Control.Foldl.NonEmpty.Fold1 a)
instance GHC.Internal.Float.Floating b => GHC.Internal.Float.Floating (Control.Foldl.NonEmpty.Fold1 a b)
instance GHC.Internal.Real.Fractional b => GHC.Internal.Real.Fractional (Control.Foldl.NonEmpty.Fold1 a b)
instance GHC.Internal.Base.Functor (Control.Foldl.NonEmpty.Fold1 a)
instance GHC.Internal.Base.Monoid b => GHC.Internal.Base.Monoid (Control.Foldl.NonEmpty.Fold1 a b)
instance GHC.Internal.Num.Num b => GHC.Internal.Num.Num (Control.Foldl.NonEmpty.Fold1 a b)
instance Data.Profunctor.Unsafe.Profunctor Control.Foldl.NonEmpty.Fold1
instance GHC.Internal.Base.Semigroup b => GHC.Internal.Base.Semigroup (Control.Foldl.NonEmpty.Fold1 a b)
instance GHC.Internal.Base.Semigroup (Control.Foldl.NonEmpty.FromMaybe b)
instance Data.Semigroupoid.Semigroupoid Control.Foldl.NonEmpty.Fold1
instance Data.Profunctor.Strong.Strong Control.Foldl.NonEmpty.Fold1

-- | 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

-- | The Foldable class represents data structures that can be reduced to a
--   summary value one element at a time. Strict left-associative folds are
--   a good fit for space-efficient reduction, while lazy right-associative
--   folds are a good fit for corecursive iteration, or for folds that
--   short-circuit after processing an initial subsequence of the
--   structure's elements.
--   
--   Instances can be derived automatically by enabling the
--   DeriveFoldable extension. For example, a derived instance for
--   a binary tree might be:
--   
--   
--   {-# LANGUAGE DeriveFoldable #-}
--   data Tree a = Empty
--               | Leaf a
--               | Node (Tree a) a (Tree a)
--       deriving Foldable
--   
--   
--   A more detailed description can be found in the Overview
--   section of Data.Foldable#overview.
--   
--   For the class laws see the Laws section of
--   Data.Foldable#laws.
class Foldable (t :: Type -> Type)

-- | 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

-- | 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 :: Type -> Type) a b

-- | A space-efficient representation of a Word8 vector, supporting
--   many efficient operations.
--   
--   A ByteString contains 8-bit bytes, or by using the operations
--   from Data.ByteString.Char8 it can be interpreted as containing
--   8-bit characters.
data ByteString

-- | 8-bit unsigned integer type
data Word8

-- | 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 Scan 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, Scans 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.
--   
--   Folds cannot be chained end-to-end
--   
--   Vice versa, Folds 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 cannot produce any output until provided with at least
--   one input.
module Control.Scanl

-- | Efficient representation of a left map-with-accumulator that preserves
--   the scan's step function and initial accumulator.
--   
--   This allows the Applicative instance to assemble derived scans
--   that traverse the container only once
--   
--   A 'Scan a b' processes elements of type a replacing each
--   with a value of type b.
data Scan a b

-- | Scan   step   initial 
Scan :: (a -> State x b) -> x -> Scan a b

-- | Like Scan, but monadic.
--   
--   A 'ScanM m a b' processes elements of type a and results
--   in a monadic value of type m b.
data ScanM (m :: Type -> Type) a b

-- | ScanM   step   initial   extract
ScanM :: (a -> StateT x m b) -> m x -> ScanM (m :: Type -> Type) a b

-- | Apply a strict left Scan to a Traversable container
scan :: Traversable t => Scan a b -> t a -> t b

-- | Like scan but monadic
scanM :: (Traversable t, Monad m) => ScanM m a b -> t a -> m (t b)

-- | Like scan but start scanning from the right
scanr :: Traversable t => Scan a b -> t a -> t b

-- | Convert a Fold into a prescan
--   
--   "Prescan" means that the last element of the scan is not included
prescan :: Fold a b -> Scan a b

-- | Convert a Fold into a postscan
--   
--   "Postscan" means that the first element of the scan is not included
postscan :: Fold a b -> Scan a b

-- | Upgrade a scan to accept the Scan type
purely :: (forall x. () => (a -> State x b) -> x -> r) -> Scan a b -> r

-- | Upgrade a more traditional scan to accept the Scan type
purely_ :: (forall x. () => (x -> a -> (x, b)) -> x -> r) -> Scan a b -> r

-- | Upgrade a monadic scan to accept the ScanM type
impurely :: (forall x. () => (a -> StateT x m b) -> m x -> r) -> ScanM m a b -> r

-- | Upgrade a more traditional monadic scan to accept the ScanM
--   type
impurely_ :: Monad m => (forall x. () => (x -> a -> m (x, b)) -> m x -> r) -> ScanM m a b -> r

-- | Generalize a Scan to a ScanM
--   
--   
--   generalize (pure r) = pure r
--   
--   generalize (f <*> x) = generalize f <*> generalize x
--   
generalize :: forall (m :: Type -> Type) a b. Monad m => Scan a b -> ScanM m a b

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

-- | Shift a ScanM 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) -> ScanM m a b -> ScanM n a b
arrM :: Monad m => (b -> m c) -> ScanM m b c

-- | (premap f scaner) returns a new Scan where f is
--   applied at each step
--   
--   
--   scan (premap f scaner) list = scan scaner (map f list)
--   
--   
--   
--   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) -> Scan b r -> Scan a r

-- | (premapM f scaner) returns a new ScanM where f is
--   applied to each input element
--   
--   
--   premapM return = 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 :: Monad m => (a -> m b) -> ScanM m b r -> ScanM m a r
instance GHC.Internal.Base.Applicative (Control.Scanl.ReverseState s)
instance GHC.Internal.Base.Applicative (Control.Scanl.Scan a)
instance GHC.Internal.Base.Applicative m => GHC.Internal.Base.Applicative (Control.Scanl.ScanM m a)
instance GHC.Internal.Control.Arrow.Arrow Control.Scanl.Scan
instance GHC.Internal.Base.Monad m => GHC.Internal.Control.Arrow.Arrow (Control.Scanl.ScanM m)
instance GHC.Internal.Control.Category.Category Control.Scanl.Scan
instance GHC.Internal.Base.Monad m => GHC.Internal.Control.Category.Category (Control.Scanl.ScanM m)
instance GHC.Internal.Float.Floating b => GHC.Internal.Float.Floating (Control.Scanl.Scan a b)
instance (GHC.Internal.Base.Monad m, GHC.Internal.Float.Floating b) => GHC.Internal.Float.Floating (Control.Scanl.ScanM m a b)
instance GHC.Internal.Real.Fractional b => GHC.Internal.Real.Fractional (Control.Scanl.Scan a b)
instance (GHC.Internal.Base.Monad m, GHC.Internal.Real.Fractional b) => GHC.Internal.Real.Fractional (Control.Scanl.ScanM m a b)
instance GHC.Internal.Base.Functor (Control.Scanl.ReverseState s)
instance GHC.Internal.Base.Functor (Control.Scanl.Scan a)
instance GHC.Internal.Base.Functor m => GHC.Internal.Base.Functor (Control.Scanl.ScanM m a)
instance GHC.Internal.Base.Monoid b => GHC.Internal.Base.Monoid (Control.Scanl.Scan a b)
instance (GHC.Internal.Base.Monad m, GHC.Internal.Base.Monoid b) => GHC.Internal.Base.Monoid (Control.Scanl.ScanM m a b)
instance GHC.Internal.Num.Num b => GHC.Internal.Num.Num (Control.Scanl.Scan a b)
instance (GHC.Internal.Base.Monad m, GHC.Internal.Num.Num b) => GHC.Internal.Num.Num (Control.Scanl.ScanM m a b)
instance Data.Profunctor.Unsafe.Profunctor Control.Scanl.Scan
instance GHC.Internal.Base.Functor m => Data.Profunctor.Unsafe.Profunctor (Control.Scanl.ScanM m)
instance GHC.Internal.Base.Semigroup b => GHC.Internal.Base.Semigroup (Control.Scanl.Scan a b)
instance (GHC.Internal.Base.Monad m, GHC.Internal.Base.Semigroup b) => GHC.Internal.Base.Semigroup (Control.Scanl.ScanM m a b)
