Safe Haskell | Safe-Inferred |
---|---|

Language | Haskell98 |

- class Foldable t where

# Documentation

class Foldable t where

Data structures that can be folded.

Minimal complete definition: `foldMap`

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

Combine the elements of a structure using a monoid.

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

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

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

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

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

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

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

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

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