GHC.Internal.Data.Foldable

Methods

• fold :: Monoid m => t m -> m

  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

  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

  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

  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

  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

  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"

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

  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

  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

  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.

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

  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

  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 *

  WARNING: When it comes to lists, you always want to use either foldl' or foldr instead.

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

  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

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

  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

  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

  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

  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]

  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

  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]

• null :: t a -> Bool

  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

  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 leftmost element).

  >>> null [1..]False

• length :: t a -> Int

  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

  Basic usage:

  >>> length []0

  >>> length ['a', 'b', 'c']3>>> length [1..]* Hangs forever *

• elem :: Eq a => a -> t a -> Boolinfix 4

  Does the element occur in the structure?

  Note: elem is often used in infix form.

  Examples

  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 *

• maximum :: Ord a => t a -> a

  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

  Basic usage:

  >>> maximum [1..10]10

  >>> maximum []*** Exception: Prelude.maximum: empty list

  >>> maximum Nothing*** Exception: maximum: empty structure

  WARNING: This function is partial for possibly-empty structures like lists.

• minimum :: Ord a => t a -> a

  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

  Basic usage:

  >>> minimum [1..10]1

  >>> minimum []*** Exception: Prelude.minimum: empty list

  >>> minimum Nothing*** Exception: minimum: empty structure

  WARNING: This function is partial for possibly-empty structures like lists.

• sum :: Num a => t a -> a

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

  Examples

  Basic usage:

  >>> sum []0

  >>> sum [42]42

  >>> sum [1..10]55

  >>> sum [4.1, 2.0, 1.7]7.8

  >>> sum [1..]* Hangs forever *

• product :: Num a => t a -> a

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

  Examples

  Basic usage:

  >>> product []1

  >>> product [42]42

  >>> product [1..10]3628800

  >>> product [4.1, 2.0, 1.7]13.939999999999998

  >>> product [1..]* Hangs forever *