FoldA -package:relude

Branch over a Foldable collection of values.

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.

A container that supports folding with an additional index.

Foldable functions, with wrappers like the Safe module.

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.

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

length = getSum . foldMap (Sum . const  1)

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)

Re-exports a subset of the Data.Foldable1 module along with some additional combinators that require Foldable1 constraints.

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.

A container that supports folding with an additional index.

A non-empty container that supports folding with an additional index.

This is the primary class for structures that are to be considered foldable. A minimum complete definition provides foldl and foldr. Instances of FoldableLL can be folded, and can be many and varied. These functions are used heavily in Data.ListLike.

Generic tools for data structures that can be folded. Written by John Goerzen, jgoerzen@complete.org

Foldable types. A minimal implementation of this interface is given by either FoldMap or Foldr, but a default still needs to be given explicitly for the other.

data MyType a = ... {- Some custom Foldable type -}

-- Method 1: Implement Foldr, default FoldMap.
type instance Eval (Foldr f y xs) = ... {- Explicit implementation -}
type instance Eval (FoldMap f xs) = FoldMapDefault_ f xs {- Default -}

-- Method 2: Implement FoldMap, default Foldr.
type instance Eval (FoldMap f xs) = ... {- Explicit implementation -}
type instance Eval (Foldr f y xs) = FoldrDefault_ f y xs {- Default -}

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)