Data.Bifoldable

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

Reduces a structure of lists to the concatenation of those lists.

Examples

Basic usage:

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

>>> biconcat (Left [1, 2, 3])[1,2,3]

>>> biconcat (BiList [[1, 2, 3, 4, 5], [6, 7, 8]] [[9]])[1,2,3,4,5,6,7,8,9]

Given a means of mapping the elements of a structure to lists, computes the concatenation of all such lists in order.

Examples

Basic usage:

>>> biconcatMap (take 3) (fmap digitToInt) ([1..], "89")[1,2,3,8,9]

>>> biconcatMap (take 3) (fmap digitToInt) (Left [1..])[1,2,3]

>>> biconcatMap (take 3) (fmap digitToInt) (Right "89")[8,9]

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

A variant of bifoldl that has no base case, and thus may only be applied to non-empty structures.

Examples

Basic usage:

>>> bifoldl1 (+) (5, 7)12

>>> bifoldl1 (+) (Right 7)7

>>> bifoldl1 (+) (Left 5)5

> bifoldl1 (+) (BiList [1, 2] [3, 4])
10 -- ((1 + 2) + 3) + 4

>>> bifoldl1 (+) (BiList [1, 2] [])3

On empty structures, this function throws an exception:

>>> bifoldl1 (+) (BiList [] [])*** Exception: bifoldl1: empty structure...

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.

A variant of bifoldr that has no base case, and thus may only be applied to non-empty structures.

Examples

Basic usage:

>>> bifoldr1 (+) (5, 7)12

>>> bifoldr1 (+) (Right 7)7

>>> bifoldr1 (+) (Left 5)5

> bifoldr1 (+) (BiList [1, 2] [3, 4])
10 -- 1 + (2 + (3 + 4))

>>> bifoldr1 (+) (BiList [1, 2] [])3

On empty structures, this function throws an exception:

>>> bifoldr1 (+) (BiList [] [])*** Exception: bifoldr1: empty structure...

Right associative monadic bifold over a structure.

Alias for bifor_.

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 *

Alias for bitraverse_.

The largest element of a non-empty structure.

Examples

Basic usage:

>>> bimaximum (42, 17)42

>>> bimaximum (Right 42)42

>>> bimaximum (BiList [13, 29, 4] [18, 1, 7])29

>>> bimaximum (BiList [13, 29, 4] [])29

On empty structures, this function throws an exception:

>>> bimaximum (BiList [] [])*** Exception: bimaximum: empty structure...

The largest element of a non-empty structure with respect to the given comparison function.

Examples

Basic usage:

>>> bimaximumBy compare (42, 17)42

>>> bimaximumBy compare (Left 17)17

>>> bimaximumBy compare (BiList [42, 17, 23] [-5, 18])42

On empty structures, this function throws an exception:

>>> bimaximumBy compare (BiList [] [])*** Exception: bifoldr1: empty structure...

The least element of a non-empty structure.

Examples

Basic usage:

>>> biminimum (42, 17)17

>>> biminimum (Right 42)42

>>> biminimum (BiList [13, 29, 4] [18, 1, 7])1

>>> biminimum (BiList [13, 29, 4] [])4

On empty structures, this function throws an exception:

>>> biminimum (BiList [] [])*** Exception: biminimum: empty structure...

The least element of a non-empty structure with respect to the given comparison function.

Examples

Basic usage:

>>> biminimumBy compare (42, 17)17

>>> biminimumBy compare (Left 17)17

>>> biminimumBy compare (BiList [42, 17, 23] [-5, 18])-5

On empty structures, this function throws an exception:

>>> biminimumBy compare (BiList [] [])*** Exception: bifoldr1: empty structure...

Alias for biasum.

binotElem is the negation of bielem.

Examples

Basic usage:

>>> binotElem 42 (17, 42)False

>>> binotElem 42 (17, 43)True

>>> binotElem 42 (Left 42)False

>>> binotElem 42 (Right 13)True

>>> binotElem 42 (BiList [1..5] [1..100])False

>>> binotElem 42 (BiList [1..5] [1..41])True

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 *

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

Examples

Basic usage:

>>> biproduct (42, 17)714

>>> biproduct (Right 42)42

>>> biproduct (BiList [13, 29, 4] [18, 1, 7])190008

>>> biproduct (BiList [13, 29, 4] [])1508

>>> biproduct (BiList [] [])1

Alias for bisequence_.

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"

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

Examples

Basic usage:

>>> bisum (42, 17)59

>>> bisum (Right 42)42

>>> bisum (BiList [13, 29, 4] [18, 1, 7])72

>>> bisum (BiList [13, 29, 4] [])46

>>> bisum (BiList [] [])0

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"