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

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

>>> fold (repeat Nothing)
* Hangs forever *

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

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

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

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

>>> foldr (||) False [False, True, False]
True

>>> foldr (||) False []
False

>>> foldr (\c acc -> acc ++ [c]) "foo" ['a', 'b', 'c', 'd']
"foodcba"

>>> foldr (||) False (True : repeat False)
True

>>> foldr (||) False (repeat False ++ [True])
* Hangs forever *

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

foldr' is a variant of foldr that performs strict reduction from right to left, i.e. starting with the right-most element. The input structure must be finite, otherwise foldr' runs out of space (diverges).

If you want a strict right fold in constant space, you need a structure that supports faster than O(n) access to the right-most element, such as Seq from the containers package.

This method does not run in constant space for structures such as lists that don't support efficient right-to-left iteration and so require O(n) space to perform right-to-left reduction. Use of this method with such a structure is a hint that the chosen structure may be a poor fit for the task at hand. If the order in which the elements are combined is not important, use foldl' instead.

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

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

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

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

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

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

>>> toList Nothing
[]

>>> toList (Just 42)
[42]

>>> toList (Left "foo")
[]

>>> toList (Node (Leaf 5) 17 (Node Empty 12 (Leaf 8)))
[5,17,12,8]

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

>>> null []
True

>>> null [1]
False

>>> 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 leftmost. Instances for structures that can compute the element count faster than via element-by-element counting, should provide a specialised implementation.

Examples

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

>>> 3 `elem` []
False

>>> 3 `elem` [1,2]
False

>>> 3 `elem` [1,2,3,4,5]
True

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

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

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

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

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