Foldable package:base

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.

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

A class of non-empty data structures that can be folded to a summary value.

Non-empty data structures that can be folded.

Bifoldable identifies foldable structures with two different varieties of elements (as opposed to Foldable, which has one variety of element). Common examples are Either and (,):

instance Bifoldable Either where
bifoldMap f _ (Left  a) = f a
bifoldMap _ g (Right b) = g b

instance Bifoldable (,) where
bifoldr f g z (a, b) = f a (g b z)

Some examples below also use the following BiList to showcase empty Bifoldable behaviors when relevant (Either and (,) containing always exactly resp. 1 and 2 elements):

data BiList a b = BiList [a] [b]

instance Bifoldable BiList where
bifoldr f g z (BiList as bs) = foldr f (foldr g z bs) as

A minimal Bifoldable definition consists of either bifoldMap or bifoldr. When defining more than this minimal set, one should ensure that the following identities hold:

bifold ≡ bifoldMap id id
bifoldMap f g ≡ bifoldr (mappend . f) (mappend . g) mempty
bifoldr f g z t ≡ appEndo (bifoldMap (Endo . f) (Endo . g) t) z

If the type is also an instance of Foldable, then it must satisfy (up to laziness):

bifoldl const ≡ foldl
bifoldr (flip const) ≡ foldr
bifoldMap (const mempty) ≡ foldMap

If the type is also a Bifunctor instance, it should satisfy:

bifoldMap f g ≡ bifold . bimap f g

which implies that

bifoldMap f g . bimap h i ≡ bifoldMap (f . h) (g . i)