Copyright | Ross Paterson 2005 |
---|---|

License | BSD-style (see the LICENSE file in the distribution) |

Maintainer | [email protected] |

Stability | experimental |

Portability | portable |

Safe Haskell | Trustworthy |

Language | Haskell2010 |

Class of data structures that can be folded to a summary value.

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

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

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

Combine the elements of a structure using a monoid.

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

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

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

Right-associative fold of a structure.

`foldr`

f z =`foldr`

f z .`toList`

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

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

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

Left-associative fold of a structure.

`foldl`

f z =`foldl`

f z .`toList`

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

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

`foldl`

f z =`foldl'`

f z .`toList`

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

A variant of `foldr`

that has no base case, and thus may only be applied to non-empty structures.

`foldr1`

f =`foldr1`

f .`toList`

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

A variant of `foldl`

that has no base case, and thus may only be applied to non-empty structures.

`foldl1`

f =`foldl1`

f .`toList`

List of elements of a structure, from left to right.

Test whether the structure is empty. The default implementation is optimized for structures that are similar to cons-lists, because there is no general way to do better.

Returns the size/length of a finite structure as an `Int`

. The default implementation is optimized for structures that are similar to cons-lists, because there is no general way to do better.

elem :: Eq a => a -> t a -> Bool infix 4 Source

Does the element occur in the structure?

maximum :: forall a. Ord a => t a -> a Source

The largest element of a non-empty structure.

minimum :: forall a. Ord a => t a -> a Source

The least element of a non-empty structure.

sum :: Num a => t a -> a Source

The `sum`

function computes the sum of the numbers of a structure.

product :: Num a => t a -> a Source

The `product`

function computes the product of the numbers of a structure.

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

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

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

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

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. For a version that doesn't ignore the results see `traverse`

.

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

`for_`

is `traverse_`

with its arguments flipped. For a version that doesn't ignore the results see `for`

.

`>>>`

1 2 3 4`for_ [1..4] print`

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

Evaluate each action in the structure from left to right, and ignore the results. For a version that doesn't ignore the results see `sequenceA`

.

asum :: (Foldable t, Alternative f) => t (f a) -> f a Source

The sum of a collection of actions, generalizing `concat`

.

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. For a version that doesn't ignore the results see `mapM`

.

As of base 4.8.0.0, `mapM_`

is just `traverse_`

, specialized to `Monad`

.

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

`forM_`

is `mapM_`

with its arguments flipped. For a version that doesn't ignore the results see `forM`

.

As of base 4.8.0.0, `forM_`

is just `for_`

, specialized to `Monad`

.

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. For a version that doesn't ignore the results see `sequence`

.

As of base 4.8.0.0, `sequence_`

is just `sequenceA_`

, specialized to `Monad`

.

msum :: (Foldable t, MonadPlus m) => t (m a) -> m a Source

The sum of a collection of actions, generalizing `concat`

. As of base 4.8.0.0, `msum`

is just `asum`

, specialized to `MonadPlus`

.

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

`and`

returns the conjunction of a container of Bools. For the result to be `True`

, the container must be finite; `False`

, however, results from a `False`

value finitely far from the left end.

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

`or`

returns the disjunction of a container of Bools. For the result to be `False`

, the container must be finite; `True`

, however, results from a `True`

value finitely far from the left end.

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

Determines whether any element of the structure satisfies the predicate.

all :: Foldable t => (a -> Bool) -> t a -> Bool Source

Determines whether all elements of the structure satisfy the predicate.

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

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

minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a Source

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

notElem :: (Foldable t, Eq a) => a -> t a -> Bool infix 4 Source

`notElem`

is the negation of `elem`

.

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

The `find`

function takes a predicate and a structure and returns the leftmost element of the structure matching the predicate, or `Nothing`

if there is no such element.

© The University of Glasgow and others

Licensed under a BSD-style license (see top of the page).

https://downloads.haskell.org/~ghc/7.10.3/docs/html/libraries/base-4.8.2.0/Data-Foldable.html