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


-- | 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 L
--   </pre>
--   
--   Use <a>fold</a> to apply a <a>Fold</a> to a list:
--   
--   <pre>
--   &gt;&gt;&gt; L.fold L.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; L.sum &lt;*&gt; L.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; L.fold average [1..10000000]
--   5000000.5
--   
--   &gt;&gt;&gt; L.fold ((,) &lt;$&gt; L.minimum &lt;*&gt; L.maximum) [1..10000000]
--   (Just 1,Just 10000000)
--   </pre>
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
data Fold a b
Fold :: (x -> a -> x) -> x -> (x -> b) -> Fold a b

-- | Like <a>Fold</a>, but monadic
data FoldM m a b
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
scan :: Fold a b -> [a] -> [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

-- | 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 all elements
product :: Num a => Fold a a

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

-- | Computes the minimum element
minimum :: Ord a => 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>(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)

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

-- | <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 all values into a vector
vector :: (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 monadic fold to accept the <a>FoldM</a> type
impurely :: Monad m => (forall x. (x -> a -> m x) -> m x -> (x -> m b) -> r) -> FoldM m a b -> r

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

-- | <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 (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) -> 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>
--   foldM (premapM f folder) list = foldM folder (map f list)
--   </pre>
--   
--   <pre>
--   premapM id = id
--   
--   premapM (f . 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 -> b) -> FoldM m b r -> FoldM m a r

-- | <tt>(pretraverse t folder)</tt> traverses each incoming element using
--   <tt>Traversal'</tt> <tt>t</tt> and folds every target of the
--   <tt>Traversal'</tt>
--   
--   <pre>
--   pretraverse id = id
--   
--   pretraverse (f . g) = pretraverse f . pretraverse g
--   </pre>
--   
--   <pre>
--   pretraverse t (pure r) = pure r
--   
--   pretraverse t (f &lt;*&gt; x) = pretraverse t f &lt;*&gt; pretraverse t x
--   </pre>
pretraverse :: Traversal' a b -> Fold b r -> Fold a r

-- | <tt>(pretraverseM t folder)</tt> traverses each incoming element using
--   <tt>Traversal'</tt> <tt>t</tt> and folds every target of the
--   <tt>Traversal'</tt>
--   
--   <pre>
--   pretraverseM id = id
--   
--   pretraverseM (f . g) = pretraverseM f . pretraverseM g
--   </pre>
--   
--   <pre>
--   pretraverseM t (pure r) = pure r
--   
--   pretraverseM t (f &lt;*&gt; x) = pretraverseM t f &lt;*&gt; pretraverseM t x
--   </pre>
pretraverseM :: Monad m => Traversal' a b -> FoldM m b r -> FoldM m a r
instance Monad m => Monoid (EndoM m a)
instance (Monoid b, Monad m) => Monoid (FoldM m a b)
instance Monad m => Applicative (FoldM m a)
instance Monad m => Functor (FoldM m a)
instance Monoid b => Monoid (Fold a b)
instance Applicative (Fold a)
instance Functor (Fold a)


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

-- | Appply a strict left <a>Fold</a> to a lazy bytestring
fold :: Fold ByteString a -> ByteString -> 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)


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

-- | Apply a strict left <a>Fold</a> to lazy text
fold :: Fold Text a -> Text -> 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)
