{-# LANGUAGE CPP, LambdaCase, TupleSections, DeriveTraversable #-}
{-# LANGUAGE GeneralizedNewtypeDeriving, DerivingVia #-}
{-# OPTIONS_GHC -fno-warn-unused-imports #-}
-----------------------------------------------------------------------------
-- |
-- Module     : Control.Selective
-- Copyright  : (c) Andrey Mokhov 2018-2023
-- 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://www.staff.ncl.ac.uk/andrey.mokhov/selective-functors.pdf.
--
-----------------------------------------------------------------------------
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
(<*?) = 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 = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a b. a -> Either a b
Left) f (Either a b)
x forall (f :: * -> *) a b.
Selective f =>
f (Either a b) -> f (a -> b) -> f b
<*? forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall a b. b -> Either a b
Right) f (a -> c)
l 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 -> forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
either a -> b
f forall a. a -> a
id Either a b
e) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f (Either a b)
x 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 forall (t :: * -> *) (f :: * -> *) a.
(Traversable t, Applicative f) =>
t (f a) -> f (t a)
sequenceA f (Either a b)
x of
    Left  a
a  -> (forall a b. (a -> b) -> a -> b
$a
a) 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 = forall (f :: * -> *) a b.
Selective f =>
f (Either a b) -> f (a -> b) -> f b
select (forall a b. a -> Either a b
Left forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f (a -> b)
f) (forall a b. a -> (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 forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \case Left  a
a -> (forall a b. (a -> b) -> a -> b
$a
a) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f (a -> b)
y -- execute y
                          Right b
b -> 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 = forall (f :: * -> *) a b c.
Selective f =>
f (Either a b) -> f (a -> c) -> f (b -> c) -> f c
branch (forall a. a -> a -> Bool -> a
bool (forall a b. b -> Either a b
Right ()) (forall a b. a -> Either a b
Left ()) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f Bool
x) (forall a b. a -> b -> a
const forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f a
t) (forall a b. a -> b -> a
const 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 = forall (f :: * -> *) a b.
Selective f =>
f (Either a b) -> f (a -> b) -> f b
select (forall {a} {b}. Eq a => a -> Either a b -> Either () (Either a b)
match a
x forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f (Either a b)
fa) (forall a b. a -> b -> a
const forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. b -> Either a b
Right 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) = forall a b. b -> Either a b
Right (forall a b. b -> Either a b
Right b
y)
    match a
x (Left  a
y) = if a
x forall a. Eq a => a -> a -> Bool
== a
y then forall a b. a -> Either a b
Left () else forall a b. b -> Either a b
Right (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 = forall a. [a] -> (a -> Bool) -> Cases a
Cases [forall a. Bounded a => a
minBound..forall a. Bounded a => a
maxBound] (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 = forall a. [a] -> (a -> Bool) -> Cases a
Cases [a]
as (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 = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (\a
c -> 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)) (forall a b. a -> Either a b
Left 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 forall a b. b -> Either a b
Right forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> a -> m b
f a
x else forall (f :: * -> *) a. Applicative f => a -> f a
pure (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 = forall {a} {b}. Either a b -> b
fromRight forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall a (f :: * -> *) b.
(Eq a, Selective f) =>
Cases a -> f a -> (a -> f b) -> f (Either a b)
matchS 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
_ = 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 = forall (f :: * -> *) a b.
Selective f =>
f (Either a b) -> f (a -> b) -> f b
select (forall a. a -> a -> Bool -> a
bool (forall a b. b -> Either a b
Right ()) (forall a b. a -> Either a b
Left ()) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f Bool
x) (forall a b. a -> b -> a
const 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
x f (Maybe a)
mx = forall (f :: * -> *) a b.
Selective f =>
f (Either a b) -> f (a -> b) -> f b
select (forall b a. b -> (a -> b) -> Maybe a -> b
maybe (forall a b. a -> Either a b
Left ()) forall a b. b -> Either a b
Right forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f (Maybe a)
mx) (forall a b. a -> b -> a
const forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f 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 = forall (f :: * -> *) a b.
Selective f =>
f (Either a b) -> f (a -> b) -> f b
select (forall e a. Either e a -> Either e (Either e a)
prepare forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f (Either e a)
x) (forall e a. Semigroup e => Either e a -> e -> Either e a
combine 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 = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap 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 = forall a b. a -> Either a b
Left (e
ex forall a. Semigroup a => a -> a -> a
<> e
ey)
    combine (Right a
a) e
_  = 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 = forall a b. Either a b -> Either b a
swapEither forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> forall (f :: * -> *) e a.
(Selective f, Semigroup e) =>
f (Either e a) -> f (Either e a) -> f (Either e a)
orElse (forall a b. Either a b -> Either b a
swapEither forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f (Either e a)
x) (forall a b. Either a b -> Either b a
swapEither 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 = forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
either forall a b. b -> Either a b
Right 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 = forall (f :: * -> *). Selective f => f Bool -> f () -> f ()
whenS f Bool
act (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 = 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 = forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap (forall a. Monoid a => a
mempty,) 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 -> (forall a. Monoid a => a -> a -> a
mappend a
a a
as, b
b)) forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f 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 = forall (f :: * -> *) a. Selective f => f Bool -> f a -> f a -> f a
ifS f Bool
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 = forall (f :: * -> *) a. Selective f => f Bool -> f a -> f a -> f a
ifS f Bool
a f Bool
b (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 = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (forall (f :: * -> *). Selective f => f Bool -> f Bool -> f Bool
(<||>) forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> f Bool
p) (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 = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (forall (f :: * -> *). Selective f => f Bool -> f Bool -> f Bool
(<&&>) forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> f Bool
p) (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 = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr forall (f :: * -> *) a e.
(Selective f, Semigroup a) =>
f (Either e a) -> f (Either e a) -> f (Either e a)
andAlso (forall (f :: * -> *) a. Applicative f => a -> f a
pure (forall a b. b -> Either a b
Right 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 -> 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
<$ :: forall a b. a -> SelectA f b -> SelectA f a
$c<$ :: forall (f :: * -> *) a b.
Functor f =>
a -> SelectA f b -> SelectA f a
fmap :: forall a b. (a -> b) -> SelectA f a -> SelectA f b
$cfmap :: forall (f :: * -> *) a b.
Functor f =>
(a -> b) -> SelectA f a -> SelectA f b
Functor, 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
<* :: forall a b. SelectA f a -> SelectA f b -> SelectA f a
$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 b
$c*> :: forall (f :: * -> *) a b.
Applicative f =>
SelectA f a -> SelectA f b -> SelectA f b
liftA2 :: forall a b c.
(a -> b -> c) -> SelectA f a -> SelectA f b -> SelectA f c
$cliftA2 :: forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> SelectA f a -> SelectA f b -> SelectA f c
<*> :: forall a b. SelectA f (a -> b) -> SelectA f a -> SelectA f b
$c<*> :: forall (f :: * -> *) a b.
Applicative f =>
SelectA f (a -> b) -> SelectA f a -> SelectA f b
pure :: forall a. a -> SelectA f a
$cpure :: forall (f :: * -> *) a. Applicative f => a -> 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 = 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)
_         = 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) = forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
either a -> b
y forall a. a -> a
id 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) = forall (f :: * -> *) a. f a -> Lift f a
Other forall a b. (a -> b) -> a -> b
$ (forall a b. (a -> b) -> a -> b
$a
x) 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) = forall (f :: * -> *) a. f a -> Lift f a
Other forall a b. (a -> b) -> a -> b
$   f (Either a b)
x  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 -> 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
<$ :: forall a b. a -> SelectM f b -> SelectM f a
$c<$ :: forall (f :: * -> *) a b.
Functor f =>
a -> SelectM f b -> SelectM f a
fmap :: forall a b. (a -> b) -> SelectM f a -> SelectM f b
$cfmap :: forall (f :: * -> *) a b.
Functor f =>
(a -> b) -> SelectM f a -> SelectM f b
Functor, 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
<* :: forall a b. SelectM f a -> SelectM f b -> SelectM f a
$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 b
$c*> :: forall (f :: * -> *) a b.
Applicative f =>
SelectM f a -> SelectM f b -> SelectM f b
liftA2 :: forall a b c.
(a -> b -> c) -> SelectM f a -> SelectM f b -> SelectM f c
$cliftA2 :: forall (f :: * -> *) a b c.
Applicative f =>
(a -> b -> c) -> SelectM f a -> SelectM f b -> SelectM f c
<*> :: forall a b. SelectM f (a -> b) -> SelectM f a -> SelectM f b
$c<*> :: forall (f :: * -> *) a b.
Applicative f =>
SelectM f (a -> b) -> SelectM f a -> SelectM f b
pure :: forall a. a -> SelectM f a
$cpure :: forall (f :: * -> *) a. Applicative f => a -> SelectM f a
Applicative, 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
return :: forall a. a -> SelectM f a
$creturn :: forall (f :: * -> *) a. Monad f => a -> SelectM f a
>> :: forall a b. SelectM f 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 -> (a -> SelectM f b) -> SelectM f b
$c>>= :: forall (f :: * -> *) a b.
Monad f =>
SelectM f a -> (a -> SelectM f b) -> SelectM f b
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 = 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
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
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
$c== :: forall m a. Eq m => Over m a -> Over m a -> Bool
Eq, 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
<$ :: forall a b. a -> Over m b -> Over m a
$c<$ :: forall m a b. a -> Over m b -> Over m a
fmap :: forall a b. (a -> b) -> Over m a -> Over m b
$cfmap :: forall m a b. (a -> b) -> Over m a -> Over m b
Functor, 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
min :: Over m a -> Over m a -> Over m a
$cmin :: forall m a. Ord m => Over m a -> Over m a -> Over m a
max :: Over m a -> Over m a -> Over m a
$cmax :: forall m a. Ord m => Over m a -> Over m a -> Over m a
>= :: 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
$c< :: forall m a. Ord m => Over m a -> Over m a -> Bool
compare :: Over m a -> Over m a -> Ordering
$ccompare :: forall m a. Ord m => Over m a -> Over m a -> Ordering
Ord, Int -> Over m a -> ShowS
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]
showList :: [Over m a] -> ShowS
$cshowList :: forall m a. Show m => [Over m a] -> ShowS
show :: Over m a -> [Char]
$cshow :: forall m a. Show m => Over m a -> [Char]
showsPrec :: Int -> Over m a -> ShowS
$cshowsPrec :: forall m a. Show m => Int -> Over m a -> ShowS
Show)
    deriving 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
<* :: forall a b. Over m a -> Over m b -> Over m a
$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 b
$c*> :: forall m a b. Monoid m => Over m a -> Over m b -> Over m b
liftA2 :: forall a b c. (a -> b -> c) -> Over m a -> Over m b -> Over m c
$cliftA2 :: 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 -> b) -> Over m a -> Over m b
$c<*> :: forall m a b. Monoid m => Over m (a -> b) -> Over m a -> Over m b
pure :: forall a. a -> Over m a
$cpure :: forall m a. Monoid m => a -> 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) = forall m a. m -> Over m a
Over (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
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
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
$c== :: forall m a. Eq m => Under m a -> Under m a -> Bool
Eq, 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
<$ :: forall a b. a -> Under m b -> Under m a
$c<$ :: forall m a b. a -> Under m b -> Under m a
fmap :: forall a b. (a -> b) -> Under m a -> Under m b
$cfmap :: forall m a b. (a -> b) -> Under m a -> Under m b
Functor, 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
min :: Under m a -> Under m a -> Under m a
$cmin :: forall m a. Ord m => Under m a -> Under m a -> Under m a
max :: Under m a -> Under m a -> Under m a
$cmax :: forall m a. Ord m => Under m a -> Under m a -> Under m a
>= :: 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
$c< :: forall m a. Ord m => Under m a -> Under m a -> Bool
compare :: Under m a -> Under m a -> Ordering
$ccompare :: forall m a. Ord m => Under m a -> Under m a -> Ordering
Ord, Int -> Under m a -> ShowS
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]
showList :: [Under m a] -> ShowS
$cshowList :: forall m a. Show m => [Under m a] -> ShowS
show :: Under m a -> [Char]
$cshow :: forall m a. Show m => Under m a -> [Char]
showsPrec :: Int -> Under m a -> ShowS
$cshowsPrec :: forall m a. Show m => Int -> Under m a -> ShowS
Show, 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 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
product :: forall a. Num a => Under m a -> a
$cproduct :: forall m a. Num a => Under m a -> a
sum :: forall a. Num a => Under m a -> a
$csum :: forall m a. Num a => Under m a -> a
minimum :: forall a. Ord a => Under m a -> a
$cminimum :: forall m a. Ord a => Under m a -> a
maximum :: forall a. Ord a => Under m a -> a
$cmaximum :: forall m a. Ord a => Under m a -> a
elem :: forall a. Eq a => a -> Under m a -> Bool
$celem :: forall m a. Eq a => a -> Under m a -> Bool
length :: forall a. Under m a -> Int
$clength :: forall m a. Under m a -> Int
null :: forall a. Under m a -> Bool
$cnull :: forall m a. Under m a -> Bool
toList :: forall a. Under m a -> [a]
$ctoList :: forall m a. Under m a -> [a]
foldl1 :: forall a. (a -> a -> a) -> Under m a -> a
$cfoldl1 :: forall m a. (a -> a -> a) -> Under m a -> a
foldr1 :: forall a. (a -> a -> a) -> Under m a -> a
$cfoldr1 :: forall m a. (a -> a -> a) -> Under m a -> a
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
$cfoldl :: forall m b a. (b -> a -> 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
$cfoldr :: forall m a b. (a -> b -> b) -> b -> Under m a -> b
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
$cfoldMap :: forall m m a. Monoid m => (a -> m) -> Under m a -> m
fold :: forall m. Monoid m => Under m m -> m
$cfold :: forall m m. Monoid m => Under m m -> m
Foldable, 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 (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Under m a -> f (Under m b)
sequence :: forall (m :: * -> *) a. Monad m => Under m (m a) -> m (Under m a)
$csequence :: forall m (m :: * -> *) a. Monad m => Under m (m a) -> m (Under m a)
mapM :: forall (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Under m a -> m (Under m b)
$cmapM :: forall m (m :: * -> *) a b.
Monad m =>
(a -> m b) -> Under m a -> m (Under m b)
sequenceA :: forall (f :: * -> *) a.
Applicative f =>
Under m (f a) -> f (Under m a)
$csequenceA :: forall m (f :: * -> *) a.
Applicative f =>
Under m (f a) -> f (Under m a)
traverse :: 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)
Traversable)
    deriving 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
<* :: forall a b. Under m a -> Under m b -> Under m a
$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 b
$c*> :: forall m a b. Monoid m => Under m a -> Under m b -> Under m b
liftA2 :: forall a b c. (a -> b -> c) -> Under m a -> Under m b -> Under m c
$cliftA2 :: 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 -> b) -> Under m a -> Under m b
$c<*> :: forall m a b.
Monoid m =>
Under m (a -> b) -> Under m a -> Under m b
pure :: forall a. a -> Under m a
$cpure :: forall m a. Monoid m => a -> 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)
_ = 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 = 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
forall a. (a -> a -> Bool) -> (a -> a -> Bool) -> Eq a
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
$c== :: forall e a.
(Eq e, Eq a) =>
Validation e a -> Validation e a -> Bool
Eq, 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
<$ :: forall a b. a -> Validation e b -> Validation e a
$c<$ :: forall e a b. a -> Validation e b -> Validation e a
fmap :: forall a b. (a -> b) -> Validation e a -> Validation e b
$cfmap :: forall e a b. (a -> b) -> Validation e a -> Validation e b
Functor, Validation e a -> Validation e a -> Bool
Validation e a -> Validation e a -> Ordering
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
min :: 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
max :: Validation e a -> Validation e a -> Validation e a
$cmax :: forall e a.
(Ord e, Ord a) =>
Validation e a -> Validation e a -> Validation e a
>= :: 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
$c< :: forall e a.
(Ord e, Ord a) =>
Validation e a -> Validation e a -> Bool
compare :: Validation e a -> Validation e a -> Ordering
$ccompare :: forall e a.
(Ord e, Ord a) =>
Validation e a -> Validation e a -> Ordering
Ord, Int -> Validation e a -> ShowS
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]
showList :: [Validation e a] -> ShowS
$cshowList :: forall e a. (Show e, Show a) => [Validation e a] -> ShowS
show :: Validation e a -> [Char]
$cshow :: forall e a. (Show e, Show a) => Validation e a -> [Char]
showsPrec :: Int -> Validation e a -> ShowS
$cshowsPrec :: forall e a. (Show e, Show a) => Int -> Validation e a -> ShowS
Show)

instance Semigroup e => Applicative (Validation e) where
    pure :: forall a. a -> Validation e a
pure = 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 = forall e a. e -> Validation e a
Failure (e
e1 forall a. Semigroup a => a -> a -> a
<> e
e2)
    Failure e
e1 <*> Success a
_  = forall e a. e -> Validation e a
Failure e
e1
    Success a -> b
_  <*> Failure e
e2 = forall e a. e -> Validation e a
Failure e
e2
    Success a -> b
f  <*> Success a
a  = 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 = (forall a b. (a -> b) -> a -> b
$a
a) 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)
_ = forall e a. a -> Validation e a
Success b
b
    select (Failure e
e        ) Validation e (a -> 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) = forall {k} (f :: k -> *) (g :: k -> *) (a :: k).
f a -> g a -> Product f g a
Pair (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) (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) = forall {k} (f :: k -> *) (a :: k). f a -> IdentityT f a
IdentityT (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) = forall r (m :: * -> *) a. (r -> m a) -> ReaderT r m a
ReaderT forall a b. (a -> b) -> a -> b
$ \env
env -> 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) = forall a b. a -> Either a b
Left  (a
a, w
w)
distributeEither (Right b
b, w
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, 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) =
        forall w (m :: * -> *) a. m (a, w) -> WriterT w m a
WriterT forall a b. (a -> b) -> a -> b
$ forall (f :: * -> *) a b.
Selective f =>
f (Either a b) -> f (a -> b) -> f b
select (forall a b w. (Either a b, w) -> Either (a, w) (b, w)
distributeEither forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f (Either a b, w)
x) (forall w a b. Monoid w => (a -> b, w) -> (a, w) -> (b, w)
distributeFunction 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) =
        forall w (m :: * -> *) a. m (a, w) -> WriterT w m a
S.WriterT forall a b. (a -> b) -> a -> b
$ forall (f :: * -> *) a b.
Selective f =>
f (Either a b) -> f (a -> b) -> f b
select (forall a b w. (Either a b, w) -> Either (a, w) (b, w)
distributeEither forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f (Either a b, w)
x) (forall w a b. Monoid w => (a -> b, w) -> (a, w) -> (b, w)
distributeFunction 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) = forall {k} {k1} (f :: k -> *) (g :: k1 -> k) (a :: k1).
f (g a) -> Compose f g a
Compose (forall (f :: * -> *) a b.
Selective f =>
f (Either a b) -> f (a -> b) -> f b
select forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f (g (Either a b))
x 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 = 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 = 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 = 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 = 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 = 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 = 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 = 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 = 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 = 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 = 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 = 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 = 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 = 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 = 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 = 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 = 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 = 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 = forall (a :: * -> * -> *) b. a () b -> ArrowMonad a b
ArrowMonad forall a b. (a -> b) -> a -> b
$ a () (Either a b)
x forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
Category cat =>
cat a b -> cat b c -> cat a c
>>> (forall (a :: * -> * -> *) i o.
Arrow a =>
ArrowMonad a (i -> o) -> a i o
toArrow ArrowMonad a (a -> b)
y forall (a :: * -> * -> *) b d c.
ArrowChoice a =>
a b d -> a c d -> a (Either b c) d
||| 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) = forall (a :: * -> * -> *) b c. Arrow a => (b -> c) -> a b c
arr ((),) forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
Category cat =>
cat a b -> cat b c -> cat a c
>>> forall (a :: * -> * -> *) b c d.
Arrow a =>
a b c -> a (b, d) (c, d)
first a () (i -> o)
f forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
Category cat =>
cat a b -> cat b c -> cat a c
>>> forall (a :: * -> * -> *) b c. Arrow a => (b -> c) -> a b c
arr (forall a b c. (a -> b -> c) -> (a, b) -> c
uncurry 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 -> 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
<$ :: forall a b.
a -> ComposeTraversable f g b -> ComposeTraversable f g a
$c<$ :: forall (f :: * -> *) (g :: * -> *) a b.
(Functor f, Functor g) =>
a -> ComposeTraversable f g b -> ComposeTraversable f g a
fmap :: forall a b.
(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
Functor, 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
<* :: forall a b.
ComposeTraversable f g a
-> ComposeTraversable f g b -> ComposeTraversable f g a
$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 b
$c*> :: forall (f :: * -> *) (g :: * -> *) a b.
(Applicative f, Applicative g) =>
ComposeTraversable f g a
-> ComposeTraversable f g b -> ComposeTraversable f g b
liftA2 :: forall a b c.
(a -> b -> c)
-> ComposeTraversable f g a
-> ComposeTraversable f g b
-> ComposeTraversable f g c
$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
<*> :: forall a b.
ComposeTraversable f g (a -> b)
-> ComposeTraversable f g a -> ComposeTraversable f g b
$c<*> :: forall (f :: * -> *) (g :: * -> *) a b.
(Applicative f, Applicative g) =>
ComposeTraversable f g (a -> b)
-> ComposeTraversable f g a -> ComposeTraversable f g b
pure :: forall a. a -> ComposeTraversable f g a
$cpure :: forall (f :: * -> *) (g :: * -> *) a.
(Applicative f, Applicative g) =>
a -> 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) = forall (f :: * -> *) (g :: * -> *) a.
f (g a) -> ComposeTraversable f g a
ComposeTraversable forall a b. (a -> b) -> a -> b
$
        forall (f :: * -> *) a b.
Selective f =>
f (Either a b) -> f (a -> b) -> f b
select (forall (g :: * -> *) a b.
Traversable g =>
g (Either a b) -> Either a (g b)
prepare forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f (g (Either a b))
x) (forall (g :: * -> *) a b. Traversable g => g (a -> b) -> a -> g b
combine 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 = forall (t :: * -> *) (f :: * -> *) a.
(Traversable t, Applicative f) =>
t (f a) -> f (t 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 = forall (t :: * -> *) (f :: * -> *) a.
(Traversable t, Applicative f) =>
t (f a) -> f (t 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 -> 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
<$ :: forall a b. a -> ComposeEither f e b -> ComposeEither f e a
$c<$ :: forall (f :: * -> *) e a b.
Functor f =>
a -> ComposeEither f e b -> ComposeEither f e a
fmap :: forall a b. (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
Functor via Compose f (Either e)
    deriving 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
select :: forall a b.
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
Selective via ComposeTraversable f (Either e)

instance Selective f => Applicative (ComposeEither f e) where
    pure :: forall a. a -> ComposeEither f e a
pure = forall (f :: * -> *) e a. f (Either e a) -> ComposeEither f e a
ComposeEither forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (f :: * -> *) a. Applicative f => a -> f a
pure forall b c a. (b -> c) -> (a -> b) -> a -> c
. 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 = forall (f :: * -> *) e a. f (Either e a) -> ComposeEither f e a
ComposeEither forall a b. (a -> b) -> a -> b
$
        forall (f :: * -> *) a b.
Selective f =>
f (Either a b) -> f (a -> b) -> f b
select (forall e a b. Either e (a -> b) -> Either (a -> b) (Either e b)
prepare forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
<$> f (Either e (a -> b))
f) (forall e a b. Either e a -> (a -> b) -> Either e b
combine 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 = forall a c b. (a -> c) -> (b -> c) -> Either a b -> c
either (forall a b. b -> Either a b
Right forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall a b. a -> Either a b
Left) 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 = forall a b c. (a -> b -> c) -> b -> a -> c
flip 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                               = forall (f :: * -> *) e a. f (Either e a) -> ComposeEither f e a
ComposeEither (forall (f :: * -> *) a. Applicative f => a -> f a
pure forall a b. (a -> b) -> a -> b
$ forall a b. a -> Either a b
Left 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 = forall (f :: * -> *) e a. f (Either e a) -> ComposeEither f e a
ComposeEither (f (Either e a)
x 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.

-}