-- 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 <tt>Applicative</tt> 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.15


-- | This module provides efficient and streaming left folds that you can
--   combine using <a>Applicative</a> style.
--   
--   Import this module qualified to avoid clashing with the Prelude:
--   
--   <pre>
--   &gt;&gt;&gt; import qualified Control.Foldl as Foldl
--   </pre>
--   
--   Use <a>fold</a> to apply a <a>Fold</a> to a list:
--   
--   <pre>
--   &gt;&gt;&gt; Foldl.fold Foldl.sum [1..100]
--   5050
--   </pre>
--   
--   <a>Fold</a>s are <a>Applicative</a>s, so you can combine them using
--   <a>Applicative</a> combinators:
--   
--   <pre>
--   &gt;&gt;&gt; import Control.Applicative
--   
--   &gt;&gt;&gt; let average = (/) &lt;$&gt; Foldl.sum &lt;*&gt; Foldl.genericLength
--   </pre>
--   
--   … or you can use <tt>do</tt> notation if you enable the
--   <tt>ApplicativeDo</tt> language extension:
--   
--   <pre>
--   &gt;&gt;&gt; :set -XApplicativeDo
--   
--   &gt;&gt;&gt; let average = do total &lt;- Foldl.sum; count &lt;- Foldl.genericLength; return (total / count)
--   </pre>
--   
--   … or you can use the fact that the <a>Fold</a> type implements
--   <a>Num</a> to do this:
--   
--   <pre>
--   &gt;&gt;&gt; let average = Foldl.sum / Foldl.genericLength
--   </pre>
--   
--   These combined folds will still traverse the list only once, streaming
--   efficiently over the list in constant space without space leaks:
--   
--   <pre>
--   &gt;&gt;&gt; Foldl.fold average [1..10000000]
--   5000000.5
--   
--   &gt;&gt;&gt; Foldl.fold ((,) &lt;$&gt; Foldl.minimum &lt;*&gt; Foldl.maximum) [1..10000000]
--   (Just 1,Just 10000000)
--   </pre>
--   
--   You might want to try enabling the <tt>-flate-dmd-anal</tt> 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 <a>Applicative</a> instance to assemble derived folds
--   that traverse the container only once
--   
--   A '<a>Fold</a> a b' processes elements of type <b>a</b> and results in
--   a value of type <b>b</b>.
data Fold a b

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

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

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

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

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

-- | Convert a strict left <a>Fold</a> into a scan
--   
--   <pre>
--   &gt;&gt;&gt; Foldl.scan Foldl.length [1..5]
--   [0,1,2,3,4,5]
--   </pre>
scan :: Fold a b -> [a] -> [b]

-- | Convert a <a>Fold</a> into a prescan for any <a>Traversable</a> type
--   
--   "Prescan" means that the last element of the scan is not included
--   
--   <pre>
--   &gt;&gt;&gt; Foldl.prescan Foldl.length [1..5]
--   [0,1,2,3,4]
--   </pre>
prescan :: Traversable t => Fold a b -> t a -> t b

-- | Convert a <a>Fold</a> into a postscan for any <a>Traversable</a> type
--   
--   "Postscan" means that the first element of the scan is not included
--   
--   <pre>
--   &gt;&gt;&gt; Foldl.postscan Foldl.length [1..5]
--   [1,2,3,4,5]
--   </pre>
postscan :: Traversable t => Fold a b -> t a -> t b

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

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

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

-- | Get the last element of a container or return <a>Nothing</a> 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 <a>True</a> if the container is empty, <a>False</a> otherwise
null :: Fold a Bool

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

-- | Returns <a>True</a> if all elements are <a>True</a>, <a>False</a>
--   otherwise
and :: Fold Bool Bool

-- | Returns <a>True</a> if any element is <a>True</a>, <a>False</a>
--   otherwise
or :: Fold Bool Bool

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

-- | <tt>(any predicate)</tt> returns <a>True</a> if any element satisfies
--   the predicate, <a>False</a> 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)

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

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

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

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

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

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

-- | <tt>(findIndex predicate)</tt> returns the index of the first element
--   that satisfies the predicate, or <a>Nothing</a> 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
--   <a>sink</a>.
mapM_ :: Monad m => (a -> m ()) -> FoldM m a ()

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

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

-- | Like <a>index</a>, except with a more general <a>Integral</a> 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]

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

-- | <i>O(n^2)</i>. 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 <a>Fold</a>, produces a <a>Map</a> which applies that fold to
--   each <tt>a</tt> separated by key <tt>k</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; fold (foldByKeyMap Control.Foldl.sum) [("a",1), ("b",2), ("b",20), ("a",10)]
--   fromList [("a",11),("b",22)]
--   </pre>
foldByKeyMap :: forall k a b. 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 <a>Fold</a>, produces a <a>HashMap</a> which applies that fold
--   to each <tt>a</tt> separated by key <tt>k</tt>.
--   
--   <pre>
--   &gt;&gt;&gt; List.sort (HashMap.toList (fold (foldByKeyHashMap Control.Foldl.sum) [("a",1), ("b",2), ("b",20), ("a",10)]))
--   [("a",11),("b",22)]
--   </pre>
foldByKeyHashMap :: forall k a b. (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 <a>vector</a> but is impure
vectorM :: (PrimMonad m, Vector v a) => FoldM m a (v a)

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

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

-- | Upgrade a monadic fold to accept the <a>FoldM</a> 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 <a>FoldM</a>
--   type
impurely_ :: Monad m => (forall x. (x -> a -> m x) -> m x -> m x) -> FoldM m a b -> m b

-- | Generalize a <a>Fold</a> to a <a>FoldM</a>
--   
--   <pre>
--   generalize (pure r) = pure r
--   
--   generalize (f &lt;*&gt; x) = generalize f &lt;*&gt; generalize x
--   </pre>
generalize :: Monad m => Fold a b -> FoldM m a b

-- | Simplify a pure <a>FoldM</a> to a <a>Fold</a>
--   
--   <pre>
--   simplify (pure r) = pure r
--   
--   simplify (f &lt;*&gt; x) = simplify f &lt;*&gt; simplify x
--   </pre>
simplify :: FoldM Identity a b -> Fold a b

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

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

-- | <tt>_Fold1 step</tt> returns a new <a>Fold</a> 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 <a>Maybe</a>. The
--   initial accumulator is retrieved from the <a>Foldable</a>, the result
--   is <tt>None</tt> for empty containers.
_Fold1 :: (a -> a -> a) -> Fold a (Maybe a)

-- | <tt>(premap f folder)</tt> returns a new <a>Fold</a> where f is
--   applied at each step
--   
--   <pre>
--   fold (premap f folder) list = fold folder (List.map f list)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; fold (premap Sum Foldl.mconcat) [1..10]
--   Sum {getSum = 55}
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; fold Foldl.mconcat (List.map Sum [1..10])
--   Sum {getSum = 55}
--   </pre>
--   
--   <pre>
--   premap id = id
--   
--   premap (f . g) = premap g . premap f
--   </pre>
--   
--   <pre>
--   premap k (pure r) = pure r
--   
--   premap k (f &lt;*&gt; x) = premap k f &lt;*&gt; premap k x
--   </pre>
premap :: (a -> b) -> Fold b r -> Fold a r

-- | <tt>(premapM f folder)</tt> returns a new <a>FoldM</a> where f is
--   applied to each input element
--   
--   <pre>
--   premapM return = id
--   
--   premapM (f &lt;=&lt; g) = premap g . premap f
--   </pre>
--   
--   <pre>
--   premapM k (pure r) = pure r
--   
--   premapM k (f &lt;*&gt; x) = premapM k f &lt;*&gt; premapM k x
--   </pre>
premapM :: Monad m => (a -> m b) -> FoldM m b r -> FoldM m a r

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

-- | <tt>(prefilterM f folder)</tt> returns a new <a>FoldM</a> 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 <a>Fold</a> into one which ignores elements until they
--   stop satisfying a predicate
--   
--   <pre>
--   fold (predropWhile p folder) list = fold folder (dropWhile p list)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; fold (predropWhile (&gt;5) Control.Foldl.sum) [10,9,5,9]
--   14
--   </pre>
predropWhile :: (a -> Bool) -> Fold a r -> Fold a r

-- | <tt>(drop n folder)</tt> returns a new <a>Fold</a> that ignores the
--   first <tt>n</tt> inputs but otherwise behaves the same as the original
--   fold.
--   
--   <pre>
--   fold (drop n folder) list = fold folder (Data.List.genericDrop n list)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; Foldl.fold (Foldl.drop 3 Foldl.sum) [10, 20, 30, 1, 2, 3]
--   6
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; Foldl.fold (Foldl.drop 10 Foldl.sum) [10, 20, 30, 1, 2, 3]
--   0
--   </pre>
drop :: Natural -> Fold a b -> Fold a b

-- | <tt>(dropM n folder)</tt> returns a new <a>FoldM</a> that ignores the
--   first <tt>n</tt> inputs but otherwise behaves the same as the original
--   fold.
--   
--   <pre>
--   foldM (dropM n folder) list = foldM folder (Data.List.genericDrop n list)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; Foldl.foldM (Foldl.dropM 3 (Foldl.generalize Foldl.sum)) [10, 20, 30, 1, 2, 3]
--   6
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; Foldl.foldM (Foldl.dropM 10 (Foldl.generalize Foldl.sum)) [10, 20, 30, 1, 2, 3]
--   0
--   </pre>
dropM :: Monad m => Natural -> FoldM m a b -> FoldM m a b

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

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

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

-- | <pre>
--   instance Monad m =&gt; Monoid (EndoM m a) where
--       mempty = EndoM return
--       mappend (EndoM f) (EndoM g) = EndoM (f &lt;=&lt; g)
--   </pre>
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 <a>FoldM</a>
--   
--   Any lens, traversal, or prism will type-check as a <a>HandlerM</a>
type HandlerM m a b = forall x. (b -> Const (Dual (EndoM m x)) b) -> a -> Const (Dual (EndoM m x)) a

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

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

-- | <pre>
--   folded :: Foldable t =&gt; Fold (t a) a
--   
--   handles folded :: Foldable t =&gt; Fold a r -&gt; Fold (t a) r
--   </pre>
folded :: (Contravariant f, Applicative f, Foldable t) => (a -> f a) -> t a -> f (t a)

-- | <pre>
--   &gt;&gt;&gt; fold (handles (filtered even) sum) [1..10]
--   30
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; foldM (handlesM (filtered even) (Foldl.mapM_ print)) [1..10]
--   2
--   4
--   6
--   8
--   10
--   </pre>
filtered :: Monoid m => (a -> Bool) -> (a -> m) -> a -> m

-- | Perform a <a>Fold</a> 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 g => (a -> g) -> Fold a r -> Fold a (Map g r)

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

-- | <tt>RealWorld</tt> is deeply magical. It is <i>primitive</i>, but it
--   is not <i>unlifted</i> (hence <tt>ptrArg</tt>). We never manipulate
--   values of type <tt>RealWorld</tt>; it's only used in the type system,
--   to parameterise <tt>State#</tt>.
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
--   <tt>DeriveFoldable</tt> extension. For example, a derived instance for
--   a binary tree might be:
--   
--   <pre>
--   {-# LANGUAGE DeriveFoldable #-}
--   data Tree a = Empty
--               | Leaf a
--               | Node (Tree a) a (Tree a)
--       deriving Foldable
--   </pre>
--   
--   A more detailed description can be found in the <b>Overview</b>
--   section of <a>Data.Foldable#overview</a>.
--   
--   For the class laws see the <b>Laws</b> section of
--   <a>Data.Foldable#laws</a>.
class () => Foldable (t :: Type -> Type)

-- | Class of immutable vectors. Every immutable vector is associated with
--   its mutable version through the <a>Mutable</a> type family. Methods of
--   this class should not be used directly. Instead,
--   <a>Data.Vector.Generic</a> and other <tt>Data.Vector</tt> modules
--   provide safe and fusible wrappers.
--   
--   Minimum complete implementation:
--   
--   <ul>
--   <li><a>basicUnsafeFreeze</a></li>
--   <li><a>basicUnsafeThaw</a></li>
--   <li><a>basicLength</a></li>
--   <li><a>basicUnsafeSlice</a></li>
--   <li><a>basicUnsafeIndexM</a></li>
--   </ul>
class MVector Mutable v a => Vector (v :: Type -> Type) a

-- | <tt>Mutable v s a</tt> is the mutable version of the immutable vector
--   type <tt>v a</tt> with the state token <tt>s</tt>. It is injective on
--   GHC 8 and newer.
type family Mutable (v :: Type -> Type) = (mv :: Type -> Type -> Type) | mv -> v
instance GHC.Base.Monad m => GHC.Base.Semigroup (Control.Foldl.EndoM m a)
instance GHC.Base.Monad m => GHC.Base.Monoid (Control.Foldl.EndoM m a)
instance GHC.Base.Functor m => GHC.Base.Functor (Control.Foldl.FoldM m a)
instance GHC.Base.Applicative m => GHC.Base.Applicative (Control.Foldl.FoldM m a)
instance GHC.Base.Monad m => Data.Functor.Extend.Extend (Control.Foldl.FoldM m a)
instance GHC.Base.Functor m => Data.Profunctor.Unsafe.Profunctor (Control.Foldl.FoldM m)
instance (GHC.Base.Semigroup b, GHC.Base.Monad m) => GHC.Base.Semigroup (Control.Foldl.FoldM m a b)
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.Functor (Control.Foldl.Fold a)
instance Data.Profunctor.Unsafe.Profunctor Control.Foldl.Fold
instance Data.Profunctor.Choice.Choice Control.Foldl.Fold
instance Data.Profunctor.Sieve.Cosieve Control.Foldl.Fold []
instance Data.Profunctor.Strong.Costrong Control.Foldl.Fold
instance Control.Comonad.Comonad (Control.Foldl.Fold a)
instance GHC.Base.Applicative (Control.Foldl.Fold a)
instance Data.Functor.Extend.Extend (Control.Foldl.Fold a)
instance GHC.Base.Semigroup b => GHC.Base.Semigroup (Control.Foldl.Fold a b)
instance Data.Semigroupoid.Semigroupoid Control.Foldl.Fold
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)


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

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

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

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

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

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

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

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

-- | <tt>(all predicate)</tt> returns <a>True</a> if all characters satisfy
--   the predicate, <a>False</a> 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)

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

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

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

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

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

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

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

-- | Combine all the strict <a>Text</a> chunks to build a lazy <a>Text</a>
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
--   <tt>DeriveFoldable</tt> extension. For example, a derived instance for
--   a binary tree might be:
--   
--   <pre>
--   {-# LANGUAGE DeriveFoldable #-}
--   data Tree a = Empty
--               | Leaf a
--               | Node (Tree a) a (Tree a)
--       deriving Foldable
--   </pre>
--   
--   A more detailed description can be found in the <b>Overview</b>
--   section of <a>Data.Foldable#overview</a>.
--   
--   For the class laws see the <b>Laws</b> section of
--   <a>Data.Foldable#laws</a>.
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 <a>Applicative</a> instance to assemble derived folds
--   that traverse the container only once
--   
--   A '<a>Fold</a> a b' processes elements of type <b>a</b> and results in
--   a value of type <b>b</b>.
data Fold a b

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

-- | A space efficient, packed, unboxed Unicode text type.
data () => Text


-- | This module provides a <a>Fold1</a> type that is a "non-empty" analog
--   of the <a>Fold</a> 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
--   <a>Control.Foldl</a> module. Instead, this module only provides the
--   utilities which can make use of the non-empty input guarantee (e.g.
--   <a>head</a>). For all other utilities you can convert them from the
--   equivalent <a>Fold</a> using <a>fromFold</a>.
module Control.Foldl.NonEmpty

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

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

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

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

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

-- | Fold all values within a non-empty container using (<a>&lt;&gt;</a>)
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
instance GHC.Base.Functor (Control.Foldl.NonEmpty.Fold1 a)
instance Data.Profunctor.Unsafe.Profunctor Control.Foldl.NonEmpty.Fold1
instance GHC.Base.Applicative (Control.Foldl.NonEmpty.Fold1 a)
instance GHC.Base.Semigroup b => GHC.Base.Semigroup (Control.Foldl.NonEmpty.Fold1 a b)
instance GHC.Base.Monoid b => GHC.Base.Monoid (Control.Foldl.NonEmpty.Fold1 a b)
instance GHC.Num.Num b => GHC.Num.Num (Control.Foldl.NonEmpty.Fold1 a b)
instance GHC.Real.Fractional b => GHC.Real.Fractional (Control.Foldl.NonEmpty.Fold1 a b)
instance GHC.Float.Floating b => GHC.Float.Floating (Control.Foldl.NonEmpty.Fold1 a b)


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

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

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

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

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

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

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

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

-- | <tt>(all predicate)</tt> returns <a>True</a> if all bytes satisfy the
--   predicate, <a>False</a> 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)

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

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

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

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

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

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

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

-- | Combine all the strict <a>ByteString</a> chunks to build a lazy
--   <a>ByteString</a>
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
--   <tt>DeriveFoldable</tt> extension. For example, a derived instance for
--   a binary tree might be:
--   
--   <pre>
--   {-# LANGUAGE DeriveFoldable #-}
--   data Tree a = Empty
--               | Leaf a
--               | Node (Tree a) a (Tree a)
--       deriving Foldable
--   </pre>
--   
--   A more detailed description can be found in the <b>Overview</b>
--   section of <a>Data.Foldable#overview</a>.
--   
--   For the class laws see the <b>Laws</b> section of
--   <a>Data.Foldable#laws</a>.
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 <a>Applicative</a> instance to assemble derived folds
--   that traverse the container only once
--   
--   A '<a>Fold</a> a b' processes elements of type <b>a</b> and results in
--   a value of type <b>b</b>.
data Fold a b

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

-- | A space-efficient representation of a <a>Word8</a> vector, supporting
--   many efficient operations.
--   
--   A <a>ByteString</a> contains 8-bit bytes, or by using the operations
--   from <a>Data.ByteString.Char8</a> 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 <a>Applicative</a> style.
--   
--   Import this module qualified to avoid clashing with the Prelude:
--   
--   <pre>
--   &gt;&gt;&gt; import qualified Control.Scanl as SL
--   </pre>
--   
--   Use <a>scan</a> to apply a <a>Scan</a> to a list (or other
--   <a>Traversable</a> structures) from left to right, and <a>scanr</a> to
--   do so from right to left.
--   
--   Note that the <a>Scan</a> type does not supersede the <a>Fold</a> type
--   nor does the <a>Fold</a> type supersede the <a>Scan</a> type. Each
--   type has a unique advantage.
--   
--   For example, <a>Scan</a>s can be chained end-to-end:
--   
--   <pre>
--   (&gt;&gt;&gt;) :: Scan a b -&gt; Scan b c -&gt; Scan a c
--   </pre>
--   
--   In other words, <a>Scan</a> is an instance of the <a>Category</a>
--   typeclass.
--   
--   <a>Fold</a>s cannot be chained end-to-end
--   
--   Vice versa, <a>Fold</a>s can produce a result even when fed no input:
--   
--   <pre>
--   extract :: Fold a b -&gt; b
--   </pre>
--   
--   In other words, <a>Fold</a> is an instance of the <tt>Comonad</tt>
--   typeclass.
--   
--   A <a>Scan</a> 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 <a>Applicative</a> instance to assemble derived scans
--   that traverse the container only once
--   
--   A '<a>Scan</a> a b' processes elements of type <b>a</b> replacing each
--   with a value of type <b>b</b>.
data Scan a b

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

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

-- | <tt>ScanM </tt> <tt> step </tt> <tt> initial </tt> <tt> extract</tt>
ScanM :: (a -> StateT x m b) -> m x -> ScanM m a b

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

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

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

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

-- | Convert a <a>Fold</a> 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 <a>Scan</a> type
purely :: (forall x. (a -> State x b) -> x -> r) -> Scan a b -> r

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

-- | Upgrade a monadic scan to accept the <a>ScanM</a> 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 <a>ScanM</a>
--   type
impurely_ :: Monad m => (forall x. (x -> a -> m (x, b)) -> m x -> r) -> ScanM m a b -> r

-- | Generalize a <a>Scan</a> to a <a>ScanM</a>
--   
--   <pre>
--   generalize (pure r) = pure r
--   
--   generalize (f &lt;*&gt; x) = generalize f &lt;*&gt; generalize x
--   </pre>
generalize :: Monad m => Scan a b -> ScanM m a b

-- | Simplify a pure <a>ScanM</a> to a <a>Scan</a>
--   
--   <pre>
--   simplify (pure r) = pure r
--   
--   simplify (f &lt;*&gt; x) = simplify f &lt;*&gt; simplify x
--   </pre>
simplify :: ScanM Identity a b -> Scan a b

-- | Shift a <a>ScanM</a> from one monad to another with a morphism such as
--   <a>lift</a> or <tt>liftIO</tt>; the effect is the same as
--   <a>hoist</a>.
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

-- | <tt>(premap f scaner)</tt> returns a new <a>Scan</a> where f is
--   applied at each step
--   
--   <pre>
--   scan (premap f scaner) list = scan scaner (map f list)
--   </pre>
--   
--   <pre>
--   premap id = id
--   
--   premap (f . g) = premap g . premap f
--   </pre>
--   
--   <pre>
--   premap k (pure r) = pure r
--   
--   premap k (f &lt;*&gt; x) = premap k f &lt;*&gt; premap k x
--   </pre>
premap :: (a -> b) -> Scan b r -> Scan a r

-- | <tt>(premapM f scaner)</tt> returns a new <a>ScanM</a> where f is
--   applied to each input element
--   
--   <pre>
--   premapM return = id
--   
--   premapM (f &lt;=&lt; g) = premap g . premap f
--   </pre>
--   
--   <pre>
--   premapM k (pure r) = pure r
--   
--   premapM k (f &lt;*&gt; x) = premapM k f &lt;*&gt; premapM k x
--   </pre>
premapM :: Monad m => (a -> m b) -> ScanM m b r -> ScanM m a r
instance GHC.Base.Functor (Control.Scanl.ReverseState s)
instance GHC.Base.Applicative (Control.Scanl.ReverseState s)
instance GHC.Base.Functor m => GHC.Base.Functor (Control.Scanl.ScanM m a)
instance GHC.Base.Applicative m => GHC.Base.Applicative (Control.Scanl.ScanM m a)
instance GHC.Base.Functor m => Data.Profunctor.Unsafe.Profunctor (Control.Scanl.ScanM m)
instance GHC.Base.Monad m => Control.Category.Category (Control.Scanl.ScanM m)
instance GHC.Base.Monad m => Control.Arrow.Arrow (Control.Scanl.ScanM m)
instance (GHC.Base.Monad m, GHC.Base.Semigroup b) => GHC.Base.Semigroup (Control.Scanl.ScanM m a b)
instance (GHC.Base.Monad m, GHC.Base.Monoid b) => GHC.Base.Monoid (Control.Scanl.ScanM m a b)
instance (GHC.Base.Monad m, GHC.Num.Num b) => GHC.Num.Num (Control.Scanl.ScanM m a b)
instance (GHC.Base.Monad m, GHC.Real.Fractional b) => GHC.Real.Fractional (Control.Scanl.ScanM m a b)
instance (GHC.Base.Monad m, GHC.Float.Floating b) => GHC.Float.Floating (Control.Scanl.ScanM m a b)
instance GHC.Base.Functor (Control.Scanl.Scan a)
instance GHC.Base.Applicative (Control.Scanl.Scan a)
instance Data.Profunctor.Unsafe.Profunctor Control.Scanl.Scan
instance Control.Category.Category Control.Scanl.Scan
instance Control.Arrow.Arrow Control.Scanl.Scan
instance GHC.Base.Semigroup b => GHC.Base.Semigroup (Control.Scanl.Scan a b)
instance GHC.Base.Monoid b => GHC.Base.Monoid (Control.Scanl.Scan a b)
instance GHC.Num.Num b => GHC.Num.Num (Control.Scanl.Scan a b)
instance GHC.Real.Fractional b => GHC.Real.Fractional (Control.Scanl.Scan a b)
instance GHC.Float.Floating b => GHC.Float.Floating (Control.Scanl.Scan a b)
