Data.Foldable (original) (raw)

Folds

class Foldable t whereSource

Data structures that can be folded.

Minimal complete definition: [foldMap](Data-Foldable.html#v:foldMap) or [foldr](Data-Foldable.html#v:foldr).

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

Methods

fold :: Monoid m => t m -> mSource

Combine the elements of a structure using a monoid.

foldMap :: Monoid m => (a -> m) -> t a -> mSource

Map each element of the structure to a monoid, and combine the results.

foldr :: (a -> b -> b) -> b -> t a -> bSource

foldr' :: (a -> b -> b) -> b -> t a -> bSource

Right-associative fold of a structure, but with strict application of the operator.

foldl :: (a -> b -> a) -> a -> t b -> aSource

foldl' :: (a -> b -> a) -> a -> t b -> aSource

Left-associative fold of a structure. but with strict application of the operator.

[foldl](Data-Foldable.html#v:foldl) f z = [foldl'](Data-List.html#v:foldl-39-) f z . [toList](Data-Foldable.html#v:toList)

foldr1 :: (a -> a -> a) -> t a -> aSource

A variant of [foldr](Data-Foldable.html#v:foldr) that has no base case, and thus may only be applied to non-empty structures.

[foldr1](Data-Foldable.html#v:foldr1) f = [foldr1](Data-List.html#v:foldr1) f . [toList](Data-Foldable.html#v:toList)

foldl1 :: (a -> a -> a) -> t a -> aSource

A variant of [foldl](Data-Foldable.html#v:foldl) that has no base case, and thus may only be applied to non-empty structures.

[foldl1](Data-Foldable.html#v:foldl1) f = [foldl1](Data-List.html#v:foldl1) f . [toList](Data-Foldable.html#v:toList)

Special biased folds

foldrM :: (Foldable t, Monad m) => (a -> b -> m b) -> b -> t a -> m bSource

Monadic fold over the elements of a structure, associating to the right, i.e. from right to left.

foldlM :: (Foldable t, Monad m) => (a -> b -> m a) -> a -> t b -> m aSource

Monadic fold over the elements of a structure, associating to the left, i.e. from left to right.

Folding actions

Applicative actions

traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f ()Source

Map each element of a structure to an action, evaluate these actions from left to right, and ignore the results.

Monadic actions

mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m ()Source

Map each element of a structure to a monadic action, evaluate these actions from left to right, and ignore the results.

sequence_ :: (Foldable t, Monad m) => t (m a) -> m ()Source

Evaluate each monadic action in the structure from left to right, and ignore the results.

Specialized folds

concat :: Foldable t => t [a] -> [a]Source

The concatenation of all the elements of a container of lists.

concatMap :: Foldable t => (a -> [b]) -> t a -> [b]Source

Map a function over all the elements of a container and concatenate the resulting lists.

and :: Foldable t => t Bool -> BoolSource

[and](Data-Foldable.html#v:and) returns the conjunction of a container of Bools. For the result to be [True](Data-Bool.html#v:True), the container must be finite; [False](Data-Bool.html#v:False), however, results from a [False](Data-Bool.html#v:False) value finitely far from the left end.

or :: Foldable t => t Bool -> BoolSource

[or](Data-Foldable.html#v:or) returns the disjunction of a container of Bools. For the result to be [False](Data-Bool.html#v:False), the container must be finite; [True](Data-Bool.html#v:True), however, results from a [True](Data-Bool.html#v:True) value finitely far from the left end.

any :: Foldable t => (a -> Bool) -> t a -> BoolSource

Determines whether any element of the structure satisfies the predicate.

maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> aSource

The largest element of a non-empty structure with respect to the given comparison function.

Searches

find :: Foldable t => (a -> Bool) -> t a -> Maybe aSource

The [find](Data-Foldable.html#v:find) function takes a predicate and a structure and returns the leftmost element of the structure matching the predicate, or[Nothing](Data-Maybe.html#v:Nothing) if there is no such element.