-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/
-- | Composable, streaming, and efficient left folds
--
-- This library provides strict left folds that stream in constant
-- memory, and you can combine folds using Applicative style to
-- derive new folds. Derived folds still traverse the container just once
-- and are often as efficient as hand-written folds.
@package foldl
@version 1.4.2
-- | This module provides efficient and streaming left folds that you can
-- combine using Applicative style.
--
-- Import this module qualified to avoid clashing with the Prelude:
--
--
-- >>> import qualified Control.Foldl as L
--
--
-- Use fold to apply a Fold to a list:
--
--
-- >>> L.fold L.sum [1..100]
-- 5050
--
--
-- Folds are Applicatives, so you can combine them using
-- Applicative combinators:
--
--
-- >>> import Control.Applicative
--
-- >>> let average = (/) <$> L.sum <*> L.genericLength
--
--
-- Taking the sum, the sum of squares, ..., upto the sum of x^5
--
--
-- >>> import Data.Traversable
--
-- >>> let powerSums = sequenceA [L.premap (^n) L.sum | n <- [1..5]]
--
-- >>> L.fold powerSums [1..10]
-- [55,385,3025,25333,220825]
--
--
-- These combined folds will still traverse the list only once, streaming
-- efficiently over the list in constant space without space leaks:
--
--
-- >>> L.fold average [1..10000000]
-- 5000000.5
--
-- >>> L.fold ((,) <$> L.minimum <*> L.maximum) [1..10000000]
-- (Just 1,Just 10000000)
--
--
-- You might want to try enabling the -flate-dmd-anal flag when
-- compiling executables that use this library to further improve
-- performance.
module Control.Foldl
-- | Efficient representation of a left fold that preserves the fold's step
-- function, initial accumulator, and extraction function
--
-- This allows the Applicative instance to assemble derived folds
-- that traverse the container only once
--
-- A 'Fold a b' processes elements of type a and results in
-- a value of type b.
data Fold a b
-- | Fold step initial extract
Fold :: (x -> a -> x) -> x -> (x -> b) -> Fold a b
-- | Like Fold, but monadic.
--
-- A 'FoldM m a b' processes elements of type a and results
-- in a monadic value of type m b.
data FoldM m a b
-- | FoldM step initial extract
FoldM :: (x -> a -> m x) -> (m x) -> (x -> m b) -> FoldM m a b
-- | Apply a strict left Fold to a Foldable container
fold :: Foldable f => Fold a b -> f a -> b
-- | Like fold, but monadic
foldM :: (Foldable f, Monad m) => FoldM m a b -> f a -> m b
-- | Convert a strict left Fold into a scan
scan :: Fold a b -> [a] -> [b]
-- | Convert a Fold into a prescan for any Traversable type
--
-- "Prescan" means that the last element of the scan is not included
prescan :: Traversable t => Fold a b -> t a -> t b
-- | Convert a Fold into a postscan for any Traversable type
--
-- "Postscan" means that the first element of the scan is not included
postscan :: Traversable t => Fold a b -> t a -> t b
-- | Fold all values within a container using mappend and
-- mempty
mconcat :: Monoid a => Fold a a
-- | Convert a "foldMap" to a Fold
foldMap :: Monoid w => (a -> w) -> (w -> b) -> Fold a b
-- | Get the first element of a container or return Nothing if the
-- container is empty
head :: Fold a (Maybe a)
-- | Get the last element of a container or return Nothing if the
-- container is empty
last :: Fold a (Maybe a)
-- | Get the last element of a container or return a default value if the
-- container is empty
lastDef :: a -> Fold a a
-- | Return the last N elements
lastN :: Int -> Fold a [a]
-- | Returns True if the container is empty, False otherwise
null :: Fold a Bool
-- | Return the length of the container
length :: Fold a Int
-- | Returns True if all elements are True, False
-- otherwise
and :: Fold Bool Bool
-- | Returns True if any element is True, False
-- otherwise
or :: Fold Bool Bool
-- | (all predicate) returns True if all elements satisfy
-- the predicate, False otherwise
all :: (a -> Bool) -> Fold a Bool
-- | (any predicate) returns True if any element satisfies
-- the predicate, False otherwise
any :: (a -> Bool) -> Fold a Bool
-- | Computes the sum of all elements
sum :: Num a => Fold a a
-- | Computes the product of all elements
product :: Num a => Fold a a
-- | Compute a numerically stable arithmetic mean of all elements
mean :: Fractional a => Fold a a
-- | Compute a numerically stable (population) variance over all elements
variance :: Fractional a => Fold a a
-- | Compute a numerically stable (population) standard deviation over all
-- elements
std :: Floating a => Fold a a
-- | Computes the maximum element
maximum :: Ord a => Fold a (Maybe a)
-- | Computes the maximum element with respect to the given comparison
-- function
maximumBy :: (a -> a -> Ordering) -> Fold a (Maybe a)
-- | Computes the minimum element
minimum :: Ord a => Fold a (Maybe a)
-- | Computes the minimum element with respect to the given comparison
-- function
minimumBy :: (a -> a -> Ordering) -> Fold a (Maybe a)
-- | (elem a) returns True if the container has an element
-- equal to a, False otherwise
elem :: Eq a => a -> Fold a Bool
-- | (notElem a) returns False if the container has an
-- element equal to a, True otherwise
notElem :: Eq a => a -> Fold a Bool
-- | (find predicate) returns the first element that satisfies the
-- predicate or Nothing if no element satisfies the predicate
find :: (a -> Bool) -> Fold a (Maybe a)
-- | (index n) returns the nth element of the container,
-- or Nothing if the container has an insufficient number of
-- elements
index :: Int -> Fold a (Maybe a)
-- | (lookup a) returns the element paired with the first matching
-- item, or Nothing if none matches
lookup :: Eq a => a -> Fold (a, b) (Maybe b)
-- | (elemIndex a) returns the index of the first element that
-- equals a, or Nothing if no element matches
elemIndex :: Eq a => a -> Fold a (Maybe Int)
-- | (findIndex predicate) returns the index of the first element
-- that satisfies the predicate, or Nothing if no element
-- satisfies the predicate
findIndex :: (a -> Bool) -> Fold a (Maybe Int)
-- | Pick a random element, using reservoir sampling
random :: FoldM IO a (Maybe a)
-- | Pick several random elements, using reservoir sampling
randomN :: Vector v a => Int -> FoldM IO a (Maybe (v a))
-- | Converts an effectful function to a fold. Specialized version of
-- sink.
mapM_ :: Monad m => (a -> m ()) -> FoldM m a ()
-- | Converts an effectful function to a fold
--
--
-- sink (f <> g) = sink f <> sink g -- if `(<>)` is commutative
-- sink mempty = mempty
--
sink :: (Monoid w, Monad m) => (a -> m w) -> FoldM m a w
-- | Like length, except with a more general Num return value
genericLength :: Num b => Fold a b
-- | Like index, except with a more general Integral argument
genericIndex :: Integral i => i -> Fold a (Maybe a)
-- | Fold all values into a list
list :: Fold a [a]
-- | Fold all values into a list, in reverse order
revList :: Fold a [a]
-- | O(n log n). Fold values into a list with duplicates removed,
-- while preserving their first occurrences
nub :: Ord a => Fold a [a]
-- | O(n^2). Fold values into a list with duplicates removed, while
-- preserving their first occurrences
eqNub :: Eq a => Fold a [a]
-- | Fold values into a set
set :: Ord a => Fold a (Set a)
-- | Fold values into a hash-set
hashSet :: (Eq a, Hashable a) => Fold a (HashSet a)
-- | Fold pairs into a map.
map :: Ord a => Fold (a, b) (Map a b)
-- | Fold pairs into a hash-map.
hashMap :: (Eq a, Hashable a) => Fold (a, b) (HashMap a b)
-- | Fold all values into a vector
vector :: Vector v a => Fold a (v a)
-- | Fold all values into a vector
--
-- This is more efficient than vector but is impure
vectorM :: (PrimMonad m, Vector v a) => FoldM m a (v a)
-- | Upgrade a fold to accept the Fold type
purely :: (forall x. (x -> a -> x) -> x -> (x -> b) -> r) -> Fold a b -> r
-- | Upgrade a more traditional fold to accept the Fold type
purely_ :: (forall x. (x -> a -> x) -> x -> x) -> Fold a b -> b
-- | Upgrade a monadic fold to accept the FoldM type
impurely :: (forall x. (x -> a -> m x) -> m x -> (x -> m b) -> r) -> FoldM m a b -> r
-- | Upgrade a more traditional monadic fold to accept the FoldM
-- type
impurely_ :: Monad m => (forall x. (x -> a -> m x) -> m x -> m x) -> FoldM m a b -> m b
-- | Generalize a Fold to a FoldM
--
--
-- generalize (pure r) = pure r
--
-- generalize (f <*> x) = generalize f <*> generalize x
--
generalize :: Monad m => Fold a b -> FoldM m a b
-- | Simplify a pure FoldM to a Fold
--
--
-- simplify (pure r) = pure r
--
-- simplify (f <*> x) = simplify f <*> simplify x
--
simplify :: FoldM Identity a b -> Fold a b
-- | Shift a FoldM from one monad to another with a morphism such as
-- lift or liftIO; the effect is the same as
-- hoist.
hoists :: (forall x. m x -> n x) -> FoldM m a b -> FoldM n a b
-- | Allows to continue feeding a FoldM even after passing it to a
-- function that closes it.
--
-- For pure Folds, this is provided by the Comonad
-- instance.
duplicateM :: Applicative m => FoldM m a b -> FoldM m a (FoldM m a b)
-- | _Fold1 step returns a new Fold using just a step
-- function that has the same type for the accumulator and the element.
-- The result type is the accumulator type wrapped in Maybe. The
-- initial accumulator is retrieved from the Foldable, the result
-- is None for empty containers.
_Fold1 :: (a -> a -> a) -> Fold a (Maybe a)
-- | (premap f folder) returns a new Fold where f is
-- applied at each step
--
--
-- fold (premap f folder) list = fold folder (map f list)
--
--
--
-- >>> fold (premap Sum mconcat) [1..10]
-- Sum {getSum = 55}
--
--
--
-- >>> fold mconcat (map Sum [1..10])
-- Sum {getSum = 55}
--
--
--
-- premap id = id
--
-- premap (f . g) = premap g . premap f
--
--
--
-- premap k (pure r) = pure r
--
-- premap k (f <*> x) = premap k f <*> premap k x
--
premap :: (a -> b) -> Fold b r -> Fold a r
-- | (premapM f folder) returns a new FoldM where f is
-- applied to each input element
--
--
-- premapM return = id
--
-- premapM (f <=< g) = premap g . premap f
--
--
--
-- premapM k (pure r) = pure r
--
-- premapM k (f <*> x) = premapM k f <*> premapM k x
--
premapM :: Monad m => (a -> m b) -> FoldM m b r -> FoldM m a r
-- | (prefilter f folder) returns a new Fold where the
-- folder's input is used only when the input satisfies a predicate f
--
-- This can also be done with handles (handles (filtered
-- f)) but prefilter does not need you to depend on a lens
-- library.
--
--
-- fold (prefilter p folder) list = fold folder (filter p list)
--
--
--
-- >>> fold (prefilter (>5) Control.Foldl.sum) [1..10]
-- 40
--
--
--
-- >>> fold Control.Foldl.sum (filter (>5) [1..10])
-- 40
--
prefilter :: (a -> Bool) -> Fold a r -> Fold a r
-- | (prefilterM f folder) returns a new Fold where the
-- folder's input is used only when the input satisfies a monadic
-- predicate f.
--
--
-- foldM (prefilterM p folder) list = foldM folder (filter p list)
--
prefilterM :: (Monad m) => (a -> m Bool) -> FoldM m a r -> FoldM m a r
-- | A handler for the upstream input of a Fold
--
-- Any lens, traversal, or prism will type-check as a Handler
type Handler a b = forall x. (b -> Const (Dual (Endo x)) b) -> a -> Const (Dual (Endo x)) a
-- | (handles t folder) transforms the input of a Fold
-- using a lens, traversal, or prism:
--
--
-- handles _1 :: Fold a r -> Fold (a, b) r
-- handles _Left :: Fold a r -> Fold (Either a b) r
-- handles traverse :: Traversable t => Fold a r -> Fold (t a) r
-- handles folded :: Foldable t => Fold a r -> Fold (t a) r
--
--
--
-- >>> fold (handles traverse sum) [[1..5],[6..10]]
-- 55
--
--
--
-- >>> fold (handles (traverse.traverse) sum) [[Nothing, Just 2, Just 7],[Just 13, Nothing, Just 20]]
-- 42
--
--
--
-- >>> fold (handles (filtered even) sum) [1..10]
-- 30
--
--
--
-- >>> fold (handles _2 mconcat) [(1,"Hello "),(2,"World"),(3,"!")]
-- "Hello World!"
--
--
--
-- handles id = id
--
-- handles (f . g) = handles f . handles g
--
--
--
-- handles t (pure r) = pure r
--
-- handles t (f <*> x) = handles t f <*> handles t x
--
handles :: Handler a b -> Fold b r -> Fold a r
-- | (foldOver f folder xs) folds all values from a Lens,
-- Traversal, Prism or Fold with the given folder
--
--
-- >>> foldOver (_Just . both) L.sum (Just (2, 3))
-- 5
--
--
--
-- >>> foldOver (_Just . both) L.sum Nothing
-- 0
--
--
--
-- L.foldOver f folder xs == L.fold folder (xs^..f)
--
--
--
-- L.foldOver (folded.f) folder == L.fold (handles f folder)
--
--
--
-- L.foldOver folded == L.fold
--
foldOver :: Handler s a -> Fold a b -> s -> b
-- |
-- instance Monad m => Monoid (EndoM m a) where
-- mempty = EndoM return
-- mappend (EndoM f) (EndoM g) = EndoM (f <=< g)
--
newtype EndoM m a
EndoM :: a -> m a -> EndoM m a
[appEndoM] :: EndoM m a -> a -> m a
-- | A Handler for the upstream input of FoldM
--
-- Any lens, traversal, or prism will type-check as a HandlerM
type HandlerM m a b = forall x. (b -> Const (Dual (EndoM m x)) b) -> a -> Const (Dual (EndoM m x)) a
-- | (handlesM t folder) transforms the input of a FoldM
-- using a lens, traversal, or prism:
--
--
-- handlesM _1 :: FoldM m a r -> FoldM (a, b) r
-- handlesM _Left :: FoldM m a r -> FoldM (Either a b) r
-- handlesM traverse :: Traversable t => FoldM m a r -> FoldM m (t a) r
-- handlesM folded :: Foldable t => FoldM m a r -> FoldM m (t a) r
--
--
-- handlesM obeys these laws:
--
--
-- handlesM id = id
--
-- handlesM (f . g) = handlesM f . handlesM g
--
--
--
-- handlesM t (pure r) = pure r
--
-- handlesM t (f <*> x) = handlesM t f <*> handlesM t x
--
handlesM :: HandlerM m a b -> FoldM m b r -> FoldM m a r
-- | (foldOverM f folder xs) folds all values from a Lens,
-- Traversal, Prism or Fold monadically with the given folder
--
--
-- L.foldOverM (folded.f) folder == L.foldM (handlesM f folder)
--
--
--
-- L.foldOverM folded == L.foldM
--
foldOverM :: Monad m => HandlerM m s a -> FoldM m a b -> s -> m b
-- |
-- folded :: Foldable t => Fold (t a) a
--
-- handles folded :: Foldable t => Fold a r -> Fold (t a) r
--
folded :: (Contravariant f, Applicative f, Foldable t) => (a -> f a) -> (t a -> f (t a))
-- |
-- >>> fold (handles (filtered even) sum) [1..10]
-- 30
--
--
--
-- >>> foldM (handlesM (filtered even) (mapM_ print)) [1..10]
-- 2
-- 4
-- 6
-- 8
-- 10
--
filtered :: Monoid m => (a -> Bool) -> (a -> m) -> a -> m
-- | Perform a Fold while grouping the data according to a specified
-- group projection function. Returns the folded result grouped as a map
-- keyed by the group.
groupBy :: Ord g => (a -> g) -> Fold a r -> Fold a (Map g r)
-- | RealWorld is deeply magical. It is primitive, but it
-- is not unlifted (hence ptrArg). We never manipulate
-- values of type RealWorld; it's only used in the type system,
-- to parameterise State#.
data RealWorld
-- | Class of monads which can perform primitive state-transformer actions
class Monad m => PrimMonad (m :: * -> *)
-- | Data structures that can be folded.
--
-- For example, given a data type
--
--
-- data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
--
--
-- a suitable instance would be
--
--
-- instance Foldable Tree where
-- foldMap f Empty = mempty
-- foldMap f (Leaf x) = f x
-- foldMap f (Node l k r) = foldMap f l `mappend` f k `mappend` foldMap f r
--
--
-- This is suitable even for abstract types, as the monoid is assumed to
-- satisfy the monoid laws. Alternatively, one could define
-- foldr:
--
--
-- instance Foldable Tree where
-- foldr f z Empty = z
-- foldr f z (Leaf x) = f x z
-- foldr f z (Node l k r) = foldr f (f k (foldr f z r)) l
--
--
-- Foldable instances are expected to satisfy the following
-- laws:
--
--
-- foldr f z t = appEndo (foldMap (Endo . f) t ) z
--
--
--
-- foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
--
--
--
-- fold = foldMap id
--
--
--
-- length = getSum . foldMap (Sum . const 1)
--
--
-- sum, product, maximum, and minimum
-- should all be essentially equivalent to foldMap forms, such
-- as
--
--
-- sum = getSum . foldMap Sum
--
--
-- but may be less defined.
--
-- If the type is also a Functor instance, it should satisfy
--
--
-- foldMap f = fold . fmap f
--
--
-- which implies that
--
--
-- foldMap f . fmap g = foldMap (f . g)
--
class Foldable (t :: * -> *)
-- | Mutable v s a is the mutable version of the pure vector type
-- v a with the state token s
-- | Class of immutable vectors. Every immutable vector is associated with
-- its mutable version through the Mutable type family. Methods of
-- this class should not be used directly. Instead,
-- Data.Vector.Generic and other Data.Vector modules provide safe
-- and fusible wrappers.
--
-- Minimum complete implementation:
--
--
class MVector Mutable v a => Vector (v :: * -> *) a
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.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 Control.Comonad.Comonad (Control.Foldl.Fold a)
instance GHC.Base.Applicative (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 byte streams
module Control.Foldl.ByteString
-- | Apply a strict left Fold to a lazy bytestring
fold :: Fold ByteString a -> ByteString -> a
-- | Apply a strict monadic left FoldM to a lazy bytestring
foldM :: Monad m => FoldM m ByteString a -> ByteString -> m a
-- | Get the first byte of a byte stream or return Nothing if the
-- stream is empty
head :: Fold ByteString (Maybe Word8)
-- | Get the last byte of a byte stream or return Nothing if the
-- byte stream is empty
last :: Fold ByteString (Maybe Word8)
-- | Returns True if the byte stream is empty, False
-- otherwise
null :: Fold ByteString Bool
-- | Return the length of the byte stream in bytes
length :: Num n => Fold ByteString n
-- | (any predicate) returns True if any byte satisfies the
-- predicate, False otherwise
any :: (Word8 -> Bool) -> Fold ByteString Bool
-- | (all predicate) returns True if all bytes satisfy the
-- predicate, False otherwise
all :: (Word8 -> Bool) -> Fold ByteString Bool
-- | Computes the maximum byte
maximum :: Fold ByteString (Maybe Word8)
-- | Computes the minimum byte
minimum :: Fold ByteString (Maybe Word8)
-- | (elem w8) returns True if the byte stream has a byte
-- equal to w8, False otherwise
elem :: Word8 -> Fold ByteString Bool
-- | (notElem w8) returns False if the byte stream has a
-- byte equal to w8, True otherwise
notElem :: Word8 -> Fold ByteString Bool
-- | (find predicate) returns the first byte that satisfies the
-- predicate or Nothing if no byte satisfies the predicate
find :: (Word8 -> Bool) -> Fold ByteString (Maybe Word8)
-- | (index n) returns the nth byte of the byte stream,
-- or Nothing if the stream has an insufficient number of bytes
index :: Integral n => n -> Fold ByteString (Maybe Word8)
-- | (elemIndex w8) returns the index of the first byte that
-- equals w8, or Nothing if no byte matches
elemIndex :: Num n => Word8 -> Fold ByteString (Maybe n)
-- | (findIndex predicate) returns the index of the first byte
-- that satisfies the predicate, or Nothing if no byte satisfies
-- the predicate
findIndex :: Num n => (Word8 -> Bool) -> Fold ByteString (Maybe n)
-- | count w8 returns the number of times w8 appears
count :: Num n => Word8 -> Fold ByteString n
-- | Combine all the strict ByteString chunks to build a lazy
-- ByteString
lazy :: Fold ByteString ByteString
-- | Data structures that can be folded.
--
-- For example, given a data type
--
--
-- data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
--
--
-- a suitable instance would be
--
--
-- instance Foldable Tree where
-- foldMap f Empty = mempty
-- foldMap f (Leaf x) = f x
-- foldMap f (Node l k r) = foldMap f l `mappend` f k `mappend` foldMap f r
--
--
-- This is suitable even for abstract types, as the monoid is assumed to
-- satisfy the monoid laws. Alternatively, one could define
-- foldr:
--
--
-- instance Foldable Tree where
-- foldr f z Empty = z
-- foldr f z (Leaf x) = f x z
-- foldr f z (Node l k r) = foldr f (f k (foldr f z r)) l
--
--
-- Foldable instances are expected to satisfy the following
-- laws:
--
--
-- foldr f z t = appEndo (foldMap (Endo . f) t ) z
--
--
--
-- foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
--
--
--
-- fold = foldMap id
--
--
--
-- length = getSum . foldMap (Sum . const 1)
--
--
-- sum, product, maximum, and minimum
-- should all be essentially equivalent to foldMap forms, such
-- as
--
--
-- sum = getSum . foldMap Sum
--
--
-- but may be less defined.
--
-- If the type is also a Functor instance, it should satisfy
--
--
-- foldMap f = fold . fmap f
--
--
-- which implies that
--
--
-- foldMap f . fmap g = foldMap (f . g)
--
class Foldable (t :: * -> *)
-- | Like Fold, but monadic.
--
-- A 'FoldM m a b' processes elements of type a and results
-- in a monadic value of type m b.
data FoldM m a b
-- | Efficient representation of a left fold that preserves the fold's step
-- function, initial accumulator, and extraction function
--
-- This allows the Applicative instance to assemble derived folds
-- that traverse the container only once
--
-- A 'Fold a b' processes elements of type a and results in
-- a value of type b.
data Fold a b
-- | A space-efficient representation of a Word8 vector, supporting
-- many efficient operations.
--
-- A ByteString contains 8-bit bytes, or by using the operations
-- from Data.ByteString.Char8 it can be interpreted as containing
-- 8-bit characters.
data ByteString
-- | 8-bit unsigned integer type
data Word8
-- | Folds for text streams
module Control.Foldl.Text
-- | Apply a strict left Fold to lazy text
fold :: Fold Text a -> Text -> a
-- | Apply a strict monadic left FoldM to lazy text
foldM :: Monad m => FoldM m Text a -> Text -> m a
-- | Get the first character of a text stream or return Nothing if
-- the stream is empty
head :: Fold Text (Maybe Char)
-- | Get the last character of a text stream or return Nothing if
-- the text stream is empty
last :: Fold Text (Maybe Char)
-- | Returns True if the text stream is empty, False
-- otherwise
null :: Fold Text Bool
-- | Return the length of the text stream in characters
length :: Num n => Fold Text n
-- | (any predicate) returns True if any character
-- satisfies the predicate, False otherwise
any :: (Char -> Bool) -> Fold Text Bool
-- | (all predicate) returns True if all characters satisfy
-- the predicate, False otherwise
all :: (Char -> Bool) -> Fold Text Bool
-- | Computes the maximum character
maximum :: Fold Text (Maybe Char)
-- | Computes the minimum character
minimum :: Fold Text (Maybe Char)
-- | (elem c) returns True if the text stream has a
-- character equal to c, False otherwise
elem :: Char -> Fold Text Bool
-- | (notElem c) returns False if the text stream has a
-- character equal to c, True otherwise
notElem :: Char -> Fold Text Bool
-- | (find predicate) returns the first character that satisfies
-- the predicate or Nothing if no character satisfies the
-- predicate
find :: (Char -> Bool) -> Fold Text (Maybe Char)
-- | (index n) returns the nth character of the text
-- stream, or Nothing if the stream has an insufficient number of
-- characters
index :: Integral n => n -> Fold Text (Maybe Char)
-- | (elemIndex c) returns the index of the first character that
-- equals c, or Nothing if no character matches
elemIndex :: Num n => Char -> Fold Text (Maybe n)
-- | (findIndex predicate) returns the index of the first
-- character that satisfies the predicate, or Nothing if no
-- character satisfies the predicate
findIndex :: Num n => (Char -> Bool) -> Fold Text (Maybe n)
-- | (count c) returns the number of times c appears
count :: Num n => Char -> Fold Text n
-- | Combine all the strict Text chunks to build a lazy Text
lazy :: Fold Text Text
-- | Data structures that can be folded.
--
-- For example, given a data type
--
--
-- data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)
--
--
-- a suitable instance would be
--
--
-- instance Foldable Tree where
-- foldMap f Empty = mempty
-- foldMap f (Leaf x) = f x
-- foldMap f (Node l k r) = foldMap f l `mappend` f k `mappend` foldMap f r
--
--
-- This is suitable even for abstract types, as the monoid is assumed to
-- satisfy the monoid laws. Alternatively, one could define
-- foldr:
--
--
-- instance Foldable Tree where
-- foldr f z Empty = z
-- foldr f z (Leaf x) = f x z
-- foldr f z (Node l k r) = foldr f (f k (foldr f z r)) l
--
--
-- Foldable instances are expected to satisfy the following
-- laws:
--
--
-- foldr f z t = appEndo (foldMap (Endo . f) t ) z
--
--
--
-- foldl f z t = appEndo (getDual (foldMap (Dual . Endo . flip f) t)) z
--
--
--
-- fold = foldMap id
--
--
--
-- length = getSum . foldMap (Sum . const 1)
--
--
-- sum, product, maximum, and minimum
-- should all be essentially equivalent to foldMap forms, such
-- as
--
--
-- sum = getSum . foldMap Sum
--
--
-- but may be less defined.
--
-- If the type is also a Functor instance, it should satisfy
--
--
-- foldMap f = fold . fmap f
--
--
-- which implies that
--
--
-- foldMap f . fmap g = foldMap (f . g)
--
class Foldable (t :: * -> *)
-- | Like Fold, but monadic.
--
-- A 'FoldM m a b' processes elements of type a and results
-- in a monadic value of type m b.
data FoldM m a b
-- | Efficient representation of a left fold that preserves the fold's step
-- function, initial accumulator, and extraction function
--
-- This allows the Applicative instance to assemble derived folds
-- that traverse the container only once
--
-- A 'Fold a b' processes elements of type a and results in
-- a value of type b.
data Fold a b
-- | A space efficient, packed, unboxed Unicode text type.
data Text
-- | This module provides efficient and streaming left map-with-accumulator
-- that you can combine using Applicative style.
--
-- Import this module qualified to avoid clashing with the Prelude:
--
--
-- >>> import qualified Control.Scanl as SL
--
--
-- Use scan to apply a Fold to a list:
module Control.Scanl
-- | Efficient representation of a left map-with-accumulator that preserves
-- the scan's step function and initial accumulator.
--
-- This allows the Applicative instance to assemble derived scans
-- that traverse the container only once
--
-- A 'Scan a b' processes elements of type a replacing each
-- with a value of type b.
data Scan a b
-- | Scan step initial
Scan :: (a -> State x b) -> x -> Scan a b
-- | Like Scan, but monadic.
--
-- A 'ScanM m a b' processes elements of type a and results
-- in a monadic value of type m b.
data ScanM m a b
-- | ScanM step initial extract
ScanM :: (a -> StateT x m b) -> (m x) -> ScanM m a b
-- | Apply a strict left Scan to a Traversable container
scan :: Traversable t => Scan a b -> t a -> t b
-- | Like scan but monadic
scanM :: (Traversable t, Monad m) => ScanM m a b -> t a -> m (t b)
-- | Convert a Fold into a prescan
--
-- "Prescan" means that the last element of the scan is not included
prescan :: Fold a b -> Scan a b
-- | Convert a Fold into a postscan
--
-- "Postscan" means that the first element of the scan is not included
postscan :: Fold a b -> Scan a b
-- | Upgrade a scan to accept the Scan type
purely :: (forall x. (a -> State x b) -> x -> r) -> Scan a b -> r
-- | Upgrade a more traditional scan to accept the Scan type
purely_ :: (forall x. (x -> a -> (x, b)) -> x -> r) -> Scan a b -> r
-- | Upgrade a monadic scan to accept the ScanM type
impurely :: (forall x. (a -> StateT x m b) -> m x -> r) -> ScanM m a b -> r
-- | Upgrade a more traditional monadic scan to accept the ScanM
-- type
impurely_ :: Monad m => (forall x. (x -> a -> m (x, b)) -> m x -> r) -> ScanM m a b -> r
-- | Generalize a Scan to a ScanM
--
--
-- generalize (pure r) = pure r
--
-- generalize (f <*> x) = generalize f <*> generalize x
--
generalize :: Monad m => Scan a b -> ScanM m a b
-- | Simplify a pure ScanM to a Scan
--
--
-- simplify (pure r) = pure r
--
-- simplify (f <*> x) = simplify f <*> simplify x
--
simplify :: ScanM Identity a b -> Scan a b
-- | Shift a ScanM from one monad to another with a morphism such as
-- lift or liftIO; the effect is the same as
-- hoist.
hoists :: (forall x. m x -> n x) -> ScanM m a b -> ScanM n a b
arrM :: Monad m => (b -> m c) -> ScanM m b c
-- | (premap f scaner) returns a new Scan where f is
-- applied at each step
--
--
-- scan (premap f scaner) list = scan scaner (map f list)
--
--
--
-- premap id = id
--
-- premap (f . g) = premap g . premap f
--
--
--
-- premap k (pure r) = pure r
--
-- premap k (f <*> x) = premap k f <*> premap k x
--
premap :: (a -> b) -> Scan b r -> Scan a r
-- | (premapM f scaner) returns a new ScanM where f is
-- applied to each input element
--
--
-- premapM return = id
--
-- premapM (f <=< g) = premap g . premap f
--
--
--
-- premapM k (pure r) = pure r
--
-- premapM k (f <*> x) = premapM k f <*> premapM k x
--
premapM :: Monad m => (a -> m b) -> ScanM m b r -> ScanM m a r
instance GHC.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)