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


-- | 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 :: Type -> Type) 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 :: Type -> Type) 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 :: 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 :: (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 :: forall (m :: Type -> Type) v a. (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 :: forall (m :: Type -> Type) a b. 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

-- | Lift a monadic value to a <a>FoldM</a>; works like <a>lift</a>.
--   
--   <pre>
--   lifts . pure = pure
--   </pre>
lifts :: Monad m => m b -> FoldM m 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 :: forall (m :: Type -> Type) a b. 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>(postmapM f folder)</tt> returns a new <a>FoldM</a> where f is
--   applied to the final value.
--   
--   <pre>
--   postmapM pure = id
--   
--   postmapM (f &gt;=&gt; g) = postmapM g . postmapM f
--   </pre>
--   
--   <pre>
--   postmapM k (pure r) = lifts (k r)
--   </pre>
postmapM :: Monad m => (a -> m r) -> FoldM m x a -> FoldM m x 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 :: 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 <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 :: 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 <a>FoldM</a>
--   
--   Any lens, traversal, or prism will type-check as a <a>HandlerM</a>
type HandlerM (m :: Type -> Type) 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 :: forall (m :: Type -> Type) a b r. 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 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)
class Monad m => PrimMonad (m :: Type -> Type)
data RealWorld
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 <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

-- | 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 :: Type -> Type) a b
class Foldable (t :: Type -> 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>.
--   
--   Import this module qualified to avoid clashing with the Prelude:
--   
--   <pre>
--   &gt;&gt;&gt; import qualified Control.Foldl.NonEmpty as Foldl1
--   </pre>
--   
--   Use <a>fold1</a> to apply a <a>Fold1</a> to a non-empty list:
--   
--   <pre>
--   &gt;&gt;&gt; Foldl1.fold1 Foldl1.last (1 :| [2..10])
--   10
--   </pre>
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

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

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

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

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

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

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

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

-- | <tt>(handles t folder)</tt> transforms the input of a <a>Fold1</a>
--   using a Lens, Traversal1, or Fold1 optic:
--   
--   <pre>
--   handles _1        :: Fold1 a r -&gt; Fold1 (a, b) r
--   handles traverse1 :: Traversable1 t =&gt; Fold1 a r -&gt; Fold1 (t a) r
--   handles folded1   :: Foldable1    t =&gt; Fold1 a r -&gt; Fold1 (t a) r
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; 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]
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; Foldl1.fold1 (handles _2 Foldl1.sconcat) $ (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 :: Handler1 a b -> Fold1 b r -> Fold1 a r

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

-- | <pre>
--   handles folded1 :: Foldable1 t =&gt; Fold1 a r -&gt; Fold1 (t a) r
--   </pre>
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 <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

-- | 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 :: Type -> Type) a b
class Foldable (t :: Type -> Type)
data ByteString
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 :: Type -> Type) a b

-- | <tt>ScanM </tt> <tt> step </tt> <tt> initial </tt> <tt> extract</tt>
ScanM :: (a -> StateT x m b) -> m x -> ScanM (m :: Type -> Type) 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 :: forall (m :: Type -> Type) a b. 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.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)
