libghc-foldl-doc 1.1.2-1build1 / usr / share / doc / libghc-foldl-doc / html / foldl.txt

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


-- | 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>
--   
--   Taking the sum, the sum of squares, ..., upto the sum of x^5
--   
--   <pre>
--   &gt;&gt;&gt; import Data.Traversable
--   
--   &gt;&gt;&gt; let powerSums = sequenceA [premap (^n) L.sum | n &lt;- [1..5]]
--   
--   &gt;&gt;&gt; L.fold powerSums [1..10]
--   [55,385,3025,25333,220825]
--   </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
--   
--   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
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

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

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

-- | 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 (map f list)
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; fold (premap Sum mconcat) [1..10]
--   Sum {getSum = 55}
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; fold mconcat (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>
--   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 :: (a -> b) -> FoldM m b r -> FoldM m a r

-- | 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 -> Constant (Endo x) b) -> a -> Constant (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
--   </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,3,5,7,21,21]
--   42
--   </pre>
--   
--   <pre>
--   &gt;&gt;&gt; fold (handles _2 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

-- | <pre>
--   instance Monad m =&gt; Monoid (EndoM m a) where
--       mempty = EndoM return
--       mappend (EndoM f) (EndoM g) = EndoM (f &gt;=&gt; 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 -> Constant (EndoM m x) b) -> a -> Constant (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
--   </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 :: Monad m => HandlerM m a b -> FoldM m b r -> FoldM m a r
instance GHC.Base.Functor (Control.Foldl.Fold a)
instance Data.Profunctor.Unsafe.Profunctor Control.Foldl.Fold
instance Control.Comonad.Comonad (Control.Foldl.Fold a)
instance GHC.Base.Applicative (Control.Foldl.Fold a)
instance GHC.Base.Monoid b => GHC.Base.Monoid (Control.Foldl.Fold a b)
instance GHC.Num.Num b => GHC.Num.Num (Control.Foldl.Fold a b)
instance GHC.Real.Fractional b => GHC.Real.Fractional (Control.Foldl.Fold a b)
instance GHC.Float.Floating b => GHC.Float.Floating (Control.Foldl.Fold a b)
instance GHC.Base.Monad m => GHC.Base.Functor (Control.Foldl.FoldM m a)
instance GHC.Base.Monad m => GHC.Base.Applicative (Control.Foldl.FoldM m a)
instance GHC.Base.Monad m => Data.Profunctor.Unsafe.Profunctor (Control.Foldl.FoldM m)
instance (GHC.Base.Monoid b, GHC.Base.Monad m) => GHC.Base.Monoid (Control.Foldl.FoldM m a b)
instance (GHC.Base.Monad m, GHC.Num.Num b) => GHC.Num.Num (Control.Foldl.FoldM m a b)
instance (GHC.Base.Monad m, GHC.Real.Fractional b) => GHC.Real.Fractional (Control.Foldl.FoldM m a b)
instance (GHC.Base.Monad m, GHC.Float.Floating b) => GHC.Float.Floating (Control.Foldl.FoldM m a b)
instance GHC.Base.Monad m => GHC.Base.Monoid (Control.Foldl.EndoM m a)


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

-- | Apply a strict left <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)

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

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