-- 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.13
-- | 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 Foldl
--
--
-- Use fold to apply a Fold to a list:
--
--
-- >>> Foldl.fold Foldl.sum [1..100]
-- 5050
--
--
-- Folds are Applicatives, so you can combine them using
-- Applicative combinators:
--
--
-- >>> import Control.Applicative
--
-- >>> let average = (/) <$> Foldl.sum <*> Foldl.genericLength
--
--
-- … or you can use do notation if you enable the
-- ApplicativeDo language extension:
--
--
-- >>> :set -XApplicativeDo
--
-- >>> let average = do total <- Foldl.sum; count <- Foldl.genericLength; return (total / count)
--
--
-- … or you can use the fact that the Fold type implements
-- Num to do this:
--
--
-- >>> let average = Foldl.sum / Foldl.genericLength
--
--
-- These combined folds will still traverse the list only once, streaming
-- efficiently over the list in constant space without space leaks:
--
--
-- >>> Foldl.fold average [1..10000000]
-- 5000000.5
--
-- >>> Foldl.fold ((,) <$> Foldl.minimum <*> Foldl.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
--
--
-- >>> Foldl.scan Foldl.length [1..5]
-- [0,1,2,3,4,5]
--
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
--
--
-- >>> Foldl.prescan Foldl.length [1..5]
-- [0,1,2,3,4]
--
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
--
--
-- >>> Foldl.postscan Foldl.length [1..5]
-- [1,2,3,4,5]
--
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)
-- | Given a Fold, produces a Map which applies that fold to
-- each a separated by key k.
--
--
-- >>> fold (foldByKeyMap Control.Foldl.sum) [("a",1), ("b",2), ("b",20), ("a",10)]
-- fromList [("a",11),("b",22)]
--
foldByKeyMap :: forall k a b. Ord k => Fold a b -> Fold (k, a) (Map k b)
-- | Fold pairs into a hash-map.
hashMap :: (Eq a, Hashable a) => Fold (a, b) (HashMap a b)
-- | Given a Fold, produces a HashMap which applies that fold
-- to each a separated by key k.
--
--
-- >>> List.sort (HashMap.toList (fold (foldByKeyHashMap Control.Foldl.sum) [("a",1), ("b",2), ("b",20), ("a",10)]))
-- [("a",11),("b",22)]
--
foldByKeyHashMap :: forall k a b. (Hashable k, Eq k) => Fold a b -> Fold (k, a) (HashMap k b)
-- | Fold all values into a vector
vector :: Vector v a => Fold a (v a)
-- | Fold all values into a vector
--
-- This is more efficient than 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 (List.map f list)
--
--
--
-- >>> fold (premap Sum Foldl.mconcat) [1..10]
-- Sum {getSum = 55}
--
--
--
-- >>> fold Foldl.mconcat (List.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 FoldM 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
-- | Transforms a Fold into one which ignores elements until they
-- stop satisfying a predicate
--
--
-- fold (predropWhile p folder) list = fold folder (dropWhile p list)
--
--
--
-- >>> fold (predropWhile (>5) Control.Foldl.sum) [10,9,5,9]
-- 14
--
predropWhile :: (a -> Bool) -> Fold a r -> Fold a r
-- | (drop n folder) returns a new Fold that ignores the
-- first n inputs but otherwise behaves the same as the original
-- fold.
--
--
-- fold (drop n folder) list = fold folder (Data.List.genericDrop n list)
--
--
--
-- >>> Foldl.fold (Foldl.drop 3 Foldl.sum) [10, 20, 30, 1, 2, 3]
-- 6
--
--
--
-- >>> Foldl.fold (Foldl.drop 10 Foldl.sum) [10, 20, 30, 1, 2, 3]
-- 0
--
drop :: Natural -> Fold a b -> Fold a b
-- | (dropM n folder) returns a new FoldM that ignores the
-- first n inputs but otherwise behaves the same as the original
-- fold.
--
--
-- foldM (dropM n folder) list = foldM folder (Data.List.genericDrop n list)
--
--
--
-- >>> Foldl.foldM (Foldl.dropM 3 (Foldl.generalize Foldl.sum)) [10, 20, 30, 1, 2, 3]
-- 6
--
--
--
-- >>> Foldl.foldM (Foldl.dropM 10 (Foldl.generalize Foldl.sum)) [10, 20, 30, 1, 2, 3]
-- 0
--
dropM :: Monad m => Natural -> FoldM m a b -> FoldM m a b
-- | 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 Foldl.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) Foldl.sum (Just (2, 3))
-- 5
--
--
--
-- >>> foldOver (_Just . both) Foldl.sum Nothing
-- 0
--
--
--
-- Foldl.foldOver f folder xs == Foldl.fold folder (xs^..f)
--
--
--
-- Foldl.foldOver (folded.f) folder == Foldl.fold (handles f folder)
--
--
--
-- Foldl.foldOver folded == Foldl.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
--
--
-- Foldl.foldOverM (folded.f) folder == Foldl.foldM (handlesM f folder)
--
--
--
-- Foldl.foldOverM folded == Foldl.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) (Foldl.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)
-- | Combine two folds into a fold over inputs for either of them.
either :: Fold a1 b1 -> Fold a2 b2 -> Fold (Either a1 a2) (b1, b2)
-- | Combine two monadic folds into a fold over inputs for either of them.
eitherM :: Monad m => FoldM m a1 b1 -> FoldM m a2 b2 -> FoldM m (Either a1 a2) (b1, b2)
-- | Nest a fold in an applicative.
nest :: Applicative f => Fold a b -> Fold (f a) (f b)
-- | 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 :: Type -> Type)
-- | The Foldable class represents data structures that can be reduced to a
-- summary value one element at a time. Strict left-associative folds are
-- a good fit for space-efficient reduction, while lazy right-associative
-- folds are a good fit for corecursive iteration, or for folds that
-- short-circuit after processing an initial subsequence of the
-- structure's elements.
--
-- Instances can be derived automatically by enabling the
-- DeriveFoldable extension. For example, a derived instance for
-- a binary tree might be:
--
--
-- {-# LANGUAGE DeriveFoldable #-}
-- data Tree a = Empty
-- | Leaf a
-- | Node (Tree a) a (Tree a)
-- deriving Foldable
--
--
-- A more detailed description can be found in the Overview
-- section of Data.Foldable#overview.
--
-- For the class laws see the Laws section of
-- Data.Foldable#laws.
class Foldable (t :: TYPE LiftedRep -> Type)
-- | Mutable v s a is the mutable version of the immutable vector
-- type v a with the state token s. It is injective on
-- GHC 8 and newer.
type family Mutable (v :: Type -> Type) = (mv :: Type -> Type -> Type) | mv -> v
-- | 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 :: Type -> Type) 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.Monad m => Data.Functor.Extend.Extend (Control.Foldl.FoldM m a)
instance GHC.Base.Functor m => Data.Profunctor.Unsafe.Profunctor (Control.Foldl.FoldM m)
instance (GHC.Base.Semigroup b, GHC.Base.Monad m) => GHC.Base.Semigroup (Control.Foldl.FoldM m a b)
instance (GHC.Base.Monoid b, GHC.Base.Monad m) => GHC.Base.Monoid (Control.Foldl.FoldM m a b)
instance (GHC.Base.Monad m, GHC.Num.Num b) => GHC.Num.Num (Control.Foldl.FoldM m a b)
instance (GHC.Base.Monad m, GHC.Real.Fractional b) => GHC.Real.Fractional (Control.Foldl.FoldM m a b)
instance (GHC.Base.Monad m, GHC.Float.Floating b) => GHC.Float.Floating (Control.Foldl.FoldM m a b)
instance GHC.Base.Functor (Control.Foldl.Fold a)
instance Data.Profunctor.Unsafe.Profunctor Control.Foldl.Fold
instance Data.Profunctor.Choice.Choice Control.Foldl.Fold
instance Control.Comonad.Comonad (Control.Foldl.Fold a)
instance GHC.Base.Applicative (Control.Foldl.Fold a)
instance Data.Functor.Extend.Extend (Control.Foldl.Fold a)
instance GHC.Base.Semigroup b => GHC.Base.Semigroup (Control.Foldl.Fold a b)
instance Data.Semigroupoid.Semigroupoid Control.Foldl.Fold
instance GHC.Base.Monoid b => GHC.Base.Monoid (Control.Foldl.Fold a b)
instance GHC.Num.Num b => GHC.Num.Num (Control.Foldl.Fold a b)
instance GHC.Real.Fractional b => GHC.Real.Fractional (Control.Foldl.Fold a b)
instance GHC.Float.Floating b => GHC.Float.Floating (Control.Foldl.Fold a b)
-- | Folds for text streams
module Control.Foldl.Text
-- | Apply a strict left 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
-- | The Foldable class represents data structures that can be reduced to a
-- summary value one element at a time. Strict left-associative folds are
-- a good fit for space-efficient reduction, while lazy right-associative
-- folds are a good fit for corecursive iteration, or for folds that
-- short-circuit after processing an initial subsequence of the
-- structure's elements.
--
-- Instances can be derived automatically by enabling the
-- DeriveFoldable extension. For example, a derived instance for
-- a binary tree might be:
--
--
-- {-# LANGUAGE DeriveFoldable #-}
-- data Tree a = Empty
-- | Leaf a
-- | Node (Tree a) a (Tree a)
-- deriving Foldable
--
--
-- A more detailed description can be found in the Overview
-- section of Data.Foldable#overview.
--
-- For the class laws see the Laws section of
-- Data.Foldable#laws.
class Foldable (t :: TYPE LiftedRep -> Type)
-- | 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 a Fold1 type that is a "non-empty" analog
-- of the Fold 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
-- Control.Foldl module. Instead, this module only provides the
-- utilities which can make use of the non-empty input guarantee (e.g.
-- head). For all other utilities you can convert them from the
-- equivalent Fold using fromFold.
module Control.Foldl.NonEmpty
-- | A Fold1 is like a Fold except that it consumes at least
-- one input element
data Fold1 a b
Fold1 :: (a -> Fold a b) -> Fold1 a b
-- | Apply a strict left Fold1 to a NonEmpty list
fold1 :: Fold1 a b -> NonEmpty a -> b
-- | Promote any Fold to an equivalent Fold1
fromFold :: Fold a b -> Fold1 a b
-- | Fold all values within a non-empty container using (<>)
sconcat :: Semigroup a => Fold1 a a
-- | Get the first element of a non-empty container
head :: Fold1 a a
-- | Get the last element of a non-empty container
last :: Fold1 a a
-- | Computes the maximum element
maximum :: Ord a => Fold1 a a
-- | Computes the maximum element with respect to the given comparison
-- function
maximumBy :: (a -> a -> Ordering) -> Fold1 a a
-- | Computes the minimum element
minimum :: Ord a => Fold1 a a
-- | Computes the minimum element with respect to the given comparison
-- function
minimumBy :: (a -> a -> Ordering) -> Fold1 a a
instance GHC.Base.Functor (Control.Foldl.NonEmpty.Fold1 a)
instance Data.Profunctor.Unsafe.Profunctor Control.Foldl.NonEmpty.Fold1
instance GHC.Base.Applicative (Control.Foldl.NonEmpty.Fold1 a)
instance GHC.Base.Semigroup b => GHC.Base.Semigroup (Control.Foldl.NonEmpty.Fold1 a b)
instance GHC.Base.Monoid b => GHC.Base.Monoid (Control.Foldl.NonEmpty.Fold1 a b)
instance GHC.Num.Num b => GHC.Num.Num (Control.Foldl.NonEmpty.Fold1 a b)
instance GHC.Real.Fractional b => GHC.Real.Fractional (Control.Foldl.NonEmpty.Fold1 a b)
instance GHC.Float.Floating b => GHC.Float.Floating (Control.Foldl.NonEmpty.Fold1 a b)
-- | Folds for byte streams
module Control.Foldl.ByteString
-- | Apply a strict left 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
-- | The Foldable class represents data structures that can be reduced to a
-- summary value one element at a time. Strict left-associative folds are
-- a good fit for space-efficient reduction, while lazy right-associative
-- folds are a good fit for corecursive iteration, or for folds that
-- short-circuit after processing an initial subsequence of the
-- structure's elements.
--
-- Instances can be derived automatically by enabling the
-- DeriveFoldable extension. For example, a derived instance for
-- a binary tree might be:
--
--
-- {-# LANGUAGE DeriveFoldable #-}
-- data Tree a = Empty
-- | Leaf a
-- | Node (Tree a) a (Tree a)
-- deriving Foldable
--
--
-- A more detailed description can be found in the Overview
-- section of Data.Foldable#overview.
--
-- For the class laws see the Laws section of
-- Data.Foldable#laws.
class Foldable (t :: TYPE LiftedRep -> Type)
-- | 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
-- | 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 Scan to a list (or other
-- Traversable structures) from left to right, and scanr to
-- do so from right to left.
--
-- Note that the Scan type does not supersede the Fold type
-- nor does the Fold type supersede the Scan type. Each
-- type has a unique advantage.
--
-- For example, Scans can be chained end-to-end:
--
--
-- (>>>) :: Scan a b -> Scan b c -> Scan a c
--
--
-- In other words, Scan is an instance of the Category
-- typeclass.
--
-- Folds cannot be chained end-to-end
--
-- Vice versa, Folds can produce a result even when fed no input:
--
--
-- extract :: Fold a b -> b
--
--
-- In other words, Fold is an instance of the Comonad
-- typeclass.
--
-- A Scan 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 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)
-- | Like scan but start scanning from the right
scanr :: Traversable t => Scan a b -> t a -> 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 (Control.Scanl.ReverseState s)
instance GHC.Base.Applicative (Control.Scanl.ReverseState s)
instance GHC.Base.Functor m => GHC.Base.Functor (Control.Scanl.ScanM m a)
instance GHC.Base.Applicative m => GHC.Base.Applicative (Control.Scanl.ScanM m a)
instance GHC.Base.Functor m => Data.Profunctor.Unsafe.Profunctor (Control.Scanl.ScanM m)
instance GHC.Base.Monad m => Control.Category.Category (Control.Scanl.ScanM m)
instance GHC.Base.Monad m => Control.Arrow.Arrow (Control.Scanl.ScanM m)
instance (GHC.Base.Monad m, GHC.Base.Semigroup b) => GHC.Base.Semigroup (Control.Scanl.ScanM m a b)
instance (GHC.Base.Monad m, GHC.Base.Monoid b) => GHC.Base.Monoid (Control.Scanl.ScanM m a b)
instance (GHC.Base.Monad m, GHC.Num.Num b) => GHC.Num.Num (Control.Scanl.ScanM m a b)
instance (GHC.Base.Monad m, GHC.Real.Fractional b) => GHC.Real.Fractional (Control.Scanl.ScanM m a b)
instance (GHC.Base.Monad m, GHC.Float.Floating b) => GHC.Float.Floating (Control.Scanl.ScanM m a b)
instance GHC.Base.Functor (Control.Scanl.Scan a)
instance GHC.Base.Applicative (Control.Scanl.Scan a)
instance Data.Profunctor.Unsafe.Profunctor Control.Scanl.Scan
instance Control.Category.Category Control.Scanl.Scan
instance Control.Arrow.Arrow Control.Scanl.Scan
instance GHC.Base.Semigroup b => GHC.Base.Semigroup (Control.Scanl.Scan a b)
instance GHC.Base.Monoid b => GHC.Base.Monoid (Control.Scanl.Scan a b)
instance GHC.Num.Num b => GHC.Num.Num (Control.Scanl.Scan a b)
instance GHC.Real.Fractional b => GHC.Real.Fractional (Control.Scanl.Scan a b)
instance GHC.Float.Floating b => GHC.Float.Floating (Control.Scanl.Scan a b)