Data.Bifoldable

class Bifoldable (p :: Type -> Type -> Type) where Источник

Bifoldable обозначает свёртываемые структуры с двумя разновидностями элементов (в отличие от Foldable, у которого есть только одна разновидность элементов). Распространённые примеры — Either и (,):

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)

В некоторых примерах ниже также используется следующий BiList, чтобы показать поведение пустых структур Bifoldable, если это уместно (Either и (,) всегда содержат соответственно ровно 1 и 2 элемента):

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

Минимальное определение Bifoldable должно включать либо bifoldMap, либо bifoldr. При определении чего-либо сверх этого минимального набора следует убедиться, что выполняются следующие тождества:

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

Если тип также является экземпляром Foldable, он должен удовлетворять следующим условиям (с точностью до ленивости):

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

Если тип также является экземпляром Bifunctor, он должен удовлетворять следующим условиям:

bifoldMap f g ≡ bifold . bimap f g

из чего следует, что

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

Начиная с: base-4.10.0.0

bifold ≡ bifoldMap id id

>>> bifold (Right [1, 2, 3])
[1,2,3]

>>> bifold (Left [5, 6])
[5,6]

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

>>> bifold (Product 6, Product 7)
Product {getProduct = 42}

>>> bifold (Sum 6, Sum 7)
Sum {getSum = 13}

bifoldMap f g ≡ bifoldr (mappend . f) (mappend . g) mempty

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

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

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

bifoldr f g z ≡ foldr (either f g) z . toEitherList

> bifoldr (+) (*) 3 (5, 7)
26 -- 5 + (7 * 3)

> bifoldr (+) (*) 3 (7, 5)
22 -- 7 + (5 * 3)

> bifoldr (+) (*) 3 (Right 5)
15 -- 5 * 3

> bifoldr (+) (*) 3 (Left 5)
8 -- 5 + 3

bifoldl f g z
     ≡ foldl (acc -> either (f acc) (g acc)) z . toEitherList

> bifoldl (+) (*) 3 (5, 7)
56 -- (5 + 3) * 7

> bifoldl (+) (*) 3 (7, 5)
50 -- (7 + 3) * 5

> bifoldl (+) (*) 3 (Right 5)
15 -- 5 * 3

> bifoldl (+) (*) 3 (Left 5)
8 -- 5 + 3

>>> bifoldr (flip const) (:) [] (undefined :: (Int, Word)) `seq` ()
()
>>> foldr (:) [] (errorWithoutStackTrace "error!" :: (Int, Word)) `seq` ()
*** Exception: error!

bifoldr' :: Bifoldable t => (a -> c -> c) -> (b -> c -> c) -> c -> t a b -> c Источник

Как bifoldr, но результат функций редукции на каждом шаге вычисляется строго.

Начиная с: base-4.10.0.0

bifoldr1 :: Bifoldable t => (a -> a -> a) -> t a a -> a Источник

Вариант bifoldr без базового случая, поэтому его можно применять только к непустым структурам.

Примеры

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

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

Начиная с: base-4.10.0.0

bifoldrM :: (Bifoldable t, Monad m) => (a -> c -> m c) -> (b -> c -> m c) -> c -> t a b -> m c Источник

Монадическая би-свёртка структуры с правоассоциативным порядком.

Начиная с: base-4.10.0.0

bifoldl' :: Bifoldable t => (a -> b -> a) -> (a -> c -> a) -> a -> t b c -> a Источник

Как bifoldl, но результат функций редукции на каждом шаге вычисляется строго.

Это гарантирует, что каждый шаг би-свёртки принудительно вычисляется до слабой головной нормальной формы перед применением, предотвращая накопление отложенных вычислений. Такой подход часто нужен для строгого сведения конечной структуры к единому монолитному результату (например, bilength).

Начиная с: base-4.10.0.0

bifoldl1 :: Bifoldable t => (a -> a -> a) -> t a a -> a Источник

Вариант bifoldl без базового случая, поэтому его можно применять только к непустым структурам.

Примеры

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

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

Начиная с: base-4.10.0.0

bifoldlM :: (Bifoldable t, Monad m) => (a -> b -> m a) -> (a -> c -> m a) -> a -> t b c -> m a Источник

Монадическая би-свёртка структуры с левосторонне-ассоциативным порядком.

Примеры

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

Начиная с: base-4.10.0.0

bitraverse_ :: (Bifoldable t, Applicative f) => (a -> f c) -> (b -> f d) -> t a b -> f () Источник

Отображает каждый элемент структуры с помощью одного из двух действий, выполняет эти действия слева направо и игнорирует результаты. Версию, которая не игнорирует результаты, см. в bitraverse.

Примеры

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

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

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

Начиная с: base-4.10.0.0

bifor_ :: (Bifoldable t, Applicative f) => t a b -> (a -> f c) -> (b -> f d) -> f () Источник

Аналог bitraverse_, но структура является первым аргументом. Версию, которая не игнорирует результаты, см. в bifor.

Примеры

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

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

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

Начиная с: base-4.10.0.0

bimapM_ :: (Bifoldable t, Applicative f) => (a -> f c) -> (b -> f d) -> t a b -> f () Источник

Псевдоним для bitraverse_.

Начиная с: base-4.10.0.0

biforM_ :: (Bifoldable t, Applicative f) => t a b -> (a -> f c) -> (b -> f d) -> f () Источник

Псевдоним для bifor_.

Начиная с: base-4.10.0.0

bimsum :: (Bifoldable t, Alternative f) => t (f a) (f a) -> f a Источник

Псевдоним для biasum.

Начиная с: base-4.10.0.0

bisequenceA_ :: (Bifoldable t, Applicative f) => t (f a) (f b) -> f () Источник

Псевдоним для bisequence_.

Начиная с: base-4.10.0.0

bisequence_ :: (Bifoldable t, Applicative f) => t (f a) (f b) -> f () Источник

Выполняет каждое действие в структуре слева направо и игнорирует результаты. Версию, которая не игнорирует результаты, см. в bisequence.

Примеры

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

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

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

Начиная с: base-4.10.0.0

biasum :: (Bifoldable t, Alternative f) => t (f a) (f a) -> f a Источник

Сумма набора действий, обобщающая biconcat.

Примеры

>>> biasum (Nothing, Nothing)
Nothing

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

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

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

Начиная с: base-4.10.0.0

biList :: Bifoldable t => t a a -> [a] Источник

Собирает элементы структуры в список слева направо.

Примеры

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

>>> biList (Left 18)
[18]

Начиная с: base-4.10.0.0

binull :: Bifoldable t => t a b -> Bool Источник

Проверяет, пуста ли структура.

Примеры

>>> binull (18, 42)
False

>>> binull (Right 42)
False

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

Начиная с: base-4.10.0.0

bilength :: Bifoldable t => t a b -> Int Источник

Возвращает размер/длину конечной структуры в виде Int.

Примеры

>>> bilength (True, 42)
2

>>> bilength (Right 42)
1

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

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

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

Начиная с: base-4.10.0.0

bielem :: (Bifoldable t, Eq a) => a -> t a a -> Bool Источник

Встречается ли элемент в структуре?

Примеры

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

Начиная с: base-4.10.0.0

bimaximum :: (Bifoldable t, Ord a) => t a a -> a Источник

Наибольший элемент непустой структуры. Эта функция эквивалентна bifoldr1 max, а её поведение для структур с несколькими наибольшими элементами зависит от соответствующей реализации max. В реализации max по умолчанию (max x y = if x <= y then y else x) порядок элементов структуры используется для разрешения равенства: если наибольших элементов несколько, выбирается самый правый (это эквивалентно bimaximumBy compare).

Примеры

>>> bimaximum (42, 17)
42

>>> bimaximum (Right 42)
42

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

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

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

Начиная с: base-4.10.0.0

biminimum :: (Bifoldable t, Ord a) => t a a -> a Источник

Наименьший элемент непустой структуры. Эта функция эквивалентна bifoldr1 min, а её поведение для структур с несколькими наименьшими элементами зависит от соответствующей реализации min. В реализации min по умолчанию (min x y = if x <= y then x else y) порядок элементов структуры используется для разрешения равенства: если наименьших элементов несколько, выбирается самый левый (это эквивалентно biminimumBy compare).

Примеры

>>> biminimum (42, 17)
17

>>> biminimum (Right 42)
42

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

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

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

Начиная с: base-4.10.0.0

bisum :: (Bifoldable t, Num a) => t a a -> a Источник

Функция bisum вычисляет сумму чисел структуры.

Примеры

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

Начиная с: base-4.10.0.0

biproduct :: (Bifoldable t, Num a) => t a a -> a Источник

Функция biproduct вычисляет произведение чисел структуры.

Примеры

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

Начиная с: base-4.10.0.0

biconcat :: Bifoldable t => t [a] [a] -> [a] Источник

Сворачивает структуру списков в конкатенацию этих списков.

Примеры

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

Начиная с: base-4.10.0.0

biconcatMap :: Bifoldable t => (a -> [c]) -> (b -> [c]) -> t a b -> [c] Источник

Получив способ отображать элементы структуры в списки, вычисляет конкатенацию всех таких списков в заданном порядке.

Примеры

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

Начиная с: base-4.10.0.0

biand :: Bifoldable t => t Bool Bool -> Bool Источник

biand возвращает конъюнкцию значений Bool в контейнере. Чтобы результат был True, контейнер должен быть конечным; однако False получается, если значение False находится на конечном расстоянии от левого края.

Примеры

>>> biand (True, False)
False

>>> biand (True, True)
True

>>> biand (Left True)
True

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

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

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

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

Начиная с: base-4.10.0.0

bior :: Bifoldable t => t Bool Bool -> Bool Источник

bior возвращает дизъюнкцию значений Bool в контейнере. Чтобы результат был False, контейнер должен быть конечным; однако True получается, если значение True находится на конечном расстоянии от левого края.

Примеры

>>> bior (True, False)
True

>>> bior (False, False)
False

>>> bior (Left True)
True

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

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

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

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

Начиная с: base-4.10.0.0

biany :: Bifoldable t => (a -> Bool) -> (b -> Bool) -> t a b -> Bool Источник

Определяет, удовлетворяет ли какой-либо элемент структуры соответствующему ему предикату. Для пустых структур результатом будет False.

Примеры

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

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

Начиная с: base-4.10.0.0

biall :: Bifoldable t => (a -> Bool) -> (b -> Bool) -> t a b -> Bool Источник

Определяет, удовлетворяют ли все элементы структуры соответствующим им предикатам. Для пустых структур результатом будет True.

Примеры

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

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

Начиная с: base-4.10.0.0

bimaximumBy :: Bifoldable t => (a -> a -> Ordering) -> t a a -> a Источник

Наибольший элемент непустой структуры относительно заданной функции сравнения. Для разрешения равенства используется порядок элементов структуры: если наибольших элементов несколько, выбирается самый правый.

Примеры

>>> bimaximumBy compare (42, 17)
42

>>> bimaximumBy compare (Left 17)
17

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

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

Начиная с: base-4.10.0.0

biminimumBy :: Bifoldable t => (a -> a -> Ordering) -> t a a -> a Источник

Наименьший элемент непустой структуры относительно заданной функции сравнения. Для разрешения равенства используется порядок элементов структуры: если наименьших элементов несколько, выбирается самый левый.

Примеры

>>> biminimumBy compare (42, 17)
17

>>> biminimumBy compare (Left 17)
17

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

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

Начиная с: base-4.10.0.0

binotElem :: (Bifoldable t, Eq a) => a -> t a a -> Bool Источник

binotElem — это отрицание bielem.

Примеры

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

Начиная с: base-4.10.0.0

bifind :: Bifoldable t => (a -> Bool) -> t a a -> Maybe a Источник

Функция bifind принимает предикат и структуру и возвращает самый левый элемент структуры, удовлетворяющий предикату, или Nothing, если такого элемента нет.

Примеры

>>> bifind even (27, 53)
Nothing

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

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

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

Начиная с: base-4.10.0.0