base-4.15.0.0: Basic libraries

Data.Foldable

Description

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

Synopsis

# Documentation

class Foldable t where Source #

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.

Minimal complete definition

Methods

fold :: Monoid m => t m -> m Source #

Given a structure with elements whose type is a Monoid, combine them via the monoid's (<>) operator. This fold is right-associative and lazy in the accumulator. When you need a strict left-associative fold, use foldMap instead, with id as the map.

#### Examples

Expand

Basic usage:

>>> fold [[1, 2, 3], [4, 5], [6], []]
[1,2,3,4,5,6]

>>> fold $Node (Leaf (Sum 1)) (Sum 3) (Leaf (Sum 5)) Sum {getSum = 9}  Folds of unbounded structures do not terminate when the monoid's (<>) operator is strict: >>> fold (repeat Nothing) * Hangs forever *  Lazy corecursive folds of unbounded structures are fine: >>> take 12$ fold $map (\i -> [i..i+2]) [0..] [0,1,2,1,2,3,2,3,4,3,4,5] >>> sum$ take 4000000 $fold$ map (\i -> [i..i+2]) [0..]
2666668666666


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

Map each element of the structure into a monoid, and combine the results with (<>). This fold is right-associative and lazy in the accumulator. For strict left-associative folds consider foldMap instead.

#### Examples

Expand

Basic usage:

>>> foldMap Sum [1, 3, 5]
Sum {getSum = 9}

>>> foldMap Product [1, 3, 5]
Product {getProduct = 15}

>>> foldMap (replicate 3) [1, 2, 3]
[1,1,1,2,2,2,3,3,3]


When a Monoid's (<>) is lazy in its second argument, foldMap can return a result even from an unbounded structure. For example, lazy accumulation enables Data.ByteString.Builder to efficiently serialise large data structures and produce the output incrementally:

>>> import qualified Data.ByteString.Lazy as L
>>> import qualified Data.ByteString.Builder as B
>>> let bld :: Int -> B.Builder; bld i = B.intDec i <> B.word8 0x20
>>> let lbs = B.toLazyByteString $foldMap bld [0..] >>> L.take 64 lbs "0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24"  foldMap' :: Monoid m => (a -> m) -> t a -> m Source # A left-associative variant of foldMap that is strict in the accumulator. Use this method for strict reduction when partial results are merged via (<>). #### Examples Expand Define a Monoid over finite bit strings under xor. Use it to strictly compute the xor of a list of Int values. >>> :set -XGeneralizedNewtypeDeriving >>> import Data.Bits (Bits, FiniteBits, xor, zeroBits) >>> import Data.Foldable (foldMap') >>> import Numeric (showHex) >>>  >>> newtype X a = X a deriving (Eq, Bounded, Enum, Bits, FiniteBits) >>> instance Bits a => Semigroup (X a) where X a <> X b = X (a xor b) >>> instance Bits a => Monoid (X a) where mempty = X zeroBits >>>  >>> let bits :: [Int]; bits = [0xcafe, 0xfeed, 0xdeaf, 0xbeef, 0x5411] >>> (\ (X a) -> showString "0x" . showHex a$ "") $foldMap' X bits "0x42"  Since: base-4.13.0.0 foldr :: (a -> b -> b) -> b -> t a -> b Source # Right-associative fold of a structure, lazy in the accumulator. In the case of lists, foldr, when applied to a binary operator, a starting value (typically the right-identity of the operator), and a list, reduces the list using the binary operator, from right to left: foldr f z [x1, x2, ..., xn] == x1 f (x2 f ... (xn f z)...) Note that since the head of the resulting expression is produced by an application of the operator to the first element of the list, given an operator lazy in its right argument, foldr can produce a terminating expression from an unbounded list. For a general Foldable structure this should be semantically identical to, foldr f z = foldr f z . toList #### Examples Expand Basic usage: >>> foldr (||) False [False, True, False] True  >>> foldr (||) False [] False  >>> foldr (\c acc -> acc ++ [c]) "foo" ['a', 'b', 'c', 'd'] "foodcba"  ##### Infinite structures ⚠️ Applying foldr to infinite structures usually doesn't terminate. It may still terminate under one of the following conditions: • the folding function is short-circuiting • the folding function is lazy on its second argument ###### Short-circuiting (||) short-circuits on True values, so the following terminates because there is a True value finitely far from the left side: >>> foldr (||) False (True : repeat False) True  But the following doesn't terminate: >>> foldr (||) False (repeat False ++ [True]) * Hangs forever *  ###### Laziness in the second argument Applying foldr to infinite structures terminates when the operator is lazy in its second argument (the initial accumulator is never used in this case, and so could be left undefined, but [] is more clear): >>> take 5$ foldr (\i acc -> i : fmap (+3) acc) [] (repeat 1)
[1,4,7,10,13]


foldr' :: (a -> b -> b) -> b -> t a -> b Source #

Right-associative fold of a structure, strict in the accumulator. This is rarely what you want.

Since: base-4.6.0.0

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

Left-associative fold of a structure, lazy in the accumulator. This is rarely what you want, but can work well for structures with efficient right-to-left sequencing and an operator that is lazy in its left argument.

In the case of lists, foldl, when applied to a binary operator, a starting value (typically the left-identity of the operator), and a list, reduces the list using the binary operator, from left to right:

foldl f z [x1, x2, ..., xn] == (...((z f x1) f x2) f...) f xn

Note that to produce the outermost application of the operator the entire input list must be traversed. Like all left-associative folds, foldl will diverge if given an infinite list.

If you want an efficient strict left-fold, you probably want to use foldl instead of foldl. The reason for this is that the latter does not force the inner results (e.g. z f x1 in the above example) before applying them to the operator (e.g. to (f x2)). This results in a thunk chain $$\mathcal{O}(n)$$ elements long, which then must be evaluated from the outside-in.

For a general Foldable structure this should be semantically identical to:

foldl f z = foldl f z . toList

#### Examples

Expand

The first example is a strict fold, which in practice is best performed with foldl.

>>> foldl (+) 42 [1,2,3,4]
52


Though the result below is lazy, the input is reversed before prepending it to the initial accumulator, so corecursion begins only after traversing the entire input string.

>>> foldl (\acc c -> c : acc) "abcd" "efgh"
"hgfeabcd"


A left fold of a structure that is infinite on the right cannot terminate, even when for any finite input the fold just returns the initial accumulator:

>>> foldl (\a _ -> a) 0 $repeat 1 * Hangs forever *  foldl' :: (b -> a -> b) -> b -> t a -> b Source # Left-associative fold of a structure but with strict application of the operator. This ensures that each step of the fold is forced to Weak Head Normal Form before being applied, avoiding the collection of thunks that would otherwise occur. This is often what you want to strictly reduce a finite structure to a single strict result (e.g. sum). For a general Foldable structure this should be semantically identical to, foldl' f z = foldl' f z . toList Since: base-4.6.0.0 foldr1 :: (a -> a -> a) -> t a -> a Source # A variant of foldr that has no base case, and thus may only be applied to non-empty structures. This function is non-total and will raise a runtime exception if the structure happens to be empty. #### Examples Expand Basic usage: >>> foldr1 (+) [1..4] 10  >>> foldr1 (+) [] Exception: Prelude.foldr1: empty list  >>> foldr1 (+) Nothing *** Exception: foldr1: empty structure  >>> foldr1 (-) [1..4] -2  >>> foldr1 (&&) [True, False, True, True] False  >>> foldr1 (||) [False, False, True, True] True  >>> foldr1 (+) [1..] * Hangs forever *  foldl1 :: (a -> a -> a) -> t a -> a Source # A variant of foldl that has no base case, and thus may only be applied to non-empty structures. This function is non-total and will raise a runtime exception if the structure happens to be empty. foldl1 f = foldl1 f . toList #### Examples Expand Basic usage: >>> foldl1 (+) [1..4] 10  >>> foldl1 (+) [] *** Exception: Prelude.foldl1: empty list  >>> foldl1 (+) Nothing *** Exception: foldl1: empty structure  >>> foldl1 (-) [1..4] -8  >>> foldl1 (&&) [True, False, True, True] False  >>> foldl1 (||) [False, False, True, True] True  >>> foldl1 (+) [1..] * Hangs forever *  toList :: t a -> [a] Source # List of elements of a structure, from left to right. If the entire list is intended to be reduced via a fold, just fold the structure directly bypassing the list. #### Examples Expand Basic usage: >>> toList Nothing []  >>> toList (Just 42) [42]  >>> toList (Left "foo") []  >>> toList (Node (Leaf 5) 17 (Node Empty 12 (Leaf 8))) [5,17,12,8]  For lists, toList is the identity: >>> toList [1, 2, 3] [1,2,3]  Since: base-4.8.0.0 null :: t a -> Bool Source # Test whether the structure is empty. The default implementation is Left-associative and lazy in both the initial element and the accumulator. Thus optimised for structures where the first element can be accessed in constant time. Structures where this is not the case should have a non-default implementation. #### Examples Expand Basic usage: >>> null [] True  >>> null [1] False  null is expected to terminate even for infinite structures. The default implementation terminates provided the structure is bounded on the left (there is a left-most element). >>> null [1..] False  Since: base-4.8.0.0 length :: t a -> Int Source # Returns the size/length of a finite structure as an Int. The default implementation just counts elements starting with the left-most. Instances for structures that can compute the element count faster than via element-by-element counting, should provide a specialised implementation. #### Examples Expand Basic usage: >>> length [] 0  >>> length ['a', 'b', 'c'] 3 >>> length [1..] * Hangs forever *  Since: base-4.8.0.0 elem :: Eq a => a -> t a -> Bool infix 4 Source # Does the element occur in the structure? Note: elem is often used in infix form. #### Examples Expand Basic usage: >>> 3 elem [] False  >>> 3 elem [1,2] False  >>> 3 elem [1,2,3,4,5] True  For infinite structures, the default implementation of elem terminates if the sought-after value exists at a finite distance from the left side of the structure: >>> 3 elem [1..] True  >>> 3 elem ([4..] ++ [3]) * Hangs forever *  Since: base-4.8.0.0 maximum :: forall a. Ord a => t a -> a Source # The largest element of a non-empty structure. This function is non-total and will raise a runtime exception if the structure happens to be empty. A structure that supports random access and maintains its elements in order should provide a specialised implementation to return the maximum in faster than linear time. #### Examples Expand Basic usage: >>> maximum [1..10] 10  >>> maximum [] *** Exception: Prelude.maximum: empty list  >>> maximum Nothing *** Exception: maximum: empty structure  Since: base-4.8.0.0 minimum :: forall a. Ord a => t a -> a Source # The least element of a non-empty structure. This function is non-total and will raise a runtime exception if the structure happens to be empty A structure that supports random access and maintains its elements in order should provide a specialised implementation to return the minimum in faster than linear time. #### Examples Expand Basic usage: >>> minimum [1..10] 1  >>> minimum [] *** Exception: Prelude.minimum: empty list  >>> minimum Nothing *** Exception: minimum: empty structure  Since: base-4.8.0.0 sum :: Num a => t a -> a Source # The sum function computes the sum of the numbers of a structure. #### Examples Expand Basic usage: >>> sum [] 0  >>> sum [42] 42  >>> sum [1..10] 55  >>> sum [4.1, 2.0, 1.7] 7.8  >>> sum [1..] * Hangs forever *  Since: base-4.8.0.0 product :: Num a => t a -> a Source # The product function computes the product of the numbers of a structure. #### Examples Expand Basic usage: >>> product [] 1  >>> product [42] 42  >>> product [1..10] 3628800  >>> product [4.1, 2.0, 1.7] 13.939999999999998  >>> product [1..] * Hangs forever *  Since: base-4.8.0.0 #### Instances Instances details  Foldable [] # Since: base-2.1 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => [m] -> m Source #foldMap :: Monoid m => (a -> m) -> [a] -> m Source #foldMap' :: Monoid m => (a -> m) -> [a] -> m Source #foldr :: (a -> b -> b) -> b -> [a] -> b Source #foldr' :: (a -> b -> b) -> b -> [a] -> b Source #foldl :: (b -> a -> b) -> b -> [a] -> b Source #foldl' :: (b -> a -> b) -> b -> [a] -> b Source #foldr1 :: (a -> a -> a) -> [a] -> a Source #foldl1 :: (a -> a -> a) -> [a] -> a Source #toList :: [a] -> [a] Source #null :: [a] -> Bool Source #length :: [a] -> Int Source #elem :: Eq a => a -> [a] -> Bool Source #maximum :: Ord a => [a] -> a Source #minimum :: Ord a => [a] -> a Source #sum :: Num a => [a] -> a Source #product :: Num a => [a] -> a Source # # Since: base-2.1 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => Maybe m -> m Source #foldMap :: Monoid m => (a -> m) -> Maybe a -> m Source #foldMap' :: Monoid m => (a -> m) -> Maybe a -> m Source #foldr :: (a -> b -> b) -> b -> Maybe a -> b Source #foldr' :: (a -> b -> b) -> b -> Maybe a -> b Source #foldl :: (b -> a -> b) -> b -> Maybe a -> b Source #foldl' :: (b -> a -> b) -> b -> Maybe a -> b Source #foldr1 :: (a -> a -> a) -> Maybe a -> a Source #foldl1 :: (a -> a -> a) -> Maybe a -> a Source #toList :: Maybe a -> [a] Source #null :: Maybe a -> Bool Source #length :: Maybe a -> Int Source #elem :: Eq a => a -> Maybe a -> Bool Source #maximum :: Ord a => Maybe a -> a Source #minimum :: Ord a => Maybe a -> a Source #sum :: Num a => Maybe a -> a Source #product :: Num a => Maybe a -> a Source # # Since: base-4.9.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => Par1 m -> m Source #foldMap :: Monoid m => (a -> m) -> Par1 a -> m Source #foldMap' :: Monoid m => (a -> m) -> Par1 a -> m Source #foldr :: (a -> b -> b) -> b -> Par1 a -> b Source #foldr' :: (a -> b -> b) -> b -> Par1 a -> b Source #foldl :: (b -> a -> b) -> b -> Par1 a -> b Source #foldl' :: (b -> a -> b) -> b -> Par1 a -> b Source #foldr1 :: (a -> a -> a) -> Par1 a -> a Source #foldl1 :: (a -> a -> a) -> Par1 a -> a Source #toList :: Par1 a -> [a] Source #null :: Par1 a -> Bool Source #length :: Par1 a -> Int Source #elem :: Eq a => a -> Par1 a -> Bool Source #maximum :: Ord a => Par1 a -> a Source #minimum :: Ord a => Par1 a -> a Source #sum :: Num a => Par1 a -> a Source #product :: Num a => Par1 a -> a Source # # Since: base-4.15 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => Solo m -> m Source #foldMap :: Monoid m => (a -> m) -> Solo a -> m Source #foldMap' :: Monoid m => (a -> m) -> Solo a -> m Source #foldr :: (a -> b -> b) -> b -> Solo a -> b Source #foldr' :: (a -> b -> b) -> b -> Solo a -> b Source #foldl :: (b -> a -> b) -> b -> Solo a -> b Source #foldl' :: (b -> a -> b) -> b -> Solo a -> b Source #foldr1 :: (a -> a -> a) -> Solo a -> a Source #foldl1 :: (a -> a -> a) -> Solo a -> a Source #toList :: Solo a -> [a] Source #null :: Solo a -> Bool Source #length :: Solo a -> Int Source #elem :: Eq a => a -> Solo a -> Bool Source #maximum :: Ord a => Solo a -> a Source #minimum :: Ord a => Solo a -> a Source #sum :: Num a => Solo a -> a Source #product :: Num a => Solo a -> a Source # # Since: base-4.9.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => NonEmpty m -> m Source #foldMap :: Monoid m => (a -> m) -> NonEmpty a -> m Source #foldMap' :: Monoid m => (a -> m) -> NonEmpty a -> m Source #foldr :: (a -> b -> b) -> b -> NonEmpty a -> b Source #foldr' :: (a -> b -> b) -> b -> NonEmpty a -> b Source #foldl :: (b -> a -> b) -> b -> NonEmpty a -> b Source #foldl' :: (b -> a -> b) -> b -> NonEmpty a -> b Source #foldr1 :: (a -> a -> a) -> NonEmpty a -> a Source #foldl1 :: (a -> a -> a) -> NonEmpty a -> a Source #toList :: NonEmpty a -> [a] Source #null :: NonEmpty a -> Bool Source #length :: NonEmpty a -> Int Source #elem :: Eq a => a -> NonEmpty a -> Bool Source #maximum :: Ord a => NonEmpty a -> a Source #minimum :: Ord a => NonEmpty a -> a Source #sum :: Num a => NonEmpty a -> a Source #product :: Num a => NonEmpty a -> a Source # # Since: base-4.12.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => Down m -> m Source #foldMap :: Monoid m => (a -> m) -> Down a -> m Source #foldMap' :: Monoid m => (a -> m) -> Down a -> m Source #foldr :: (a -> b -> b) -> b -> Down a -> b Source #foldr' :: (a -> b -> b) -> b -> Down a -> b Source #foldl :: (b -> a -> b) -> b -> Down a -> b Source #foldl' :: (b -> a -> b) -> b -> Down a -> b Source #foldr1 :: (a -> a -> a) -> Down a -> a Source #foldl1 :: (a -> a -> a) -> Down a -> a Source #toList :: Down a -> [a] Source #null :: Down a -> Bool Source #length :: Down a -> Int Source #elem :: Eq a => a -> Down a -> Bool Source #maximum :: Ord a => Down a -> a Source #minimum :: Ord a => Down a -> a Source #sum :: Num a => Down a -> a Source #product :: Num a => Down a -> a Source # # Since: base-4.8.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => Product m -> m Source #foldMap :: Monoid m => (a -> m) -> Product a -> m Source #foldMap' :: Monoid m => (a -> m) -> Product a -> m Source #foldr :: (a -> b -> b) -> b -> Product a -> b Source #foldr' :: (a -> b -> b) -> b -> Product a -> b Source #foldl :: (b -> a -> b) -> b -> Product a -> b Source #foldl' :: (b -> a -> b) -> b -> Product a -> b Source #foldr1 :: (a -> a -> a) -> Product a -> a Source #foldl1 :: (a -> a -> a) -> Product a -> a Source #toList :: Product a -> [a] Source #null :: Product a -> Bool Source #length :: Product a -> Int Source #elem :: Eq a => a -> Product a -> Bool Source #maximum :: Ord a => Product a -> a Source #minimum :: Ord a => Product a -> a Source #sum :: Num a => Product a -> a Source #product :: Num a => Product a -> a Source # # Since: base-4.8.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => Sum m -> m Source #foldMap :: Monoid m => (a -> m) -> Sum a -> m Source #foldMap' :: Monoid m => (a -> m) -> Sum a -> m Source #foldr :: (a -> b -> b) -> b -> Sum a -> b Source #foldr' :: (a -> b -> b) -> b -> Sum a -> b Source #foldl :: (b -> a -> b) -> b -> Sum a -> b Source #foldl' :: (b -> a -> b) -> b -> Sum a -> b Source #foldr1 :: (a -> a -> a) -> Sum a -> a Source #foldl1 :: (a -> a -> a) -> Sum a -> a Source #toList :: Sum a -> [a] Source #null :: Sum a -> Bool Source #length :: Sum a -> Int Source #elem :: Eq a => a -> Sum a -> Bool Source #maximum :: Ord a => Sum a -> a Source #minimum :: Ord a => Sum a -> a Source #sum :: Num a => Sum a -> a Source #product :: Num a => Sum a -> a Source # # Since: base-4.8.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => Dual m -> m Source #foldMap :: Monoid m => (a -> m) -> Dual a -> m Source #foldMap' :: Monoid m => (a -> m) -> Dual a -> m Source #foldr :: (a -> b -> b) -> b -> Dual a -> b Source #foldr' :: (a -> b -> b) -> b -> Dual a -> b Source #foldl :: (b -> a -> b) -> b -> Dual a -> b Source #foldl' :: (b -> a -> b) -> b -> Dual a -> b Source #foldr1 :: (a -> a -> a) -> Dual a -> a Source #foldl1 :: (a -> a -> a) -> Dual a -> a Source #toList :: Dual a -> [a] Source #null :: Dual a -> Bool Source #length :: Dual a -> Int Source #elem :: Eq a => a -> Dual a -> Bool Source #maximum :: Ord a => Dual a -> a Source #minimum :: Ord a => Dual a -> a Source #sum :: Num a => Dual a -> a Source #product :: Num a => Dual a -> a Source # # Since: base-4.8.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => Last m -> m Source #foldMap :: Monoid m => (a -> m) -> Last a -> m Source #foldMap' :: Monoid m => (a -> m) -> Last a -> m Source #foldr :: (a -> b -> b) -> b -> Last a -> b Source #foldr' :: (a -> b -> b) -> b -> Last a -> b Source #foldl :: (b -> a -> b) -> b -> Last a -> b Source #foldl' :: (b -> a -> b) -> b -> Last a -> b Source #foldr1 :: (a -> a -> a) -> Last a -> a Source #foldl1 :: (a -> a -> a) -> Last a -> a Source #toList :: Last a -> [a] Source #null :: Last a -> Bool Source #length :: Last a -> Int Source #elem :: Eq a => a -> Last a -> Bool Source #maximum :: Ord a => Last a -> a Source #minimum :: Ord a => Last a -> a Source #sum :: Num a => Last a -> a Source #product :: Num a => Last a -> a Source # # Since: base-4.8.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => First m -> m Source #foldMap :: Monoid m => (a -> m) -> First a -> m Source #foldMap' :: Monoid m => (a -> m) -> First a -> m Source #foldr :: (a -> b -> b) -> b -> First a -> b Source #foldr' :: (a -> b -> b) -> b -> First a -> b Source #foldl :: (b -> a -> b) -> b -> First a -> b Source #foldl' :: (b -> a -> b) -> b -> First a -> b Source #foldr1 :: (a -> a -> a) -> First a -> a Source #foldl1 :: (a -> a -> a) -> First a -> a Source #toList :: First a -> [a] Source #null :: First a -> Bool Source #length :: First a -> Int Source #elem :: Eq a => a -> First a -> Bool Source #maximum :: Ord a => First a -> a Source #minimum :: Ord a => First a -> a Source #sum :: Num a => First a -> a Source #product :: Num a => First a -> a Source # # Since: base-4.8.0.0 Instance detailsDefined in Data.Functor.Identity Methodsfold :: Monoid m => Identity m -> m Source #foldMap :: Monoid m => (a -> m) -> Identity a -> m Source #foldMap' :: Monoid m => (a -> m) -> Identity a -> m Source #foldr :: (a -> b -> b) -> b -> Identity a -> b Source #foldr' :: (a -> b -> b) -> b -> Identity a -> b Source #foldl :: (b -> a -> b) -> b -> Identity a -> b Source #foldl' :: (b -> a -> b) -> b -> Identity a -> b Source #foldr1 :: (a -> a -> a) -> Identity a -> a Source #foldl1 :: (a -> a -> a) -> Identity a -> a Source #toList :: Identity a -> [a] Source #null :: Identity a -> Bool Source #length :: Identity a -> Int Source #elem :: Eq a => a -> Identity a -> Bool Source #maximum :: Ord a => Identity a -> a Source #minimum :: Ord a => Identity a -> a Source #sum :: Num a => Identity a -> a Source #product :: Num a => Identity a -> a Source # # Since: base-4.9.0.0 Instance detailsDefined in Control.Applicative Methodsfold :: Monoid m => ZipList m -> m Source #foldMap :: Monoid m => (a -> m) -> ZipList a -> m Source #foldMap' :: Monoid m => (a -> m) -> ZipList a -> m Source #foldr :: (a -> b -> b) -> b -> ZipList a -> b Source #foldr' :: (a -> b -> b) -> b -> ZipList a -> b Source #foldl :: (b -> a -> b) -> b -> ZipList a -> b Source #foldl' :: (b -> a -> b) -> b -> ZipList a -> b Source #foldr1 :: (a -> a -> a) -> ZipList a -> a Source #foldl1 :: (a -> a -> a) -> ZipList a -> a Source #toList :: ZipList a -> [a] Source #null :: ZipList a -> Bool Source #length :: ZipList a -> Int Source #elem :: Eq a => a -> ZipList a -> Bool Source #maximum :: Ord a => ZipList a -> a Source #minimum :: Ord a => ZipList a -> a Source #sum :: Num a => ZipList a -> a Source #product :: Num a => ZipList a -> a Source # # Since: base-4.9.0.0 Instance detailsDefined in Data.Semigroup Methodsfold :: Monoid m => Option m -> m Source #foldMap :: Monoid m => (a -> m) -> Option a -> m Source #foldMap' :: Monoid m => (a -> m) -> Option a -> m Source #foldr :: (a -> b -> b) -> b -> Option a -> b Source #foldr' :: (a -> b -> b) -> b -> Option a -> b Source #foldl :: (b -> a -> b) -> b -> Option a -> b Source #foldl' :: (b -> a -> b) -> b -> Option a -> b Source #foldr1 :: (a -> a -> a) -> Option a -> a Source #foldl1 :: (a -> a -> a) -> Option a -> a Source #toList :: Option a -> [a] Source #null :: Option a -> Bool Source #length :: Option a -> Int Source #elem :: Eq a => a -> Option a -> Bool Source #maximum :: Ord a => Option a -> a Source #minimum :: Ord a => Option a -> a Source #sum :: Num a => Option a -> a Source #product :: Num a => Option a -> a Source # # Since: base-4.9.0.0 Instance detailsDefined in Data.Semigroup Methodsfold :: Monoid m => Last m -> m Source #foldMap :: Monoid m => (a -> m) -> Last a -> m Source #foldMap' :: Monoid m => (a -> m) -> Last a -> m Source #foldr :: (a -> b -> b) -> b -> Last a -> b Source #foldr' :: (a -> b -> b) -> b -> Last a -> b Source #foldl :: (b -> a -> b) -> b -> Last a -> b Source #foldl' :: (b -> a -> b) -> b -> Last a -> b Source #foldr1 :: (a -> a -> a) -> Last a -> a Source #foldl1 :: (a -> a -> a) -> Last a -> a Source #toList :: Last a -> [a] Source #null :: Last a -> Bool Source #length :: Last a -> Int Source #elem :: Eq a => a -> Last a -> Bool Source #maximum :: Ord a => Last a -> a Source #minimum :: Ord a => Last a -> a Source #sum :: Num a => Last a -> a Source #product :: Num a => Last a -> a Source # # Since: base-4.9.0.0 Instance detailsDefined in Data.Semigroup Methodsfold :: Monoid m => First m -> m Source #foldMap :: Monoid m => (a -> m) -> First a -> m Source #foldMap' :: Monoid m => (a -> m) -> First a -> m Source #foldr :: (a -> b -> b) -> b -> First a -> b Source #foldr' :: (a -> b -> b) -> b -> First a -> b Source #foldl :: (b -> a -> b) -> b -> First a -> b Source #foldl' :: (b -> a -> b) -> b -> First a -> b Source #foldr1 :: (a -> a -> a) -> First a -> a Source #foldl1 :: (a -> a -> a) -> First a -> a Source #toList :: First a -> [a] Source #null :: First a -> Bool Source #length :: First a -> Int Source #elem :: Eq a => a -> First a -> Bool Source #maximum :: Ord a => First a -> a Source #minimum :: Ord a => First a -> a Source #sum :: Num a => First a -> a Source #product :: Num a => First a -> a Source # # Since: base-4.9.0.0 Instance detailsDefined in Data.Semigroup Methodsfold :: Monoid m => Max m -> m Source #foldMap :: Monoid m => (a -> m) -> Max a -> m Source #foldMap' :: Monoid m => (a -> m) -> Max a -> m Source #foldr :: (a -> b -> b) -> b -> Max a -> b Source #foldr' :: (a -> b -> b) -> b -> Max a -> b Source #foldl :: (b -> a -> b) -> b -> Max a -> b Source #foldl' :: (b -> a -> b) -> b -> Max a -> b Source #foldr1 :: (a -> a -> a) -> Max a -> a Source #foldl1 :: (a -> a -> a) -> Max a -> a Source #toList :: Max a -> [a] Source #null :: Max a -> Bool Source #length :: Max a -> Int Source #elem :: Eq a => a -> Max a -> Bool Source #maximum :: Ord a => Max a -> a Source #minimum :: Ord a => Max a -> a Source #sum :: Num a => Max a -> a Source #product :: Num a => Max a -> a Source # # Since: base-4.9.0.0 Instance detailsDefined in Data.Semigroup Methodsfold :: Monoid m => Min m -> m Source #foldMap :: Monoid m => (a -> m) -> Min a -> m Source #foldMap' :: Monoid m => (a -> m) -> Min a -> m Source #foldr :: (a -> b -> b) -> b -> Min a -> b Source #foldr' :: (a -> b -> b) -> b -> Min a -> b Source #foldl :: (b -> a -> b) -> b -> Min a -> b Source #foldl' :: (b -> a -> b) -> b -> Min a -> b Source #foldr1 :: (a -> a -> a) -> Min a -> a Source #foldl1 :: (a -> a -> a) -> Min a -> a Source #toList :: Min a -> [a] Source #null :: Min a -> Bool Source #length :: Min a -> Int Source #elem :: Eq a => a -> Min a -> Bool Source #maximum :: Ord a => Min a -> a Source #minimum :: Ord a => Min a -> a Source #sum :: Num a => Min a -> a Source #product :: Num a => Min a -> a Source # # Since: base-4.9.0.0 Instance detailsDefined in Data.Complex Methodsfold :: Monoid m => Complex m -> m Source #foldMap :: Monoid m => (a -> m) -> Complex a -> m Source #foldMap' :: Monoid m => (a -> m) -> Complex a -> m Source #foldr :: (a -> b -> b) -> b -> Complex a -> b Source #foldr' :: (a -> b -> b) -> b -> Complex a -> b Source #foldl :: (b -> a -> b) -> b -> Complex a -> b Source #foldl' :: (b -> a -> b) -> b -> Complex a -> b Source #foldr1 :: (a -> a -> a) -> Complex a -> a Source #foldl1 :: (a -> a -> a) -> Complex a -> a Source #toList :: Complex a -> [a] Source #null :: Complex a -> Bool Source #length :: Complex a -> Int Source #elem :: Eq a => a -> Complex a -> Bool Source #maximum :: Ord a => Complex a -> a Source #minimum :: Ord a => Complex a -> a Source #sum :: Num a => Complex a -> a Source #product :: Num a => Complex a -> a Source # # Since: base-4.7.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => Either a m -> m Source #foldMap :: Monoid m => (a0 -> m) -> Either a a0 -> m Source #foldMap' :: Monoid m => (a0 -> m) -> Either a a0 -> m Source #foldr :: (a0 -> b -> b) -> b -> Either a a0 -> b Source #foldr' :: (a0 -> b -> b) -> b -> Either a a0 -> b Source #foldl :: (b -> a0 -> b) -> b -> Either a a0 -> b Source #foldl' :: (b -> a0 -> b) -> b -> Either a a0 -> b Source #foldr1 :: (a0 -> a0 -> a0) -> Either a a0 -> a0 Source #foldl1 :: (a0 -> a0 -> a0) -> Either a a0 -> a0 Source #toList :: Either a a0 -> [a0] Source #null :: Either a a0 -> Bool Source #length :: Either a a0 -> Int Source #elem :: Eq a0 => a0 -> Either a a0 -> Bool Source #maximum :: Ord a0 => Either a a0 -> a0 Source #minimum :: Ord a0 => Either a a0 -> a0 Source #sum :: Num a0 => Either a a0 -> a0 Source #product :: Num a0 => Either a a0 -> a0 Source # Foldable (V1 :: Type -> Type) # Since: base-4.9.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => V1 m -> m Source #foldMap :: Monoid m => (a -> m) -> V1 a -> m Source #foldMap' :: Monoid m => (a -> m) -> V1 a -> m Source #foldr :: (a -> b -> b) -> b -> V1 a -> b Source #foldr' :: (a -> b -> b) -> b -> V1 a -> b Source #foldl :: (b -> a -> b) -> b -> V1 a -> b Source #foldl' :: (b -> a -> b) -> b -> V1 a -> b Source #foldr1 :: (a -> a -> a) -> V1 a -> a Source #foldl1 :: (a -> a -> a) -> V1 a -> a Source #toList :: V1 a -> [a] Source #null :: V1 a -> Bool Source #length :: V1 a -> Int Source #elem :: Eq a => a -> V1 a -> Bool Source #maximum :: Ord a => V1 a -> a Source #minimum :: Ord a => V1 a -> a Source #sum :: Num a => V1 a -> a Source #product :: Num a => V1 a -> a Source # Foldable (U1 :: Type -> Type) # Since: base-4.9.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => U1 m -> m Source #foldMap :: Monoid m => (a -> m) -> U1 a -> m Source #foldMap' :: Monoid m => (a -> m) -> U1 a -> m Source #foldr :: (a -> b -> b) -> b -> U1 a -> b Source #foldr' :: (a -> b -> b) -> b -> U1 a -> b Source #foldl :: (b -> a -> b) -> b -> U1 a -> b Source #foldl' :: (b -> a -> b) -> b -> U1 a -> b Source #foldr1 :: (a -> a -> a) -> U1 a -> a Source #foldl1 :: (a -> a -> a) -> U1 a -> a Source #toList :: U1 a -> [a] Source #null :: U1 a -> Bool Source #length :: U1 a -> Int Source #elem :: Eq a => a -> U1 a -> Bool Source #maximum :: Ord a => U1 a -> a Source #minimum :: Ord a => U1 a -> a Source #sum :: Num a => U1 a -> a Source #product :: Num a => U1 a -> a Source # Foldable (UAddr :: Type -> Type) # Since: base-4.9.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => UAddr m -> m Source #foldMap :: Monoid m => (a -> m) -> UAddr a -> m Source #foldMap' :: Monoid m => (a -> m) -> UAddr a -> m Source #foldr :: (a -> b -> b) -> b -> UAddr a -> b Source #foldr' :: (a -> b -> b) -> b -> UAddr a -> b Source #foldl :: (b -> a -> b) -> b -> UAddr a -> b Source #foldl' :: (b -> a -> b) -> b -> UAddr a -> b Source #foldr1 :: (a -> a -> a) -> UAddr a -> a Source #foldl1 :: (a -> a -> a) -> UAddr a -> a Source #toList :: UAddr a -> [a] Source #null :: UAddr a -> Bool Source #length :: UAddr a -> Int Source #elem :: Eq a => a -> UAddr a -> Bool Source #maximum :: Ord a => UAddr a -> a Source #minimum :: Ord a => UAddr a -> a Source #sum :: Num a => UAddr a -> a Source #product :: Num a => UAddr a -> a Source # Foldable (UChar :: Type -> Type) # Since: base-4.9.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => UChar m -> m Source #foldMap :: Monoid m => (a -> m) -> UChar a -> m Source #foldMap' :: Monoid m => (a -> m) -> UChar a -> m Source #foldr :: (a -> b -> b) -> b -> UChar a -> b Source #foldr' :: (a -> b -> b) -> b -> UChar a -> b Source #foldl :: (b -> a -> b) -> b -> UChar a -> b Source #foldl' :: (b -> a -> b) -> b -> UChar a -> b Source #foldr1 :: (a -> a -> a) -> UChar a -> a Source #foldl1 :: (a -> a -> a) -> UChar a -> a Source #toList :: UChar a -> [a] Source #null :: UChar a -> Bool Source #length :: UChar a -> Int Source #elem :: Eq a => a -> UChar a -> Bool Source #maximum :: Ord a => UChar a -> a Source #minimum :: Ord a => UChar a -> a Source #sum :: Num a => UChar a -> a Source #product :: Num a => UChar a -> a Source # Foldable (UDouble :: Type -> Type) # Since: base-4.9.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => UDouble m -> m Source #foldMap :: Monoid m => (a -> m) -> UDouble a -> m Source #foldMap' :: Monoid m => (a -> m) -> UDouble a -> m Source #foldr :: (a -> b -> b) -> b -> UDouble a -> b Source #foldr' :: (a -> b -> b) -> b -> UDouble a -> b Source #foldl :: (b -> a -> b) -> b -> UDouble a -> b Source #foldl' :: (b -> a -> b) -> b -> UDouble a -> b Source #foldr1 :: (a -> a -> a) -> UDouble a -> a Source #foldl1 :: (a -> a -> a) -> UDouble a -> a Source #toList :: UDouble a -> [a] Source #null :: UDouble a -> Bool Source #length :: UDouble a -> Int Source #elem :: Eq a => a -> UDouble a -> Bool Source #maximum :: Ord a => UDouble a -> a Source #minimum :: Ord a => UDouble a -> a Source #sum :: Num a => UDouble a -> a Source #product :: Num a => UDouble a -> a Source # Foldable (UFloat :: Type -> Type) # Since: base-4.9.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => UFloat m -> m Source #foldMap :: Monoid m => (a -> m) -> UFloat a -> m Source #foldMap' :: Monoid m => (a -> m) -> UFloat a -> m Source #foldr :: (a -> b -> b) -> b -> UFloat a -> b Source #foldr' :: (a -> b -> b) -> b -> UFloat a -> b Source #foldl :: (b -> a -> b) -> b -> UFloat a -> b Source #foldl' :: (b -> a -> b) -> b -> UFloat a -> b Source #foldr1 :: (a -> a -> a) -> UFloat a -> a Source #foldl1 :: (a -> a -> a) -> UFloat a -> a Source #toList :: UFloat a -> [a] Source #null :: UFloat a -> Bool Source #length :: UFloat a -> Int Source #elem :: Eq a => a -> UFloat a -> Bool Source #maximum :: Ord a => UFloat a -> a Source #minimum :: Ord a => UFloat a -> a Source #sum :: Num a => UFloat a -> a Source #product :: Num a => UFloat a -> a Source # Foldable (UInt :: Type -> Type) # Since: base-4.9.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => UInt m -> m Source #foldMap :: Monoid m => (a -> m) -> UInt a -> m Source #foldMap' :: Monoid m => (a -> m) -> UInt a -> m Source #foldr :: (a -> b -> b) -> b -> UInt a -> b Source #foldr' :: (a -> b -> b) -> b -> UInt a -> b Source #foldl :: (b -> a -> b) -> b -> UInt a -> b Source #foldl' :: (b -> a -> b) -> b -> UInt a -> b Source #foldr1 :: (a -> a -> a) -> UInt a -> a Source #foldl1 :: (a -> a -> a) -> UInt a -> a Source #toList :: UInt a -> [a] Source #null :: UInt a -> Bool Source #length :: UInt a -> Int Source #elem :: Eq a => a -> UInt a -> Bool Source #maximum :: Ord a => UInt a -> a Source #minimum :: Ord a => UInt a -> a Source #sum :: Num a => UInt a -> a Source #product :: Num a => UInt a -> a Source # Foldable (UWord :: Type -> Type) # Since: base-4.9.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => UWord m -> m Source #foldMap :: Monoid m => (a -> m) -> UWord a -> m Source #foldMap' :: Monoid m => (a -> m) -> UWord a -> m Source #foldr :: (a -> b -> b) -> b -> UWord a -> b Source #foldr' :: (a -> b -> b) -> b -> UWord a -> b Source #foldl :: (b -> a -> b) -> b -> UWord a -> b Source #foldl' :: (b -> a -> b) -> b -> UWord a -> b Source #foldr1 :: (a -> a -> a) -> UWord a -> a Source #foldl1 :: (a -> a -> a) -> UWord a -> a Source #toList :: UWord a -> [a] Source #null :: UWord a -> Bool Source #length :: UWord a -> Int Source #elem :: Eq a => a -> UWord a -> Bool Source #maximum :: Ord a => UWord a -> a Source #minimum :: Ord a => UWord a -> a Source #sum :: Num a => UWord a -> a Source #product :: Num a => UWord a -> a Source # Foldable ((,) a) # Since: base-4.7.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => (a, m) -> m Source #foldMap :: Monoid m => (a0 -> m) -> (a, a0) -> m Source #foldMap' :: Monoid m => (a0 -> m) -> (a, a0) -> m Source #foldr :: (a0 -> b -> b) -> b -> (a, a0) -> b Source #foldr' :: (a0 -> b -> b) -> b -> (a, a0) -> b Source #foldl :: (b -> a0 -> b) -> b -> (a, a0) -> b Source #foldl' :: (b -> a0 -> b) -> b -> (a, a0) -> b Source #foldr1 :: (a0 -> a0 -> a0) -> (a, a0) -> a0 Source #foldl1 :: (a0 -> a0 -> a0) -> (a, a0) -> a0 Source #toList :: (a, a0) -> [a0] Source #null :: (a, a0) -> Bool Source #length :: (a, a0) -> Int Source #elem :: Eq a0 => a0 -> (a, a0) -> Bool Source #maximum :: Ord a0 => (a, a0) -> a0 Source #minimum :: Ord a0 => (a, a0) -> a0 Source #sum :: Num a0 => (a, a0) -> a0 Source #product :: Num a0 => (a, a0) -> a0 Source # # Since: base-4.8.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => Array i m -> m Source #foldMap :: Monoid m => (a -> m) -> Array i a -> m Source #foldMap' :: Monoid m => (a -> m) -> Array i a -> m Source #foldr :: (a -> b -> b) -> b -> Array i a -> b Source #foldr' :: (a -> b -> b) -> b -> Array i a -> b Source #foldl :: (b -> a -> b) -> b -> Array i a -> b Source #foldl' :: (b -> a -> b) -> b -> Array i a -> b Source #foldr1 :: (a -> a -> a) -> Array i a -> a Source #foldl1 :: (a -> a -> a) -> Array i a -> a Source #toList :: Array i a -> [a] Source #null :: Array i a -> Bool Source #length :: Array i a -> Int Source #elem :: Eq a => a -> Array i a -> Bool Source #maximum :: Ord a => Array i a -> a Source #minimum :: Ord a => Array i a -> a Source #sum :: Num a => Array i a -> a Source #product :: Num a => Array i a -> a Source # Foldable (Proxy :: Type -> Type) # Since: base-4.7.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => Proxy m -> m Source #foldMap :: Monoid m => (a -> m) -> Proxy a -> m Source #foldMap' :: Monoid m => (a -> m) -> Proxy a -> m Source #foldr :: (a -> b -> b) -> b -> Proxy a -> b Source #foldr' :: (a -> b -> b) -> b -> Proxy a -> b Source #foldl :: (b -> a -> b) -> b -> Proxy a -> b Source #foldl' :: (b -> a -> b) -> b -> Proxy a -> b Source #foldr1 :: (a -> a -> a) -> Proxy a -> a Source #foldl1 :: (a -> a -> a) -> Proxy a -> a Source #toList :: Proxy a -> [a] Source #null :: Proxy a -> Bool Source #length :: Proxy a -> Int Source #elem :: Eq a => a -> Proxy a -> Bool Source #maximum :: Ord a => Proxy a -> a Source #minimum :: Ord a => Proxy a -> a Source #sum :: Num a => Proxy a -> a Source #product :: Num a => Proxy a -> a Source # Foldable (Arg a) # Since: base-4.9.0.0 Instance detailsDefined in Data.Semigroup Methodsfold :: Monoid m => Arg a m -> m Source #foldMap :: Monoid m => (a0 -> m) -> Arg a a0 -> m Source #foldMap' :: Monoid m => (a0 -> m) -> Arg a a0 -> m Source #foldr :: (a0 -> b -> b) -> b -> Arg a a0 -> b Source #foldr' :: (a0 -> b -> b) -> b -> Arg a a0 -> b Source #foldl :: (b -> a0 -> b) -> b -> Arg a a0 -> b Source #foldl' :: (b -> a0 -> b) -> b -> Arg a a0 -> b Source #foldr1 :: (a0 -> a0 -> a0) -> Arg a a0 -> a0 Source #foldl1 :: (a0 -> a0 -> a0) -> Arg a a0 -> a0 Source #toList :: Arg a a0 -> [a0] Source #null :: Arg a a0 -> Bool Source #length :: Arg a a0 -> Int Source #elem :: Eq a0 => a0 -> Arg a a0 -> Bool Source #maximum :: Ord a0 => Arg a a0 -> a0 Source #minimum :: Ord a0 => Arg a a0 -> a0 Source #sum :: Num a0 => Arg a a0 -> a0 Source #product :: Num a0 => Arg a a0 -> a0 Source # Foldable f => Foldable (Rec1 f) # Since: base-4.9.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => Rec1 f m -> m Source #foldMap :: Monoid m => (a -> m) -> Rec1 f a -> m Source #foldMap' :: Monoid m => (a -> m) -> Rec1 f a -> m Source #foldr :: (a -> b -> b) -> b -> Rec1 f a -> b Source #foldr' :: (a -> b -> b) -> b -> Rec1 f a -> b Source #foldl :: (b -> a -> b) -> b -> Rec1 f a -> b Source #foldl' :: (b -> a -> b) -> b -> Rec1 f a -> b Source #foldr1 :: (a -> a -> a) -> Rec1 f a -> a Source #foldl1 :: (a -> a -> a) -> Rec1 f a -> a Source #toList :: Rec1 f a -> [a] Source #null :: Rec1 f a -> Bool Source #length :: Rec1 f a -> Int Source #elem :: Eq a => a -> Rec1 f a -> Bool Source #maximum :: Ord a => Rec1 f a -> a Source #minimum :: Ord a => Rec1 f a -> a Source #sum :: Num a => Rec1 f a -> a Source #product :: Num a => Rec1 f a -> a Source # Foldable f => Foldable (Alt f) # Since: base-4.12.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => Alt f m -> m Source #foldMap :: Monoid m => (a -> m) -> Alt f a -> m Source #foldMap' :: Monoid m => (a -> m) -> Alt f a -> m Source #foldr :: (a -> b -> b) -> b -> Alt f a -> b Source #foldr' :: (a -> b -> b) -> b -> Alt f a -> b Source #foldl :: (b -> a -> b) -> b -> Alt f a -> b Source #foldl' :: (b -> a -> b) -> b -> Alt f a -> b Source #foldr1 :: (a -> a -> a) -> Alt f a -> a Source #foldl1 :: (a -> a -> a) -> Alt f a -> a Source #toList :: Alt f a -> [a] Source #null :: Alt f a -> Bool Source #length :: Alt f a -> Int Source #elem :: Eq a => a -> Alt f a -> Bool Source #maximum :: Ord a => Alt f a -> a Source #minimum :: Ord a => Alt f a -> a Source #sum :: Num a => Alt f a -> a Source #product :: Num a => Alt f a -> a Source # Foldable f => Foldable (Ap f) # Since: base-4.12.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => Ap f m -> m Source #foldMap :: Monoid m => (a -> m) -> Ap f a -> m Source #foldMap' :: Monoid m => (a -> m) -> Ap f a -> m Source #foldr :: (a -> b -> b) -> b -> Ap f a -> b Source #foldr' :: (a -> b -> b) -> b -> Ap f a -> b Source #foldl :: (b -> a -> b) -> b -> Ap f a -> b Source #foldl' :: (b -> a -> b) -> b -> Ap f a -> b Source #foldr1 :: (a -> a -> a) -> Ap f a -> a Source #foldl1 :: (a -> a -> a) -> Ap f a -> a Source #toList :: Ap f a -> [a] Source #null :: Ap f a -> Bool Source #length :: Ap f a -> Int Source #elem :: Eq a => a -> Ap f a -> Bool Source #maximum :: Ord a => Ap f a -> a Source #minimum :: Ord a => Ap f a -> a Source #sum :: Num a => Ap f a -> a Source #product :: Num a => Ap f a -> a Source # Foldable (Const m :: Type -> Type) # Since: base-4.7.0.0 Instance detailsDefined in Data.Functor.Const Methodsfold :: Monoid m0 => Const m m0 -> m0 Source #foldMap :: Monoid m0 => (a -> m0) -> Const m a -> m0 Source #foldMap' :: Monoid m0 => (a -> m0) -> Const m a -> m0 Source #foldr :: (a -> b -> b) -> b -> Const m a -> b Source #foldr' :: (a -> b -> b) -> b -> Const m a -> b Source #foldl :: (b -> a -> b) -> b -> Const m a -> b Source #foldl' :: (b -> a -> b) -> b -> Const m a -> b Source #foldr1 :: (a -> a -> a) -> Const m a -> a Source #foldl1 :: (a -> a -> a) -> Const m a -> a Source #toList :: Const m a -> [a] Source #null :: Const m a -> Bool Source #length :: Const m a -> Int Source #elem :: Eq a => a -> Const m a -> Bool Source #maximum :: Ord a => Const m a -> a Source #minimum :: Ord a => Const m a -> a Source #sum :: Num a => Const m a -> a Source #product :: Num a => Const m a -> a Source # Foldable (K1 i c :: Type -> Type) # Since: base-4.9.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => K1 i c m -> m Source #foldMap :: Monoid m => (a -> m) -> K1 i c a -> m Source #foldMap' :: Monoid m => (a -> m) -> K1 i c a -> m Source #foldr :: (a -> b -> b) -> b -> K1 i c a -> b Source #foldr' :: (a -> b -> b) -> b -> K1 i c a -> b Source #foldl :: (b -> a -> b) -> b -> K1 i c a -> b Source #foldl' :: (b -> a -> b) -> b -> K1 i c a -> b Source #foldr1 :: (a -> a -> a) -> K1 i c a -> a Source #foldl1 :: (a -> a -> a) -> K1 i c a -> a Source #toList :: K1 i c a -> [a] Source #null :: K1 i c a -> Bool Source #length :: K1 i c a -> Int Source #elem :: Eq a => a -> K1 i c a -> Bool Source #maximum :: Ord a => K1 i c a -> a Source #minimum :: Ord a => K1 i c a -> a Source #sum :: Num a => K1 i c a -> a Source #product :: Num a => K1 i c a -> a Source # (Foldable f, Foldable g) => Foldable (f :+: g) # Since: base-4.9.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => (f :+: g) m -> m Source #foldMap :: Monoid m => (a -> m) -> (f :+: g) a -> m Source #foldMap' :: Monoid m => (a -> m) -> (f :+: g) a -> m Source #foldr :: (a -> b -> b) -> b -> (f :+: g) a -> b Source #foldr' :: (a -> b -> b) -> b -> (f :+: g) a -> b Source #foldl :: (b -> a -> b) -> b -> (f :+: g) a -> b Source #foldl' :: (b -> a -> b) -> b -> (f :+: g) a -> b Source #foldr1 :: (a -> a -> a) -> (f :+: g) a -> a Source #foldl1 :: (a -> a -> a) -> (f :+: g) a -> a Source #toList :: (f :+: g) a -> [a] Source #null :: (f :+: g) a -> Bool Source #length :: (f :+: g) a -> Int Source #elem :: Eq a => a -> (f :+: g) a -> Bool Source #maximum :: Ord a => (f :+: g) a -> a Source #minimum :: Ord a => (f :+: g) a -> a Source #sum :: Num a => (f :+: g) a -> a Source #product :: Num a => (f :+: g) a -> a Source # (Foldable f, Foldable g) => Foldable (f :*: g) # Since: base-4.9.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => (f :*: g) m -> m Source #foldMap :: Monoid m => (a -> m) -> (f :*: g) a -> m Source #foldMap' :: Monoid m => (a -> m) -> (f :*: g) a -> m Source #foldr :: (a -> b -> b) -> b -> (f :*: g) a -> b Source #foldr' :: (a -> b -> b) -> b -> (f :*: g) a -> b Source #foldl :: (b -> a -> b) -> b -> (f :*: g) a -> b Source #foldl' :: (b -> a -> b) -> b -> (f :*: g) a -> b Source #foldr1 :: (a -> a -> a) -> (f :*: g) a -> a Source #foldl1 :: (a -> a -> a) -> (f :*: g) a -> a Source #toList :: (f :*: g) a -> [a] Source #null :: (f :*: g) a -> Bool Source #length :: (f :*: g) a -> Int Source #elem :: Eq a => a -> (f :*: g) a -> Bool Source #maximum :: Ord a => (f :*: g) a -> a Source #minimum :: Ord a => (f :*: g) a -> a Source #sum :: Num a => (f :*: g) a -> a Source #product :: Num a => (f :*: g) a -> a Source # (Foldable f, Foldable g) => Foldable (Sum f g) # Since: base-4.9.0.0 Instance detailsDefined in Data.Functor.Sum Methodsfold :: Monoid m => Sum f g m -> m Source #foldMap :: Monoid m => (a -> m) -> Sum f g a -> m Source #foldMap' :: Monoid m => (a -> m) -> Sum f g a -> m Source #foldr :: (a -> b -> b) -> b -> Sum f g a -> b Source #foldr' :: (a -> b -> b) -> b -> Sum f g a -> b Source #foldl :: (b -> a -> b) -> b -> Sum f g a -> b Source #foldl' :: (b -> a -> b) -> b -> Sum f g a -> b Source #foldr1 :: (a -> a -> a) -> Sum f g a -> a Source #foldl1 :: (a -> a -> a) -> Sum f g a -> a Source #toList :: Sum f g a -> [a] Source #null :: Sum f g a -> Bool Source #length :: Sum f g a -> Int Source #elem :: Eq a => a -> Sum f g a -> Bool Source #maximum :: Ord a => Sum f g a -> a Source #minimum :: Ord a => Sum f g a -> a Source #sum :: Num a => Sum f g a -> a Source #product :: Num a => Sum f g a -> a Source # (Foldable f, Foldable g) => Foldable (Product f g) # Since: base-4.9.0.0 Instance detailsDefined in Data.Functor.Product Methodsfold :: Monoid m => Product f g m -> m Source #foldMap :: Monoid m => (a -> m) -> Product f g a -> m Source #foldMap' :: Monoid m => (a -> m) -> Product f g a -> m Source #foldr :: (a -> b -> b) -> b -> Product f g a -> b Source #foldr' :: (a -> b -> b) -> b -> Product f g a -> b Source #foldl :: (b -> a -> b) -> b -> Product f g a -> b Source #foldl' :: (b -> a -> b) -> b -> Product f g a -> b Source #foldr1 :: (a -> a -> a) -> Product f g a -> a Source #foldl1 :: (a -> a -> a) -> Product f g a -> a Source #toList :: Product f g a -> [a] Source #null :: Product f g a -> Bool Source #length :: Product f g a -> Int Source #elem :: Eq a => a -> Product f g a -> Bool Source #maximum :: Ord a => Product f g a -> a Source #minimum :: Ord a => Product f g a -> a Source #sum :: Num a => Product f g a -> a Source #product :: Num a => Product f g a -> a Source # Foldable f => Foldable (M1 i c f) # Since: base-4.9.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => M1 i c f m -> m Source #foldMap :: Monoid m => (a -> m) -> M1 i c f a -> m Source #foldMap' :: Monoid m => (a -> m) -> M1 i c f a -> m Source #foldr :: (a -> b -> b) -> b -> M1 i c f a -> b Source #foldr' :: (a -> b -> b) -> b -> M1 i c f a -> b Source #foldl :: (b -> a -> b) -> b -> M1 i c f a -> b Source #foldl' :: (b -> a -> b) -> b -> M1 i c f a -> b Source #foldr1 :: (a -> a -> a) -> M1 i c f a -> a Source #foldl1 :: (a -> a -> a) -> M1 i c f a -> a Source #toList :: M1 i c f a -> [a] Source #null :: M1 i c f a -> Bool Source #length :: M1 i c f a -> Int Source #elem :: Eq a => a -> M1 i c f a -> Bool Source #maximum :: Ord a => M1 i c f a -> a Source #minimum :: Ord a => M1 i c f a -> a Source #sum :: Num a => M1 i c f a -> a Source #product :: Num a => M1 i c f a -> a Source # (Foldable f, Foldable g) => Foldable (f :.: g) # Since: base-4.9.0.0 Instance detailsDefined in Data.Foldable Methodsfold :: Monoid m => (f :.: g) m -> m Source #foldMap :: Monoid m => (a -> m) -> (f :.: g) a -> m Source #foldMap' :: Monoid m => (a -> m) -> (f :.: g) a -> m Source #foldr :: (a -> b -> b) -> b -> (f :.: g) a -> b Source #foldr' :: (a -> b -> b) -> b -> (f :.: g) a -> b Source #foldl :: (b -> a -> b) -> b -> (f :.: g) a -> b Source #foldl' :: (b -> a -> b) -> b -> (f :.: g) a -> b Source #foldr1 :: (a -> a -> a) -> (f :.: g) a -> a Source #foldl1 :: (a -> a -> a) -> (f :.: g) a -> a Source #toList :: (f :.: g) a -> [a] Source #null :: (f :.: g) a -> Bool Source #length :: (f :.: g) a -> Int Source #elem :: Eq a => a -> (f :.: g) a -> Bool Source #maximum :: Ord a => (f :.: g) a -> a Source #minimum :: Ord a => (f :.: g) a -> a Source #sum :: Num a => (f :.: g) a -> a Source #product :: Num a => (f :.: g) a -> a Source # (Foldable f, Foldable g) => Foldable (Compose f g) # Since: base-4.9.0.0 Instance detailsDefined in Data.Functor.Compose Methodsfold :: Monoid m => Compose f g m -> m Source #foldMap :: Monoid m => (a -> m) -> Compose f g a -> m Source #foldMap' :: Monoid m => (a -> m) -> Compose f g a -> m Source #foldr :: (a -> b -> b) -> b -> Compose f g a -> b Source #foldr' :: (a -> b -> b) -> b -> Compose f g a -> b Source #foldl :: (b -> a -> b) -> b -> Compose f g a -> b Source #foldl' :: (b -> a -> b) -> b -> Compose f g a -> b Source #foldr1 :: (a -> a -> a) -> Compose f g a -> a Source #foldl1 :: (a -> a -> a) -> Compose f g a -> a Source #toList :: Compose f g a -> [a] Source #null :: Compose f g a -> Bool Source #length :: Compose f g a -> Int Source #elem :: Eq a => a -> Compose f g a -> Bool Source #maximum :: Ord a => Compose f g a -> a Source #minimum :: Ord a => Compose f g a -> a Source #sum :: Num a => Compose f g a -> a Source #product :: Num a => Compose f g a -> a Source # # Special biased folds foldrM :: (Foldable t, Monad m) => (a -> b -> m b) -> b -> t a -> m b Source # Monadic fold over the elements of a structure. This type of fold is left-associative in the monadic effects, and right-associative in the output value. Given a structure t with elements (a, b, c, ..., x, y), the result of a fold with an operator function f is equivalent to: foldrM f z t = do { yy <- f y z; xx <- f x yy; ... ; bb <- f b cc; f a bb } If in a MonadPlus the bind short-circuits, the evaluated effects will be from a tail of the sequence. If you want to evaluate the monadic effects in left-to-right order, or perhaps be able to short-circuit after an initial sequence of elements, you'll need to use foldlM instead. If the monadic effects don't short-circuit, the outer-most application of f is to left-most element a, so that, ignoring effects, the result looks like a right fold: a f (b f (c f (... (x f (y f z))))). and yet, left-associative monadic binds, rather than right-associative applications of f, sequence the computation. #### Examples Expand Basic usage: >>> let f i acc = do { print i ; return$ i : acc }
>>> foldrM f [] [0..3]
3
2
1
0
[0,1,2,3]


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

Monadic fold over the elements of a structure. This type of fold is right-associative in the monadic effects, and left-associative in the output value.

Given a structure t with elements (a, b, ..., w, x, y), the result of a fold with an operator function f is equivalent to:

foldlM f z t = do { aa <- f z a; bb <- f aa b; ... ; xx <- f ww x; f xx y }

If in a MonadPlus the bind short-circuits, the evaluated effects will be from an initial portion of the sequence. If you want to evaluate the monadic effects in right-to-left order, or perhaps be able to short-circuit after processing a tail of the sequence of elements, you'll need to use foldrM instead.

If the monadic effects don't short-circuit, the outer-most application of f is to the right-most element y, so that, ignoring effects, the result looks like a left fold:

((((z f a) f b) ... f w) f x) f y

and yet, right-associative monadic binds, rather than left-associative applications of f, sequence the computation.

Expand

Basic usage:

>>> let f a e = do { print e ; return $e : a } >>> foldlM f [] [0..3] 0 1 2 3 [3,2,1,0]  # Folding actions ## Applicative actions traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f () Source # Map each element of a structure to an Applicative action, evaluate these actions from left to right, and ignore the results. For a version that doesn't ignore the results see traverse. traverse_ is just like mapM_, but generalised to Applicative actions. #### Examples Expand Basic usage: >>> traverse_ print ["Hello", "world", "!"] "Hello" "world" "!"  for_ :: (Foldable t, Applicative f) => t a -> (a -> f b) -> f () Source # for_ is traverse_ with its arguments flipped. For a version that doesn't ignore the results see for. This is forM_ generalised to Applicative actions. for_ is just like forM_, but generalised to Applicative actions. #### Examples Expand Basic usage: >>> for_ [1..4] print 1 2 3 4  sequenceA_ :: (Foldable t, Applicative f) => t (f a) -> f () Source # Evaluate each action in the structure from left to right, and ignore the results. For a version that doesn't ignore the results see sequenceA. sequenceA_ is just like sequence_, but generalised to Applicative actions. #### Examples Expand Basic usage: >>> sequenceA_ [print "Hello", print "world", print "!"] "Hello" "world" "!"  asum :: (Foldable t, Alternative f) => t (f a) -> f a Source # The sum of a collection of actions, generalizing concat. asum is just like msum, but generalised to Alternative. #### Examples Expand Basic usage: >>> asum [Just "Hello", Nothing, Just "World"] Just "Hello"  ## Monadic actions mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m () Source # Map each element of a structure to a monadic action, evaluate these actions from left to right, and ignore the results. For a version that doesn't ignore the results see mapM. mapM_ is just like traverse_, but specialised to monadic actions. forM_ :: (Foldable t, Monad m) => t a -> (a -> m b) -> m () Source # forM_ is mapM_ with its arguments flipped. For a version that doesn't ignore the results see forM. forM_ is just like for_, but specialised to monadic actions. sequence_ :: (Foldable t, Monad m) => t (m a) -> m () Source # Evaluate each monadic action in the structure from left to right, and ignore the results. For a version that doesn't ignore the results see sequence. sequence_ is just like sequenceA_, but specialised to monadic actions. msum :: (Foldable t, MonadPlus m) => t (m a) -> m a Source # The sum of a collection of actions, generalizing concat. msum is just like asum, but specialised to MonadPlus. # Specialized folds concat :: Foldable t => t [a] -> [a] Source # The concatenation of all the elements of a container of lists. #### Examples Expand Basic usage: >>> concat (Just [1, 2, 3]) [1,2,3]  >>> concat (Left 42) []  >>> concat [[1, 2, 3], [4, 5], [6], []] [1,2,3,4,5,6]  concatMap :: Foldable t => (a -> [b]) -> t a -> [b] Source # Map a function over all the elements of a container and concatenate the resulting lists. #### Examples Expand Basic usage: >>> concatMap (take 3) [[1..], [10..], [100..], [1000..]] [1,2,3,10,11,12,100,101,102,1000,1001,1002]  >>> concatMap (take 3) (Just [1..]) [1,2,3]  and :: Foldable t => t Bool -> Bool Source # 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. #### Examples Expand Basic usage: >>> and [] True  >>> and [True] True  >>> and [False] False  >>> and [True, True, False] False  >>> and (False : repeat True) -- Infinite list [False,True,True,True,... False  >>> and (repeat True) * Hangs forever *  or :: Foldable t => t Bool -> Bool Source # 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. #### Examples Expand Basic usage: >>> or [] False  >>> or [True] True  >>> or [False] False  >>> or [True, True, False] True  >>> or (True : repeat False) -- Infinite list [True,False,False,False,... True  >>> or (repeat False) * Hangs forever *  any :: Foldable t => (a -> Bool) -> t a -> Bool Source # Determines whether any element of the structure satisfies the predicate. #### Examples Expand Basic usage: >>> any (> 3) [] False  >>> any (> 3) [1,2] False  >>> any (> 3) [1,2,3,4,5] True  >>> any (> 3) [1..] True  >>> any (> 3) [0, -1..] * Hangs forever *  all :: Foldable t => (a -> Bool) -> t a -> Bool Source # Determines whether all elements of the structure satisfy the predicate. #### Examples Expand Basic usage: >>> all (> 3) [] True  >>> all (> 3) [1,2] False  >>> all (> 3) [1,2,3,4,5] False  >>> all (> 3) [1..] False  >>> all (> 3) [4..] * Hangs forever *  maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a Source # The largest element of a non-empty structure with respect to the given comparison function. #### Examples Expand Basic usage: >>> maximumBy (compare on length) ["Hello", "World", "!", "Longest", "bar"] "Longest"  minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a Source # The least element of a non-empty structure with respect to the given comparison function. #### Examples Expand Basic usage: >>> minimumBy (compare on length) ["Hello", "World", "!", "Longest", "bar"] "!"  # Searches notElem :: (Foldable t, Eq a) => a -> t a -> Bool infix 4 Source # notElem is the negation of elem. #### Examples Expand Basic usage: >>> 3 notElem [] True  >>> 3 notElem [1,2] True  >>> 3 notElem [1,2,3,4,5] False  For infinite structures, notElem terminates if the value exists at a finite distance from the left side of the structure: >>> 3 notElem [1..] False  >>> 3 notElem ([4..] ++ [3]) * Hangs forever *  find :: Foldable t => (a -> Bool) -> t a -> Maybe a Source # 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. #### Examples Expand Basic usage: >>> find (> 42) [0, 5..] Just 45  >>> find (> 12) [1..7] Nothing  # Overview Foldable structures are reduced to a summary value by accumulating contributions to the result one element at a time. ## Left and right folds Merging the contribution of the current element with an accumulator value from a partial result is performed by an operator function, either explicitly provided by the caller as in foldr, implicit as in length, or partly implicit as in foldMap (where each element is mapped into a Monoid, and the monoid's mappend operator performs the merge). A key distinction is between left-associative and right-associative folds: • In left-associative folds the accumulator is a partial fold over the elements that precede the current element, and is passed to the operator as its first (left) argument. The outer-most application of the operator merges the contribution of the last element of the structure with the contributions of all its predecessors. • In right-associative folds the accumulator is a partial fold over the elements that follow the current element, and is passed to the operator as its second (right) argument. The outer-most application of the operator merges the contribution of the first element of the structure with the contributions of all its successors. These two types of folds are typified by the left-associative strict foldl and the right-associative lazy foldr. foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b  Example usage: >>> foldl' (+) 0 [1..100] 5050 >>> foldr (&&) True (repeat False) False  The first argument of both is an explicit operator that merges the contribution of an element of the structure with a partial fold over, respectively, either the preceding or following elements of the structure. The second argument of both is an initial accumulator value z of type b. This is the result of the fold when the structure is empty. When the structure is non-empty, this is the accumulator value merged with the first element in left-associative folds, or with the last element in right-associative folds. The third and final argument is a Foldable structure containing elements (a, b, c, …). • foldl takes an operator function of the form: f :: b -- accumulated fold of the initial elements -> a -- current element -> b -- updated fold, inclusive of current element  If the structure's last element is y, the result of the fold is: g y . … . g c . g b . g a$ z
where g element !acc = f acc element


Since foldl is strict in the accumulator, this is always a strict reduction with no opportunity for early return or intermediate results. The structure must be finite, since no result is returned until the last element is processed. The advantage of strictness is space efficiency: the final result can be computed without storing a potentially deep stack of lazy intermediate results.

• foldr takes an operator function of the form:

f :: a -- current element
-> b -- accumulated fold of the remaining elements
-> b -- updated fold, inclusive of current element


the result of the fold is:

f a . f b . f c . … $z If each call of f on the current element e, (referenced as (f e) below) returns a structure in which its second argument is captured in a lazily-evaluated component, then the fold of the remaining elements is available to the caller of foldr as a pending computation (thunk) that is computed only when that component is evaluated. Alternatively, if any of the (f e) ignore their second argument, the fold stops there, with the remaining elements unused. As a result, foldr is well suited to define both corecursive and short-circuit reductions. When the operator is always strict in the second argument, foldl is generally a better choice than foldr. When foldr is called with a strict operator, evaluation cannot begin until the last element is reached, by which point a deep stack of pending function applications may have been built up in memory. In finite structures for which right-to-left sequencing no less efficient than left-to-right sequencing, there is no inherent performance distinction between left-associative and right-associative folds. If the structure's Foldable instance takes advantage of this symmetry to also make strict right folds space-efficient and lazy left folds corecursive, one need only take care to choose either a strict or lazy method for the task at hand. ## Recursive and corecursive reduction As observed in the above description of left and right folds, there are three general ways in which a structure can be reduced to a summary value: • Recursive reduction, which is strict in all the elements of the structure. This produces a single final result only after processing the entire input structure, and so the input must be finite. • Corecursion, which yields intermediate results as it encounters additional input elements. Lazy processing of the remaining elements makes the intermediate results available even before the rest of the input is processed. The input may be unbounded, and the caller can stop processing intermediate results early. • Short-circuit reduction, which examines some initial sequence of the input elements, but stops once a termination condition is met, returning a final result based only on the elements considered up to that point. The remaining elements are not considered. The input should generally be finite, because the termination condition might otherwise never be met. Whether a fold is recursive, corecursive or short-circuiting can depend on both the method chosen to perform the fold and on the operator passed to that method (which may be implicit, as with the mappend method of a monoid instance). There are also hybrid cases, where the method and/or operator are not well suited to the task at hand, resulting in a fold that fails to yield incremental results until the entire input is processed, or fails to strictly evaluate results as it goes, deferring all the work to the evaluation of a large final thunk. Such cases should be avoided, either by selecting a more appropriate Foldable method, or by tailoring the operator to the chosen method. The distinction between these types of folds is critical, both in deciding which Foldable method to use to perform the reduction efficiently, and in writing Foldable instances for new structures. Below is a more detailed overview of each type. ### Strict recursive folds Common examples of strict recursive reduction are the various aggregate functions, like sum, product, length, as well as more complex summaries such as frequency counts. These functions return only a single value after processing the entire input structure. In such cases, lazy processing of the tail of the input structure is generally not only unnecessary, but also inefficient. Thus, these and similar folds should be implemented in terms of strict left-associative Foldable methods (typically foldl) to perform an efficient reduction in constant space. Conversely, an implementation of Foldable for a new structure should ensure that foldl actually performs a strict left-associative reduction. The foldMap method is a special case of foldl, in which the initial accumulator is mempty and the operator is mappend . f, where f maps each input element into the Monoid in question. Therefore, foldMap is an appropriate choice under essentially the same conditions as foldl, and its implementation for a given Foldable structure should also be a strict left-associative reduction. While the examples below are not necessarily the most optimal definitions of the intended functions, they are all cases in which foldMap is far more appropriate (as well as more efficient) than the lazy foldMap. length = getSum . foldMap' (const (Sum 1)) sum = getSum . foldMap' Sum product = getProduct . foldMap' Product [ The actual default definitions employ coercions to optimise out getSum and getProduct. ] #### List of strict functions The full list of strict recursive functions in this module is: • Provided the operator is strict in its left argument: foldl :: Foldable t => (b -> a -> b) -> b -> t a -> b • Provided mappend is strict in its left argument: foldMap :: (Foldable t, Monoid m) => (a -> m) -> t a -> m • Provided the instance is correctly defined: length :: Foldable t => t a -> Int sum :: (Foldable t, Num a) => t a -> a product :: (Foldable t, Num a) => t a -> a maximum :: (Foldable t, Ord a) => t a -> a minimum :: (Foldable t, Ord a) => t a -> a maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a  ### Lazy corecursive folds Common examples of lazy corecursive reduction are functions that map and flatten a structure to a lazy stream of result values, i.e. an iterator over the transformed input elements. In such cases, it is important to choose a Foldable method that is lazy in the tail of the structure, such as foldr (or foldMap, if the result Monoid has a lazy mappend as with e.g. ByteString Builders). Conversely, an implementation of foldr for a structure that can accommodate a large (and possibly unbounded) number of elements is expected to be lazy in the tail of the input, allowing operators that are lazy in the accumulator to yield intermediate results incrementally. Such folds are right-associative, with the tail of the stream returned as a lazily evaluated component of the result (an element of a tuple or some other non-strict constructor, e.g. the (:) constructor for lists). The toList function below lazily transforms a Foldable structure to a List. Note that this transformation may be lossy, e.g. for a keyed container (Map, HashMap, …) the output stream holds only the values, not the keys. Lossless transformations to/from lists of (key, value) pairs are typically available in the modules for the specific container types. toList = foldr (:) [] #### List of lazy functions The full list of lazy corecursive functions in this module is: • Provided the reduction function is lazy in its second argument, (otherwise best to use a strict recursive reduction): foldr :: Foldable t => (a -> b -> b) -> b -> t a -> b foldr1 :: Foldable t => (a -> a -> a) -> t a -> a  • Provided the Monoid mappend is lazy in its second argument (otherwise best to use a strict recursive reduction): fold :: Foldable t => Monoid m => t m -> m foldMap :: Foldable t => Monoid m => (a -> m) -> t a -> m  • Provided the instance is correctly defined: toList :: Foldable t => t a -> [a] concat :: Foldable t => t [a] -> [a] concatMap :: Foldable t => (a -> [b]) -> t a -> [b]  ### Short-circuit folds Examples of short-cicuit reduction include various boolean predicates that test whether some or all the elements of a structure satisfy a given condition. Because these don't necessarily consume the entire list, they typically employ foldr with an operator that is conditionally strict in its second argument. Once the termination condition is met the second argument (tail of the input structure) is ignored. No result is returned until that happens. The key distinguishing feature of these folds is conditional strictness in the second argument, it is sometimes evaluated and sometimes not. The simplest (degenerate case) of these is null, which determines whether a structure is empty or not. This only needs to look at the first element, and only to the extent of whether it exists or not, and not its value. In this case termination is guaranteed, and infinite input structures are fine. Its default definition is of course in terms of the lazy foldr: null = foldr (\_ _ -> False) True A more general example is any, which applies a predicate to each input element in turn until it finds the first one for which the predicate is true, at which point it returns success. If, in an infinite input stream the predicate is false for all the elements, any will not terminate, but since it runs in constant space, it typically won't run out of memory, it'll just loop forever. #### List of short-circuit functions The full list of short-circuit folds in this module is: • Boolean predicate folds. These functions examine elements strictly until a condition is met, but then return a result ignoring the rest (lazy in the tail). These may loop forever given an unbounded input where no elements satisy the termination condition. null :: Foldable t => t a -> Bool elem :: Foldable t => Eq a => a -> t a -> Bool notElem :: (Foldable t, Eq a) => a -> t a -> Bool and :: Foldable t => t Bool -> Bool or :: Foldable t => t Bool -> Bool find :: Foldable t => (a -> Bool) -> t a -> Maybe a any :: Foldable t => (a -> Bool) -> t a -> Bool all :: Foldable t => (a -> Bool) -> t a -> Bool  • Many instances of <|> (e.g. the Maybe instance) are conditionally lazy, and use or don't use their second argument depending on the value of the first. These are used with the folds below, which terminate as early as possible, but otherwise generally keep going. Some instances (e.g. for List) are always strict, but the result is lazy in the tail of the output, so that asum for a list of lists is in fact corecursive. These folds are defined in terms of foldr. asum :: (Foldable t, Alternative f) => t (f a) -> f a msum :: (Foldable t, MonadPlus m) => t (m a) -> m a  • Likewise, the *> operator in some Applicative functors, and >> in some monads are conditionally lazy and can short-circuit a chain of computations. The below folds will terminate as early as possible, but even infinite loops can be productive here, when evaluated solely for their stream of IO side-effects. See Data.Traversable for some additional discussion. traverse_ :: (Foldable t, Applicative f) => (a -> f b) -> t a -> f () for_ :: (Foldable t, Applicative f) => t a -> (a -> f b) -> f () sequenceA_ :: (Foldable t, Applicative f) => t (f a) -> f () mapM_ :: (Foldable t, Monad m) => (a -> m b) -> t a -> m () forM_ :: (Foldable t, Monad m) => t a -> (a -> m b) -> m () sequence_ :: (Foldable t, Monad m) => t (m a) -> m ()  • Finally, there's one more special case, foldlM, which can short-circuit when the monad m is a MonadPlus, and the operator invokes mzero. foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b This type of fold is right-associative in the monadic effects, and left-associative in the output value. Given a structure t with elements (a, b, ..., x, y), the result of a fold with operator f is equivalent to: foldlM f z t = do { aa <- f z a; bb <- f aa b; ... ; f xx y } If in a MonadPlus the bind short-circuits, the evaluated effects will be from an initial portion of the sequence. >>> :set -XBangPatterns >>> import Control.Monad >>> import Control.Monad.Trans.Class >>> import Control.Monad.Trans.Maybe >>> import Data.Foldable >>> let f !_ e = when (e > 3) mzero >> lift (print e) >>> runMaybeT$ foldlM f () [0..]
0
1
2
3
Nothing


Contrast this with foldrM, which uses foldl to sequence the effects, and therefore diverges (running out of space) when given an unbounded input structure. The short-circuit condition is never reached

>>> let f e _ = when (e > 3) mzero >> lift (print e)
>>> runMaybeT $foldrM f () [0..] ...hangs...  If instead the operator short-circuits on the initial elements and the structure is finite, foldrM will perform the monadic effects in reverse order: >>> let f e _ = when (e < 3) mzero >> lift (print e) >>> runMaybeT$ foldrM f () [0..5]
5
4
3
Nothing


### Hybrid folds

The below folds, are neither strict reductions that produce a final answer in constant space, nor lazy corecursions, and so have limited applicability. They do have specialised uses, but are best avoided when in doubt.

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


The lazy left-folds (used corecursively) and foldrM (used to sequence actions right-to-left) can be efficient in structures whose Foldable instances take advantage of efficient right-to-left iteration to perform lazy left folds outside-in from the right-most element.

The strict foldr is the least likely to be useful, structures that support efficient sequencing only right-to-left are not at all common.

## Generative Recursion

So far, we have not discussed generative recursion. Unlike recursive reduction or corecursion, instead of processing a sequence of elements already in memory, generative recursion involves producing a possibly unbounded sequence of values from an initial seed value. The canonical example of this is unfoldr for Lists, with variants available for Vectors and various other structures.

A key issue with lists, when used generatively as iterators, rather than as poor-man's containers (see [1]), is that such iterators tend to consume memory when used more than once. A single traversal of a list-as-iterator will run in constant space, but as soon as the list is retained for reuse, its entire element sequence is stored in memory, and the second traversal reads the copy, rather than regenerates the elements. It is sometimes better to recompute the elements rather than memoise the list.

Memoisation happens because the built-in Haskell list [] is represented as data, either empty or a cons-cell holding the first element and the tail of the list. The Foldable class enables a variant representation of iterators as functions, which take an operator and a starting accumulator and output a summary result.

The fmlist package takes this approach, by representing a list via its foldMap action.

Below we implement an analogous data structure using a representation based on foldr. This is an example of Church encoding (named after Alonzo Church, inventor of the lambda calculus).

{-# LANGUAGE RankNTypes #-}
newtype FRList a = FR { unFR :: forall b. (a -> b -> b) -> b -> b }

The unFR field of this type is essentially its foldr method with the list as its first rather than last argument. Thus we immediately get a Foldable instance (and a toList function mapping an FRList to a regular list).

instance Foldable FRList where
foldr f z l = unFR l f z
-- With older versions of @base@, also define sum, product, ...
-- to ensure use of the strict foldl'.
-- sum = foldl' (+) 0
-- ...

We can convert a regular list to an FRList with:

fromList :: [a] -> FRList a
fromList as = FRList $\ f z -> foldr f z as However, reuse of an FRList obtained in this way will typically memoise the underlying element sequence. Instead, we can define FRList terms directly: -- | Immediately return the initial accumulator nil :: FRList a nil = FRList$ \ _ z -> z
{-# INLINE nil #-}
-- | Fold the tail to use as an accumulator with the new initial element
cons :: a -> FRList a -> FRList a
cons a l = FRList $\ f z -> f a (unFR l f z) {-# INLINE cons #-} More crucially, we can also directly define the key building block for generative recursion: -- | Generative recursion, dual to foldr. unfoldr :: (s -> Maybe (a, s)) -> s -> FRList a unfoldr g s0 = FR generate where generate f z = loop s0 where loop s | Just (a, t) <- g s = f a (loop t) | otherwise = z {-# INLINE unfoldr #-} Which can, for example, be specialised to number ranges: -- | Generate a range of consecutive integral values. range :: (Ord a, Integral a) => a -> a -> FRList a range lo hi = unfoldr (\s -> if s > hi then Nothing else Just (s, s+1)) lo {-# INLINE range #-} The program below, when compiled with optimisation: main :: IO () main = do let r :: FRList Int r = range 1 10000000 in print (sum r, length r) produces the expected output with no noticeable garbage-collection, despite reuse of the FRList term r. (50000005000000,10000000) 52,120 bytes allocated in the heap 3,320 bytes copied during GC 44,376 bytes maximum residency (1 sample(s)) 25,256 bytes maximum slop 3 MiB total memory in use (0 MB lost due to fragmentation) The Weak Head Normal Form of an FRList is a lambda abstraction not a data value, and reuse does not lead to memoisation. Reuse of the iterator above is somewhat contrived, when computing multiple folds over a common list, you should generally traverse a list only once. The goal is to demonstrate that the separate computations of the sum and length run efficiently in constant space, despite reuse. This would not be the case with the list [1..10000000]. This is, however, an artificially simple reduction. More typically, there are likely to be some allocations in the inner loop, but the temporary storage used will be garbage-collected as needed, and overall memory utilisation will remain modest and will not scale with the size of the list. If we go back to built-in lists (i.e. []), but avoid reuse by performing reduction in a single pass, as below: data PairS a b = P !a !b -- We define a strict pair datatype main :: IO () main = do let l :: [Int] l = [1..10000000] in print$ average l
where
sumlen :: PairS Int Int -> Int -> PairS Int Int
sumlen (P s l) a = P (s + a) (l + 1)

average is =
let (P s l) = foldl' sumlen (P 0 0) is
in (fromIntegral s :: Double) / fromIntegral l

the result is again obtained in constant space:

5000000.5
102,176 bytes allocated in the heap
3,320 bytes copied during GC
44,376 bytes maximum residency (1 sample(s))
25,256 bytes maximum slop
3 MiB total memory in use (0 MB lost due to fragmentation)

(and, in fact, faster than with FRList by a small factor).

The [] list structure works as an efficient iterator when used just once. When space-leaks via list reuse are not a concern, and/or memoisation is actually desirable, the regular list implementation is likely to be faster. This is not a suggestion to replace all your uses of [] with a generative alternative.

The FRList type could be further extended with instances of Functor, Applicative, Monad, Alternative, etc., and could then provide a fully-featured list type, optimised for reuse without space-leaks. If, however, all that's required is space-efficient, re-use friendly iteration, less is perhaps more, and just Foldable may be sufficient.

## Avoiding multi-pass folds

In applications where you want to compute a composite function of a structure, which requires more than one aggregate as an input, it is generally best to compute all the aggregates in a single pass, rather than to traverse the same structure repeatedly.

The foldl package implements a robust general framework for dealing with this situation. If you choose to to do it yourself, with a bit of care, the simplest cases are not difficult to handle directly. You just need to accumulate the individual aggregates as strict components of a single data type, and then apply a final transformation to it to extract the composite result. For example, computing an average requires computing both the sum and the length of a (non-empty) structure and dividing the sum by the length:

import Data.Foldable (foldl')

data PairS a b = P !a !b -- We define a strict pair datatype

-- | Compute sum and length in a single pass, then reduce to the average.
average :: (Foldable f, Fractional a) => f a -> a
average xs =
let sumlen (P s l) a = P (s + a) (l + 1 :: Int)
(P s l) = foldl' sumlen (P 0 0) xs
in s / fromIntegral l

The above example is somewhat contrived, some structures keep track of their length internally, and can return it in $$\mathcal{O}(1)$$ time, so this particular recipe for averages is not always the most efficient. In general, composite aggregate functions of large structures benefit from single-pass reduction. This is especially the case when reuse of a list and memoisation of its elements is thereby avoided,

# Defining instances

For many structures reasonably efficient Foldable instances can be derived automatically, by enabling the DeriveFoldable GHC extension. When this works, it is generally not necessary to define a custom instance by hand. Though in some cases one may be able to get slightly faster hand-tuned code, care is required to avoid producing slower code, or code that is not sufficiently lazy, strict or lawful.

The hand-crafted instances can get away with only defining one of foldr or foldMap. All the other methods have default definitions in terms of one of these. The default definitions have the expected strictness and the expected asymptotic runtime and space costs, modulo small constant factors. If you choose to hand-tune, benchmarking is advised to see whether you're doing better than the default derived implementations, plus careful tests to ensure that the custom methods are correct.

Below we construct a Foldable instance for a data type representing a (finite) binary tree with depth-first traversal.

data Tree a = Empty | Leaf a | Node (Tree a) a (Tree a)

a suitable instance would be:

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

The Node case is a right fold of the left subtree whose initial value is a right fold of the rest of the tree.

For example, when f is (:), all three cases return an immediate value, respectively z or a cons cell holding x or l, with the remainder the structure, if any, encapsulated in a lazy thunk. This meets the expected efficient corecursive behaviour of foldr.

Alternatively, one could define foldMap:

instance Foldable Tree where
foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node l k r) = foldMap f l <> f k <> foldMap f r

And indeed some efficiency may be gained by directly defining both, avoiding some indirection in the default definitions that express one in terms of the other. If you implement just one, likely foldr is the better choice.

A binary tree typically (when balanced, or randomly biased) provides equally efficient access to its left and right subtrees. This makes it possible to define a foldl optimised for corecursive folds with operators that are lazy in their first (left) argument.

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
--
foldMap f Empty = mempty
foldMap f (Leaf x) = f x
foldMap f (Node l k r) = foldMap f l <> f k <> foldMap f r
--
foldl f z Empty = z
foldl f z (Leaf x) = f z x
foldl f z (Node l k r) = foldl f (f (foldl f z l) k) r

Now left-to-right and right-to-left iteration over the structure elements are equally efficient (note the mirror-order output when using foldl):

>>> foldr (\e acc -> e : acc) [] (Node (Leaf 1) 2 (Leaf 3))
[1,2,3]
>>> foldl (\acc e -> e : acc) [] (Node (Leaf 1) 2 (Leaf 3))
[3,2,1]


We can carry this further, and define more non-default methods...

The structure definition actually admits trees that are unbounded on either or both sides. The only fold that can plausibly terminate for a tree unbounded on both left and right is null, when defined as shown below. The default definition in terms of foldr diverges if the tree is unbounded on the left. Here we define a variant that avoids travelling down the tree to find the left-most element and just examines the root node.

   null Empty = True
null _     = False

This is a sound choice also for finite trees.

In practice, unbounded trees are quite uncommon, and can barely be said to be Foldable. They would typically employ breadth first traversal, and would support only corecursive and short-circuit folds (diverge under strict reduction).

Returning to simpler instances, defined just in terms of foldr, it is somewhat surprising that a fairly efficient default implementation of the strict foldl is defined in terms of lazy foldr when only the latter is explicitly provided by the instance. It may be instructive to take a look at how this works.

### Being strict by being lazy

The left fold:

foldl' f z [a, b, …, x, y]

can be expanded as:

id . g y . g x . … . g b . g a $z where g = flip f  In which to maintain the expected strictness we need to perform function application eagerly, and composition lazily. To that end we introduce a new function f' which maps each element x to an eager application of g x to its argument, followed by an application of a lazily computed composition (k) of the g e functions for the remaining elements e: f' x k z = k$! (g x) z = k $! f z x We see that a lazy foldr of the g e endomorphisms, with f' as as the operator, in fact yields a strict left fold, that avoids building a deep chain of intermediate thunks: foldl' f z0 xs = foldr f' id xs z0 where f' x k z = k$! f z x

The function applied to z0 is built corecursively, and its terms are applied eagerly to the accumulator before further terms are applied to the result. So, as promised, this will run in constant space, and GHC is able to optimise this to an efficient loop.

# Laws

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
product = getProduct . foldMap' Product

but are generally more efficient when defined more directly as:

sum = foldl' (+) 0
sum = foldl' (*) 1

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)

# Notes

The absence of a Functor superclass allows Foldable structures to impose constraints on their element types. Thus, Sets are Foldable, even though Set imposes an Ord constraint on its elements (this precludes defining a Functor instance for Set).

The Foldable class makes it possible to use idioms familiar from the List type with container structures that are better suited to the task at hand. This allows a user to substitute more appropriate Foldable data types for Lists without requiring new idioms (see [1] for when not to use lists).

The more general methods of the Foldable class are now exported by the Prelude in place of the original List-specific methods (see the FTP Proposal). The List-specific variants are for now still available in GHC.OldList, but that module is intended only as a transitional aid, and may be removed in the future.

Surprises can arise from the Foldable instance of the 2-tuple (a,) which now behaves as a 1-element Foldable container in its second slot. In contexts where a specific monomorphic type is expected, and you want to be able to rely on type errors to guide refactoring, it may make sense to define and use less-polymorphic variants of some of the Foldable methods.

Below are two examples showing a definition of a reusable less-polymorphic sum and a one-off in-line specialisation of length:

{-# LANGUAGE TypeApplications #-}

mySum :: Num a => [a] -> a
mySum = sum

type SlowVector a = [a]
slowLength :: SlowVector -> Int
slowLength v = length @[] v`

In both cases, if the data type to which the function is applied changes to something other than a list, the call-site will no longer compile until appropriate changes are made.