Foldable -is: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.

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)

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

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)

Give the ability to fold a collection on itself

Equivalent of Foldable for rank 2 data types

Foldable class, generalised to use arrows in categories other than ->. This changes the interface somewhat – in particular, foldr relies on currying and hence can't really be expressed in a category without exponential objects; however the monoidal folds come out quite nicely. (Of course, it's debatable how much sense the Hask-Monoid class even makes in other categories.) Unlike with the Functor classes, there is no derived instance Foldable f => Foldable f (->) (->): in this case, it would prevent some genarality. See below for how to define such an instance manually.

Encode a Foldable as a JSON array.

Note that foldable doesn't check the strictness of foldl', foldr' and foldMap'.

Construct from any foldable

Construct from any foldable

Construct from any foldable

Non-empty data structures that can be folded.

A container that supports folding with an additional index.

The class of foldable data structures that cannot be empty.

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.

This is a generalization of the Foldable class to structures over parameterized terms.

This is a generalization of the Foldable class to structures over parameterized terms.