    {-# LANGUAGE Trustworthy #-}
    {-# LANGUAGE DeriveGeneric #-}
    {-# LANGUAGE GeneralizedNewtypeDeriving #-}
    {-# LANGUAGE NoImplicitPrelude #-}
    {-# LANGUAGE KindSignatures #-}
    {-# LANGUAGE StandaloneDeriving #-}
    {-# LANGUAGE DeriveDataTypeable #-}

    -----------------------------------------------------------------------------
    -- |
    -- Module      :  Control.Applicative
    -- Copyright   :  Conor McBride and Ross Paterson 2005
    -- License     :  BSD-style (see the LICENSE file in the distribution)
    --
    -- Maintainer  :  libraries@haskell.org
    -- Stability   :  stable
    -- Portability :  portable
    --
    -- This module describes a structure intermediate between a functor and
    -- a monad (technically, a strong lax monoidal functor).  Compared with
    -- monads, this interface lacks the full power of the binding operation
    -- '>>=', but
    --
    -- * it has more instances.
    --
    -- * it is sufficient for many uses, e.g. context-free parsing, or the
    --   'Data.Traversable.Traversable' class.
    --
    -- * instances can perform analysis of computations before they are
    --   executed, and thus produce shared optimizations.
    --
    -- This interface was introduced for parsers by Niklas R&#xF6;jemo, because
    -- it admits more sharing than the monadic interface.  The names here are
    -- mostly based on parsing work by Doaitse Swierstra.
    --
    -- For more details, see
    -- <http://www.soi.city.ac.uk/~ross/papers/Applicative.html Applicative Programming with Effects>,
    -- by Conor McBride and Ross Paterson.

    module Control.Applicative (
        -- * Applicative functors
        Applicative(..),
        -- * Alternatives
        Alternative(..),
        -- * Instances
        Const(..), WrappedMonad(..), WrappedArrow(..), ZipList(..),
        -- * Utility functions
        (<$>), (<$), (<**>),
        liftA, liftA3,
        optional,
        asum,
        ) where

    import GHC.Internal.Control.Category hiding ((.), id)
    import GHC.Internal.Control.Arrow
    import GHC.Internal.Data.Maybe
    import GHC.Internal.Data.Tuple
    import GHC.Internal.Data.Foldable (asum)
    import GHC.Internal.Data.Functor ((<$>))
    import GHC.Internal.Data.Functor.Const (Const(..))
    import GHC.Internal.Data.Typeable (Typeable)
    import GHC.Internal.Data.Data (Data)

    import GHC.Internal.Base
    import GHC.Internal.Functor.ZipList (ZipList(..))
    import GHC.Generics

    -- $setup
    -- >>> import Prelude

    newtype WrappedMonad m a = WrapMonad { forall (m :: * -> *) a. WrappedMonad m a -> m a
    unwrapMonad :: m a }
                             deriving ( (forall x. WrappedMonad m a -> Rep (WrappedMonad m a) x)
    -> (forall x. Rep (WrappedMonad m a) x -> WrappedMonad m a)
    -> Generic (WrappedMonad m a)
    forall x. Rep (WrappedMonad m a) x -> WrappedMonad m a
    forall x. WrappedMonad m a -> Rep (WrappedMonad m a) x
    forall a.
    (forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
    forall (m :: * -> *) a x.
    Rep (WrappedMonad m a) x -> WrappedMonad m a
    forall (m :: * -> *) a x.
    WrappedMonad m a -> Rep (WrappedMonad m a) x
    $cfrom :: forall (m :: * -> *) a x.
    WrappedMonad m a -> Rep (WrappedMonad m a) x
    from :: forall x. WrappedMonad m a -> Rep (WrappedMonad m a) x
    $cto :: forall (m :: * -> *) a x.
    Rep (WrappedMonad m a) x -> WrappedMonad m a
    to :: forall x. Rep (WrappedMonad m a) x -> WrappedMonad m a
    Generic  -- ^ @since 4.7.0.0
                                      , (forall a. WrappedMonad m a -> Rep1 (WrappedMonad m) a)
    -> (forall a. Rep1 (WrappedMonad m) a -> WrappedMonad m a)
    -> Generic1 (WrappedMonad m)
    forall a. Rep1 (WrappedMonad m) a -> WrappedMonad m a
    forall a. WrappedMonad m a -> Rep1 (WrappedMonad m) a
    forall k (f :: k -> *).
    (forall (a :: k). f a -> Rep1 f a)
    -> (forall (a :: k). Rep1 f a -> f a) -> Generic1 f
    forall (m :: * -> *) a. Rep1 (WrappedMonad m) a -> WrappedMonad m a
    forall (m :: * -> *) a. WrappedMonad m a -> Rep1 (WrappedMonad m) a
    $cfrom1 :: forall (m :: * -> *) a. WrappedMonad m a -> Rep1 (WrappedMonad m) a
    from1 :: forall a. WrappedMonad m a -> Rep1 (WrappedMonad m) a
    $cto1 :: forall (m :: * -> *) a. Rep1 (WrappedMonad m) a -> WrappedMonad m a
    to1 :: forall a. Rep1 (WrappedMonad m) a -> WrappedMonad m a
    Generic1 -- ^ @since 4.7.0.0
                                      , Applicative (WrappedMonad m)
    Applicative (WrappedMonad m) =>
    (forall a b.
     WrappedMonad m a -> (a -> WrappedMonad m b) -> WrappedMonad m b)
    -> (forall a b.
        WrappedMonad m a -> WrappedMonad m b -> WrappedMonad m b)
    -> (forall a. a -> WrappedMonad m a)
    -> Monad (WrappedMonad m)
    forall a. a -> WrappedMonad m a
    forall a b.
    WrappedMonad m a -> WrappedMonad m b -> WrappedMonad m b
    forall a b.
    WrappedMonad m a -> (a -> WrappedMonad m b) -> WrappedMonad m b
    forall (m :: * -> *). Monad m => Applicative (WrappedMonad m)
    forall (m :: * -> *) a. Monad m => a -> WrappedMonad m a
    forall (m :: * -> *) a b.
    Monad m =>
    WrappedMonad m a -> WrappedMonad m b -> WrappedMonad m b
    forall (m :: * -> *) a b.
    Monad m =>
    WrappedMonad m a -> (a -> WrappedMonad m b) -> WrappedMonad m 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 (m :: * -> *) a b.
    Monad m =>
    WrappedMonad m a -> (a -> WrappedMonad m b) -> WrappedMonad m b
    >>= :: forall a b.
    WrappedMonad m a -> (a -> WrappedMonad m b) -> WrappedMonad m b
    $c>> :: forall (m :: * -> *) a b.
    Monad m =>
    WrappedMonad m a -> WrappedMonad m b -> WrappedMonad m b
    >> :: forall a b.
    WrappedMonad m a -> WrappedMonad m b -> WrappedMonad m b
    $creturn :: forall (m :: * -> *) a. Monad m => a -> WrappedMonad m a
    return :: forall a. a -> WrappedMonad m a
    Monad    -- ^ @since 4.7.0.0
                                      )

    -- | @since 2.01
    instance Monad m => Functor (WrappedMonad m) where
        fmap :: forall a b. (a -> b) -> WrappedMonad m a -> WrappedMonad m b
    fmap a -> b
    f (WrapMonad m a
    v) = m b -> WrappedMonad m b
    forall (m :: * -> *) a. m a -> WrappedMonad m a
    WrapMonad ((a -> b) -> m a -> m b
    forall (m :: * -> *) a1 r. Monad m => (a1 -> r) -> m a1 -> m r
    liftM a -> b
    f m a
    v)

    -- | @since 2.01
    instance Monad m => Applicative (WrappedMonad m) where
        pure :: forall a. a -> WrappedMonad m a
    pure = m a -> WrappedMonad m a
    forall (m :: * -> *) a. m a -> WrappedMonad m a
    WrapMonad (m a -> WrappedMonad m a) -> (a -> m a) -> a -> WrappedMonad m a
    forall b c a. (b -> c) -> (a -> b) -> a -> c
    . a -> m a
    forall a. a -> m a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure
        WrapMonad m (a -> b)
    f <*> :: forall a b.
    WrappedMonad m (a -> b) -> WrappedMonad m a -> WrappedMonad m b
    <*> WrapMonad m a
    v = m b -> WrappedMonad m b
    forall (m :: * -> *) a. m a -> WrappedMonad m a
    WrapMonad (m (a -> b)
    f m (a -> b) -> m a -> m b
    forall (m :: * -> *) a b. Monad m => m (a -> b) -> m a -> m b
    `ap` m a
    v)
        liftA2 :: forall a b c.
    (a -> b -> c)
    -> WrappedMonad m a -> WrappedMonad m b -> WrappedMonad m c
    liftA2 a -> b -> c
    f (WrapMonad m a
    x) (WrapMonad m b
    y) = m c -> WrappedMonad m c
    forall (m :: * -> *) a. m a -> WrappedMonad m a
    WrapMonad ((a -> b -> c) -> m a -> m b -> m c
    forall (m :: * -> *) a1 a2 r.
    Monad m =>
    (a1 -> a2 -> r) -> m a1 -> m a2 -> m r
    liftM2 a -> b -> c
    f m a
    x m b
    y)

    -- | @since 2.01
    instance MonadPlus m => Alternative (WrappedMonad m) where
        empty :: forall a. WrappedMonad m a
    empty = m a -> WrappedMonad m a
    forall (m :: * -> *) a. m a -> WrappedMonad m a
    WrapMonad m a
    forall a. m a
    forall (m :: * -> *) a. MonadPlus m => m a
    mzero
        WrapMonad m a
    u <|> :: forall a. WrappedMonad m a -> WrappedMonad m a -> WrappedMonad m a
    <|> WrapMonad m a
    v = m a -> WrappedMonad m a
    forall (m :: * -> *) a. m a -> WrappedMonad m a
    WrapMonad (m a
    u m a -> m a -> m a
    forall a. m a -> m a -> m a
    forall (m :: * -> *) a. MonadPlus m => m a -> m a -> m a
    `mplus` m a
    v)

    -- | @since 4.14.0.0
    deriving instance (Typeable (m :: Type -> Type), Typeable a, Data (m a))
             => Data (WrappedMonad m a)

    newtype WrappedArrow a b c = WrapArrow { forall (a :: * -> * -> *) b c. WrappedArrow a b c -> a b c
    unwrapArrow :: a b c }
                               deriving ( (forall x. WrappedArrow a b c -> Rep (WrappedArrow a b c) x)
    -> (forall x. Rep (WrappedArrow a b c) x -> WrappedArrow a b c)
    -> Generic (WrappedArrow a b c)
    forall x. Rep (WrappedArrow a b c) x -> WrappedArrow a b c
    forall x. WrappedArrow a b c -> Rep (WrappedArrow a b c) x
    forall a.
    (forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
    forall (a :: * -> * -> *) b c x.
    Rep (WrappedArrow a b c) x -> WrappedArrow a b c
    forall (a :: * -> * -> *) b c x.
    WrappedArrow a b c -> Rep (WrappedArrow a b c) x
    $cfrom :: forall (a :: * -> * -> *) b c x.
    WrappedArrow a b c -> Rep (WrappedArrow a b c) x
    from :: forall x. WrappedArrow a b c -> Rep (WrappedArrow a b c) x
    $cto :: forall (a :: * -> * -> *) b c x.
    Rep (WrappedArrow a b c) x -> WrappedArrow a b c
    to :: forall x. Rep (WrappedArrow a b c) x -> WrappedArrow a b c
    Generic  -- ^ @since 4.7.0.0
                                        , (forall a. WrappedArrow a b a -> Rep1 (WrappedArrow a b) a)
    -> (forall a. Rep1 (WrappedArrow a b) a -> WrappedArrow a b a)
    -> Generic1 (WrappedArrow a b)
    forall a. Rep1 (WrappedArrow a b) a -> WrappedArrow a b a
    forall a. WrappedArrow a b a -> Rep1 (WrappedArrow a b) a
    forall k (f :: k -> *).
    (forall (a :: k). f a -> Rep1 f a)
    -> (forall (a :: k). Rep1 f a -> f a) -> Generic1 f
    forall (a :: * -> * -> *) b a.
    Rep1 (WrappedArrow a b) a -> WrappedArrow a b a
    forall (a :: * -> * -> *) b a.
    WrappedArrow a b a -> Rep1 (WrappedArrow a b) a
    $cfrom1 :: forall (a :: * -> * -> *) b a.
    WrappedArrow a b a -> Rep1 (WrappedArrow a b) a
    from1 :: forall a. WrappedArrow a b a -> Rep1 (WrappedArrow a b) a
    $cto1 :: forall (a :: * -> * -> *) b a.
    Rep1 (WrappedArrow a b) a -> WrappedArrow a b a
    to1 :: forall a. Rep1 (WrappedArrow a b) a -> WrappedArrow a b a
    Generic1 -- ^ @since 4.7.0.0
                                        )

    -- | @since 2.01
    instance Arrow a => Functor (WrappedArrow a b) where
        fmap :: forall a b. (a -> b) -> WrappedArrow a b a -> WrappedArrow a b b
    fmap a -> b
    f (WrapArrow a b a
    a) = a b b -> WrappedArrow a b b
    forall (a :: * -> * -> *) b c. a b c -> WrappedArrow a b c
    WrapArrow (a b a
    a a b a -> a a b -> a b b
    forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
    Category cat =>
    cat a b -> cat b c -> cat a c
    >>> (a -> b) -> a a b
    forall b c. (b -> c) -> a b c
    forall (a :: * -> * -> *) b c. Arrow a => (b -> c) -> a b c
    arr a -> b
    f)

    -- | @since 2.01
    instance Arrow a => Applicative (WrappedArrow a b) where
        pure :: forall a. a -> WrappedArrow a b a
    pure a
    x = a b a -> WrappedArrow a b a
    forall (a :: * -> * -> *) b c. a b c -> WrappedArrow a b c
    WrapArrow ((b -> a) -> a b a
    forall b c. (b -> c) -> a b c
    forall (a :: * -> * -> *) b c. Arrow a => (b -> c) -> a b c
    arr (a -> b -> a
    forall a b. a -> b -> a
    const a
    x))
        liftA2 :: forall a b c.
    (a -> b -> c)
    -> WrappedArrow a b a -> WrappedArrow a b b -> WrappedArrow a b c
    liftA2 a -> b -> c
    f (WrapArrow a b a
    u) (WrapArrow a b b
    v) =
          a b c -> WrappedArrow a b c
    forall (a :: * -> * -> *) b c. a b c -> WrappedArrow a b c
    WrapArrow (a b a
    u a b a -> a b b -> a b (a, b)
    forall b c c'. a b c -> a b c' -> a b (c, c')
    forall (a :: * -> * -> *) b c c'.
    Arrow a =>
    a b c -> a b c' -> a b (c, c')
    &&& a b b
    v a b (a, b) -> a (a, b) c -> a b c
    forall {k} (cat :: k -> k -> *) (a :: k) (b :: k) (c :: k).
    Category cat =>
    cat a b -> cat b c -> cat a c
    >>> ((a, b) -> c) -> a (a, b) c
    forall b c. (b -> c) -> a b c
    forall (a :: * -> * -> *) b c. Arrow a => (b -> c) -> a b c
    arr ((a -> b -> c) -> (a, b) -> c
    forall a b c. (a -> b -> c) -> (a, b) -> c
    uncurry a -> b -> c
    f))

    -- | @since 2.01
    instance (ArrowZero a, ArrowPlus a) => Alternative (WrappedArrow a b) where
        empty :: forall a. WrappedArrow a b a
    empty = a b a -> WrappedArrow a b a
    forall (a :: * -> * -> *) b c. a b c -> WrappedArrow a b c
    WrapArrow a b a
    forall b c. a b c
    forall (a :: * -> * -> *) b c. ArrowZero a => a b c
    zeroArrow
        WrapArrow a b a
    u <|> :: forall a.
    WrappedArrow a b a -> WrappedArrow a b a -> WrappedArrow a b a
    <|> WrapArrow a b a
    v = a b a -> WrappedArrow a b a
    forall (a :: * -> * -> *) b c. a b c -> WrappedArrow a b c
    WrapArrow (a b a
    u a b a -> a b a -> a b a
    forall b c. a b c -> a b c -> a b c
    forall (a :: * -> * -> *) b c.
    ArrowPlus a =>
    a b c -> a b c -> a b c
    <+> a b a
    v)

    -- | @since 4.14.0.0
    deriving instance (Typeable (a :: Type -> Type -> Type), Typeable b, Typeable c,
                       Data (a b c))
             => Data (WrappedArrow a b c)

    -- extra functions

    -- | One or none.
    --
    -- It is useful for modelling any computation that is allowed to fail.
    --
    -- ==== __Examples__
    --
    -- Using the 'Alternative' instance of "Control.Monad.Except", the following functions:
    --
    -- >>> import Control.Monad.Except
    --
    -- >>> canFail = throwError "it failed" :: Except String Int
    -- >>> final = return 42                :: Except String Int
    --
    -- Can be combined by allowing the first function to fail:
    --
    -- >>> runExcept $ canFail *> final
    -- Left "it failed"
    --
    -- >>> runExcept $ optional canFail *> final
    -- Right 42

    optional :: Alternative f => f a -> f (Maybe a)
    optional :: forall (f :: * -> *) a. Alternative f => f a -> f (Maybe a)
    optional f a
    v = a -> Maybe a
    forall a. a -> Maybe a
    Just (a -> Maybe a) -> f a -> f (Maybe a)
    forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
    <$> f a
    v f (Maybe a) -> f (Maybe a) -> f (Maybe a)
    forall a. f a -> f a -> f a
    forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
    <|> Maybe a -> f (Maybe a)
    forall a. a -> f a
    forall (f :: * -> *) a. Applicative f => a -> f a
    pure Maybe a
    forall a. Maybe a
    Nothing