{-# LANGUAGE Safe #-}
{-# LANGUAGE ScopedTypeVariables #-}

-----------------------------------------------------------------------------
-- |
-- Module      :  Data.Bifoldable
-- Copyright   :  (C) 2011-2016 Edward Kmett
-- License     :  BSD-style (see the file LICENSE)
--
-- Maintainer  :  libraries@haskell.org
-- Stability   :  provisional
-- Portability :  portable
--
-- @since 4.10.0.0
----------------------------------------------------------------------------
module Data.Bifoldable
  ( Bifoldable(..)
  , bifoldr'
  , bifoldr1
  , bifoldrM
  , bifoldl'
  , bifoldl1
  , bifoldlM
  , bitraverse_
  , bifor_
  , bimapM_
  , biforM_
  , bimsum
  , bisequenceA_
  , bisequence_
  , biasum
  , biList
  , binull
  , bilength
  , bielem
  , bimaximum
  , biminimum
  , bisum
  , biproduct
  , biconcat
  , biconcatMap
  , biand
  , bior
  , biany
  , biall
  , bimaximumBy
  , biminimumBy
  , binotElem
  , bifind
  ) where

import Control.Applicative
import GHC.Internal.Data.Functor.Utils (Max(..), Min(..), (#.))
import GHC.Internal.Data.Maybe (fromMaybe)
import GHC.Internal.Data.Monoid
import GHC.Generics (K1(..))
import Prelude

-- $setup
-- >>> import Prelude
-- >>> import Data.Char
-- >>> import GHC.Internal.Data.Monoid (Product (..), Sum (..))
-- >>> 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' 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 'Data.Bifunctor.Bifunctor' instance, it should satisfy:
--
-- @
-- 'bifoldMap' f g ≡ 'bifold' . 'Data.Bifunctor.bimap' f g
-- @
--
-- which implies that
--
-- @
-- 'bifoldMap' f g . 'Data.Bifunctor.bimap' h i ≡ 'bifoldMap' (f . h) (g . i)
-- @
--
-- @since 4.10.0.0
class Bifoldable p where
  {-# MINIMAL bifoldr | bifoldMap #-}

  -- | Combines the elements of a structure using a monoid.
  --
  -- @'bifold' ≡ 'bifoldMap' 'id' 'id'@
  --
  -- ==== __Examples__
  --
  -- Basic usage:
  --
  -- >>> 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}
  --
  -- @since 4.10.0.0
  bifold :: Monoid m => p m m -> m
  bifold = (m -> m) -> (m -> m) -> p m m -> m
forall m a b. Monoid m => (a -> m) -> (b -> m) -> p a b -> m
forall (p :: * -> * -> *) m a b.
(Bifoldable p, Monoid m) =>
(a -> m) -> (b -> m) -> p a b -> m
bifoldMap m -> m
forall a. a -> a
id m -> m
forall a. a -> a
id

  -- | Combines the elements of a structure, given ways of mapping them to a
  -- common monoid.
  --
  -- @'bifoldMap' f g ≡ 'bifoldr' ('mappend' . f) ('mappend' . g) 'mempty'@
  --
  -- ==== __Examples__
  --
  -- Basic usage:
  --
  -- >>> 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]
  --
  -- @since 4.10.0.0
  bifoldMap :: Monoid m => (a -> m) -> (b -> m) -> p a b -> m
  bifoldMap a -> m
f b -> m
g = (a -> m -> m) -> (b -> m -> m) -> m -> p a b -> m
forall a c b. (a -> c -> c) -> (b -> c -> c) -> c -> p a b -> c
forall (p :: * -> * -> *) a c b.
Bifoldable p =>
(a -> c -> c) -> (b -> c -> c) -> c -> p a b -> c
bifoldr (m -> m -> m
forall a. Monoid a => a -> a -> a
mappend (m -> m -> m) -> (a -> m) -> a -> m -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> m
f) (m -> m -> m
forall a. Monoid a => a -> a -> a
mappend (m -> m -> m) -> (b -> m) -> b -> m -> m
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> m
g) m
forall a. Monoid a => a
mempty

  -- | Combines the elements of a structure in a right associative manner.
  -- Given a hypothetical function @toEitherList :: p a b -> [Either a b]@
  -- yielding a list of all elements of a structure in order, the following
  -- would hold:
  --
  -- @'bifoldr' f g z ≡ 'foldr' ('either' f g) z . toEitherList@
  --
  -- ==== __Examples__
  --
  -- Basic usage:
  --
  -- @
  -- > 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
  -- @
  --
  -- @since 4.10.0.0
  bifoldr :: (a -> c -> c) -> (b -> c -> c) -> c -> p a b -> c
  bifoldr a -> c -> c
f b -> c -> c
g c
z p a b
t = Endo c -> c -> c
forall a. Endo a -> a -> a
appEndo ((a -> Endo c) -> (b -> Endo c) -> p a b -> Endo c
forall m a b. Monoid m => (a -> m) -> (b -> m) -> p a b -> m
forall (p :: * -> * -> *) m a b.
(Bifoldable p, Monoid m) =>
(a -> m) -> (b -> m) -> p a b -> m
bifoldMap ((c -> c) -> Endo c
forall a. (a -> a) -> Endo a
Endo ((c -> c) -> Endo c) -> (a -> c -> c) -> a -> Endo c
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. a -> c -> c
f) ((c -> c) -> Endo c
forall a. (a -> a) -> Endo a
Endo ((c -> c) -> Endo c) -> (b -> c -> c) -> b -> Endo c
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. b -> c -> c
g) p a b
t) c
z

  -- | Combines the elements of a structure in a left associative manner. Given
  -- a hypothetical function @toEitherList :: p a b -> [Either a b]@ yielding a
  -- list of all elements of a structure in order, the following would hold:
  --
  -- @'bifoldl' f g z
  --     ≡ 'foldl' (\acc -> 'either' (f acc) (g acc)) z . toEitherList@
  --
  -- Note that if you want an efficient left-fold, you probably want to use
  -- 'bifoldl'' instead of 'bifoldl'. The reason is that the latter does not
  -- force the "inner" results, resulting in a thunk chain which then must be
  -- evaluated from the outside-in.
  --
  -- ==== __Examples__
  --
  -- Basic usage:
  --
  -- @
  -- > 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
  -- @
  --
  -- @since 4.10.0.0
  bifoldl :: (c -> a -> c) -> (c -> b -> c) -> c -> p a b -> c
  bifoldl c -> a -> c
f c -> b -> c
g c
z p a b
t = Endo c -> c -> c
forall a. Endo a -> a -> a
appEndo (Dual (Endo c) -> Endo c
forall a. Dual a -> a
getDual ((a -> Dual (Endo c))
-> (b -> Dual (Endo c)) -> p a b -> Dual (Endo c)
forall m a b. Monoid m => (a -> m) -> (b -> m) -> p a b -> m
forall (p :: * -> * -> *) m a b.
(Bifoldable p, Monoid m) =>
(a -> m) -> (b -> m) -> p a b -> m
bifoldMap (Endo c -> Dual (Endo c)
forall a. a -> Dual a
Dual (Endo c -> Dual (Endo c)) -> (a -> Endo c) -> a -> Dual (Endo c)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (c -> c) -> Endo c
forall a. (a -> a) -> Endo a
Endo ((c -> c) -> Endo c) -> (a -> c -> c) -> a -> Endo c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (c -> a -> c) -> a -> c -> c
forall a b c. (a -> b -> c) -> b -> a -> c
flip c -> a -> c
f)
                                                (Endo c -> Dual (Endo c)
forall a. a -> Dual a
Dual (Endo c -> Dual (Endo c)) -> (b -> Endo c) -> b -> Dual (Endo c)
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (c -> c) -> Endo c
forall a. (a -> a) -> Endo a
Endo ((c -> c) -> Endo c) -> (b -> c -> c) -> b -> Endo c
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (c -> b -> c) -> b -> c -> c
forall a b c. (a -> b -> c) -> b -> a -> c
flip c -> b -> c
g) p a b
t)) c
z

-- | Class laws for tuples hold only up to laziness. The
-- Bifoldable methods are lazier than their Foldable counterparts.
-- For example the law @'bifoldr' ('flip' 'const') ≡ 'foldr'@ does
-- not hold for tuples if laziness is exploited:
--
-- >>> bifoldr (flip const) (:) [] (undefined :: (Int, Word)) `seq` ()
-- ()
-- >>> foldr (:) [] (errorWithoutStackTrace "error!" :: (Int, Word)) `seq` ()
-- *** Exception: error!
--
-- @since 4.10.0.0
instance Bifoldable (,) where
  bifoldMap :: forall m a b. Monoid m => (a -> m) -> (b -> m) -> (a, b) -> m
bifoldMap a -> m
f b -> m
g ~(a
a, b
b) = a -> m
f a
a m -> m -> m
forall a. Monoid a => a -> a -> a
`mappend` b -> m
g b
b

-- | @since 4.10.0.0
instance Bifoldable Const where
  bifoldMap :: forall m a b. Monoid m => (a -> m) -> (b -> m) -> Const a b -> m
bifoldMap a -> m
f b -> m
_ (Const a
a) = a -> m
f a
a

-- | @since 4.10.0.0
instance Bifoldable (K1 i) where
  bifoldMap :: forall m a b. Monoid m => (a -> m) -> (b -> m) -> K1 i a b -> m
bifoldMap a -> m
f b -> m
_ (K1 a
c) = a -> m
f a
c

-- | @since 4.10.0.0
instance Bifoldable ((,,) x) where
  bifoldMap :: forall m a b. Monoid m => (a -> m) -> (b -> m) -> (x, a, b) -> m
bifoldMap a -> m
f b -> m
g ~(x
_,a
a,b
b) = a -> m
f a
a m -> m -> m
forall a. Monoid a => a -> a -> a
`mappend` b -> m
g b
b

-- | @since 4.10.0.0
instance Bifoldable ((,,,) x y) where
  bifoldMap :: forall m a b. Monoid m => (a -> m) -> (b -> m) -> (x, y, a, b) -> m
bifoldMap a -> m
f b -> m
g ~(x
_,y
_,a
a,b
b) = a -> m
f a
a m -> m -> m
forall a. Monoid a => a -> a -> a
`mappend` b -> m
g b
b

-- | @since 4.10.0.0
instance Bifoldable ((,,,,) x y z) where
  bifoldMap :: forall m a b.
Monoid m =>
(a -> m) -> (b -> m) -> (x, y, z, a, b) -> m
bifoldMap a -> m
f b -> m
g ~(x
_,y
_,z
_,a
a,b
b) = a -> m
f a
a m -> m -> m
forall a. Monoid a => a -> a -> a
`mappend` b -> m
g b
b

-- | @since 4.10.0.0
instance Bifoldable ((,,,,,) x y z w) where
  bifoldMap :: forall m a b.
Monoid m =>
(a -> m) -> (b -> m) -> (x, y, z, w, a, b) -> m
bifoldMap a -> m
f b -> m
g ~(x
_,y
_,z
_,w
_,a
a,b
b) = a -> m
f a
a m -> m -> m
forall a. Monoid a => a -> a -> a
`mappend` b -> m
g b
b

-- | @since 4.10.0.0
instance Bifoldable ((,,,,,,) x y z w v) where
  bifoldMap :: forall m a b.
Monoid m =>
(a -> m) -> (b -> m) -> (x, y, z, w, v, a, b) -> m
bifoldMap a -> m
f b -> m
g ~(x
_,y
_,z
_,w
_,v
_,a
a,b
b) = a -> m
f a
a m -> m -> m
forall a. Monoid a => a -> a -> a
`mappend` b -> m
g b
b

-- | @since 4.10.0.0
instance Bifoldable Either where
  bifoldMap :: forall m a b. Monoid m => (a -> m) -> (b -> m) -> Either a b -> m
bifoldMap a -> m
f b -> m
_ (Left a
a) = a -> m
f a
a
  bifoldMap a -> m
_ b -> m
g (Right b
b) = b -> m
g b
b

-- | As 'bifoldr', but strict in the result of the reduction functions at each
-- step.
--
-- @since 4.10.0.0
bifoldr' :: Bifoldable t => (a -> c -> c) -> (b -> c -> c) -> c -> t a b -> c
bifoldr' :: forall (t :: * -> * -> *) a c b.
Bifoldable t =>
(a -> c -> c) -> (b -> c -> c) -> c -> t a b -> c
bifoldr' a -> c -> c
f b -> c -> c
g c
z0 t a b
xs = ((c -> c) -> a -> c -> c)
-> ((c -> c) -> b -> c -> c) -> (c -> c) -> t a b -> c -> c
forall c a b. (c -> a -> c) -> (c -> b -> c) -> c -> t a b -> c
forall (p :: * -> * -> *) c a b.
Bifoldable p =>
(c -> a -> c) -> (c -> b -> c) -> c -> p a b -> c
bifoldl (c -> c) -> a -> c -> c
forall {b}. (c -> b) -> a -> c -> b
f' (c -> c) -> b -> c -> c
forall {b}. (c -> b) -> b -> c -> b
g' c -> c
forall a. a -> a
id t a b
xs c
z0 where
  f' :: (c -> b) -> a -> c -> b
f' c -> b
k a
x c
z = c -> b
k (c -> b) -> c -> b
forall a b. (a -> b) -> a -> b
$! a -> c -> c
f a
x c
z
  g' :: (c -> b) -> b -> c -> b
g' c -> b
k b
x c
z = c -> b
k (c -> b) -> c -> b
forall a b. (a -> b) -> a -> b
$! b -> c -> c
g b
x c
z

-- | 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
-- ...
--
-- @since 4.10.0.0
bifoldr1 :: Bifoldable t => (a -> a -> a) -> t a a -> a
bifoldr1 :: forall (t :: * -> * -> *) a.
Bifoldable t =>
(a -> a -> a) -> t a a -> a
bifoldr1 a -> a -> a
f t a a
xs = a -> Maybe a -> a
forall a. a -> Maybe a -> a
fromMaybe ([Char] -> a
forall a. HasCallStack => [Char] -> a
error [Char]
"bifoldr1: empty structure")
                  ((a -> Maybe a -> Maybe a)
-> (a -> Maybe a -> Maybe a) -> Maybe a -> t a a -> Maybe a
forall a c b. (a -> c -> c) -> (b -> c -> c) -> c -> t a b -> c
forall (p :: * -> * -> *) a c b.
Bifoldable p =>
(a -> c -> c) -> (b -> c -> c) -> c -> p a b -> c
bifoldr a -> Maybe a -> Maybe a
mbf a -> Maybe a -> Maybe a
mbf Maybe a
forall a. Maybe a
Nothing t a a
xs)
  where
    mbf :: a -> Maybe a -> Maybe a
mbf a
x Maybe a
m = a -> Maybe a
forall a. a -> Maybe a
Just (case Maybe a
m of
                      Maybe a
Nothing -> a
x
                      Just a
y  -> a -> a -> a
f a
x a
y)

-- | Right associative monadic bifold over a structure.
--
-- @since 4.10.0.0
bifoldrM :: (Bifoldable t, Monad m)
         => (a -> c -> m c) -> (b -> c -> m c) -> c -> t a b -> m c
bifoldrM :: forall (t :: * -> * -> *) (m :: * -> *) a c b.
(Bifoldable t, Monad m) =>
(a -> c -> m c) -> (b -> c -> m c) -> c -> t a b -> m c
bifoldrM a -> c -> m c
f b -> c -> m c
g c
z0 t a b
xs = ((c -> m c) -> a -> c -> m c)
-> ((c -> m c) -> b -> c -> m c) -> (c -> m c) -> t a b -> c -> m c
forall c a b. (c -> a -> c) -> (c -> b -> c) -> c -> t a b -> c
forall (p :: * -> * -> *) c a b.
Bifoldable p =>
(c -> a -> c) -> (c -> b -> c) -> c -> p a b -> c
bifoldl (c -> m c) -> a -> c -> m c
forall {b}. (c -> m b) -> a -> c -> m b
f' (c -> m c) -> b -> c -> m c
forall {b}. (c -> m b) -> b -> c -> m b
g' c -> m c
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return t a b
xs c
z0 where
  f' :: (c -> m b) -> a -> c -> m b
f' c -> m b
k a
x c
z = a -> c -> m c
f a
x c
z m c -> (c -> m b) -> m b
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= c -> m b
k
  g' :: (c -> m b) -> b -> c -> m b
g' c -> m b
k b
x c
z = b -> c -> m c
g b
x c
z m c -> (c -> m b) -> m b
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= c -> m b
k

-- | 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').
--
-- @since 4.10.0.0
bifoldl':: Bifoldable t => (a -> b -> a) -> (a -> c -> a) -> a -> t b c -> a
bifoldl' :: forall (t :: * -> * -> *) a b c.
Bifoldable t =>
(a -> b -> a) -> (a -> c -> a) -> a -> t b c -> a
bifoldl' a -> b -> a
f a -> c -> a
g a
z0 t b c
xs = (b -> (a -> a) -> a -> a)
-> (c -> (a -> a) -> a -> a) -> (a -> a) -> t b c -> a -> a
forall a c b. (a -> c -> c) -> (b -> c -> c) -> c -> t a b -> c
forall (p :: * -> * -> *) a c b.
Bifoldable p =>
(a -> c -> c) -> (b -> c -> c) -> c -> p a b -> c
bifoldr b -> (a -> a) -> a -> a
forall {b}. b -> (a -> b) -> a -> b
f' c -> (a -> a) -> a -> a
forall {b}. c -> (a -> b) -> a -> b
g' a -> a
forall a. a -> a
id t b c
xs a
z0 where
  f' :: b -> (a -> b) -> a -> b
f' b
x a -> b
k a
z = a -> b
k (a -> b) -> a -> b
forall a b. (a -> b) -> a -> b
$! a -> b -> a
f a
z b
x
  g' :: c -> (a -> b) -> a -> b
g' c
x a -> b
k a
z = a -> b
k (a -> b) -> a -> b
forall a b. (a -> b) -> a -> b
$! a -> c -> a
g a
z c
x

-- | 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
-- ...
--
-- @since 4.10.0.0
bifoldl1 :: Bifoldable t => (a -> a -> a) -> t a a -> a
bifoldl1 :: forall (t :: * -> * -> *) a.
Bifoldable t =>
(a -> a -> a) -> t a a -> a
bifoldl1 a -> a -> a
f t a a
xs = a -> Maybe a -> a
forall a. a -> Maybe a -> a
fromMaybe ([Char] -> a
forall a. HasCallStack => [Char] -> a
error [Char]
"bifoldl1: empty structure")
                  ((Maybe a -> a -> Maybe a)
-> (Maybe a -> a -> Maybe a) -> Maybe a -> t a a -> Maybe a
forall c a b. (c -> a -> c) -> (c -> b -> c) -> c -> t a b -> c
forall (p :: * -> * -> *) c a b.
Bifoldable p =>
(c -> a -> c) -> (c -> b -> c) -> c -> p a b -> c
bifoldl Maybe a -> a -> Maybe a
mbf Maybe a -> a -> Maybe a
mbf Maybe a
forall a. Maybe a
Nothing t a a
xs)
  where
    mbf :: Maybe a -> a -> Maybe a
mbf Maybe a
m a
y = a -> Maybe a
forall a. a -> Maybe a
Just (case Maybe a
m of
                      Maybe a
Nothing -> a
y
                      Just a
x  -> a -> a -> a
f a
x a
y)

-- | 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
--
-- @since 4.10.0.0
bifoldlM :: (Bifoldable t, Monad m)
         => (a -> b -> m a) -> (a -> c -> m a) -> a -> t b c -> m a
bifoldlM :: forall (t :: * -> * -> *) (m :: * -> *) a b c.
(Bifoldable t, Monad m) =>
(a -> b -> m a) -> (a -> c -> m a) -> a -> t b c -> m a
bifoldlM a -> b -> m a
f a -> c -> m a
g a
z0 t b c
xs = (b -> (a -> m a) -> a -> m a)
-> (c -> (a -> m a) -> a -> m a) -> (a -> m a) -> t b c -> a -> m a
forall a c b. (a -> c -> c) -> (b -> c -> c) -> c -> t a b -> c
forall (p :: * -> * -> *) a c b.
Bifoldable p =>
(a -> c -> c) -> (b -> c -> c) -> c -> p a b -> c
bifoldr b -> (a -> m a) -> a -> m a
forall {b}. b -> (a -> m b) -> a -> m b
f' c -> (a -> m a) -> a -> m a
forall {b}. c -> (a -> m b) -> a -> m b
g' a -> m a
forall a. a -> m a
forall (m :: * -> *) a. Monad m => a -> m a
return t b c
xs a
z0 where
  f' :: b -> (a -> m b) -> a -> m b
f' b
x a -> m b
k a
z = a -> b -> m a
f a
z b
x m a -> (a -> m b) -> m b
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= a -> m b
k
  g' :: c -> (a -> m b) -> a -> m b
g' c
x a -> m b
k a
z = a -> c -> m a
g a
z c
x m a -> (a -> m b) -> m b
forall a b. m a -> (a -> m b) -> m b
forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= a -> m b
k

-- | 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 'Data.Bitraversable.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"
--
-- @since 4.10.0.0
bitraverse_ :: (Bifoldable t, Applicative f)
            => (a -> f c) -> (b -> f d) -> t a b -> f ()
bitraverse_ :: forall (t :: * -> * -> *) (f :: * -> *) a c b d.
(Bifoldable t, Applicative f) =>
(a -> f c) -> (b -> f d) -> t a b -> f ()
bitraverse_ a -> f c
f b -> f d
g = (a -> f () -> f ()) -> (b -> f () -> f ()) -> f () -> t a b -> f ()
forall a c b. (a -> c -> c) -> (b -> c -> c) -> c -> t a b -> c
forall (p :: * -> * -> *) a c b.
Bifoldable p =>
(a -> c -> c) -> (b -> c -> c) -> c -> p a b -> c
bifoldr (f c -> f () -> f ()
forall a b. f a -> f b -> f b
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
(*>) (f c -> f () -> f ()) -> (a -> f c) -> a -> f () -> f ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> f c
f) (f d -> f () -> f ()
forall a b. f a -> f b -> f b
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
(*>) (f d -> f () -> f ()) -> (b -> f d) -> b -> f () -> f ()
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> f d
g) (() -> f ()
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ())

-- | As 'bitraverse_', but with the structure as the primary argument. For a
-- version that doesn't ignore the results, see 'Data.Bitraversable.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"
--
-- @since 4.10.0.0
bifor_ :: (Bifoldable t, Applicative f)
       => t a b -> (a -> f c) -> (b -> f d) -> f ()
bifor_ :: forall (t :: * -> * -> *) (f :: * -> *) a b c d.
(Bifoldable t, Applicative f) =>
t a b -> (a -> f c) -> (b -> f d) -> f ()
bifor_ t a b
t a -> f c
f b -> f d
g = (a -> f c) -> (b -> f d) -> t a b -> f ()
forall (t :: * -> * -> *) (f :: * -> *) a c b d.
(Bifoldable t, Applicative f) =>
(a -> f c) -> (b -> f d) -> t a b -> f ()
bitraverse_ a -> f c
f b -> f d
g t a b
t

-- | Alias for 'bitraverse_'.
--
-- @since 4.10.0.0
bimapM_ :: (Bifoldable t, Applicative f)
        => (a -> f c) -> (b -> f d) -> t a b -> f ()
bimapM_ :: forall (t :: * -> * -> *) (f :: * -> *) a c b d.
(Bifoldable t, Applicative f) =>
(a -> f c) -> (b -> f d) -> t a b -> f ()
bimapM_ = (a -> f c) -> (b -> f d) -> t a b -> f ()
forall (t :: * -> * -> *) (f :: * -> *) a c b d.
(Bifoldable t, Applicative f) =>
(a -> f c) -> (b -> f d) -> t a b -> f ()
bitraverse_

-- | Alias for 'bifor_'.
--
-- @since 4.10.0.0
biforM_ :: (Bifoldable t, Applicative f)
        => t a b ->  (a -> f c) -> (b -> f d) -> f ()
biforM_ :: forall (t :: * -> * -> *) (f :: * -> *) a b c d.
(Bifoldable t, Applicative f) =>
t a b -> (a -> f c) -> (b -> f d) -> f ()
biforM_ = t a b -> (a -> f c) -> (b -> f d) -> f ()
forall (t :: * -> * -> *) (f :: * -> *) a b c d.
(Bifoldable t, Applicative f) =>
t a b -> (a -> f c) -> (b -> f d) -> f ()
bifor_

-- | Alias for 'bisequence_'.
--
-- @since 4.10.0.0
bisequenceA_ :: (Bifoldable t, Applicative f) => t (f a) (f b) -> f ()
bisequenceA_ :: forall (t :: * -> * -> *) (f :: * -> *) a b.
(Bifoldable t, Applicative f) =>
t (f a) (f b) -> f ()
bisequenceA_ = t (f a) (f b) -> f ()
forall (t :: * -> * -> *) (f :: * -> *) a b.
(Bifoldable t, Applicative f) =>
t (f a) (f b) -> f ()
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
-- 'Data.Bitraversable.bisequence'.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> bisequence_ (print "Hello", print "World")
-- "Hello"
-- "World"
--
-- >>> bisequence_ (Left (print "Hello"))
-- "Hello"
--
-- >>> bisequence_ (Right (print "World"))
-- "World"
--
-- @since 4.10.0.0
bisequence_ :: (Bifoldable t, Applicative f) => t (f a) (f b) -> f ()
bisequence_ :: forall (t :: * -> * -> *) (f :: * -> *) a b.
(Bifoldable t, Applicative f) =>
t (f a) (f b) -> f ()
bisequence_ = (f a -> f () -> f ())
-> (f b -> f () -> f ()) -> f () -> t (f a) (f b) -> f ()
forall a c b. (a -> c -> c) -> (b -> c -> c) -> c -> t a b -> c
forall (p :: * -> * -> *) a c b.
Bifoldable p =>
(a -> c -> c) -> (b -> c -> c) -> c -> p a b -> c
bifoldr f a -> f () -> f ()
forall a b. f a -> f b -> f b
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
(*>) f b -> f () -> f ()
forall a b. f a -> f b -> f b
forall (f :: * -> *) a b. Applicative f => f a -> f b -> f b
(*>) (() -> f ()
forall a. a -> f a
forall (f :: * -> *) a. Applicative f => a -> f a
pure ())

-- | 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
--
-- @since 4.10.0.0
biasum :: (Bifoldable t, Alternative f) => t (f a) (f a) -> f a
biasum :: forall (t :: * -> * -> *) (f :: * -> *) a.
(Bifoldable t, Alternative f) =>
t (f a) (f a) -> f a
biasum = (f a -> f a -> f a)
-> (f a -> f a -> f a) -> f a -> t (f a) (f a) -> f a
forall a c b. (a -> c -> c) -> (b -> c -> c) -> c -> t a b -> c
forall (p :: * -> * -> *) a c b.
Bifoldable p =>
(a -> c -> c) -> (b -> c -> c) -> c -> p a b -> c
bifoldr f a -> f a -> f a
forall a. f a -> f a -> f a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
(<|>) f a -> f a -> f a
forall a. f a -> f a -> f a
forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
(<|>) f a
forall a. f a
forall (f :: * -> *) a. Alternative f => f a
empty

-- | Alias for 'biasum'.
--
-- @since 4.10.0.0
bimsum :: (Bifoldable t, Alternative f) => t (f a) (f a) -> f a
bimsum :: forall (t :: * -> * -> *) (f :: * -> *) a.
(Bifoldable t, Alternative f) =>
t (f a) (f a) -> f a
bimsum = t (f a) (f a) -> f a
forall (t :: * -> * -> *) (f :: * -> *) a.
(Bifoldable t, Alternative f) =>
t (f a) (f a) -> f a
biasum

-- | Collects the list of elements of a structure, from left to right.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> biList (18, 42)
-- [18,42]
--
-- >>> biList (Left 18)
-- [18]
--
-- @since 4.10.0.0
biList :: Bifoldable t => t a a -> [a]
biList :: forall (t :: * -> * -> *) a. Bifoldable t => t a a -> [a]
biList = (a -> [a] -> [a]) -> (a -> [a] -> [a]) -> [a] -> t a a -> [a]
forall a c b. (a -> c -> c) -> (b -> c -> c) -> c -> t a b -> c
forall (p :: * -> * -> *) a c b.
Bifoldable p =>
(a -> c -> c) -> (b -> c -> c) -> c -> p a b -> c
bifoldr (:) (:) []

-- | Test whether the structure is empty.
--
-- ==== __Examples__
--
-- Basic usage:
--
-- >>> binull (18, 42)
-- False
--
-- >>> binull (Right 42)
-- False
--
-- >>> binull (BiList [] [])
-- True
--
-- @since 4.10.0.0
binull :: Bifoldable t => t a b -> Bool
binull :: forall (t :: * -> * -> *) a b. Bifoldable t => t a b -> Bool
binull = (a -> Bool -> Bool) -> (b -> Bool -> Bool) -> Bool -> t a b -> Bool
forall a c b. (a -> c -> c) -> (b -> c -> c) -> c -> t a b -> c
forall (p :: * -> * -> *) a c b.
Bifoldable p =>
(a -> c -> c) -> (b -> c -> c) -> c -> p a b -> c
bifoldr (\a
_ Bool
_ -> Bool
False) (\b
_ Bool
_ -> Bool
False) Bool
True

-- | 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 *
-- @
--
-- @since 4.10.0.0
bilength :: Bifoldable t => t a b -> Int
bilength :: forall (t :: * -> * -> *) a b. Bifoldable t => t a b -> Int
bilength = (Int -> a -> Int) -> (Int -> b -> Int) -> Int -> t a b -> Int
forall (t :: * -> * -> *) a b c.
Bifoldable t =>
(a -> b -> a) -> (a -> c -> a) -> a -> t b c -> a
bifoldl' (\Int
c a
_ -> Int
cInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) (\Int
c b
_ -> Int
cInt -> Int -> Int
forall a. Num a => a -> a -> a
+Int
1) Int
0

-- | 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
--
-- @since 4.10.0.0
bielem :: (Bifoldable t, Eq a) => a -> t a a -> Bool
bielem :: forall (t :: * -> * -> *) a.
(Bifoldable t, Eq a) =>
a -> t a a -> Bool
bielem a
x = (a -> Bool) -> (a -> Bool) -> t a a -> Bool
forall (t :: * -> * -> *) a b.
Bifoldable t =>
(a -> Bool) -> (b -> Bool) -> t a b -> Bool
biany (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
x) (a -> a -> Bool
forall a. Eq a => a -> a -> Bool
== a
x)

-- | 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]
--
-- @since 4.10.0.0
biconcat :: Bifoldable t => t [a] [a] -> [a]
biconcat :: forall (t :: * -> * -> *) a. Bifoldable t => t [a] [a] -> [a]
biconcat = t [a] [a] -> [a]
forall m. Monoid m => t m m -> m
forall (p :: * -> * -> *) m. (Bifoldable p, Monoid m) => p m m -> m
bifold

-- | The largest element of a non-empty structure. This function is equivalent
-- to @'bifoldr1' 'max'@, and its behavior on structures with multiple largest
-- elements depends on the relevant implementation of 'max'. For the default
-- implementation of 'max' (@max x y = if x <= y then y else x@), structure
-- order is used as a tie-breaker: if there are multiple largest elements, the
-- rightmost of them is chosen (this is equivalent to @'bimaximumBy'
-- 'compare'@).
--
-- ==== __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
-- ...
--
-- @since 4.10.0.0
bimaximum :: forall t a. (Bifoldable t, Ord a) => t a a -> a
bimaximum :: forall (t :: * -> * -> *) a. (Bifoldable t, Ord a) => t a a -> a
bimaximum = a -> Maybe a -> a
forall a. a -> Maybe a -> a
fromMaybe ([Char] -> a
forall a. HasCallStack => [Char] -> a
error [Char]
"bimaximum: empty structure") (Maybe a -> a) -> (t a a -> Maybe a) -> t a a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
    Max a -> Maybe a
forall a. Max a -> Maybe a
getMax (Max a -> Maybe a) -> (t a a -> Max a) -> t a a -> Maybe a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Max a) -> (a -> Max a) -> t a a -> Max a
forall m a b. Monoid m => (a -> m) -> (b -> m) -> t a b -> m
forall (p :: * -> * -> *) m a b.
(Bifoldable p, Monoid m) =>
(a -> m) -> (b -> m) -> p a b -> m
bifoldMap a -> Max a
mj a -> Max a
mj
  where mj :: a -> Max a
mj = Maybe a -> Max a
forall a. Maybe a -> Max a
Max (Maybe a -> Max a) -> (a -> Maybe a) -> a -> Max a
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. (a -> Maybe a
forall a. a -> Maybe a
Just :: a -> Maybe a)

-- | The least element of a non-empty structure. This function is equivalent to
-- @'bifoldr1' 'min'@, and its behavior on structures with multiple least
-- elements depends on the relevant implementation of 'min'. For the default
-- implementation of 'min' (@min x y = if x <= y then x else y@), structure
-- order is used as a tie-breaker: if there are multiple least elements, the
-- leftmost of them is chosen (this is equivalent to @'biminimumBy'
-- 'compare'@).
--
-- ==== __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
-- ...
--
-- @since 4.10.0.0
biminimum :: forall t a. (Bifoldable t, Ord a) => t a a -> a
biminimum :: forall (t :: * -> * -> *) a. (Bifoldable t, Ord a) => t a a -> a
biminimum = a -> Maybe a -> a
forall a. a -> Maybe a -> a
fromMaybe ([Char] -> a
forall a. HasCallStack => [Char] -> a
error [Char]
"biminimum: empty structure") (Maybe a -> a) -> (t a a -> Maybe a) -> t a a -> a
forall b c a. (b -> c) -> (a -> b) -> a -> c
.
    Min a -> Maybe a
forall a. Min a -> Maybe a
getMin (Min a -> Maybe a) -> (t a a -> Min a) -> t a a -> Maybe a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> Min a) -> (a -> Min a) -> t a a -> Min a
forall m a b. Monoid m => (a -> m) -> (b -> m) -> t a b -> m
forall (p :: * -> * -> *) m a b.
(Bifoldable p, Monoid m) =>
(a -> m) -> (b -> m) -> p a b -> m
bifoldMap a -> Min a
mj a -> Min a
mj
  where mj :: a -> Min a
mj = Maybe a -> Min a
forall a. Maybe a -> Min a
Min (Maybe a -> Min a) -> (a -> Maybe a) -> a -> Min a
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. (a -> Maybe a
forall a. a -> Maybe a
Just :: a -> Maybe a)

-- | 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
--
-- @since 4.10.0.0
bisum :: (Bifoldable t, Num a) => t a a -> a
bisum :: forall (t :: * -> * -> *) a. (Bifoldable t, Num a) => t a a -> a
bisum = Sum a -> a
forall a. Sum a -> a
getSum (Sum a -> a) -> (t a a -> Sum a) -> t a a -> a
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. (a -> Sum a) -> (a -> Sum a) -> t a a -> Sum a
forall m a b. Monoid m => (a -> m) -> (b -> m) -> t a b -> m
forall (p :: * -> * -> *) m a b.
(Bifoldable p, Monoid m) =>
(a -> m) -> (b -> m) -> p a b -> m
bifoldMap a -> Sum a
forall a. a -> Sum a
Sum a -> Sum a
forall a. a -> Sum a
Sum

-- | 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
--
-- @since 4.10.0.0
biproduct :: (Bifoldable t, Num a) => t a a -> a
biproduct :: forall (t :: * -> * -> *) a. (Bifoldable t, Num a) => t a a -> a
biproduct = Product a -> a
forall a. Product a -> a
getProduct (Product a -> a) -> (t a a -> Product a) -> t a a -> a
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. (a -> Product a) -> (a -> Product a) -> t a a -> Product a
forall m a b. Monoid m => (a -> m) -> (b -> m) -> t a b -> m
forall (p :: * -> * -> *) m a b.
(Bifoldable p, Monoid m) =>
(a -> m) -> (b -> m) -> p a b -> m
bifoldMap a -> Product a
forall a. a -> Product a
Product a -> Product a
forall a. a -> Product a
Product

-- | 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]
--
-- @since 4.10.0.0
biconcatMap :: Bifoldable t => (a -> [c]) -> (b -> [c]) -> t a b -> [c]
biconcatMap :: forall (t :: * -> * -> *) a c b.
Bifoldable t =>
(a -> [c]) -> (b -> [c]) -> t a b -> [c]
biconcatMap = (a -> [c]) -> (b -> [c]) -> t a b -> [c]
forall m a b. Monoid m => (a -> m) -> (b -> m) -> t a b -> m
forall (p :: * -> * -> *) m a b.
(Bifoldable p, Monoid m) =>
(a -> m) -> (b -> m) -> p a b -> m
bifoldMap

-- | '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 *
-- @
--
-- @since 4.10.0.0
biand :: Bifoldable t => t Bool Bool -> Bool
biand :: forall (t :: * -> * -> *). Bifoldable t => t Bool Bool -> Bool
biand = All -> Bool
getAll (All -> Bool) -> (t Bool Bool -> All) -> t Bool Bool -> Bool
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. (Bool -> All) -> (Bool -> All) -> t Bool Bool -> All
forall m a b. Monoid m => (a -> m) -> (b -> m) -> t a b -> m
forall (p :: * -> * -> *) m a b.
(Bifoldable p, Monoid m) =>
(a -> m) -> (b -> m) -> p a b -> m
bifoldMap Bool -> All
All Bool -> All
All

-- | '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 *
-- @
--
-- @since 4.10.0.0
bior :: Bifoldable t => t Bool Bool -> Bool
bior :: forall (t :: * -> * -> *). Bifoldable t => t Bool Bool -> Bool
bior = Any -> Bool
getAny (Any -> Bool) -> (t Bool Bool -> Any) -> t Bool Bool -> Bool
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. (Bool -> Any) -> (Bool -> Any) -> t Bool Bool -> Any
forall m a b. Monoid m => (a -> m) -> (b -> m) -> t a b -> m
forall (p :: * -> * -> *) m a b.
(Bifoldable p, Monoid m) =>
(a -> m) -> (b -> m) -> p a b -> m
bifoldMap Bool -> Any
Any Bool -> Any
Any

-- | 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
--
-- @since 4.10.0.0
biany :: Bifoldable t => (a -> Bool) -> (b -> Bool) -> t a b -> Bool
biany :: forall (t :: * -> * -> *) a b.
Bifoldable t =>
(a -> Bool) -> (b -> Bool) -> t a b -> Bool
biany a -> Bool
p b -> Bool
q = Any -> Bool
getAny (Any -> Bool) -> (t a b -> Any) -> t a b -> Bool
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. (a -> Any) -> (b -> Any) -> t a b -> Any
forall m a b. Monoid m => (a -> m) -> (b -> m) -> t a b -> m
forall (p :: * -> * -> *) m a b.
(Bifoldable p, Monoid m) =>
(a -> m) -> (b -> m) -> p a b -> m
bifoldMap (Bool -> Any
Any (Bool -> Any) -> (a -> Bool) -> a -> Any
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
p) (Bool -> Any
Any (Bool -> Any) -> (b -> Bool) -> b -> Any
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> Bool
q)

-- | 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
--
-- @since 4.10.0.0
biall :: Bifoldable t => (a -> Bool) -> (b -> Bool) -> t a b -> Bool
biall :: forall (t :: * -> * -> *) a b.
Bifoldable t =>
(a -> Bool) -> (b -> Bool) -> t a b -> Bool
biall a -> Bool
p b -> Bool
q = All -> Bool
getAll (All -> Bool) -> (t a b -> All) -> t a b -> Bool
forall b c a. Coercible b c => (b -> c) -> (a -> b) -> a -> c
#. (a -> All) -> (b -> All) -> t a b -> All
forall m a b. Monoid m => (a -> m) -> (b -> m) -> t a b -> m
forall (p :: * -> * -> *) m a b.
(Bifoldable p, Monoid m) =>
(a -> m) -> (b -> m) -> p a b -> m
bifoldMap (Bool -> All
All (Bool -> All) -> (a -> Bool) -> a -> All
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Bool
p) (Bool -> All
All (Bool -> All) -> (b -> Bool) -> b -> All
forall b c a. (b -> c) -> (a -> b) -> a -> c
. b -> Bool
q)

-- | The largest element of a non-empty structure with respect to the
-- given comparison function. Structure order is used as a tie-breaker: if
-- there are multiple largest elements, the rightmost of them is chosen.
--
-- ==== __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
-- ...
--
-- @since 4.10.0.0
bimaximumBy :: Bifoldable t => (a -> a -> Ordering) -> t a a -> a
bimaximumBy :: forall (t :: * -> * -> *) a.
Bifoldable t =>
(a -> a -> Ordering) -> t a a -> a
bimaximumBy a -> a -> Ordering
cmp = (a -> a -> a) -> t a a -> a
forall (t :: * -> * -> *) a.
Bifoldable t =>
(a -> a -> a) -> t a a -> a
bifoldr1 a -> a -> a
max'
  where max' :: a -> a -> a
max' a
x a
y = case a -> a -> Ordering
cmp a
x a
y of
                        Ordering
GT -> a
x
                        Ordering
_  -> a
y

-- | The least element of a non-empty structure with respect to the
-- given comparison function. Structure order is used as a tie-breaker: if
-- there are multiple least elements, the leftmost of them is chosen.
--
-- ==== __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
-- ...
--
-- @since 4.10.0.0
biminimumBy :: Bifoldable t => (a -> a -> Ordering) -> t a a -> a
biminimumBy :: forall (t :: * -> * -> *) a.
Bifoldable t =>
(a -> a -> Ordering) -> t a a -> a
biminimumBy a -> a -> Ordering
cmp = (a -> a -> a) -> t a a -> a
forall (t :: * -> * -> *) a.
Bifoldable t =>
(a -> a -> a) -> t a a -> a
bifoldr1 a -> a -> a
min'
  where min' :: a -> a -> a
min' a
x a
y = case a -> a -> Ordering
cmp a
x a
y of
                        Ordering
GT -> a
y
                        Ordering
_  -> a
x

-- | '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
--
-- @since 4.10.0.0
binotElem :: (Bifoldable t, Eq a) => a -> t a a-> Bool
binotElem :: forall (t :: * -> * -> *) a.
(Bifoldable t, Eq a) =>
a -> t a a -> Bool
binotElem a
x =  Bool -> Bool
not (Bool -> Bool) -> (t a a -> Bool) -> t a a -> Bool
forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> t a a -> Bool
forall (t :: * -> * -> *) a.
(Bifoldable t, Eq a) =>
a -> t a a -> Bool
bielem a
x

-- | 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
--
-- @since 4.10.0.0
bifind :: Bifoldable t => (a -> Bool) -> t a a -> Maybe a
bifind :: forall (t :: * -> * -> *) a.
Bifoldable t =>
(a -> Bool) -> t a a -> Maybe a
bifind a -> Bool
p = First a -> Maybe a
forall a. First a -> Maybe a
getFirst (First a -> Maybe a) -> (t a a -> First a) -> t a a -> Maybe a
forall b c a. (b -> c) -> (a -> b) -> a -> c
. (a -> First a) -> (a -> First a) -> t a a -> First a
forall m a b. Monoid m => (a -> m) -> (b -> m) -> t a b -> m
forall (p :: * -> * -> *) m a b.
(Bifoldable p, Monoid m) =>
(a -> m) -> (b -> m) -> p a b -> m
bifoldMap a -> First a
finder a -> First a
finder
  where finder :: a -> First a
finder a
x = Maybe a -> First a
forall a. Maybe a -> First a
First (if a -> Bool
p a
x then a -> Maybe a
forall a. a -> Maybe a
Just a
x else Maybe a
forall a. Maybe a
Nothing)