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.

Like Fold, but monadic.

A 'FoldM m a b' processes elements of type a and results in a monadic value of type m b.

Apply a strict left Fold to a Foldable container

Like fold, but monadic

Convert a strict left Fold into a scan

>>> Foldl.scan Foldl.length [1..5][0,1,2,3,4,5]

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]

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]

Fold all values within a container using mappend and mempty

Convert a "foldMap" to a Fold

Get the first element of a container or return Nothing if the container is empty

Get the last element of a container or return Nothing if the container is empty

Get the last element of a container or return a default value if the container is empty

Return the last N elements

Returns True if the container is empty, False otherwise

Return the length of the container

Returns True if all elements are True, False otherwise

Returns True if any element is True, False otherwise

(all predicate) returns True if all elements satisfy the predicate, False otherwise

(any predicate) returns True if any element satisfies the predicate, False otherwise

Computes the sum of all elements

Computes the product of all elements

Compute a numerically stable arithmetic mean of all elements

Compute a numerically stable (population) variance over all elements

Compute a numerically stable (population) standard deviation over all elements

Computes the maximum element

Computes the maximum element with respect to the given comparison function

Computes the minimum element

Computes the minimum element with respect to the given comparison function

(elem a) returns True if the container has an element equal to a, False otherwise

(notElem a) returns False if the container has an element equal to a, True otherwise

(find predicate) returns the first element that satisfies the predicate or Nothing if no element satisfies the predicate

(index n) returns the nth element of the container, or Nothing if the container has an insufficient number of elements

(lookup a) returns the element paired with the first matching item, or Nothing if none matches

(elemIndex a) returns the index of the first element that equals a, or Nothing if no element matches

(findIndex predicate) returns the index of the first element that satisfies the predicate, or Nothing if no element satisfies the predicate

Pick a random element, using reservoir sampling

Pick several random elements, using reservoir sampling

Converts an effectful function to a fold. Specialized version of sink.

Converts an effectful function to a fold

sink (f <> g) = sink f <> sink g -- if `(<>)` is commutative
sink mempty = mempty

Upgrade a fold to accept the Fold type

Upgrade a more traditional fold to accept the Fold type

Upgrade a monadic fold to accept the FoldM type

Upgrade a more traditional monadic fold to accept the FoldM type

Generalize a Fold to a FoldM

generalize (pure r) = pure r

generalize (f <*> x) = generalize f <*> generalize x

Simplify a pure FoldM to a Fold

simplify (pure r) = pure r

simplify (f <*> x) = simplify f <*> simplify x

Lift a monadic value to a FoldM; works like lift.

lifts . pure = pure

Shift a FoldM from one monad to another with a morphism such as lift or liftIO; the effect is the same as hoist.

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.

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

(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

(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

(postmapM f folder) returns a new FoldM where f is applied to the final value.

postmapM pure = id

postmapM (f >=> g) = postmapM g . postmapM f

postmapM k (pure r) = lifts (k 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

(prefilterM f folder) returns a new FoldM where the folder's input is used only when the input satisfies a monadic predicate f.

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

(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

(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

A handler for the upstream input of a Fold

Any lens, traversal, or prism will type-check as a Handler

(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

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

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

A Handler for the upstream input of FoldM

Any lens, traversal, or prism will type-check as a HandlerM

(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

(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

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.

Combine two folds into a fold over inputs for either of them.

Combine two monadic folds into a fold over inputs for either of them.

Nest a fold in an applicative.

Class of monads which can perform primitive state-transformer actions.

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

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.