    {-# LANGUAGE CPP, LambdaCase, TupleSections, DeriveTraversable #-}
    {-# LANGUAGE GeneralizedNewtypeDeriving, DerivingVia #-}
    {-# OPTIONS_GHC -fno-warn-unused-imports #-}
    -----------------------------------------------------------------------------
    -- |
    -- Module     : Control.Selective
    -- Copyright  : (c) Andrey Mokhov 2018-2024
    -- License    : MIT (see the file LICENSE)
    -- Maintainer : andrey.mokhov@gmail.com
    -- Stability  : experimental
    --
    -- This is a library for /selective applicative functors/, or just
    -- /selective functors/ for short, an abstraction between applicative functors
    -- and monads, introduced in this paper: https://dl.acm.org/doi/10.1145/3341694.
    --
    -----------------------------------------------------------------------------
    module Control.Selective (
        -- * Type class
        Selective (..), (<*?), branch, selectA, selectT, apS, selectM,

        -- * Conditional combinators
        ifS, whenS, fromMaybeS, orElse, andAlso, untilRight, whileS, (<||>), (<&&>),
        foldS, anyS, allS, bindS, Cases, casesEnum, cases, matchS, matchM,

        -- * Selective functors
        SelectA (..), SelectM (..), Over (..), Under (..), Validation (..),

        -- * Miscellaneous
        swapEither, ComposeEither (..), ComposeTraversable (..)
        ) where

    import Control.Applicative
    import Control.Applicative.Lift
    import Control.Arrow
    import Control.Monad.ST
    import Control.Monad.Trans.Cont
    import Control.Monad.Trans.Identity
    import Control.Monad.Trans.Maybe
    import Control.Monad.Trans.Reader
    import Control.Monad.Trans.RWS
    import Control.Monad.Trans.State
    import Control.Monad.Trans.Writer
    import Data.Bool
    import Data.Function
    import Data.Functor.Compose
    import Data.Functor.Identity
    import Data.Functor.Product
    import Data.List.NonEmpty
    import Data.Proxy
    import Data.Semigroup (Semigroup (..))
    import GHC.Conc (STM)

    import qualified Control.Monad.Trans.RWS.Strict    as S
    import qualified Control.Monad.Trans.State.Strict  as S
    import qualified Control.Monad.Trans.Writer.Strict as S

    -- | Selective applicative functors. You can think of 'select' as a selective
    -- function application: when given a value of type 'Left' @a@, you __must apply__
    -- the given function, but when given a 'Right' @b@, you __may skip__ the
    -- function and associated effects, and simply return the @b@.
    --
    -- Note that it is not a requirement for selective functors to skip unnecessary
    -- effects. It may be counterintuitive, but this makes them more useful. Why?
    -- Typically, when executing a selective computation, you would want to skip the
    -- effects (saving work); but on the other hand, if your goal is to statically
    -- analyse a given selective computation and extract the set of all possible
    -- effects (without actually executing them), then you do not want to skip any
    -- effects, because that defeats the purpose of static analysis.
    --
    -- The type signature of 'select' is reminiscent of both '<*>' and '>>=', and
    -- indeed a selective functor is in some sense a composition of an applicative
    -- functor and the 'Either' monad.
    --
    -- Laws:
    --
    -- * Identity:
    --
    -- @
    -- x \<*? pure id = either id id \<$\> x
    -- @
    --
    -- * Distributivity; note that @y@ and @z@ have the same type @f (a -> b)@:
    --
    -- @
    -- pure x \<*? (y *\> z) = (pure x \<*? y) *\> (pure x \<*? z)
    -- @
    --
    -- * Associativity:
    --
    -- @
    -- x \<*? (y \<*? z) = (f \<$\> x) \<*? (g \<$\> y) \<*? (h \<$\> z)
    --   where
    --     f x = Right \<$\> x
    --     g y = \a -\> bimap (,a) ($a) y
    --     h z = uncurry z
    -- @
    --
    -- * Monadic 'select' (for selective functors that are also monads):
    --
    -- @
    -- select = selectM
    -- @
    --
    -- There are also a few useful theorems:
    --
    -- * Apply a pure function to the result:
    --
    -- @
    -- f \<$\> select x y = select (fmap f \<$\> x) (fmap f \<$\> y)
    -- @
    --
    -- * Apply a pure function to the @Left@ case of the first argument:
    --
    -- @
    -- select (first f \<$\> x) y = select x ((. f) \<$\> y)
    -- @
    --
    -- * Apply a pure function to the second argument:
    --
    -- @
    -- select x (f \<$\> y) = select (first (flip f) \<$\> x) ((&) \<$\> y)
    -- @
    --
    -- * Generalised identity:
    --
    -- @
    -- x \<*? pure y = either y id \<$\> x
    -- @
    --
    -- * A selective functor is /rigid/ if it satisfies '<*>' @=@ 'apS'. The
    -- following /interchange/ law holds for rigid selective functors:
    --
    -- @
    -- x *\> (y \<*? z) = (x *\> y) \<*? z
    -- @
    --
    -- If f is also a 'Monad', we require that 'select' = 'selectM', from which one
    -- can prove '<*>' @=@ 'apS'.
    class Applicative f => Selective f where
        select :: f (Either a b) -> f (a -> b) -> f b

    {- Why do we have skew associativity, where we can reassociate effects to the
       left but not to the right?

       The following two tables, which list all possible combinations of effect
       execution and skipping, might give you some intuition on why this happens.

         ---------------
         (x <*? y) <*? z
         ---------------
          1     0      0
          1     1      0
          1     0      1
          1     1      1

         ---------------
         x <*? (y <*? z)
         ---------------
         1      0     0
         1      1     0
         1      1     1

       A key observation is that when effects are associated to the right, we can't
       skip the effect y and execute the effect z: combination 101 is impossible.
    -}

    -- | An operator alias for 'select', which is sometimes convenient. It tries to
    -- follow the notational convention for 'Applicative' operators. The angle
    -- bracket pointing to the left means we always use the corresponding value.
    -- The value on the right, however, may be skipped, hence the question mark.
    (<*?) :: Selective f => f (Either a b) -> f (a -> b) -> f b
    <*? :: forall (f :: * -> *) a b.
    Selective f =>
    f (Either a b) -> f (a -> b) -> f b
    (<*?) = f (Either a b) -> f (a -> b) -> f b
    forall a b. f (Either a b) -> f (a -> b) -> f b
    forall (f :: * -> *) a b.
    Selective f =>
    f (Either a b) -> f (a -> b) -> f b
    select

    infixl 4 <*?

    -- | The 'branch' function is a natural generalisation of 'select': instead of
    -- skipping an unnecessary effect, it chooses which of the two given effectful
    -- functions to apply to a given argument; the other effect is unnecessary. It
    -- is possible to implement 'branch' in terms of 'select', which is a good
    -- puzzle (give it a try!).
    --
    -- We can also implement 'select' via 'branch':
    --
    -- @
    -- selectB :: Selective f => f (Either a b) -> f (a -> b) -> f b
    -- selectB x y = branch x y (pure id)
    -- @
    --
    branch :: Selective f => f (Either a b) -> f (a -> c) -> f (b -> c) -> f c
    branch :: forall (f :: * -> *) a b c.
    Selective f =>
    f (Either a b) -> f (a -> c) -> f (b -> c) -> f c
    branch f (Either a b)
    x f (a -> c)
    l f (b -> c)
    r = (Either a b -> Either a (Either b c))
    -> f (Either a b) -> f (Either a (Either b c))
    forall a b. (a -> b) -> f a -> f b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap ((b -> Either b c) -> Either a b -> Either a (Either b c)
    forall a b. (a -> b) -> Either a a -> Either a b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap b -> Either b c
    forall a b. a -> Either a b
    Left) f (Either a b)
    x f (Either a (Either b c)) -> f (a -> Either b c) -> f (Either b c)
    forall (f :: * -> *) a b.
    Selective f =>
    f (Either a b) -> f (a -> b) -> f b
    <*? ((a -> c) -> a -> Either b c) -> f (a -> c) -> f (a -> Either b c)
    forall a b. (a -> b) -> f a -> f b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap ((c -> Either b c) -> (a -> c) -> a -> Either b c
    forall a b. (a -> b) -> (a -> a) -> a -> b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap c -> Either b c
    forall a b. b -> Either a b
    Right) f (a -> c)
    l f (Either b c) -> f (b -> c) -> f c
    forall (f :: * -> *) a b.
    Selective f =>
    f (Either a b) -> f (a -> b) -> f b
    <*? f (b -> c)
    r

    -- | We can write a function with the type signature of 'select' using the
    -- 'Applicative' type class, but it will always execute the effects associated
    -- with the second argument, hence being potentially less efficient.
    selectA :: Applicative f => f (Either a b) -> f (a -> b) -> f b
    selectA :: forall (f :: * -> *) a b.
    Applicative f =>
    f (Either a b) -> f (a -> b) -> f b
    selectA f (Either a b)
    x f (a -> b)
    y = (\Either a b
    e a -> b
    f -> (a -> b) -> (b -> b) -> Either a b -> b
    forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
    either a -> b
    f b -> b
    forall a. a -> a
    id Either a b
    e) (Either a b -> (a -> b) -> b)
    -> f (Either a b) -> f ((a -> b) -> b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Either a b)
    x f ((a -> b) -> b) -> f (a -> b) -> f b
    forall a b. f (a -> b) -> f a -> f b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> f (a -> b)
    y

    -- | For traversable functors, we can implement 'select' in another interesting
    -- way: the effects associated with the second argument can be skipped as long
    -- as the first argument contains only 'Right' values.
    selectT :: Traversable f => f (Either a b) -> f (a -> b) -> f b
    selectT :: forall (f :: * -> *) a b.
    Traversable f =>
    f (Either a b) -> f (a -> b) -> f b
    selectT f (Either a b)
    x f (a -> b)
    y = case f (Either a b) -> Either a (f b)
    forall (t :: * -> *) (f :: * -> *) a.
    (Traversable t, Applicative f) =>
    t (f a) -> f (t a)
    forall (f :: * -> *) a. Applicative f => f (f a) -> f (f a)
    sequenceA f (Either a b)
    x of
        Left  a
    a  -> ((a -> b) -> a -> b
    forall a b. (a -> b) -> a -> b
    $a
    a) ((a -> b) -> b) -> f (a -> b) -> f b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (a -> b)
    y
        Right f b
    fb -> f b
    fb

    {-| Recover the application operator '<*>' from 'select'. /Rigid/ selective
    functors satisfy the law '<*>' @=@ 'apS' and furthermore, the resulting
    applicative functor satisfies all laws of 'Applicative':

    * Identity:

        > pure id <*> v = v

    * Homomorphism:

        > pure f <*> pure x = pure (f x)

    * Interchange:

        > u <*> pure y = pure ($y) <*> u

    * Composition:

        > (.) <$> u <*> v <*> w = u <*> (v <*> w)
    -}
    apS :: Selective f => f (a -> b) -> f a -> f b
    apS :: forall (f :: * -> *) a b. Selective f => f (a -> b) -> f a -> f b
    apS f (a -> b)
    f f a
    x = f (Either (a -> b) b) -> f ((a -> b) -> b) -> f b
    forall a b. f (Either a b) -> f (a -> b) -> f b
    forall (f :: * -> *) a b.
    Selective f =>
    f (Either a b) -> f (a -> b) -> f b
    select ((a -> b) -> Either (a -> b) b
    forall a b. a -> Either a b
    Left ((a -> b) -> Either (a -> b) b)
    -> f (a -> b) -> f (Either (a -> b) b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (a -> b)
    f) (a -> (a -> b) -> b
    forall a b. a -> (a -> b) -> b
    (&) (a -> (a -> b) -> b) -> f a -> f ((a -> b) -> b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f a
    x)

    -- | One can easily implement a monadic 'selectM' that satisfies the laws,
    -- hence any 'Monad' is 'Selective'.
    selectM :: Monad f => f (Either a b) -> f (a -> b) -> f b
    selectM :: forall (f :: * -> *) a b.
    Monad f =>
    f (Either a b) -> f (a -> b) -> f b
    selectM f (Either a b)
    x f (a -> b)
    y = f (Either a b)
    x f (Either a b) -> (Either a b -> f b) -> f b
    forall a b. f a -> (a -> f b) -> f b
    forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
    >>= \case Left  a
    a -> ((a -> b) -> a -> b
    forall a b. (a -> b) -> a -> b
    $a
    a) ((a -> b) -> b) -> f (a -> b) -> f b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (a -> b)
    y -- execute y
                              Right b
    b -> b -> f b
    forall a. a -> f a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure b
    b     -- skip y

    -- Many useful 'Monad' combinators can be implemented with 'Selective'

    -- | Branch on a Boolean value, skipping unnecessary effects.
    ifS :: Selective f => f Bool -> f a -> f a -> f a
    ifS :: forall (f :: * -> *) a. Selective f => f Bool -> f a -> f a -> f a
    ifS f Bool
    x f a
    t f a
    e = f (Either () ()) -> f (() -> a) -> f (() -> a) -> f a
    forall (f :: * -> *) a b c.
    Selective f =>
    f (Either a b) -> f (a -> c) -> f (b -> c) -> f c
    branch (Either () () -> Either () () -> Bool -> Either () ()
    forall a. a -> a -> Bool -> a
    bool (() -> Either () ()
    forall a b. b -> Either a b
    Right ()) (() -> Either () ()
    forall a b. a -> Either a b
    Left ()) (Bool -> Either () ()) -> f Bool -> f (Either () ())
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f Bool
    x) (a -> () -> a
    forall a b. a -> b -> a
    const (a -> () -> a) -> f a -> f (() -> a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f a
    t) (a -> () -> a
    forall a b. a -> b -> a
    const (a -> () -> a) -> f a -> f (() -> a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f a
    e)

    -- Implementation used in the paper:
    -- ifS x t e = branch selector (fmap const t) (fmap const e)
    --   where
    --     selector = bool (Right ()) (Left ()) <$> x -- NB: convert True to Left ()

    -- | Eliminate a specified value @a@ from @f (Either a b)@ by replacing it
    -- with a given @f b@.
    eliminate :: (Eq a, Selective f) => a -> f b -> f (Either a b) -> f (Either a b)
    eliminate :: forall a (f :: * -> *) b.
    (Eq a, Selective f) =>
    a -> f b -> f (Either a b) -> f (Either a b)
    eliminate a
    x f b
    fb f (Either a b)
    fa = f (Either () (Either a b))
    -> f (() -> Either a b) -> f (Either a b)
    forall a b. f (Either a b) -> f (a -> b) -> f b
    forall (f :: * -> *) a b.
    Selective f =>
    f (Either a b) -> f (a -> b) -> f b
    select (a -> Either a b -> Either () (Either a b)
    forall {a} {b}. Eq a => a -> Either a b -> Either () (Either a b)
    match a
    x (Either a b -> Either () (Either a b))
    -> f (Either a b) -> f (Either () (Either a b))
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Either a b)
    fa) (Either a b -> () -> Either a b
    forall a b. a -> b -> a
    const (Either a b -> () -> Either a b)
    -> (b -> Either a b) -> b -> () -> Either a b
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . b -> Either a b
    forall a b. b -> Either a b
    Right (b -> () -> Either a b) -> f b -> f (() -> Either a b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f b
    fb)
      where
        match :: a -> Either a b -> Either () (Either a b)
    match a
    _ (Right b
    y) = Either a b -> Either () (Either a b)
    forall a b. b -> Either a b
    Right (b -> Either a b
    forall a b. b -> Either a b
    Right b
    y)
        match a
    x (Left  a
    y) = if a
    x a -> a -> Bool
    forall a. Eq a => a -> a -> Bool
    == a
    y then () -> Either () (Either a b)
    forall a b. a -> Either a b
    Left () else Either a b -> Either () (Either a b)
    forall a b. b -> Either a b
    Right (a -> Either a b
    forall a b. a -> Either a b
    Left a
    y)

    -- | A list of values, equipped with a fast membership test.
    data Cases a = Cases [a] (a -> Bool)

    -- | The list of all possible values of an enumerable data type.
    casesEnum :: (Bounded a, Enum a) => Cases a
    casesEnum :: forall a. (Bounded a, Enum a) => Cases a
    casesEnum = [a] -> (a -> Bool) -> Cases a
    forall a. [a] -> (a -> Bool) -> Cases a
    Cases [a
    forall a. Bounded a => a
    minBound..a
    forall a. Bounded a => a
    maxBound] (Bool -> a -> Bool
    forall a b. a -> b -> a
    const Bool
    True)

    -- | Embed a list of values into 'Cases' using the trivial but slow membership
    -- test based on 'elem'.
    cases :: Eq a => [a] -> Cases a
    cases :: forall a. Eq a => [a] -> Cases a
    cases [a]
    as = [a] -> (a -> Bool) -> Cases a
    forall a. [a] -> (a -> Bool) -> Cases a
    Cases [a]
    as (a -> [a] -> Bool
    forall a. Eq a => a -> [a] -> Bool
    forall (t :: * -> *) a. (Foldable t, Eq a) => a -> t a -> Bool
    `elem` [a]
    as)

    -- | Eliminate all specified values @a@ from @f (Either a b)@ by replacing each
    -- of them with a given @f a@.
    matchS :: (Eq a, Selective f) => Cases a -> f a -> (a -> f b) -> f (Either a b)
    matchS :: forall a (f :: * -> *) b.
    (Eq a, Selective f) =>
    Cases a -> f a -> (a -> f b) -> f (Either a b)
    matchS (Cases [a]
    cs a -> Bool
    _) f a
    x a -> f b
    f = (a -> f (Either a b) -> f (Either a b))
    -> f (Either a b) -> [a] -> f (Either a b)
    forall a b. (a -> b -> b) -> b -> [a] -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr (\a
    c -> a -> f b -> f (Either a b) -> f (Either a b)
    forall a (f :: * -> *) b.
    (Eq a, Selective f) =>
    a -> f b -> f (Either a b) -> f (Either a b)
    eliminate a
    c (a -> f b
    f a
    c)) (a -> Either a b
    forall a b. a -> Either a b
    Left (a -> Either a b) -> f a -> f (Either a b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f a
    x) [a]
    cs

    -- | Eliminate all specified values @a@ from @f (Either a b)@ by replacing each
    -- of them with a given @f a@.
    matchM :: Monad m => Cases a -> m a -> (a -> m b) -> m (Either a b)
    matchM :: forall (m :: * -> *) a b.
    Monad m =>
    Cases a -> m a -> (a -> m b) -> m (Either a b)
    matchM (Cases [a]
    _ a -> Bool
    p) m a
    mx a -> m b
    f = do
        a
    x <- m a
    mx
        if a -> Bool
    p a
    x then b -> Either a b
    forall a b. b -> Either a b
    Right (b -> Either a b) -> m b -> m (Either a b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> a -> m b
    f a
    x else Either a b -> m (Either a b)
    forall a. a -> m a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (a -> Either a b
    forall a b. a -> Either a b
    Left a
    x)

    -- TODO: Add a type-safe version based on @KnownNat@.
    -- | A restricted version of monadic bind. Fails with an error if the 'Bounded'
    -- and 'Enum' instances for @a@ do not cover all values of @a@.
    bindS :: (Bounded a, Enum a, Eq a, Selective f) => f a -> (a -> f b) -> f b
    bindS :: forall a (f :: * -> *) b.
    (Bounded a, Enum a, Eq a, Selective f) =>
    f a -> (a -> f b) -> f b
    bindS f a
    x a -> f b
    f = Either a b -> b
    forall {a} {b}. Either a b -> b
    fromRight (Either a b -> b) -> f (Either a b) -> f b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Cases a -> f a -> (a -> f b) -> f (Either a b)
    forall a (f :: * -> *) b.
    (Eq a, Selective f) =>
    Cases a -> f a -> (a -> f b) -> f (Either a b)
    matchS Cases a
    forall a. (Bounded a, Enum a) => Cases a
    casesEnum f a
    x a -> f b
    f
      where
        fromRight :: Either a b -> b
    fromRight (Right b
    b) = b
    b
        fromRight Either a b
    _ = [Char] -> b
    forall a. HasCallStack => [Char] -> a
    error [Char]
    "Selective.bindS: incorrect Bounded and/or Enum instance"

    -- | Conditionally perform an effect.
    whenS :: Selective f => f Bool -> f () -> f ()
    whenS :: forall (f :: * -> *). Selective f => f Bool -> f () -> f ()
    whenS f Bool
    x f ()
    y = f (Either () ()) -> f (() -> ()) -> f ()
    forall a b. f (Either a b) -> f (a -> b) -> f b
    forall (f :: * -> *) a b.
    Selective f =>
    f (Either a b) -> f (a -> b) -> f b
    select (Either () () -> Either () () -> Bool -> Either () ()
    forall a. a -> a -> Bool -> a
    bool (() -> Either () ()
    forall a b. b -> Either a b
    Right ()) (() -> Either () ()
    forall a b. a -> Either a b
    Left ()) (Bool -> Either () ()) -> f Bool -> f (Either () ())
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f Bool
    x) (() -> () -> ()
    forall a b. a -> b -> a
    const (() -> () -> ()) -> f () -> f (() -> ())
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f ()
    y)

    -- Implementation used in the paper:
    -- whenS x y = selector <*? effect
    --   where
    --     selector = bool (Right ()) (Left ()) <$> x -- NB: maps True to Left ()
    --     effect   = const                     <$> y

    -- | A lifted version of 'Data.Maybe.fromMaybe'.
    fromMaybeS :: Selective f => f a -> f (Maybe a) -> f a
    fromMaybeS :: forall (f :: * -> *) a. Selective f => f a -> f (Maybe a) -> f a
    fromMaybeS f a
    fNothing f (Maybe a)
    fMaybe =
        f (Either () a) -> f (() -> a) -> f a
    forall a b. f (Either a b) -> f (a -> b) -> f b
    forall (f :: * -> *) a b.
    Selective f =>
    f (Either a b) -> f (a -> b) -> f b
    select (Maybe a -> Either () a
    forall a. Maybe a -> Either () a
    toEither (Maybe a -> Either () a) -> f (Maybe a) -> f (Either () a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Maybe a)
    fMaybe) (a -> () -> a
    forall a. a -> () -> a
    toUnitFunction (a -> () -> a) -> f a -> f (() -> a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f a
    fNothing)
      where
        toEither :: Maybe a -> Either () a
        toEither :: forall a. Maybe a -> Either () a
    toEither Maybe a
    Nothing  = () -> Either () a
    forall a b. a -> Either a b
    Left ()
        toEither (Just a
    a) = a -> Either () a
    forall a b. b -> Either a b
    Right a
    a
        toUnitFunction :: a -> () -> a
        toUnitFunction :: forall a. a -> () -> a
    toUnitFunction a
    x () = a
    x

    -- | Return the first @Right@ value. If both are @Left@'s, accumulate errors.
    orElse :: (Selective f, Semigroup e) => f (Either e a) -> f (Either e a) -> f (Either e a)
    orElse :: forall (f :: * -> *) e a.
    (Selective f, Semigroup e) =>
    f (Either e a) -> f (Either e a) -> f (Either e a)
    orElse f (Either e a)
    x f (Either e a)
    y = f (Either e (Either e a)) -> f (e -> Either e a) -> f (Either e a)
    forall a b. f (Either a b) -> f (a -> b) -> f b
    forall (f :: * -> *) a b.
    Selective f =>
    f (Either a b) -> f (a -> b) -> f b
    select (Either e a -> Either e (Either e a)
    forall e a. Either e a -> Either e (Either e a)
    prepare (Either e a -> Either e (Either e a))
    -> f (Either e a) -> f (Either e (Either e a))
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Either e a)
    x) (Either e a -> e -> Either e a
    forall e a. Semigroup e => Either e a -> e -> Either e a
    combine (Either e a -> e -> Either e a)
    -> f (Either e a) -> f (e -> Either e a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Either e a)
    y)
      where
        prepare :: Either e a -> Either e (Either e a)
        prepare :: forall e a. Either e a -> Either e (Either e a)
    prepare = (a -> Either e a) -> Either e a -> Either e (Either e a)
    forall a b. (a -> b) -> Either e a -> Either e b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap a -> Either e a
    forall a b. b -> Either a b
    Right

        combine :: Semigroup e => Either e a -> e -> Either e a
        combine :: forall e a. Semigroup e => Either e a -> e -> Either e a
    combine (Left e
    ey) e
    ex = e -> Either e a
    forall a b. a -> Either a b
    Left (e
    ex e -> e -> e
    forall a. Semigroup a => a -> a -> a
    <> e
    ey)
        combine (Right a
    a) e
    _  = a -> Either e a
    forall a b. b -> Either a b
    Right a
    a

    -- | Accumulate the @Right@ values, or return the first @Left@.
    andAlso :: (Selective f, Semigroup a) => f (Either e a) -> f (Either e a) -> f (Either e a)
    andAlso :: forall (f :: * -> *) a e.
    (Selective f, Semigroup a) =>
    f (Either e a) -> f (Either e a) -> f (Either e a)
    andAlso f (Either e a)
    x f (Either e a)
    y = Either a e -> Either e a
    forall a b. Either a b -> Either b a
    swapEither (Either a e -> Either e a) -> f (Either a e) -> f (Either e a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Either a e) -> f (Either a e) -> f (Either a e)
    forall (f :: * -> *) e a.
    (Selective f, Semigroup e) =>
    f (Either e a) -> f (Either e a) -> f (Either e a)
    orElse (Either e a -> Either a e
    forall a b. Either a b -> Either b a
    swapEither (Either e a -> Either a e) -> f (Either e a) -> f (Either a e)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Either e a)
    x) (Either e a -> Either a e
    forall a b. Either a b -> Either b a
    swapEither (Either e a -> Either a e) -> f (Either e a) -> f (Either a e)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Either e a)
    y)

    -- | Swap @Left@ and @Right@.
    swapEither :: Either a b -> Either b a
    swapEither :: forall a b. Either a b -> Either b a
    swapEither = (a -> Either b a) -> (b -> Either b a) -> Either a b -> Either b a
    forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
    either a -> Either b a
    forall a b. b -> Either a b
    Right b -> Either b a
    forall a b. a -> Either a b
    Left

    -- | Keep checking an effectful condition while it holds.
    whileS :: Selective f => f Bool -> f ()
    whileS :: forall (f :: * -> *). Selective f => f Bool -> f ()
    whileS f Bool
    act = f Bool -> f () -> f ()
    forall (f :: * -> *). Selective f => f Bool -> f () -> f ()
    whenS f Bool
    act (f Bool -> f ()
    forall (f :: * -> *). Selective f => f Bool -> f ()
    whileS f Bool
    act)

    -- | Keep running an effectful computation until it returns a @Right@ value,
    -- collecting the @Left@'s using a supplied @Monoid@ instance.
    untilRight :: (Monoid a, Selective f) => f (Either a b) -> f (a, b)
    untilRight :: forall a (f :: * -> *) b.
    (Monoid a, Selective f) =>
    f (Either a b) -> f (a, b)
    untilRight f (Either a b)
    x = f (Either a (a, b)) -> f (a -> (a, b)) -> f (a, b)
    forall a b. f (Either a b) -> f (a -> b) -> f b
    forall (f :: * -> *) a b.
    Selective f =>
    f (Either a b) -> f (a -> b) -> f b
    select f (Either a (a, b))
    y f (a -> (a, b))
    h
      where
        -- y :: f (Either a (a, b))
        y :: f (Either a (a, b))
    y = (b -> (a, b)) -> Either a b -> Either a (a, b)
    forall a b. (a -> b) -> Either a a -> Either a b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap (a
    forall a. Monoid a => a
    mempty,) (Either a b -> Either a (a, b))
    -> f (Either a b) -> f (Either a (a, b))
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Either a b)
    x
        -- h :: f (a -> (a, b))
        h :: f (a -> (a, b))
    h = (\(a
    as, b
    b) a
    a -> (a -> a -> a
    forall a. Monoid a => a -> a -> a
    mappend a
    a a
    as, b
    b)) ((a, b) -> a -> (a, b)) -> f (a, b) -> f (a -> (a, b))
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Either a b) -> f (a, b)
    forall a (f :: * -> *) b.
    (Monoid a, Selective f) =>
    f (Either a b) -> f (a, b)
    untilRight f (Either a b)
    x

    -- | A lifted version of lazy Boolean OR.
    (<||>) :: Selective f => f Bool -> f Bool -> f Bool
    f Bool
    a <||> :: forall (f :: * -> *). Selective f => f Bool -> f Bool -> f Bool
    <||> f Bool
    b = f Bool -> f Bool -> f Bool -> f Bool
    forall (f :: * -> *) a. Selective f => f Bool -> f a -> f a -> f a
    ifS f Bool
    a (Bool -> f Bool
    forall a. a -> f a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure Bool
    True) f Bool
    b

    -- | A lifted version of lazy Boolean AND.
    (<&&>) :: Selective f => f Bool -> f Bool -> f Bool
    f Bool
    a <&&> :: forall (f :: * -> *). Selective f => f Bool -> f Bool -> f Bool
    <&&> f Bool
    b = f Bool -> f Bool -> f Bool -> f Bool
    forall (f :: * -> *) a. Selective f => f Bool -> f a -> f a -> f a
    ifS f Bool
    a f Bool
    b (Bool -> f Bool
    forall a. a -> f a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure Bool
    False)

    -- | A lifted version of 'any'. Retains the short-circuiting behaviour.
    anyS :: Selective f => (a -> f Bool) -> [a] -> f Bool
    anyS :: forall (f :: * -> *) a.
    Selective f =>
    (a -> f Bool) -> [a] -> f Bool
    anyS a -> f Bool
    p = (a -> f Bool -> f Bool) -> f Bool -> [a] -> f Bool
    forall a b. (a -> b -> b) -> b -> [a] -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr (f Bool -> f Bool -> f Bool
    forall (f :: * -> *). Selective f => f Bool -> f Bool -> f Bool
    (<||>) (f Bool -> f Bool -> f Bool)
    -> (a -> f Bool) -> a -> f Bool -> f Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> f Bool
    p) (Bool -> f Bool
    forall a. a -> f a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure Bool
    False)

    -- | A lifted version of 'all'. Retains the short-circuiting behaviour.
    allS :: Selective f => (a -> f Bool) -> [a] -> f Bool
    allS :: forall (f :: * -> *) a.
    Selective f =>
    (a -> f Bool) -> [a] -> f Bool
    allS a -> f Bool
    p = (a -> f Bool -> f Bool) -> f Bool -> [a] -> f Bool
    forall a b. (a -> b -> b) -> b -> [a] -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr (f Bool -> f Bool -> f Bool
    forall (f :: * -> *). Selective f => f Bool -> f Bool -> f Bool
    (<&&>) (f Bool -> f Bool -> f Bool)
    -> (a -> f Bool) -> a -> f Bool -> f Bool
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> f Bool
    p) (Bool -> f Bool
    forall a. a -> f a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure Bool
    True)

    -- | Generalised folding with the short-circuiting behaviour.
    foldS :: (Selective f, Foldable t, Monoid a) => t (f (Either e a)) -> f (Either e a)
    foldS :: forall (f :: * -> *) (t :: * -> *) a e.
    (Selective f, Foldable t, Monoid a) =>
    t (f (Either e a)) -> f (Either e a)
    foldS = (f (Either e a) -> f (Either e a) -> f (Either e a))
    -> f (Either e a) -> t (f (Either e a)) -> f (Either e a)
    forall a b. (a -> b -> b) -> b -> t a -> b
    forall (t :: * -> *) a b.
    Foldable t =>
    (a -> b -> b) -> b -> t a -> b
    foldr f (Either e a) -> f (Either e a) -> f (Either e a)
    forall (f :: * -> *) a e.
    (Selective f, Semigroup a) =>
    f (Either e a) -> f (Either e a) -> f (Either e a)
    andAlso (Either e a -> f (Either e a)
    forall a. a -> f a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (a -> Either e a
    forall a b. b -> Either a b
    Right a
    forall a. Monoid a => a
    mempty))

    -- Instances

    -- | Any applicative functor can be given a 'Selective' instance by defining
    -- 'select' @=@ 'selectA'. This data type captures this pattern, so you can use
    -- it in combination with the @DerivingVia@ extension as follows:
    --
    -- @
    -- newtype Over m a = Over m
    --     deriving (Functor, Applicative, Selective) via SelectA (Const m)
    -- @
    --
    newtype SelectA f a = SelectA { forall (f :: * -> *) a. SelectA f a -> f a
    getSelectA :: f a }
        deriving ((forall a b. (a -> b) -> SelectA f a -> SelectA f b)
    -> (forall a b. a -> SelectA f b -> SelectA f a)
    -> Functor (SelectA f)
    forall a b. a -> SelectA f b -> SelectA f a
    forall a b. (a -> b) -> SelectA f a -> SelectA f b
    forall (f :: * -> *) a b.
    Functor f =>
    a -> SelectA f b -> SelectA f a
    forall (f :: * -> *) a b.
    Functor f =>
    (a -> b) -> SelectA f a -> SelectA f b
    forall (f :: * -> *).
    (forall a b. (a -> b) -> f a -> f b)
    -> (forall a b. a -> f b -> f a) -> Functor f
    $cfmap :: forall (f :: * -> *) a b.
    Functor f =>
    (a -> b) -> SelectA f a -> SelectA f b
    fmap :: forall a b. (a -> b) -> SelectA f a -> SelectA f b
    $c<$ :: forall (f :: * -> *) a b.
    Functor f =>
    a -> SelectA f b -> SelectA f a
    <$ :: forall a b. a -> SelectA f b -> SelectA f a
    Functor, Functor (SelectA f)
    Functor (SelectA f) =>
    (forall a. a -> SelectA f a)
    -> (forall a b. SelectA f (a -> b) -> SelectA f a -> SelectA f b)
    -> (forall a b c.
        (a -> b -> c) -> SelectA f a -> SelectA f b -> SelectA f c)
    -> (forall a b. SelectA f a -> SelectA f b -> SelectA f b)
    -> (forall a b. SelectA f a -> SelectA f b -> SelectA f a)
    -> Applicative (SelectA f)
    forall a. a -> SelectA f a
    forall a b. SelectA f a -> SelectA f b -> SelectA f a
    forall a b. SelectA f a -> SelectA f b -> SelectA f b
    forall a b. SelectA f (a -> b) -> SelectA f a -> SelectA f b
    forall a b c.
    (a -> b -> c) -> SelectA f a -> SelectA f b -> SelectA f c
    forall (f :: * -> *).
    Functor f =>
    (forall a. a -> f a)
    -> (forall a b. f (a -> b) -> f a -> f b)
    -> (forall a b c. (a -> b -> c) -> f a -> f b -> f c)
    -> (forall a b. f a -> f b -> f b)
    -> (forall a b. f a -> f b -> f a)
    -> Applicative f
    forall (f :: * -> *). Applicative f => Functor (SelectA f)
    forall (f :: * -> *) a. Applicative f => a -> SelectA f a
    forall (f :: * -> *) a b.
    Applicative f =>
    SelectA f a -> SelectA f b -> SelectA f a
    forall (f :: * -> *) a b.
    Applicative f =>
    SelectA f a -> SelectA f b -> SelectA f b
    forall (f :: * -> *) a b.
    Applicative f =>
    SelectA f (a -> b) -> SelectA f a -> SelectA f b
    forall (f :: * -> *) a b c.
    Applicative f =>
    (a -> b -> c) -> SelectA f a -> SelectA f b -> SelectA f c
    $cpure :: forall (f :: * -> *) a. Applicative f => a -> SelectA f a
    pure :: forall a. a -> SelectA f a
    $c<*> :: forall (f :: * -> *) a b.
    Applicative f =>
    SelectA f (a -> b) -> SelectA f a -> SelectA f b
    <*> :: forall a b. SelectA f (a -> b) -> SelectA f a -> SelectA f b
    $cliftA2 :: forall (f :: * -> *) a b c.
    Applicative f =>
    (a -> b -> c) -> SelectA f a -> SelectA f b -> SelectA f c
    liftA2 :: forall a b c.
    (a -> b -> c) -> SelectA f a -> SelectA f b -> SelectA f c
    $c*> :: forall (f :: * -> *) a b.
    Applicative f =>
    SelectA f a -> SelectA f b -> SelectA f b
    *> :: forall a b. SelectA f a -> SelectA f b -> SelectA f b
    $c<* :: forall (f :: * -> *) a b.
    Applicative f =>
    SelectA f a -> SelectA f b -> SelectA f a
    <* :: forall a b. SelectA f a -> SelectA f b -> SelectA f a
    Applicative)

    instance Applicative f => Selective (SelectA f) where
        select :: forall a b.
    SelectA f (Either a b) -> SelectA f (a -> b) -> SelectA f b
    select = SelectA f (Either a b) -> SelectA f (a -> b) -> SelectA f b
    forall (f :: * -> *) a b.
    Applicative f =>
    f (Either a b) -> f (a -> b) -> f b
    selectA

    -- Note: Validation e a ~ Lift (Under e) a
    instance Selective f => Selective (Lift f) where
        select :: forall a b. Lift f (Either a b) -> Lift f (a -> b) -> Lift f b
    select (Pure (Right b
    x)) Lift f (a -> b)
    _         = b -> Lift f b
    forall (f :: * -> *) a. a -> Lift f a
    Pure b
    x -- Lazy in the second argument
        select              Lift f (Either a b)
    x   (Pure  a -> b
    y) = (a -> b) -> (b -> b) -> Either a b -> b
    forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
    either a -> b
    y b -> b
    forall a. a -> a
    id (Either a b -> b) -> Lift f (Either a b) -> Lift f b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Lift f (Either a b)
    x
        select (Pure (Left  a
    x)) (Other f (a -> b)
    y) = f b -> Lift f b
    forall (f :: * -> *) a. f a -> Lift f a
    Other (f b -> Lift f b) -> f b -> Lift f b
    forall a b. (a -> b) -> a -> b
    $ ((a -> b) -> a -> b
    forall a b. (a -> b) -> a -> b
    $a
    x) ((a -> b) -> b) -> f (a -> b) -> f b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (a -> b)
    y
        select (Other       f (Either a b)
    x ) (Other f (a -> b)
    y) = f b -> Lift f b
    forall (f :: * -> *) a. f a -> Lift f a
    Other (f b -> Lift f b) -> f b -> Lift f b
    forall a b. (a -> b) -> a -> b
    $   f (Either a b)
    x  f (Either a b) -> f (a -> b) -> f b
    forall (f :: * -> *) a b.
    Selective f =>
    f (Either a b) -> f (a -> b) -> f b
    <*? f (a -> b)
    y

    -- | Any monad can be given a 'Selective' instance by defining
    -- 'select' @=@ 'selectM'. This data type captures this pattern, so you can use
    -- it in combination with the @DerivingVia@ extension as follows:
    --
    -- @
    -- newtype V1 a = V1 a
    --     deriving (Functor, Applicative, Selective, Monad) via SelectM Identity
    -- @
    --
    newtype SelectM f a = SelectM { forall (f :: * -> *) a. SelectM f a -> f a
    getSelectM :: f a }
        deriving ((forall a b. (a -> b) -> SelectM f a -> SelectM f b)
    -> (forall a b. a -> SelectM f b -> SelectM f a)
    -> Functor (SelectM f)
    forall a b. a -> SelectM f b -> SelectM f a
    forall a b. (a -> b) -> SelectM f a -> SelectM f b
    forall (f :: * -> *) a b.
    Functor f =>
    a -> SelectM f b -> SelectM f a
    forall (f :: * -> *) a b.
    Functor f =>
    (a -> b) -> SelectM f a -> SelectM f b
    forall (f :: * -> *).
    (forall a b. (a -> b) -> f a -> f b)
    -> (forall a b. a -> f b -> f a) -> Functor f
    $cfmap :: forall (f :: * -> *) a b.
    Functor f =>
    (a -> b) -> SelectM f a -> SelectM f b
    fmap :: forall a b. (a -> b) -> SelectM f a -> SelectM f b
    $c<$ :: forall (f :: * -> *) a b.
    Functor f =>
    a -> SelectM f b -> SelectM f a
    <$ :: forall a b. a -> SelectM f b -> SelectM f a
    Functor, Functor (SelectM f)
    Functor (SelectM f) =>
    (forall a. a -> SelectM f a)
    -> (forall a b. SelectM f (a -> b) -> SelectM f a -> SelectM f b)
    -> (forall a b c.
        (a -> b -> c) -> SelectM f a -> SelectM f b -> SelectM f c)
    -> (forall a b. SelectM f a -> SelectM f b -> SelectM f b)
    -> (forall a b. SelectM f a -> SelectM f b -> SelectM f a)
    -> Applicative (SelectM f)
    forall a. a -> SelectM f a
    forall a b. SelectM f a -> SelectM f b -> SelectM f a
    forall a b. SelectM f a -> SelectM f b -> SelectM f b
    forall a b. SelectM f (a -> b) -> SelectM f a -> SelectM f b
    forall a b c.
    (a -> b -> c) -> SelectM f a -> SelectM f b -> SelectM f c
    forall (f :: * -> *).
    Functor f =>
    (forall a. a -> f a)
    -> (forall a b. f (a -> b) -> f a -> f b)
    -> (forall a b c. (a -> b -> c) -> f a -> f b -> f c)
    -> (forall a b. f a -> f b -> f b)
    -> (forall a b. f a -> f b -> f a)
    -> Applicative f
    forall (f :: * -> *). Applicative f => Functor (SelectM f)
    forall (f :: * -> *) a. Applicative f => a -> SelectM f a
    forall (f :: * -> *) a b.
    Applicative f =>
    SelectM f a -> SelectM f b -> SelectM f a
    forall (f :: * -> *) a b.
    Applicative f =>
    SelectM f a -> SelectM f b -> SelectM f b
    forall (f :: * -> *) a b.
    Applicative f =>
    SelectM f (a -> b) -> SelectM f a -> SelectM f b
    forall (f :: * -> *) a b c.
    Applicative f =>
    (a -> b -> c) -> SelectM f a -> SelectM f b -> SelectM f c
    $cpure :: forall (f :: * -> *) a. Applicative f => a -> SelectM f a
    pure :: forall a. a -> SelectM f a
    $c<*> :: forall (f :: * -> *) a b.
    Applicative f =>
    SelectM f (a -> b) -> SelectM f a -> SelectM f b
    <*> :: forall a b. SelectM f (a -> b) -> SelectM f a -> SelectM f b
    $cliftA2 :: forall (f :: * -> *) a b c.
    Applicative f =>
    (a -> b -> c) -> SelectM f a -> SelectM f b -> SelectM f c
    liftA2 :: forall a b c.
    (a -> b -> c) -> SelectM f a -> SelectM f b -> SelectM f c
    $c*> :: forall (f :: * -> *) a b.
    Applicative f =>
    SelectM f a -> SelectM f b -> SelectM f b
    *> :: forall a b. SelectM f a -> SelectM f b -> SelectM f b
    $c<* :: forall (f :: * -> *) a b.
    Applicative f =>
    SelectM f a -> SelectM f b -> SelectM f a
    <* :: forall a b. SelectM f a -> SelectM f b -> SelectM f a
    Applicative, Applicative (SelectM f)
    Applicative (SelectM f) =>
    (forall a b. SelectM f a -> (a -> SelectM f b) -> SelectM f b)
    -> (forall a b. SelectM f a -> SelectM f b -> SelectM f b)
    -> (forall a. a -> SelectM f a)
    -> Monad (SelectM f)
    forall a. a -> SelectM f a
    forall a b. SelectM f a -> SelectM f b -> SelectM f b
    forall a b. SelectM f a -> (a -> SelectM f b) -> SelectM f b
    forall (f :: * -> *). Monad f => Applicative (SelectM f)
    forall (f :: * -> *) a. Monad f => a -> SelectM f a
    forall (f :: * -> *) a b.
    Monad f =>
    SelectM f a -> SelectM f b -> SelectM f b
    forall (f :: * -> *) a b.
    Monad f =>
    SelectM f a -> (a -> SelectM f b) -> SelectM f b
    forall (m :: * -> *).
    Applicative m =>
    (forall a b. m a -> (a -> m b) -> m b)
    -> (forall a b. m a -> m b -> m b)
    -> (forall a. a -> m a)
    -> Monad m
    $c>>= :: forall (f :: * -> *) a b.
    Monad f =>
    SelectM f a -> (a -> SelectM f b) -> SelectM f b
    >>= :: forall a b. SelectM f a -> (a -> SelectM f b) -> SelectM f b
    $c>> :: forall (f :: * -> *) a b.
    Monad f =>
    SelectM f a -> SelectM f b -> SelectM f b
    >> :: forall a b. SelectM f a -> SelectM f b -> SelectM f b
    $creturn :: forall (f :: * -> *) a. Monad f => a -> SelectM f a
    return :: forall a. a -> SelectM f a
    Monad)

    instance Monad f => Selective (SelectM f) where
        select :: forall a b.
    SelectM f (Either a b) -> SelectM f (a -> b) -> SelectM f b
    select = SelectM f (Either a b) -> SelectM f (a -> b) -> SelectM f b
    forall (f :: * -> *) a b.
    Monad f =>
    f (Either a b) -> f (a -> b) -> f b
    selectM

    -- | Static analysis of selective functors with over-approximation.
    newtype Over m a = Over { forall m a. Over m a -> m
    getOver :: m }
        deriving (Over m a -> Over m a -> Bool
    (Over m a -> Over m a -> Bool)
    -> (Over m a -> Over m a -> Bool) -> Eq (Over m a)
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    forall m a. Eq m => Over m a -> Over m a -> Bool
    $c== :: forall m a. Eq m => Over m a -> Over m a -> Bool
    == :: Over m a -> Over m a -> Bool
    $c/= :: forall m a. Eq m => Over m a -> Over m a -> Bool
    /= :: Over m a -> Over m a -> Bool
    Eq, (forall a b. (a -> b) -> Over m a -> Over m b)
    -> (forall a b. a -> Over m b -> Over m a) -> Functor (Over m)
    forall a b. a -> Over m b -> Over m a
    forall a b. (a -> b) -> Over m a -> Over m b
    forall m a b. a -> Over m b -> Over m a
    forall m a b. (a -> b) -> Over m a -> Over m b
    forall (f :: * -> *).
    (forall a b. (a -> b) -> f a -> f b)
    -> (forall a b. a -> f b -> f a) -> Functor f
    $cfmap :: forall m a b. (a -> b) -> Over m a -> Over m b
    fmap :: forall a b. (a -> b) -> Over m a -> Over m b
    $c<$ :: forall m a b. a -> Over m b -> Over m a
    <$ :: forall a b. a -> Over m b -> Over m a
    Functor, Eq (Over m a)
    Eq (Over m a) =>
    (Over m a -> Over m a -> Ordering)
    -> (Over m a -> Over m a -> Bool)
    -> (Over m a -> Over m a -> Bool)
    -> (Over m a -> Over m a -> Bool)
    -> (Over m a -> Over m a -> Bool)
    -> (Over m a -> Over m a -> Over m a)
    -> (Over m a -> Over m a -> Over m a)
    -> Ord (Over m a)
    Over m a -> Over m a -> Bool
    Over m a -> Over m a -> Ordering
    Over m a -> Over m a -> Over m a
    forall a.
    Eq a =>
    (a -> a -> Ordering)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> a)
    -> (a -> a -> a)
    -> Ord a
    forall m a. Ord m => Eq (Over m a)
    forall m a. Ord m => Over m a -> Over m a -> Bool
    forall m a. Ord m => Over m a -> Over m a -> Ordering
    forall m a. Ord m => Over m a -> Over m a -> Over m a
    $ccompare :: forall m a. Ord m => Over m a -> Over m a -> Ordering
    compare :: Over m a -> Over m a -> Ordering
    $c< :: forall m a. Ord m => Over m a -> Over m a -> Bool
    < :: Over m a -> Over m a -> Bool
    $c<= :: forall m a. Ord m => Over m a -> Over m a -> Bool
    <= :: Over m a -> Over m a -> Bool
    $c> :: forall m a. Ord m => Over m a -> Over m a -> Bool
    > :: Over m a -> Over m a -> Bool
    $c>= :: forall m a. Ord m => Over m a -> Over m a -> Bool
    >= :: Over m a -> Over m a -> Bool
    $cmax :: forall m a. Ord m => Over m a -> Over m a -> Over m a
    max :: Over m a -> Over m a -> Over m a
    $cmin :: forall m a. Ord m => Over m a -> Over m a -> Over m a
    min :: Over m a -> Over m a -> Over m a
    Ord, Int -> Over m a -> ShowS
    [Over m a] -> ShowS
    Over m a -> [Char]
    (Int -> Over m a -> ShowS)
    -> (Over m a -> [Char]) -> ([Over m a] -> ShowS) -> Show (Over m a)
    forall a.
    (Int -> a -> ShowS) -> (a -> [Char]) -> ([a] -> ShowS) -> Show a
    forall m a. Show m => Int -> Over m a -> ShowS
    forall m a. Show m => [Over m a] -> ShowS
    forall m a. Show m => Over m a -> [Char]
    $cshowsPrec :: forall m a. Show m => Int -> Over m a -> ShowS
    showsPrec :: Int -> Over m a -> ShowS
    $cshow :: forall m a. Show m => Over m a -> [Char]
    show :: Over m a -> [Char]
    $cshowList :: forall m a. Show m => [Over m a] -> ShowS
    showList :: [Over m a] -> ShowS
    Show)
        deriving Functor (Over m)
    Functor (Over m) =>
    (forall a. a -> Over m a)
    -> (forall a b. Over m (a -> b) -> Over m a -> Over m b)
    -> (forall a b c.
        (a -> b -> c) -> Over m a -> Over m b -> Over m c)
    -> (forall a b. Over m a -> Over m b -> Over m b)
    -> (forall a b. Over m a -> Over m b -> Over m a)
    -> Applicative (Over m)
    forall a. a -> Over m a
    forall m. Monoid m => Functor (Over m)
    forall m a. Monoid m => a -> Over m a
    forall m a b. Monoid m => Over m a -> Over m b -> Over m a
    forall m a b. Monoid m => Over m a -> Over m b -> Over m b
    forall m a b. Monoid m => Over m (a -> b) -> Over m a -> Over m b
    forall m a b c.
    Monoid m =>
    (a -> b -> c) -> Over m a -> Over m b -> Over m c
    forall a b. Over m a -> Over m b -> Over m a
    forall a b. Over m a -> Over m b -> Over m b
    forall a b. Over m (a -> b) -> Over m a -> Over m b
    forall a b c. (a -> b -> c) -> Over m a -> Over m b -> Over m c
    forall (f :: * -> *).
    Functor f =>
    (forall a. a -> f a)
    -> (forall a b. f (a -> b) -> f a -> f b)
    -> (forall a b c. (a -> b -> c) -> f a -> f b -> f c)
    -> (forall a b. f a -> f b -> f b)
    -> (forall a b. f a -> f b -> f a)
    -> Applicative f
    $cpure :: forall m a. Monoid m => a -> Over m a
    pure :: forall a. a -> Over m a
    $c<*> :: forall m a b. Monoid m => Over m (a -> b) -> Over m a -> Over m b
    <*> :: forall a b. Over m (a -> b) -> Over m a -> Over m b
    $cliftA2 :: forall m a b c.
    Monoid m =>
    (a -> b -> c) -> Over m a -> Over m b -> Over m c
    liftA2 :: forall a b c. (a -> b -> c) -> Over m a -> Over m b -> Over m c
    $c*> :: forall m a b. Monoid m => Over m a -> Over m b -> Over m b
    *> :: forall a b. Over m a -> Over m b -> Over m b
    $c<* :: forall m a b. Monoid m => Over m a -> Over m b -> Over m a
    <* :: forall a b. Over m a -> Over m b -> Over m a
    Applicative via (Const m)

    -- select = selectA
    instance Monoid m => Selective (Over m) where
        select :: forall a b. Over m (Either a b) -> Over m (a -> b) -> Over m b
    select (Over m
    x) (Over m
    y) = m -> Over m b
    forall m a. m -> Over m a
    Over (m -> m -> m
    forall a. Monoid a => a -> a -> a
    mappend m
    x m
    y)

    -- | Static analysis of selective functors with under-approximation.
    newtype Under m a = Under { forall m a. Under m a -> m
    getUnder :: m }
        deriving (Under m a -> Under m a -> Bool
    (Under m a -> Under m a -> Bool)
    -> (Under m a -> Under m a -> Bool) -> Eq (Under m a)
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    forall m a. Eq m => Under m a -> Under m a -> Bool
    $c== :: forall m a. Eq m => Under m a -> Under m a -> Bool
    == :: Under m a -> Under m a -> Bool
    $c/= :: forall m a. Eq m => Under m a -> Under m a -> Bool
    /= :: Under m a -> Under m a -> Bool
    Eq, (forall a b. (a -> b) -> Under m a -> Under m b)
    -> (forall a b. a -> Under m b -> Under m a) -> Functor (Under m)
    forall a b. a -> Under m b -> Under m a
    forall a b. (a -> b) -> Under m a -> Under m b
    forall m a b. a -> Under m b -> Under m a
    forall m a b. (a -> b) -> Under m a -> Under m b
    forall (f :: * -> *).
    (forall a b. (a -> b) -> f a -> f b)
    -> (forall a b. a -> f b -> f a) -> Functor f
    $cfmap :: forall m a b. (a -> b) -> Under m a -> Under m b
    fmap :: forall a b. (a -> b) -> Under m a -> Under m b
    $c<$ :: forall m a b. a -> Under m b -> Under m a
    <$ :: forall a b. a -> Under m b -> Under m a
    Functor, Eq (Under m a)
    Eq (Under m a) =>
    (Under m a -> Under m a -> Ordering)
    -> (Under m a -> Under m a -> Bool)
    -> (Under m a -> Under m a -> Bool)
    -> (Under m a -> Under m a -> Bool)
    -> (Under m a -> Under m a -> Bool)
    -> (Under m a -> Under m a -> Under m a)
    -> (Under m a -> Under m a -> Under m a)
    -> Ord (Under m a)
    Under m a -> Under m a -> Bool
    Under m a -> Under m a -> Ordering
    Under m a -> Under m a -> Under m a
    forall a.
    Eq a =>
    (a -> a -> Ordering)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> a)
    -> (a -> a -> a)
    -> Ord a
    forall m a. Ord m => Eq (Under m a)
    forall m a. Ord m => Under m a -> Under m a -> Bool
    forall m a. Ord m => Under m a -> Under m a -> Ordering
    forall m a. Ord m => Under m a -> Under m a -> Under m a
    $ccompare :: forall m a. Ord m => Under m a -> Under m a -> Ordering
    compare :: Under m a -> Under m a -> Ordering
    $c< :: forall m a. Ord m => Under m a -> Under m a -> Bool
    < :: Under m a -> Under m a -> Bool
    $c<= :: forall m a. Ord m => Under m a -> Under m a -> Bool
    <= :: Under m a -> Under m a -> Bool
    $c> :: forall m a. Ord m => Under m a -> Under m a -> Bool
    > :: Under m a -> Under m a -> Bool
    $c>= :: forall m a. Ord m => Under m a -> Under m a -> Bool
    >= :: Under m a -> Under m a -> Bool
    $cmax :: forall m a. Ord m => Under m a -> Under m a -> Under m a
    max :: Under m a -> Under m a -> Under m a
    $cmin :: forall m a. Ord m => Under m a -> Under m a -> Under m a
    min :: Under m a -> Under m a -> Under m a
    Ord, Int -> Under m a -> ShowS
    [Under m a] -> ShowS
    Under m a -> [Char]
    (Int -> Under m a -> ShowS)
    -> (Under m a -> [Char])
    -> ([Under m a] -> ShowS)
    -> Show (Under m a)
    forall a.
    (Int -> a -> ShowS) -> (a -> [Char]) -> ([a] -> ShowS) -> Show a
    forall m a. Show m => Int -> Under m a -> ShowS
    forall m a. Show m => [Under m a] -> ShowS
    forall m a. Show m => Under m a -> [Char]
    $cshowsPrec :: forall m a. Show m => Int -> Under m a -> ShowS
    showsPrec :: Int -> Under m a -> ShowS
    $cshow :: forall m a. Show m => Under m a -> [Char]
    show :: Under m a -> [Char]
    $cshowList :: forall m a. Show m => [Under m a] -> ShowS
    showList :: [Under m a] -> ShowS
    Show, (forall m. Monoid m => Under m m -> m)
    -> (forall m a. Monoid m => (a -> m) -> Under m a -> m)
    -> (forall m a. Monoid m => (a -> m) -> Under m a -> m)
    -> (forall a b. (a -> b -> b) -> b -> Under m a -> b)
    -> (forall a b. (a -> b -> b) -> b -> Under m a -> b)
    -> (forall b a. (b -> a -> b) -> b -> Under m a -> b)
    -> (forall b a. (b -> a -> b) -> b -> Under m a -> b)
    -> (forall a. (a -> a -> a) -> Under m a -> a)
    -> (forall a. (a -> a -> a) -> Under m a -> a)
    -> (forall a. Under m a -> [a])
    -> (forall a. Under m a -> Bool)
    -> (forall a. Under m a -> Int)
    -> (forall a. Eq a => a -> Under m a -> Bool)
    -> (forall a. Ord a => Under m a -> a)
    -> (forall a. Ord a => Under m a -> a)
    -> (forall a. Num a => Under m a -> a)
    -> (forall a. Num a => Under m a -> a)
    -> Foldable (Under m)
    forall a. Eq a => a -> Under m a -> Bool
    forall a. Num a => Under m a -> a
    forall a. Ord a => Under m a -> a
    forall m. Monoid m => Under m m -> m
    forall a. Under m a -> Bool
    forall a. Under m a -> Int
    forall a. Under m a -> [a]
    forall a. (a -> a -> a) -> Under m a -> a
    forall m a. Eq a => a -> Under m a -> Bool
    forall m a. Num a => Under m a -> a
    forall m a. Ord a => Under m a -> a
    forall m a. Monoid m => (a -> m) -> Under m a -> m
    forall m m. Monoid m => Under m m -> m
    forall m a. Under m a -> Bool
    forall m a. Under m a -> Int
    forall m a. Under m a -> [a]
    forall b a. (b -> a -> b) -> b -> Under m a -> b
    forall a b. (a -> b -> b) -> b -> Under m a -> b
    forall m a. (a -> a -> a) -> Under m a -> a
    forall m m a. Monoid m => (a -> m) -> Under m a -> m
    forall m b a. (b -> a -> b) -> b -> Under m a -> b
    forall m a b. (a -> b -> b) -> b -> Under m a -> b
    forall (t :: * -> *).
    (forall m. Monoid m => t m -> m)
    -> (forall m a. Monoid m => (a -> m) -> t a -> m)
    -> (forall m a. Monoid m => (a -> m) -> t a -> m)
    -> (forall a b. (a -> b -> b) -> b -> t a -> b)
    -> (forall a b. (a -> b -> b) -> b -> t a -> b)
    -> (forall b a. (b -> a -> b) -> b -> t a -> b)
    -> (forall b a. (b -> a -> b) -> b -> t a -> b)
    -> (forall a. (a -> a -> a) -> t a -> a)
    -> (forall a. (a -> a -> a) -> t a -> a)
    -> (forall a. t a -> [a])
    -> (forall a. t a -> Bool)
    -> (forall a. t a -> Int)
    -> (forall a. Eq a => a -> t a -> Bool)
    -> (forall a. Ord a => t a -> a)
    -> (forall a. Ord a => t a -> a)
    -> (forall a. Num a => t a -> a)
    -> (forall a. Num a => t a -> a)
    -> Foldable t
    $cfold :: forall m m. Monoid m => Under m m -> m
    fold :: forall m. Monoid m => Under m m -> m
    $cfoldMap :: forall m m a. Monoid m => (a -> m) -> Under m a -> m
    foldMap :: forall m a. Monoid m => (a -> m) -> Under m a -> m
    $cfoldMap' :: forall m m a. Monoid m => (a -> m) -> Under m a -> m
    foldMap' :: forall m a. Monoid m => (a -> m) -> Under m a -> m
    $cfoldr :: forall m a b. (a -> b -> b) -> b -> Under m a -> b
    foldr :: forall a b. (a -> b -> b) -> b -> Under m a -> b
    $cfoldr' :: forall m a b. (a -> b -> b) -> b -> Under m a -> b
    foldr' :: forall a b. (a -> b -> b) -> b -> Under m a -> b
    $cfoldl :: forall m b a. (b -> a -> b) -> b -> Under m a -> b
    foldl :: forall b a. (b -> a -> b) -> b -> Under m a -> b
    $cfoldl' :: forall m b a. (b -> a -> b) -> b -> Under m a -> b
    foldl' :: forall b a. (b -> a -> b) -> b -> Under m a -> b
    $cfoldr1 :: forall m a. (a -> a -> a) -> Under m a -> a
    foldr1 :: forall a. (a -> a -> a) -> Under m a -> a
    $cfoldl1 :: forall m a. (a -> a -> a) -> Under m a -> a
    foldl1 :: forall a. (a -> a -> a) -> Under m a -> a
    $ctoList :: forall m a. Under m a -> [a]
    toList :: forall a. Under m a -> [a]
    $cnull :: forall m a. Under m a -> Bool
    null :: forall a. Under m a -> Bool
    $clength :: forall m a. Under m a -> Int
    length :: forall a. Under m a -> Int
    $celem :: forall m a. Eq a => a -> Under m a -> Bool
    elem :: forall a. Eq a => a -> Under m a -> Bool
    $cmaximum :: forall m a. Ord a => Under m a -> a
    maximum :: forall a. Ord a => Under m a -> a
    $cminimum :: forall m a. Ord a => Under m a -> a
    minimum :: forall a. Ord a => Under m a -> a
    $csum :: forall m a. Num a => Under m a -> a
    sum :: forall a. Num a => Under m a -> a
    $cproduct :: forall m a. Num a => Under m a -> a
    product :: forall a. Num a => Under m a -> a
    Foldable, Functor (Under m)
    Foldable (Under m)
    (Functor (Under m), Foldable (Under m)) =>
    (forall (f :: * -> *) a b.
     Applicative f =>
     (a -> f b) -> Under m a -> f (Under m b))
    -> (forall (f :: * -> *) a.
        Applicative f =>
        Under m (f a) -> f (Under m a))
    -> (forall (m :: * -> *) a b.
        Monad m =>
        (a -> m b) -> Under m a -> m (Under m b))
    -> (forall (m :: * -> *) a.
        Monad m =>
        Under m (m a) -> m (Under m a))
    -> Traversable (Under m)
    forall m. Functor (Under m)
    forall m. Foldable (Under m)
    forall m (m :: * -> *) a. Monad m => Under m (m a) -> m (Under m a)
    forall m (f :: * -> *) a.
    Applicative f =>
    Under m (f a) -> f (Under m a)
    forall m (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> Under m a -> m (Under m b)
    forall m (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Under m a -> f (Under m b)
    forall (t :: * -> *).
    (Functor t, Foldable t) =>
    (forall (f :: * -> *) a b.
     Applicative f =>
     (a -> f b) -> t a -> f (t b))
    -> (forall (f :: * -> *) a. Applicative f => t (f a) -> f (t a))
    -> (forall (m :: * -> *) a b.
        Monad m =>
        (a -> m b) -> t a -> m (t b))
    -> (forall (m :: * -> *) a. Monad m => t (m a) -> m (t a))
    -> Traversable t
    forall (m :: * -> *) a. Monad m => Under m (m a) -> m (Under m a)
    forall (f :: * -> *) a.
    Applicative f =>
    Under m (f a) -> f (Under m a)
    forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> Under m a -> m (Under m b)
    forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Under m a -> f (Under m b)
    $ctraverse :: forall m (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Under m a -> f (Under m b)
    traverse :: forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Under m a -> f (Under m b)
    $csequenceA :: forall m (f :: * -> *) a.
    Applicative f =>
    Under m (f a) -> f (Under m a)
    sequenceA :: forall (f :: * -> *) a.
    Applicative f =>
    Under m (f a) -> f (Under m a)
    $cmapM :: forall m (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> Under m a -> m (Under m b)
    mapM :: forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> Under m a -> m (Under m b)
    $csequence :: forall m (m :: * -> *) a. Monad m => Under m (m a) -> m (Under m a)
    sequence :: forall (m :: * -> *) a. Monad m => Under m (m a) -> m (Under m a)
    Traversable)
        deriving Functor (Under m)
    Functor (Under m) =>
    (forall a. a -> Under m a)
    -> (forall a b. Under m (a -> b) -> Under m a -> Under m b)
    -> (forall a b c.
        (a -> b -> c) -> Under m a -> Under m b -> Under m c)
    -> (forall a b. Under m a -> Under m b -> Under m b)
    -> (forall a b. Under m a -> Under m b -> Under m a)
    -> Applicative (Under m)
    forall a. a -> Under m a
    forall m. Monoid m => Functor (Under m)
    forall m a. Monoid m => a -> Under m a
    forall m a b. Monoid m => Under m a -> Under m b -> Under m a
    forall m a b. Monoid m => Under m a -> Under m b -> Under m b
    forall m a b.
    Monoid m =>
    Under m (a -> b) -> Under m a -> Under m b
    forall m a b c.
    Monoid m =>
    (a -> b -> c) -> Under m a -> Under m b -> Under m c
    forall a b. Under m a -> Under m b -> Under m a
    forall a b. Under m a -> Under m b -> Under m b
    forall a b. Under m (a -> b) -> Under m a -> Under m b
    forall a b c. (a -> b -> c) -> Under m a -> Under m b -> Under m c
    forall (f :: * -> *).
    Functor f =>
    (forall a. a -> f a)
    -> (forall a b. f (a -> b) -> f a -> f b)
    -> (forall a b c. (a -> b -> c) -> f a -> f b -> f c)
    -> (forall a b. f a -> f b -> f b)
    -> (forall a b. f a -> f b -> f a)
    -> Applicative f
    $cpure :: forall m a. Monoid m => a -> Under m a
    pure :: forall a. a -> Under m a
    $c<*> :: forall m a b.
    Monoid m =>
    Under m (a -> b) -> Under m a -> Under m b
    <*> :: forall a b. Under m (a -> b) -> Under m a -> Under m b
    $cliftA2 :: forall m a b c.
    Monoid m =>
    (a -> b -> c) -> Under m a -> Under m b -> Under m c
    liftA2 :: forall a b c. (a -> b -> c) -> Under m a -> Under m b -> Under m c
    $c*> :: forall m a b. Monoid m => Under m a -> Under m b -> Under m b
    *> :: forall a b. Under m a -> Under m b -> Under m b
    $c<* :: forall m a b. Monoid m => Under m a -> Under m b -> Under m a
    <* :: forall a b. Under m a -> Under m b -> Under m a
    Applicative via (Const m)

    -- select = selectT
    instance Monoid m => Selective (Under m) where
        select :: forall a b. Under m (Either a b) -> Under m (a -> b) -> Under m b
    select (Under m
    m) Under m (a -> b)
    _ = m -> Under m b
    forall m a. m -> Under m a
    Under m
    m

    -- The 'Selective' 'ZipList' instance corresponds to the SIMT execution model.
    -- Quoting https://en.wikipedia.org/wiki/Single_instruction,_multiple_threads:
    --
    -- "...to handle an IF-ELSE block where various threads of a processor execute
    -- different paths, all threads must actually process both paths (as all threads
    -- of a processor always execute in lock-step), but masking is used to disable
    -- and enable the various threads as appropriate..."
    instance Selective ZipList where select :: forall a b. ZipList (Either a b) -> ZipList (a -> b) -> ZipList b
    select = ZipList (Either a b) -> ZipList (a -> b) -> ZipList b
    forall (f :: * -> *) a b.
    Applicative f =>
    f (Either a b) -> f (a -> b) -> f b
    selectA

    -- | Selective instance for the standard applicative functor Validation. This is
    -- a good example of a non-trivial selective functor which is not a monad.
    data Validation e a = Failure e | Success a deriving (Validation e a -> Validation e a -> Bool
    (Validation e a -> Validation e a -> Bool)
    -> (Validation e a -> Validation e a -> Bool)
    -> Eq (Validation e a)
    forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
    forall e a.
    (Eq e, Eq a) =>
    Validation e a -> Validation e a -> Bool
    $c== :: forall e a.
    (Eq e, Eq a) =>
    Validation e a -> Validation e a -> Bool
    == :: Validation e a -> Validation e a -> Bool
    $c/= :: forall e a.
    (Eq e, Eq a) =>
    Validation e a -> Validation e a -> Bool
    /= :: Validation e a -> Validation e a -> Bool
    Eq, (forall a b. (a -> b) -> Validation e a -> Validation e b)
    -> (forall a b. a -> Validation e b -> Validation e a)
    -> Functor (Validation e)
    forall a b. a -> Validation e b -> Validation e a
    forall a b. (a -> b) -> Validation e a -> Validation e b
    forall e a b. a -> Validation e b -> Validation e a
    forall e a b. (a -> b) -> Validation e a -> Validation e b
    forall (f :: * -> *).
    (forall a b. (a -> b) -> f a -> f b)
    -> (forall a b. a -> f b -> f a) -> Functor f
    $cfmap :: forall e a b. (a -> b) -> Validation e a -> Validation e b
    fmap :: forall a b. (a -> b) -> Validation e a -> Validation e b
    $c<$ :: forall e a b. a -> Validation e b -> Validation e a
    <$ :: forall a b. a -> Validation e b -> Validation e a
    Functor, Eq (Validation e a)
    Eq (Validation e a) =>
    (Validation e a -> Validation e a -> Ordering)
    -> (Validation e a -> Validation e a -> Bool)
    -> (Validation e a -> Validation e a -> Bool)
    -> (Validation e a -> Validation e a -> Bool)
    -> (Validation e a -> Validation e a -> Bool)
    -> (Validation e a -> Validation e a -> Validation e a)
    -> (Validation e a -> Validation e a -> Validation e a)
    -> Ord (Validation e a)
    Validation e a -> Validation e a -> Bool
    Validation e a -> Validation e a -> Ordering
    Validation e a -> Validation e a -> Validation e a
    forall a.
    Eq a =>
    (a -> a -> Ordering)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> Bool)
    -> (a -> a -> a)
    -> (a -> a -> a)
    -> Ord a
    forall e a. (Ord e, Ord a) => Eq (Validation e a)
    forall e a.
    (Ord e, Ord a) =>
    Validation e a -> Validation e a -> Bool
    forall e a.
    (Ord e, Ord a) =>
    Validation e a -> Validation e a -> Ordering
    forall e a.
    (Ord e, Ord a) =>
    Validation e a -> Validation e a -> Validation e a
    $ccompare :: forall e a.
    (Ord e, Ord a) =>
    Validation e a -> Validation e a -> Ordering
    compare :: Validation e a -> Validation e a -> Ordering
    $c< :: forall e a.
    (Ord e, Ord a) =>
    Validation e a -> Validation e a -> Bool
    < :: Validation e a -> Validation e a -> Bool
    $c<= :: forall e a.
    (Ord e, Ord a) =>
    Validation e a -> Validation e a -> Bool
    <= :: Validation e a -> Validation e a -> Bool
    $c> :: forall e a.
    (Ord e, Ord a) =>
    Validation e a -> Validation e a -> Bool
    > :: Validation e a -> Validation e a -> Bool
    $c>= :: forall e a.
    (Ord e, Ord a) =>
    Validation e a -> Validation e a -> Bool
    >= :: Validation e a -> Validation e a -> Bool
    $cmax :: forall e a.
    (Ord e, Ord a) =>
    Validation e a -> Validation e a -> Validation e a
    max :: Validation e a -> Validation e a -> Validation e a
    $cmin :: forall e a.
    (Ord e, Ord a) =>
    Validation e a -> Validation e a -> Validation e a
    min :: Validation e a -> Validation e a -> Validation e a
    Ord, Int -> Validation e a -> ShowS
    [Validation e a] -> ShowS
    Validation e a -> [Char]
    (Int -> Validation e a -> ShowS)
    -> (Validation e a -> [Char])
    -> ([Validation e a] -> ShowS)
    -> Show (Validation e a)
    forall a.
    (Int -> a -> ShowS) -> (a -> [Char]) -> ([a] -> ShowS) -> Show a
    forall e a. (Show e, Show a) => Int -> Validation e a -> ShowS
    forall e a. (Show e, Show a) => [Validation e a] -> ShowS
    forall e a. (Show e, Show a) => Validation e a -> [Char]
    $cshowsPrec :: forall e a. (Show e, Show a) => Int -> Validation e a -> ShowS
    showsPrec :: Int -> Validation e a -> ShowS
    $cshow :: forall e a. (Show e, Show a) => Validation e a -> [Char]
    show :: Validation e a -> [Char]
    $cshowList :: forall e a. (Show e, Show a) => [Validation e a] -> ShowS
    showList :: [Validation e a] -> ShowS
    Show)

    instance Semigroup e => Applicative (Validation e) where
        pure :: forall a. a -> Validation e a
    pure = a -> Validation e a
    forall e a. a -> Validation e a
    Success
        Failure e
    e1 <*> :: forall a b.
    Validation e (a -> b) -> Validation e a -> Validation e b
    <*> Failure e
    e2 = e -> Validation e b
    forall e a. e -> Validation e a
    Failure (e
    e1 e -> e -> e
    forall a. Semigroup a => a -> a -> a
    <> e
    e2)
        Failure e
    e1 <*> Success a
    _  = e -> Validation e b
    forall e a. e -> Validation e a
    Failure e
    e1
        Success a -> b
    _  <*> Failure e
    e2 = e -> Validation e b
    forall e a. e -> Validation e a
    Failure e
    e2
        Success a -> b
    f  <*> Success a
    a  = b -> Validation e b
    forall e a. a -> Validation e a
    Success (a -> b
    f a
    a)

    instance Semigroup e => Selective (Validation e) where
        select :: forall a b.
    Validation e (Either a b)
    -> Validation e (a -> b) -> Validation e b
    select (Success (Left  a
    a)) Validation e (a -> b)
    f = ((a -> b) -> a -> b
    forall a b. (a -> b) -> a -> b
    $a
    a) ((a -> b) -> b) -> Validation e (a -> b) -> Validation e b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> Validation e (a -> b)
    f
        select (Success (Right b
    b)) Validation e (a -> b)
    _ = b -> Validation e b
    forall e a. a -> Validation e a
    Success b
    b
        select (Failure e
    e        ) Validation e (a -> b)
    _ = e -> Validation e b
    forall e a. e -> Validation e a
    Failure e
    e

    instance (Selective f, Selective g) => Selective (Product f g) where
        select :: forall a b.
    Product f g (Either a b) -> Product f g (a -> b) -> Product f g b
    select (Pair f (Either a b)
    fx g (Either a b)
    gx) (Pair f (a -> b)
    fy g (a -> b)
    gy) = f b -> g b -> Product f g b
    forall {k} (f :: k -> *) (g :: k -> *) (a :: k).
    f a -> g a -> Product f g a
    Pair (f (Either a b) -> f (a -> b) -> f b
    forall a b. f (Either a b) -> f (a -> b) -> f b
    forall (f :: * -> *) a b.
    Selective f =>
    f (Either a b) -> f (a -> b) -> f b
    select f (Either a b)
    fx f (a -> b)
    fy) (g (Either a b) -> g (a -> b) -> g b
    forall a b. g (Either a b) -> g (a -> b) -> g b
    forall (f :: * -> *) a b.
    Selective f =>
    f (Either a b) -> f (a -> b) -> f b
    select g (Either a b)
    gx g (a -> b)
    gy)

    instance Selective f => Selective (IdentityT f) where
        select :: forall a b.
    IdentityT f (Either a b) -> IdentityT f (a -> b) -> IdentityT f b
    select (IdentityT f (Either a b)
    x) (IdentityT f (a -> b)
    y) = f b -> IdentityT f b
    forall {k} (f :: k -> *) (a :: k). f a -> IdentityT f a
    IdentityT (f (Either a b) -> f (a -> b) -> f b
    forall a b. f (Either a b) -> f (a -> b) -> f b
    forall (f :: * -> *) a b.
    Selective f =>
    f (Either a b) -> f (a -> b) -> f b
    select f (Either a b)
    x f (a -> b)
    y)

    instance Selective f => Selective (ReaderT env f) where
        select :: forall a b.
    ReaderT env f (Either a b)
    -> ReaderT env f (a -> b) -> ReaderT env f b
    select (ReaderT env -> f (Either a b)
    x) (ReaderT env -> f (a -> b)
    y) = (env -> f b) -> ReaderT env f b
    forall r (m :: * -> *) a. (r -> m a) -> ReaderT r m a
    ReaderT ((env -> f b) -> ReaderT env f b)
    -> (env -> f b) -> ReaderT env f b
    forall a b. (a -> b) -> a -> b
    $ \env
    env -> f (Either a b) -> f (a -> b) -> f b
    forall a b. f (Either a b) -> f (a -> b) -> f b
    forall (f :: * -> *) a b.
    Selective f =>
    f (Either a b) -> f (a -> b) -> f b
    select (env -> f (Either a b)
    x env
    env) (env -> f (a -> b)
    y env
    env)

    distributeEither :: (Either a b, w) -> Either (a, w) (b, w)
    distributeEither :: forall a b w. (Either a b, w) -> Either (a, w) (b, w)
    distributeEither (Left  a
    a, w
    w) = (a, w) -> Either (a, w) (b, w)
    forall a b. a -> Either a b
    Left  (a
    a, w
    w)
    distributeEither (Right b
    b, w
    w) = (b, w) -> Either (a, w) (b, w)
    forall a b. b -> Either a b
    Right (b
    b, w
    w)

    distributeFunction :: Monoid w => (a -> b, w) -> (a, w) -> (b, w)
    distributeFunction :: forall w a b. Monoid w => (a -> b, w) -> (a, w) -> (b, w)
    distributeFunction (a -> b
    f, w
    wf) (a
    x, w
    wx) = (a -> b
    f a
    x, w -> w -> w
    forall a. Monoid a => a -> a -> a
    mappend w
    wx w
    wf)

    instance (Monoid w, Selective f) => Selective (WriterT w f) where
        select :: forall a b.
    WriterT w f (Either a b) -> WriterT w f (a -> b) -> WriterT w f b
    select (WriterT f (Either a b, w)
    x) (WriterT f (a -> b, w)
    f) =
            f (b, w) -> WriterT w f b
    forall w (m :: * -> *) a. m (a, w) -> WriterT w m a
    WriterT (f (b, w) -> WriterT w f b) -> f (b, w) -> WriterT w f b
    forall a b. (a -> b) -> a -> b
    $ f (Either (a, w) (b, w)) -> f ((a, w) -> (b, w)) -> f (b, w)
    forall a b. f (Either a b) -> f (a -> b) -> f b
    forall (f :: * -> *) a b.
    Selective f =>
    f (Either a b) -> f (a -> b) -> f b
    select ((Either a b, w) -> Either (a, w) (b, w)
    forall a b w. (Either a b, w) -> Either (a, w) (b, w)
    distributeEither ((Either a b, w) -> Either (a, w) (b, w))
    -> f (Either a b, w) -> f (Either (a, w) (b, w))
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Either a b, w)
    x) ((a -> b, w) -> (a, w) -> (b, w)
    forall w a b. Monoid w => (a -> b, w) -> (a, w) -> (b, w)
    distributeFunction ((a -> b, w) -> (a, w) -> (b, w))
    -> f (a -> b, w) -> f ((a, w) -> (b, w))
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (a -> b, w)
    f)

    instance (Monoid w, Selective f) => Selective (S.WriterT w f) where
        select :: forall a b.
    WriterT w f (Either a b) -> WriterT w f (a -> b) -> WriterT w f b
    select (S.WriterT f (Either a b, w)
    x) (S.WriterT f (a -> b, w)
    f) =
            f (b, w) -> WriterT w f b
    forall w (m :: * -> *) a. m (a, w) -> WriterT w m a
    S.WriterT (f (b, w) -> WriterT w f b) -> f (b, w) -> WriterT w f b
    forall a b. (a -> b) -> a -> b
    $ f (Either (a, w) (b, w)) -> f ((a, w) -> (b, w)) -> f (b, w)
    forall a b. f (Either a b) -> f (a -> b) -> f b
    forall (f :: * -> *) a b.
    Selective f =>
    f (Either a b) -> f (a -> b) -> f b
    select ((Either a b, w) -> Either (a, w) (b, w)
    forall a b w. (Either a b, w) -> Either (a, w) (b, w)
    distributeEither ((Either a b, w) -> Either (a, w) (b, w))
    -> f (Either a b, w) -> f (Either (a, w) (b, w))
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Either a b, w)
    x) ((a -> b, w) -> (a, w) -> (b, w)
    forall w a b. Monoid w => (a -> b, w) -> (a, w) -> (b, w)
    distributeFunction ((a -> b, w) -> (a, w) -> (b, w))
    -> f (a -> b, w) -> f ((a, w) -> (b, w))
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (a -> b, w)
    f)

    -- TODO: Is this a useful instance? Note that composition of 'Alternative'
    -- requires @f@ to be 'Alternative', and @g@ to be 'Applicative', which is
    -- opposite to what we have here:
    --
    -- instance (Alternative f, Applicative g) => Alternative (Compose f g) ...
    --
    instance (Applicative f, Selective g) => Selective (Compose f g) where
        select :: forall a b.
    Compose f g (Either a b) -> Compose f g (a -> b) -> Compose f g b
    select (Compose f (g (Either a b))
    x) (Compose f (g (a -> b))
    y) = f (g b) -> Compose f g b
    forall {k} {k1} (f :: k -> *) (g :: k1 -> k) (a :: k1).
    f (g a) -> Compose f g a
    Compose (g (Either a b) -> g (a -> b) -> g b
    forall a b. g (Either a b) -> g (a -> b) -> g b
    forall (f :: * -> *) a b.
    Selective f =>
    f (Either a b) -> f (a -> b) -> f b
    select (g (Either a b) -> g (a -> b) -> g b)
    -> f (g (Either a b)) -> f (g (a -> b) -> g b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (g (Either a b))
    x f (g (a -> b) -> g b) -> f (g (a -> b)) -> f (g b)
    forall a b. f (a -> b) -> f a -> f b
    forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
    <*> f (g (a -> b))
    y)

    {- Here is why composing selective functors is tricky.

    Consider @Compose Maybe IO@. The only sensible implementation is:

    > select :: Maybe (IO (Either a b)) -> Maybe (IO (a -> b)) -> Maybe (IO b)
    > select Nothing  _        = Nothing
    > select (Just x) (Just y) = Just (select x y)
    > select (Just x) Nothing  = Nothing -- Can't use Just: we don't have @a -> b@!

    In other words, we have to be 'Applicative' on the outside functor 'Maybe',
    because there is no way to peek inside 'IO', which forces us to statically
    choose between 'Just', which doesn't work since we have no function @a -> b@,
    and 'Nothing' which corresponds to the behaviour of 'selectA'.

    -}

    -- Monad instances

    -- As a quick experiment, try: ifS (pure True) (print 1) (print 2)
    instance Selective IO where select :: forall a b. IO (Either a b) -> IO (a -> b) -> IO b
    select = IO (Either a b) -> IO (a -> b) -> IO b
    forall (f :: * -> *) a b.
    Monad f =>
    f (Either a b) -> f (a -> b) -> f b
    selectM

    -- And... we need to write a lot more instances
    instance             Selective []         where select :: forall a b. [Either a b] -> [a -> b] -> [b]
    select = [Either a b] -> [a -> b] -> [b]
    forall (f :: * -> *) a b.
    Monad f =>
    f (Either a b) -> f (a -> b) -> f b
    selectM
    instance Monoid a => Selective ((,) a)    where select :: forall a b. (a, Either a b) -> (a, a -> b) -> (a, b)
    select = (a, Either a b) -> (a, a -> b) -> (a, b)
    forall (f :: * -> *) a b.
    Monad f =>
    f (Either a b) -> f (a -> b) -> f b
    selectM
    instance             Selective ((->) a)   where select :: forall a b. (a -> Either a b) -> (a -> (a -> b)) -> a -> b
    select = (a -> Either a b) -> (a -> a -> b) -> a -> b
    forall (f :: * -> *) a b.
    Monad f =>
    f (Either a b) -> f (a -> b) -> f b
    selectM
    instance             Selective (Either e) where select :: forall a b.
    Either e (Either a b) -> Either e (a -> b) -> Either e b
    select = Either e (Either a b) -> Either e (a -> b) -> Either e b
    forall (f :: * -> *) a b.
    Monad f =>
    f (Either a b) -> f (a -> b) -> f b
    selectM
    instance             Selective Identity   where select :: forall a b.
    Identity (Either a b) -> Identity (a -> b) -> Identity b
    select = Identity (Either a b) -> Identity (a -> b) -> Identity b
    forall (f :: * -> *) a b.
    Monad f =>
    f (Either a b) -> f (a -> b) -> f b
    selectM
    instance             Selective Maybe      where select :: forall a b. Maybe (Either a b) -> Maybe (a -> b) -> Maybe b
    select = Maybe (Either a b) -> Maybe (a -> b) -> Maybe b
    forall (f :: * -> *) a b.
    Monad f =>
    f (Either a b) -> f (a -> b) -> f b
    selectM
    instance             Selective NonEmpty   where select :: forall a b.
    NonEmpty (Either a b) -> NonEmpty (a -> b) -> NonEmpty b
    select = NonEmpty (Either a b) -> NonEmpty (a -> b) -> NonEmpty b
    forall (f :: * -> *) a b.
    Monad f =>
    f (Either a b) -> f (a -> b) -> f b
    selectM
    instance             Selective Proxy      where select :: forall a b. Proxy (Either a b) -> Proxy (a -> b) -> Proxy b
    select = Proxy (Either a b) -> Proxy (a -> b) -> Proxy b
    forall (f :: * -> *) a b.
    Monad f =>
    f (Either a b) -> f (a -> b) -> f b
    selectM
    instance             Selective (ST s)     where select :: forall a b. ST s (Either a b) -> ST s (a -> b) -> ST s b
    select = ST s (Either a b) -> ST s (a -> b) -> ST s b
    forall (f :: * -> *) a b.
    Monad f =>
    f (Either a b) -> f (a -> b) -> f b
    selectM
    instance             Selective STM        where select :: forall a b. STM (Either a b) -> STM (a -> b) -> STM b
    select = STM (Either a b) -> STM (a -> b) -> STM b
    forall (f :: * -> *) a b.
    Monad f =>
    f (Either a b) -> f (a -> b) -> f b
    selectM

    instance                        Selective (ContT      r m) where select :: forall a b.
    ContT r m (Either a b) -> ContT r m (a -> b) -> ContT r m b
    select = ContT r m (Either a b) -> ContT r m (a -> b) -> ContT r m b
    forall (f :: * -> *) a b.
    Monad f =>
    f (Either a b) -> f (a -> b) -> f b
    selectM
    instance            Monad m  => Selective (MaybeT       m) where select :: forall a b.
    MaybeT m (Either a b) -> MaybeT m (a -> b) -> MaybeT m b
    select = MaybeT m (Either a b) -> MaybeT m (a -> b) -> MaybeT m b
    forall (f :: * -> *) a b.
    Monad f =>
    f (Either a b) -> f (a -> b) -> f b
    selectM
    instance (Monoid w, Monad m) => Selective (RWST   r w s m) where select :: forall a b.
    RWST r w s m (Either a b)
    -> RWST r w s m (a -> b) -> RWST r w s m b
    select = RWST r w s m (Either a b)
    -> RWST r w s m (a -> b) -> RWST r w s m b
    forall (f :: * -> *) a b.
    Monad f =>
    f (Either a b) -> f (a -> b) -> f b
    selectM
    instance (Monoid w, Monad m) => Selective (S.RWST r w s m) where select :: forall a b.
    RWST r w s m (Either a b)
    -> RWST r w s m (a -> b) -> RWST r w s m b
    select = RWST r w s m (Either a b)
    -> RWST r w s m (a -> b) -> RWST r w s m b
    forall (f :: * -> *) a b.
    Monad f =>
    f (Either a b) -> f (a -> b) -> f b
    selectM
    instance            Monad m  => Selective (StateT     s m) where select :: forall a b.
    StateT s m (Either a b) -> StateT s m (a -> b) -> StateT s m b
    select = StateT s m (Either a b) -> StateT s m (a -> b) -> StateT s m b
    forall (f :: * -> *) a b.
    Monad f =>
    f (Either a b) -> f (a -> b) -> f b
    selectM
    instance            Monad m  => Selective (S.StateT   s m) where select :: forall a b.
    StateT s m (Either a b) -> StateT s m (a -> b) -> StateT s m b
    select = StateT s m (Either a b) -> StateT s m (a -> b) -> StateT s m b
    forall (f :: * -> *) a b.
    Monad f =>
    f (Either a b) -> f (a -> b) -> f b
    selectM

    ------------------------------------ Arrows ------------------------------------
    -- See the following standard definitions in "Control.Arrow".
    -- newtype ArrowMonad a o = ArrowMonad (a () o)
    -- instance Arrow a => Functor (ArrowMonad a)
    -- instance Arrow a => Applicative (ArrowMonad a)

    instance ArrowChoice a => Selective (ArrowMonad a) where
        select :: forall a b.
    ArrowMonad a (Either a b)
    -> ArrowMonad a (a -> b) -> ArrowMonad a b
    select (ArrowMonad a () (Either a b)
    x) ArrowMonad a (a -> b)
    y = a () b -> ArrowMonad a b
    forall (a :: * -> * -> *) b. a () b -> ArrowMonad a b
    ArrowMonad (a () b -> ArrowMonad a b) -> a () b -> ArrowMonad a b
    forall a b. (a -> b) -> a -> b
    $ a () (Either a b)
    x a () (Either a b) -> a (Either a b) b -> a () b
    forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
    Category cat =>
    cat a b -> cat b c -> cat a c
    >>> (ArrowMonad a (a -> b) -> a a b
    forall (a :: * -> * -> *) i o.
    Arrow a =>
    ArrowMonad a (i -> o) -> a i o
    toArrow ArrowMonad a (a -> b)
    y a a b -> a b b -> a (Either a b) b
    forall b d c. a b d -> a c d -> a (Either b c) d
    forall (a :: * -> * -> *) b d c.
    ArrowChoice a =>
    a b d -> a c d -> a (Either b c) d
    ||| a b b
    forall (a :: * -> * -> *) b. Arrow a => a b b
    returnA)

    toArrow :: Arrow a => ArrowMonad a (i -> o) -> a i o
    toArrow :: forall (a :: * -> * -> *) i o.
    Arrow a =>
    ArrowMonad a (i -> o) -> a i o
    toArrow (ArrowMonad a () (i -> o)
    f) = (i -> ((), i)) -> a i ((), i)
    forall b c. (b -> c) -> a b c
    forall (a :: * -> * -> *) b c. Arrow a => (b -> c) -> a b c
    arr ((),) a i ((), i) -> a ((), i) o -> a i o
    forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
    Category cat =>
    cat a b -> cat b c -> cat a c
    >>> a () (i -> o) -> a ((), i) (i -> o, i)
    forall b c d. a b c -> a (b, d) (c, d)
    forall (a :: * -> * -> *) b c d.
    Arrow a =>
    a b c -> a (b, d) (c, d)
    first a () (i -> o)
    f a ((), i) (i -> o, i) -> a (i -> o, i) o -> a ((), i) o
    forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
    Category cat =>
    cat a b -> cat b c -> cat a c
    >>> ((i -> o, i) -> o) -> a (i -> o, i) o
    forall b c. (b -> c) -> a b c
    forall (a :: * -> * -> *) b c. Arrow a => (b -> c) -> a b c
    arr (((i -> o) -> i -> o) -> (i -> o, i) -> o
    forall a b c. (a -> b -> c) -> (a, b) -> c
    uncurry (i -> o) -> i -> o
    forall a b. (a -> b) -> a -> b
    ($))

    ------------------------------ ComposeTraversable ------------------------------
    -- | Composition of a selective functor @f@ and an applicative traversable
    -- functor @g@.
    newtype ComposeTraversable f g a = ComposeTraversable (f (g a))
        deriving ((forall a b.
     (a -> b) -> ComposeTraversable f g a -> ComposeTraversable f g b)
    -> (forall a b.
        a -> ComposeTraversable f g b -> ComposeTraversable f g a)
    -> Functor (ComposeTraversable f g)
    forall a b.
    a -> ComposeTraversable f g b -> ComposeTraversable f g a
    forall a b.
    (a -> b) -> ComposeTraversable f g a -> ComposeTraversable f g b
    forall (f :: * -> *).
    (forall a b. (a -> b) -> f a -> f b)
    -> (forall a b. a -> f b -> f a) -> Functor f
    forall (f :: * -> *) (g :: * -> *) a b.
    (Functor f, Functor g) =>
    a -> ComposeTraversable f g b -> ComposeTraversable f g a
    forall (f :: * -> *) (g :: * -> *) a b.
    (Functor f, Functor g) =>
    (a -> b) -> ComposeTraversable f g a -> ComposeTraversable f g b
    $cfmap :: forall (f :: * -> *) (g :: * -> *) a b.
    (Functor f, Functor g) =>
    (a -> b) -> ComposeTraversable f g a -> ComposeTraversable f g b
    fmap :: forall a b.
    (a -> b) -> ComposeTraversable f g a -> ComposeTraversable f g b
    $c<$ :: forall (f :: * -> *) (g :: * -> *) a b.
    (Functor f, Functor g) =>
    a -> ComposeTraversable f g b -> ComposeTraversable f g a
    <$ :: forall a b.
    a -> ComposeTraversable f g b -> ComposeTraversable f g a
    Functor, Functor (ComposeTraversable f g)
    Functor (ComposeTraversable f g) =>
    (forall a. a -> ComposeTraversable f g a)
    -> (forall a b.
        ComposeTraversable f g (a -> b)
        -> ComposeTraversable f g a -> ComposeTraversable f g b)
    -> (forall a b c.
        (a -> b -> c)
        -> ComposeTraversable f g a
        -> ComposeTraversable f g b
        -> ComposeTraversable f g c)
    -> (forall a b.
        ComposeTraversable f g a
        -> ComposeTraversable f g b -> ComposeTraversable f g b)
    -> (forall a b.
        ComposeTraversable f g a
        -> ComposeTraversable f g b -> ComposeTraversable f g a)
    -> Applicative (ComposeTraversable f g)
    forall a. a -> ComposeTraversable f g a
    forall a b.
    ComposeTraversable f g a
    -> ComposeTraversable f g b -> ComposeTraversable f g a
    forall a b.
    ComposeTraversable f g a
    -> ComposeTraversable f g b -> ComposeTraversable f g b
    forall a b.
    ComposeTraversable f g (a -> b)
    -> ComposeTraversable f g a -> ComposeTraversable f g b
    forall a b c.
    (a -> b -> c)
    -> ComposeTraversable f g a
    -> ComposeTraversable f g b
    -> ComposeTraversable f g c
    forall (f :: * -> *).
    Functor f =>
    (forall a. a -> f a)
    -> (forall a b. f (a -> b) -> f a -> f b)
    -> (forall a b c. (a -> b -> c) -> f a -> f b -> f c)
    -> (forall a b. f a -> f b -> f b)
    -> (forall a b. f a -> f b -> f a)
    -> Applicative f
    forall (f :: * -> *) (g :: * -> *).
    (Applicative f, Applicative g) =>
    Functor (ComposeTraversable f g)
    forall (f :: * -> *) (g :: * -> *) a.
    (Applicative f, Applicative g) =>
    a -> ComposeTraversable f g a
    forall (f :: * -> *) (g :: * -> *) a b.
    (Applicative f, Applicative g) =>
    ComposeTraversable f g a
    -> ComposeTraversable f g b -> ComposeTraversable f g a
    forall (f :: * -> *) (g :: * -> *) a b.
    (Applicative f, Applicative g) =>
    ComposeTraversable f g a
    -> ComposeTraversable f g b -> ComposeTraversable f g b
    forall (f :: * -> *) (g :: * -> *) a b.
    (Applicative f, Applicative g) =>
    ComposeTraversable f g (a -> b)
    -> ComposeTraversable f g a -> ComposeTraversable f g b
    forall (f :: * -> *) (g :: * -> *) a b c.
    (Applicative f, Applicative g) =>
    (a -> b -> c)
    -> ComposeTraversable f g a
    -> ComposeTraversable f g b
    -> ComposeTraversable f g c
    $cpure :: forall (f :: * -> *) (g :: * -> *) a.
    (Applicative f, Applicative g) =>
    a -> ComposeTraversable f g a
    pure :: forall a. a -> ComposeTraversable f g a
    $c<*> :: forall (f :: * -> *) (g :: * -> *) a b.
    (Applicative f, Applicative g) =>
    ComposeTraversable f g (a -> b)
    -> ComposeTraversable f g a -> ComposeTraversable f g b
    <*> :: forall a b.
    ComposeTraversable f g (a -> b)
    -> ComposeTraversable f g a -> ComposeTraversable f g b
    $cliftA2 :: forall (f :: * -> *) (g :: * -> *) a b c.
    (Applicative f, Applicative g) =>
    (a -> b -> c)
    -> ComposeTraversable f g a
    -> ComposeTraversable f g b
    -> ComposeTraversable f g c
    liftA2 :: forall a b c.
    (a -> b -> c)
    -> ComposeTraversable f g a
    -> ComposeTraversable f g b
    -> ComposeTraversable f g c
    $c*> :: forall (f :: * -> *) (g :: * -> *) a b.
    (Applicative f, Applicative g) =>
    ComposeTraversable f g a
    -> ComposeTraversable f g b -> ComposeTraversable f g b
    *> :: forall a b.
    ComposeTraversable f g a
    -> ComposeTraversable f g b -> ComposeTraversable f g b
    $c<* :: forall (f :: * -> *) (g :: * -> *) a b.
    (Applicative f, Applicative g) =>
    ComposeTraversable f g a
    -> ComposeTraversable f g b -> ComposeTraversable f g a
    <* :: forall a b.
    ComposeTraversable f g a
    -> ComposeTraversable f g b -> ComposeTraversable f g a
    Applicative) via Compose f g

    instance (Selective f, Applicative g, Traversable g) => Selective (ComposeTraversable f g) where
        select :: forall a b.
    ComposeTraversable f g (Either a b)
    -> ComposeTraversable f g (a -> b) -> ComposeTraversable f g b
    select (ComposeTraversable f (g (Either a b))
    x) (ComposeTraversable f (g (a -> b))
    f) = f (g b) -> ComposeTraversable f g b
    forall (f :: * -> *) (g :: * -> *) a.
    f (g a) -> ComposeTraversable f g a
    ComposeTraversable (f (g b) -> ComposeTraversable f g b)
    -> f (g b) -> ComposeTraversable f g b
    forall a b. (a -> b) -> a -> b
    $
            f (Either a (g b)) -> f (a -> g b) -> f (g b)
    forall a b. f (Either a b) -> f (a -> b) -> f b
    forall (f :: * -> *) a b.
    Selective f =>
    f (Either a b) -> f (a -> b) -> f b
    select (g (Either a b) -> Either a (g b)
    forall (g :: * -> *) a b.
    Traversable g =>
    g (Either a b) -> Either a (g b)
    prepare (g (Either a b) -> Either a (g b))
    -> f (g (Either a b)) -> f (Either a (g b))
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (g (Either a b))
    x) (g (a -> b) -> a -> g b
    forall (g :: * -> *) a b. Traversable g => g (a -> b) -> a -> g b
    combine (g (a -> b) -> a -> g b) -> f (g (a -> b)) -> f (a -> g b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (g (a -> b))
    f)
          where
            prepare :: Traversable g => g (Either a b) -> Either a (g b)
            prepare :: forall (g :: * -> *) a b.
    Traversable g =>
    g (Either a b) -> Either a (g b)
    prepare = g (Either a b) -> Either a (g b)
    forall (t :: * -> *) (f :: * -> *) a.
    (Traversable t, Applicative f) =>
    t (f a) -> f (t a)
    forall (f :: * -> *) a. Applicative f => g (f a) -> f (g a)
    sequenceA

            combine :: Traversable g => g (a -> b) -> a -> g b
            combine :: forall (g :: * -> *) a b. Traversable g => g (a -> b) -> a -> g b
    combine = g (a -> b) -> a -> g b
    forall (t :: * -> *) (f :: * -> *) a.
    (Traversable t, Applicative f) =>
    t (f a) -> f (t a)
    forall (f :: * -> *) a. Applicative f => g (f a) -> f (g a)
    sequenceA

    --------------------------------- ComposeEither --------------------------------
    -- | Composition of a selective functor @f@ with the 'Either' monad.
    newtype ComposeEither f e a = ComposeEither (f (Either e a))
        deriving (forall a b.
     (a -> b) -> ComposeEither f e a -> ComposeEither f e b)
    -> (forall a b. a -> ComposeEither f e b -> ComposeEither f e a)
    -> Functor (ComposeEither f e)
    forall a b. a -> ComposeEither f e b -> ComposeEither f e a
    forall a b. (a -> b) -> ComposeEither f e a -> ComposeEither f e b
    forall (f :: * -> *).
    (forall a b. (a -> b) -> f a -> f b)
    -> (forall a b. a -> f b -> f a) -> Functor f
    forall (f :: * -> *) e a b.
    Functor f =>
    a -> ComposeEither f e b -> ComposeEither f e a
    forall (f :: * -> *) e a b.
    Functor f =>
    (a -> b) -> ComposeEither f e a -> ComposeEither f e b
    $cfmap :: forall (f :: * -> *) e a b.
    Functor f =>
    (a -> b) -> ComposeEither f e a -> ComposeEither f e b
    fmap :: forall a b. (a -> b) -> ComposeEither f e a -> ComposeEither f e b
    $c<$ :: forall (f :: * -> *) e a b.
    Functor f =>
    a -> ComposeEither f e b -> ComposeEither f e a
    <$ :: forall a b. a -> ComposeEither f e b -> ComposeEither f e a
    Functor via Compose f (Either e)
        deriving Applicative (ComposeEither f e)
    Applicative (ComposeEither f e) =>
    (forall a b.
     ComposeEither f e (Either a b)
     -> ComposeEither f e (a -> b) -> ComposeEither f e b)
    -> Selective (ComposeEither f e)
    forall a b.
    ComposeEither f e (Either a b)
    -> ComposeEither f e (a -> b) -> ComposeEither f e b
    forall (f :: * -> *).
    Applicative f =>
    (forall a b. f (Either a b) -> f (a -> b) -> f b) -> Selective f
    forall (f :: * -> *) e.
    Selective f =>
    Applicative (ComposeEither f e)
    forall (f :: * -> *) e a b.
    Selective f =>
    ComposeEither f e (Either a b)
    -> ComposeEither f e (a -> b) -> ComposeEither f e b
    $cselect :: forall (f :: * -> *) e a b.
    Selective f =>
    ComposeEither f e (Either a b)
    -> ComposeEither f e (a -> b) -> ComposeEither f e b
    select :: forall a b.
    ComposeEither f e (Either a b)
    -> ComposeEither f e (a -> b) -> ComposeEither f e b
    Selective via ComposeTraversable f (Either e)

    instance Selective f => Applicative (ComposeEither f e) where
        pure :: forall a. a -> ComposeEither f e a
    pure = f (Either e a) -> ComposeEither f e a
    forall (f :: * -> *) e a. f (Either e a) -> ComposeEither f e a
    ComposeEither (f (Either e a) -> ComposeEither f e a)
    -> (a -> f (Either e a)) -> a -> ComposeEither f e a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . Either e a -> f (Either e a)
    forall a. a -> f a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (Either e a -> f (Either e a))
    -> (a -> Either e a) -> a -> f (Either e a)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> Either e a
    forall a b. b -> Either a b
    Right

        ComposeEither f (Either e (a -> b))
    f <*> :: forall a b.
    ComposeEither f e (a -> b)
    -> ComposeEither f e a -> ComposeEither f e b
    <*> ComposeEither f (Either e a)
    a = f (Either e b) -> ComposeEither f e b
    forall (f :: * -> *) e a. f (Either e a) -> ComposeEither f e a
    ComposeEither (f (Either e b) -> ComposeEither f e b)
    -> f (Either e b) -> ComposeEither f e b
    forall a b. (a -> b) -> a -> b
    $
            f (Either (a -> b) (Either e b))
    -> f ((a -> b) -> Either e b) -> f (Either e b)
    forall a b. f (Either a b) -> f (a -> b) -> f b
    forall (f :: * -> *) a b.
    Selective f =>
    f (Either a b) -> f (a -> b) -> f b
    select (Either e (a -> b) -> Either (a -> b) (Either e b)
    forall e a b. Either e (a -> b) -> Either (a -> b) (Either e b)
    prepare (Either e (a -> b) -> Either (a -> b) (Either e b))
    -> f (Either e (a -> b)) -> f (Either (a -> b) (Either e b))
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Either e (a -> b))
    f) (Either e a -> (a -> b) -> Either e b
    forall e a b. Either e a -> (a -> b) -> Either e b
    combine (Either e a -> (a -> b) -> Either e b)
    -> f (Either e a) -> f ((a -> b) -> Either e b)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f (Either e a)
    a)
          where
            prepare :: Either e (a -> b) -> Either (a -> b) (Either e b)
            prepare :: forall e a b. Either e (a -> b) -> Either (a -> b) (Either e b)
    prepare = (e -> Either (a -> b) (Either e b))
    -> ((a -> b) -> Either (a -> b) (Either e b))
    -> Either e (a -> b)
    -> Either (a -> b) (Either e b)
    forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
    either (Either e b -> Either (a -> b) (Either e b)
    forall a b. b -> Either a b
    Right (Either e b -> Either (a -> b) (Either e b))
    -> (e -> Either e b) -> e -> Either (a -> b) (Either e b)
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . e -> Either e b
    forall a b. a -> Either a b
    Left) (a -> b) -> Either (a -> b) (Either e b)
    forall a b. a -> Either a b
    Left

            combine :: Either e a -> (a -> b) -> Either e b
            combine :: forall e a b. Either e a -> (a -> b) -> Either e b
    combine = ((a -> b) -> Either e a -> Either e b)
    -> Either e a -> (a -> b) -> Either e b
    forall a b c. (a -> b -> c) -> b -> a -> c
    flip (a -> b) -> Either e a -> Either e b
    forall a b. (a -> b) -> Either e a -> Either e b
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    fmap

    ---------------------------------- Alternative ---------------------------------
    instance (Selective f, Monoid e) => Alternative (ComposeEither f e) where
        empty :: forall a. ComposeEither f e a
    empty                               = f (Either e a) -> ComposeEither f e a
    forall (f :: * -> *) e a. f (Either e a) -> ComposeEither f e a
    ComposeEither (Either e a -> f (Either e a)
    forall a. a -> f a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure (Either e a -> f (Either e a)) -> Either e a -> f (Either e a)
    forall a b. (a -> b) -> a -> b
    $ e -> Either e a
    forall a b. a -> Either a b
    Left e
    forall a. Monoid a => a
    mempty)
        ComposeEither f (Either e a)
    x <|> :: forall a.
    ComposeEither f e a -> ComposeEither f e a -> ComposeEither f e a
    <|> ComposeEither f (Either e a)
    y = f (Either e a) -> ComposeEither f e a
    forall (f :: * -> *) e a. f (Either e a) -> ComposeEither f e a
    ComposeEither (f (Either e a)
    x f (Either e a) -> f (Either e a) -> f (Either e a)
    forall (f :: * -> *) e a.
    (Selective f, Semigroup e) =>
    f (Either e a) -> f (Either e a) -> f (Either e a)
    `orElse` f (Either e a)
    y)

    {- One could also try implementing 'select' via 'Alternative' as follows:

    selectAlt :: Alternative f => f (Either a b) -> f (a -> b) -> f b
    selectAlt x y = failIfLeft x <|> selectA x y
      where
        failIfLeft :: Alternative f => f (Either a b) -> f b
        failIfLeft = undefined

    This has two issues:

    1) A generic 'failIfLeft' if not possible, although many actual instances should
       be able to implement it.

    2) More importantly, this requires duplication of work: if we failed because we
       happened to parse a 'Left' value in the first parser, then we need to rerun
       it, obtain a 'Left' once again, and then execute the second parser. Again, a
       specific instance may be able to cache the result and reuse it without
       duplicating any work, but this does not seem to be possible to achieve
       generically for any Alternative.

    -}