Relude.Foldable.Reexport

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

For the class laws see the Laws section of Data.Foldable#laws.

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 *

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 *

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 *

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"

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]

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]

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

Basic usage:

>>> find (> 42) [0, 5..]Just 45

>>> find (> 12) [1..7]Nothing

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]0123[3,2,1,0]

forM_ is mapM_ with its arguments flipped. For a version that doesn't ignore the results see Data.Traversable.forM.

forM_ is just like for_, but specialised to monadic actions.

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

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 Data.Traversable.mapM.

mapM_ is just like traverse_, but specialised to monadic actions.

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 *

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

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 Data.Traversable.sequence.

sequence_ is just like sequenceA_, but specialised to monadic actions.

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

Functors representing data structures that can be transformed to structures of the same shape by performing an Applicative (or, therefore, Monad) action on each element from left to right.

A more detailed description of what same shape means, the various methods, how traversals are constructed, and example advanced use-cases can be found in the Overview section of Data.Traversable#overview.

For the class laws see the Laws section of Data.Traversable#laws.

forM is mapM with its arguments flipped. For a version that ignores the results see Data.Foldable.forM_.

The mapAccumL function behaves like a combination of fmap and foldl; it applies a function to each element of a structure, passing an accumulating parameter from left to right, and returning a final value of this accumulator together with the new structure.

Examples

Basic usage:

>>> mapAccumL (\a b -> (a + b, a)) 0 [1..10](55,[0,1,3,6,10,15,21,28,36,45])

>>> mapAccumL (\a b -> (a <> show b, a)) "0" [1..5]("012345",["0","01","012","0123","01234"])

The mapAccumR function behaves like a combination of fmap and foldr; it applies a function to each element of a structure, passing an accumulating parameter from right to left, and returning a final value of this accumulator together with the new structure.

Examples

Basic usage:

>>> mapAccumR (\a b -> (a + b, a)) 0 [1..10](55,[54,52,49,45,40,34,27,19,10,0])

>>> mapAccumR (\a b -> (a <> show b, a)) "0" [1..5]("054321",["05432","0543","054","05","0"])

Bifoldable identifies foldable structures with two different varieties of elements (as opposed to Foldable, which has one variety of element). Common examples are Either and (,):

instance Bifoldable Either where
  bifoldMap f _ (Left  a) = f a
  bifoldMap _ g (Right b) = g b

instance Bifoldable (,) where
  bifoldr f g z (a, b) = f a (g b z)

Some examples below also use the following BiList to showcase empty Bifoldable behaviors when relevant (Either and (,) containing always exactly resp. 1 and 2 elements):

data BiList a b = BiList [a] [b]

instance Bifoldable BiList where
  bifoldr f g z (BiList as bs) = foldr f (foldr g z bs) as

A minimal Bifoldable definition consists of either bifoldMap or bifoldr. When defining more than this minimal set, one should ensure that the following identities hold:

bifold ≡ bifoldMap id id
bifoldMap f g ≡ bifoldr (mappend . f) (mappend . g) mempty
bifoldr f g z t ≡ appEndo (bifoldMap (Endo . f) (Endo . g) t) z

If the type is also an instance of Foldable, then it must satisfy (up to laziness):

bifoldl const ≡ foldl
bifoldr (flip const) ≡ foldr
bifoldMap (const mempty) ≡ foldMap

If the type is also a Bifunctor instance, it should satisfy:

bifoldMap f g ≡ bifold . bimap f g

which implies that

bifoldMap f g . bimap h i ≡ bifoldMap (f . h) (g . i)

Collects the list of elements of a structure, from left to right.

Examples

Basic usage:

>>> biList (18, 42)[18,42]

>>> biList (Left 18)[18]

Determines whether all elements of the structure satisfy their appropriate predicate argument. Empty structures yield True.

Examples

Basic usage:

>>> biall even isDigit (27, 't')False

>>> biall even isDigit (26, '8')True

>>> biall even isDigit (Left 27)False

>>> biall even isDigit (Left 26)True

>>> biall even isDigit (BiList [26, 52] ['3', '8'])True

Empty structures yield True:

>>> biall even isDigit (BiList [] [])True

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

>>> biand (True, False)False

>>> biand (True, True)True

>>> biand (Left True)True

Empty structures yield True:

>>> biand (BiList [] [])True

A False value finitely far from the left end yields False (short circuit):

>>> biand (BiList [True, True, False, True] (repeat True))False

A False value infinitely far from the left end hangs:

> biand (BiList (repeat True) [False])
* Hangs forever *

An infinitely True value hangs:

> biand (BiList (repeat True) [])
* Hangs forever *

Determines whether any element of the structure satisfies its appropriate predicate argument. Empty structures yield False.

Examples

Basic usage:

>>> biany even isDigit (27, 't')False

>>> biany even isDigit (27, '8')True

>>> biany even isDigit (26, 't')True

>>> biany even isDigit (Left 27)False

>>> biany even isDigit (Left 26)True

>>> biany even isDigit (BiList [27, 53] ['t', '8'])True

Empty structures yield False:

>>> biany even isDigit (BiList [] [])False

The sum of a collection of actions, generalizing biconcat.

Examples

Basic usage:

>>> biasum (Nothing, Nothing)Nothing

>>> biasum (Nothing, Just 42)Just 42

>>> biasum (Just 18, Nothing)Just 18

>>> biasum (Just 18, Just 42)Just 18

Does the element occur in the structure?

Examples

Basic usage:

>>> bielem 42 (17, 42)True

>>> bielem 42 (17, 43)False

>>> bielem 42 (Left 42)True

>>> bielem 42 (Right 13)False

>>> bielem 42 (BiList [1..5] [1..100])True

>>> bielem 42 (BiList [1..5] [1..41])False

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

Basic usage:

>>> bifind even (27, 53)Nothing

>>> bifind even (27, 52)Just 52

>>> bifind even (26, 52)Just 26

Empty structures always yield Nothing:

>>> bifind even (BiList [] [])Nothing

As bifoldl, but strict in the result of the reduction functions at each step.

This ensures that each step of the bifold 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, monolithic result (e.g., bilength).

Left associative monadic bifold over a structure.

Examples

Basic usage:

>>> bifoldlM (\a b -> print b >> pure a) (\a c -> print (show c) >> pure a) 42 ("Hello", True)"Hello""True"42

>>> bifoldlM (\a b -> print b >> pure a) (\a c -> print (show c) >> pure a) 42 (Right True)"True"42

>>> bifoldlM (\a b -> print b >> pure a) (\a c -> print (show c) >> pure a) 42 (Left "Hello")"Hello"42

As bifoldr, but strict in the result of the reduction functions at each step.

Right associative monadic bifold over a structure.

As bitraverse_, but with the structure as the primary argument. For a version that doesn't ignore the results, see bifor.

Examples

Basic usage:

>>> bifor_ ("Hello", True) print (print . show)"Hello""True"

>>> bifor_ (Right True) print (print . show)"True"

>>> bifor_ (Left "Hello") print (print . show)"Hello"

Returns the size/length of a finite structure as an Int.

Examples

Basic usage:

>>> bilength (True, 42)2

>>> bilength (Right 42)1

>>> bilength (BiList [1,2,3] [4,5])5

>>> bilength (BiList [] [])0

On infinite structures, this function hangs:

> bilength (BiList [1..] [])
* Hangs forever *

Test whether the structure is empty.

Examples

Basic usage:

>>> binull (18, 42)False

>>> binull (Right 42)False

>>> binull (BiList [] [])True

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

>>> bior (True, False)True

>>> bior (False, False)False

>>> bior (Left True)True

Empty structures yield False:

>>> bior (BiList [] [])False

A True value finitely far from the left end yields True (short circuit):

>>> bior (BiList [False, False, True, False] (repeat False))True

A True value infinitely far from the left end hangs:

> bior (BiList (repeat False) [True])
* Hangs forever *

An infinitely False value hangs:

> bior (BiList (repeat False) [])
* Hangs forever *

Evaluate each action in the structure from left to right, and ignore the results. For a version that doesn't ignore the results, see bisequence.

Examples

Basic usage:

>>> bisequence_ (print "Hello", print "World")"Hello""World"

>>> bisequence_ (Left (print "Hello"))"Hello"

>>> bisequence_ (Right (print "World"))"World"

Map each element of a structure using one of two actions, evaluate these actions from left to right, and ignore the results. For a version that doesn't ignore the results, see bitraverse.

Examples

Basic usage:

>>> bitraverse_ print (print . show) ("Hello", True)"Hello""True"

>>> bitraverse_ print (print . show) (Right True)"True"

>>> bitraverse_ print (print . show) (Left "Hello")"Hello"

Bitraversable identifies bifunctorial data structures whose elements can be traversed in order, performing Applicative or Monad actions at each element, and collecting a result structure with the same shape.

As opposed to Traversable data structures, which have one variety of element on which an action can be performed, Bitraversable data structures have two such varieties of elements.

A definition of bitraverse must satisfy the following laws:

Naturality

bitraverse (t . f) (t . g) ≡ t . bitraverse f g

for every applicative transformation

t

Identity

bitraverse Identity Identity ≡ Identity

Composition

Compose . fmap (bitraverse g1 g2) . bitraverse f1 f2 ≡ bitraverse (Compose . fmap g1 . f1) (Compose . fmap g2 . f2)

where an applicative transformation is a function

t :: (Applicative f, Applicative g) => f a -> g a

preserving the Applicative operations:

t (pure x) ≡ pure x
t (f <*> x) ≡ t f <*> t x

and the identity functor Identity and composition functors Compose are from Data.Functor.Identity and Data.Functor.Compose.

Some simple examples are Either and (,):

instance Bitraversable Either where
  bitraverse f _ (Left x) = Left <$> f x
  bitraverse _ g (Right y) = Right <$> g y

instance Bitraversable (,) where
  bitraverse f g (x, y) = (,) <$> f x <*> g y

Bitraversable relates to its superclasses in the following ways:

bimap f g ≡ runIdentity . bitraverse (Identity . f) (Identity . g)
bifoldMap f g ≡ getConst . bitraverse (Const . f) (Const . g)

These are available as bimapDefault and bifoldMapDefault respectively.

If the type is also an instance of Traversable, then it must satisfy (up to laziness):

traverse ≡ bitraverse pure

A default definition of bifoldMap in terms of the Bitraversable operations.

bifoldMapDefault f g ≡
    getConst . bitraverse (Const . f) (Const . g)

bifor is bitraverse with the structure as the first argument. For a version that ignores the results, see bifor_.

Examples

Basic usage:

>>> bifor (Left []) listToMaybe (find even)Nothing

>>> bifor (Left [1, 2, 3]) listToMaybe (find even)Just (Left 1)

>>> bifor (Right [4, 5]) listToMaybe (find even)Just (Right 4)

>>> bifor ([1, 2, 3], [4, 5]) listToMaybe (find even)Just (1,4)

>>> bifor ([], [4, 5]) listToMaybe (find even)Nothing

A default definition of bimap in terms of the Bitraversable operations.

bimapDefault f g ≡
     runIdentity . bitraverse (Identity . f) (Identity . g)

Sequences all the actions in a structure, building a new structure with the same shape using the results of the actions. For a version that ignores the results, see bisequence_.

bisequence ≡ bitraverse id id

Examples

Basic usage:

>>> bisequence (Just 4, Nothing)Nothing

>>> bisequence (Just 4, Just 5)Just (4,5)

>>> bisequence ([1, 2, 3], [4, 5])[(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)]