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 #

Data structures that can be folded.

For example, given a data type

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

a suitable instance would be

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

This is suitable even for abstract types, as the monoid is assumed to satisfy the monoid laws. Alternatively, one could define foldr:

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

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

but may be less defined.

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)

Minimal complete definition

Methods

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

Combine the elements of a structure using a monoid.

#### Examples

Expand

Basic usage:

>>> fold [[1, 2, 3], [4, 5], [6], []]
[1,2,3,4,5,6]
>>> fold [Sum 1, Sum 3, Sum 5]
Sum {getSum = 9}

Infinite structures never terminate:

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

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

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

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

Infinite structures never terminate:

>>> foldMap Sum [1..]
* Hangs forever *

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

A variant of foldMap that is strict in the accumulator.

Since: base-4.13.0.0

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

Right-associative fold of a structure.

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, foldr can produce a terminating expression from an infinite 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 (\nextChar reversedString -> reversedString ++ [nextChar]) "foo" ['a', 'b', 'c', 'd']
"foodcba"
##### Infinite structures

⚠️ Applying foldr to infinite structures usually doesn't terminate.

It may still terminate in 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 folding function is lazy on its second argument:

>>> foldr (\nextElement accumulator -> nextElement : fmap (+3) accumulator) [42] (repeat 1)
[1,4,7,10,13,16,19,22,25,28,31,34,37,40,43...
>>> take 5 \$ foldr (\nextElement accumulator -> nextElement : fmap (+3) accumulator) [42] (repeat 1)
[1,4,7,10,13]

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

Right-associative fold of a structure, but with strict application of the operator.

Since: base-4.6.0.0

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

Left-associative fold of a structure.

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. This means that foldl' will diverge if given an infinite list.

Also note that if you want an efficient left-fold, you probably want to use foldl' instead of foldl. The reason for this is that 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

Basic usage:

>>> foldl (+) 42 (Node (Leaf 1) 3 (Node Empty 4 (Leaf 2)))
52
>>> foldl (+) 42 Empty
42
>>> foldl (\string nextElement -> nextElement : string) "abcd" (Node (Leaf 'd') 'e' (Node Empty 'f' (Leaf 'g')))
"gfedabcd"

Left-folding infinite structures never terminates:

>>> let infiniteNode = Node Empty 1 infiniteNode in foldl (+) 42 infiniteNode
* Hangs forever *

Evaluating the head of the result (when applicable) does not terminate, unlike foldr:

>>> let infiniteNode = Node Empty 'd' infiniteNode in take 5 (foldl (\string nextElement -> nextElement : string) "abc" infiniteNode)
* 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 list to a single, monolithic result (e.g. length).

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.

#### 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 optimized for structures that are similar to cons-lists, because there is no general way to do better.

#### Examples

Expand

Basic usage:

>>> null []
True
>>> null [1]
False

null terminates even for infinite structures:

>>> 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 is optimized for structures that are similar to cons-lists, because there is no general way to do better.

#### 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, elem terminates if the 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.

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

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

# 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, associating to the right, i.e. from right to left.

#### Examples

Expand

Basic usage:

>>> foldrM (\string acc -> print string >> pure (acc + length string)) 42 ["Hello", "world", "!"]
"!"
"world"
"Hello"
53

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

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

#### Examples

Expand

Basic usage:

>>> foldlM (\acc string -> print string >> pure (acc + length string)) 42 ["Hello", "world", "!"]
"Hello"
"world"
"!"
53

# Folding actions

## Applicative actions

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

Map each element of a structure to an action, evaluate these actions from left to right, and ignore the results. For a version that doesn't ignore the results see traverse.

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

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

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

#### Examples

Expand

Basic usage:

>>> asum [Just "Hello", Nothing, Just "World"]
Just "Hello"

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.

As of base 4.8.0.0, mapM_ is just traverse_, specialized to Monad.

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.

As of base 4.8.0.0, forM_ is just for_, specialized to Monad.

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.

As of base 4.8.0.0, sequence_ is just sequenceA_, specialized to Monad.

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

The sum of a collection of actions, generalizing concat. As of base 4.8.0.0, msum is just asum, specialized 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 (Node (Leaf [1, 2, 3]) [4, 5] (Node Empty [6] (Leaf [])))
[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) (Node (Leaf [1..]) [10..] Empty)
[1,2,3,10,11,12]

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,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,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 (> 4) (Node (Leaf 3) 17 (Node Empty 12 (Leaf 8)))
Just 17
>>> find (> 12) [1..7]
Nothing