FoldA package:rio

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.

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