Data.Collections.Foldable

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

Folds

class Foldable t a | t -> a where

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.

Methods

fold :: Monoid a => t -> a

Combine the elements of a structure using a monoid.

foldMap :: Monoid m => (a -> m) -> t -> m

Map each element of the structure to a monoid, and combine the results.

foldr :: (a -> b -> b) -> b -> t -> b

Right-associative fold of a structure.

foldr f z = foldr f z . toList

foldl :: (b -> a -> b) -> b -> t -> b

Left-associative fold of a structure.

foldl f z = foldl f z . toList

foldr1 :: (a -> a -> a) -> t -> a

A variant of foldr that has no base case, and thus may only be applied to non-empty structures.

foldr1 f = foldr1 f . toList

foldl1 :: (a -> a -> a) -> t -> a

A variant of foldl that has no base case, and thus may only be applied to non-empty structures.

foldl1 f = foldl1 f . toList

null :: t -> Bool

Tells whether the structure is empty.

size :: t -> Int

Returns the size of the structure.

isSingleton :: t -> Bool

Tells whether the structure contains a single element.

Instances

Foldable ByteString Word8

Foldable ByteString Word8

Foldable IntSet Int

Foldable [a] a

Foldable (Maybe a) a

Foldable (Set a) a

Foldable (Seq a) a

Enum a => Foldable (Set a) a

Foldable (Set a) a

Foldable (SetList [a]) a

Foldable (IntMap a) (Int, a)

Ix i => Foldable (Array i a) (i, a)

Foldable (Map k a) (k, a)

Foldable (Map k a) (k, a)

Foldable m (k, v) => Foldable (ElemsView m k v) v

Foldable m (k, v) => Foldable (KeysView m k v) k

Sequence c (k, v) => Foldable (AssocList c k v) (k, v)

Sequence s k => Foldable (Trie s k v) (s, v)

Special biased folds

foldr' :: Foldable t a => (a -> b -> b) -> b -> t -> b

Fold over the elements of a structure, associating to the right, but strictly.

foldl' :: Foldable t b => (a -> b -> a) -> a -> t -> a

Fold over the elements of a structure, associating to the left, but strictly.

foldrM :: (Foldable t a, Monad m) => (a -> b -> m b) -> b -> t -> m b

Monadic fold over the elements of a structure, associating to the right, i.e. from right to left.

foldlM :: (Foldable t b, Monad m) => (a -> b -> m a) -> a -> t -> m a

Monadic fold over the elements of a structure, associating to the left, i.e. from left to right.

Folding actions

Applicative actions

traverse_ :: (Foldable t a, Applicative f) => (a -> f b) -> t -> f ()

Map each element of a structure to an action, evaluate these actions from left to right, and ignore the results.

for_ :: (Foldable t a, Applicative f) => t -> (a -> f b) -> f ()

for_ is traverse_ with its arguments flipped.

sequenceA_ :: forall f a t. (Foldable t (f a), Applicative f) => t -> f ()

Evaluate each action in the structure from left to right, and ignore the results.

asum :: (Foldable t (f a), Alternative f) => t -> f a

The sum of a collection of actions, generalizing concat.

Monadic actions

mapM_ :: (Foldable t a, Monad m) => (a -> m b) -> t -> m ()

Map each element of a structure to a monadic action, evaluate these actions from left to right, and ignore the results.

forM_ :: (Foldable t a, Monad m) => t -> (a -> m b) -> m ()

forM_ is mapM_ with its arguments flipped.

sequence_ :: forall m a t. (Foldable t (m a), Monad m) => t -> m ()

Evaluate each monadic action in the structure from left to right, and ignore the results.

msum :: (Foldable t (m a), MonadPlus m) => t -> m a

The sum of a collection of actions, generalizing concat.

Specialized folds

toList :: Foldable t a => t -> [a]

List of elements of a structure.

and :: Foldable t Bool => t -> Bool

and returns the conjunction of a container of Bools. For the result to be True, the container must be finite; False, however, results from a False value finitely far from the left end.

or :: Foldable t Bool => t -> Bool

or returns the disjunction of a container of Bools. For the result to be False, the container must be finite; True, however, results from a True value finitely far from the left end.

any :: Foldable t a => (a -> Bool) -> t -> Bool

Determines whether any element of the structure satisfies the predicate.

all :: Foldable t a => (a -> Bool) -> t -> Bool

Determines whether all elements of the structure satisfy the predicate.

sum :: (Foldable t a, Num a) => t -> a

The sum function computes the sum of the numbers of a structure.

product :: (Foldable t a, Num a) => t -> a

The product function computes the product of the numbers of a structure.

maximum :: (Foldable t a, Ord a) => t -> a

The largest element of the structure.

maximumBy :: Foldable t a => (a -> a -> Ordering) -> t -> a

The largest element of a non-empty structure with respect to the given comparison function.

minimum :: (Foldable t a, Ord a) => t -> a

The least element of a non-null structure.

minimumBy :: Foldable t a => (a -> a -> Ordering) -> t -> a

The least element of a non-empty structure with respect to the given comparison function.

Searches

elem :: (Foldable t a, Eq a) => a -> t -> Bool

Does the element occur in the structure?

notElem :: (Foldable t a, Eq a) => a -> t -> Bool

notElem is the negation of elem.

find :: Foldable t a => (a -> Bool) -> t -> Maybe a

The find function takes a predicate and a structure and returns the leftmost element of the structure matching the predicate, or Nothing if there is no such element.