Copyright | Ross Paterson 2005 |
---|---|
License | BSD-style (see the LICENSE file in the distribution) |
Maintainer | libraries@haskell.org |
Stability | stable |
Portability | portable |
Safe Haskell | Trustworthy |
Language | Haskell2010 |
Class of data structures that can be folded to a summary value.
Synopsis
- class Foldable (t :: Type -> Type) where
- fold :: Monoid m => t m -> m
- foldMap :: Monoid m => (a -> m) -> t a -> m
- foldMap' :: Monoid m => (a -> m) -> t a -> m
- foldr :: (a -> b -> b) -> b -> t a -> b
- foldr' :: (a -> b -> b) -> b -> t a -> b
- foldl :: (b -> a -> b) -> b -> t a -> b
- foldl' :: (b -> a -> b) -> b -> t a -> b
- foldr1 :: (a -> a -> a) -> t a -> a
- foldl1 :: (a -> a -> a) -> t a -> a
- toList :: t a -> [a]
- null :: t a -> Bool
- length :: t a -> Int
- elem :: Eq a => a -> t a -> Bool
- maximum :: Ord a => t a -> a
- minimum :: Ord a => t a -> a
- sum :: Num a => t a -> a
- product :: Num a => t a -> a
- foldrM :: (Foldable t, Monad m) => (a -> b -> m b) -> b -> t a -> m b
- foldlM :: (Foldable t, Monad m) => (b -> a -> m b) -> b -> t a -> m b
- 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 ()
- asum :: (Foldable t, Alternative f) => t (f a) -> f a
- 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 ()
- msum :: (Foldable t, MonadPlus m) => t (m a) -> m a
- concat :: Foldable t => t [a] -> [a]
- concatMap :: Foldable t => (a -> [b]) -> t a -> [b]
- and :: Foldable t => t Bool -> Bool
- or :: Foldable t => t Bool -> Bool
- any :: Foldable t => (a -> Bool) -> t a -> Bool
- all :: Foldable t => (a -> Bool) -> t a -> Bool
- maximumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
- minimumBy :: Foldable t => (a -> a -> Ordering) -> t a -> a
- notElem :: (Foldable t, Eq a) => a -> t a -> Bool
- find :: Foldable t => (a -> Bool) -> t a -> Maybe a
Documentation
class Foldable (t :: Type -> Type) 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.
For the class laws see the Laws section of Data.Foldable.
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
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
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
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
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 #
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
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 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
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
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 *
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]
Since: base-4.8.0.0
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
Since: base-4.8.0.0
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 *
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
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 :: 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
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.
Since: base-4.8.0.0
minimum :: 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
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.
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
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
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
Foldable NonEmpty Source # | Since: base-4.9.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable Identity Source # | Since: base-4.8.0.0 |
Defined in GHC.Internal.Data.Functor.Identity fold :: 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 # | |
Foldable First Source # | Since: base-4.8.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable Last Source # | Since: base-4.8.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable Down Source # | Since: base-4.12.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable Dual Source # | Since: base-4.8.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable Product Source # | Since: base-4.8.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable Sum Source # | Since: base-4.8.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable ZipList Source # | Since: base-4.9.0.0 |
Defined in GHC.Internal.Functor.ZipList fold :: 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 # | |
Foldable Par1 Source # | Since: base-4.9.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable Maybe Source # | Since: base-2.1 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable Solo Source # | Since: base-4.15 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable [] Source # | Since: base-2.1 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # elem :: Eq a => a -> [a] -> Bool Source # maximum :: Ord a => [a] -> a Source # minimum :: Ord a => [a] -> a Source # | |
Foldable (Array i) Source # | Since: base-4.8.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable (Either a) Source # | Since: base-4.7.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable (Proxy :: Type -> Type) Source # | Since: base-4.7.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable (U1 :: Type -> Type) Source # | Since: base-4.9.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # 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 # | |
Foldable (UAddr :: Type -> Type) Source # | Since: base-4.9.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable (UChar :: Type -> Type) Source # | Since: base-4.9.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable (UDouble :: Type -> Type) Source # | Since: base-4.9.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable (UFloat :: Type -> Type) Source # | Since: base-4.9.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable (UInt :: Type -> Type) Source # | Since: base-4.9.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable (UWord :: Type -> Type) Source # | Since: base-4.9.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable (V1 :: Type -> Type) Source # | Since: base-4.9.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # 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 # | |
Foldable ((,) a) Source # | Since: base-4.7.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable (Const m :: Type -> Type) Source # | Since: base-4.7.0.0 |
Defined in GHC.Internal.Data.Functor.Const fold :: 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 # | |
Foldable f => Foldable (Ap f) Source # | Since: base-4.12.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable f => Foldable (Alt f) Source # | Since: base-4.12.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable f => Foldable (Rec1 f) Source # | Since: base-4.9.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
(Foldable f, Foldable g) => Foldable (f :*: g) Source # | Since: base-4.9.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
(Foldable f, Foldable g) => Foldable (f :+: g) Source # | Since: base-4.9.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable (K1 i c :: Type -> Type) Source # | Since: base-4.9.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
(Foldable f, Foldable g) => Foldable (f :.: g) Source # | Since: base-4.9.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # | |
Foldable f => Foldable (M1 i c f) Source # | Since: base-4.9.0.0 |
Defined in GHC.Internal.Data.Foldable fold :: 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 # |
Special biased folds
foldrM :: (Foldable t, Monad m) => (a -> b -> m b) -> b -> t a -> m b Source #
Right-to-left monadic fold over the elements of a structure.
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 aa <- f a bb return aa -- Just @return z@ when the structure is empty
For a Monad m
, given two functions f1 :: a -> m b
and f2 :: b -> m c
,
their Kleisli composition (f1 >=> f2) :: a -> m c
is defined by:
(f1 >=> f2) a = f1 a >>= f2
Another way of thinking about foldrM
is that it amounts to an application
to z
of a Kleisli composition:
foldrM f z t = f y >=> f x >=> ... >=> f b >=> f a $ z
The monadic effects of foldrM
are sequenced from right to left, and e.g.
folds of infinite lists will diverge.
If at some step the bind operator (
short-circuits (as with, e.g.,
>>=
)mzero
in a MonadPlus
), the evaluated effects will be from a tail of the
element 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 outermost application of
f
is to the leftmost element a
, so that, ignoring effects, the result
looks like a right fold:
a `f` (b `f` (c `f` (... (x `f` (y `f` z))))).
Examples
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 #
Left-to-right monadic fold over the elements of a structure.
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 yy <- f xx y return yy -- Just @return z@ when the structure is empty
For a Monad m
, given two functions f1 :: a -> m b
and f2 :: b -> m c
,
their Kleisli composition (f1 >=> f2) :: a -> m c
is defined by:
(f1 >=> f2) a = f1 a >>= f2
Another way of thinking about foldlM
is that it amounts to an application
to z
of a Kleisli composition:
foldlM f z t = flip f a >=> flip f b >=> ... >=> flip f x >=> flip f y $ z
The monadic effects of foldlM
are sequenced from left to right.
If at some step the bind operator (
short-circuits (as with, e.g.,
>>=
)mzero
in a MonadPlus
), the evaluated effects will be from an initial
segment of the element 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 outermost application of
f
is to the rightmost element y
, so that, ignoring effects, the result
looks like a left fold:
((((z `f` a) `f` b) ... `f` w) `f` x) `f` y
Examples
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
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
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
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 using (<|>)
, generalizing concat
.
asum
is just like msum
, but generalised to Alternative
.
Examples
Basic usage:
>>>
asum [Just "Hello", Nothing, Just "World"]
Just "Hello"
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.
Specialized folds
concat :: Foldable t => t [a] -> [a] Source #
The concatenation of all the elements of a container of lists.
Examples
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
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
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
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
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
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
Basic usage:
>>>
maximumBy (compare `on` length) ["Hello", "World", "!", "Longest", "bar"]
"Longest"
WARNING: This function is partial for possibly-empty structures like lists.
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
Basic usage:
>>>
minimumBy (compare `on` length) ["Hello", "World", "!", "Longest", "bar"]
"!"
WARNING: This function is partial for possibly-empty structures like lists.
Searches
notElem :: (Foldable t, Eq a) => a -> t a -> Bool infix 4 Source #
notElem
is the negation of elem
.
Examples
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 *