Class of data structures that can be folded to a summary value.
Many of these functions generalize Prelude, Control.Monad and Data.List functions of the same names from lists to any Foldable functor. To avoid ambiguity, either import those modules hiding these names or qualify uses of these function names with an alias for this module.

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