    {-
    A simple homogeneous pair type with useful Functor, Applicative, and
    Traversable instances.
    -}

    {-# LANGUAGE DeriveTraversable #-}

    module GHC.Data.Pair
       ( Pair(..)
       , unPair
       , toPair
       , swap
       , pLiftFst, pLiftSnd
       , unzipPairs
       )
    where

    import GHC.Prelude

    import GHC.Utils.Outputable
    import qualified Data.Semigroup as Semi

    data Pair a = Pair { forall a. Pair a -> a
    pFst :: a, forall a. Pair a -> a
    pSnd :: a }
      deriving ((forall m. Monoid m => Pair m -> m)
    -> (forall m a. Monoid m => (a -> m) -> Pair a -> m)
    -> (forall m a. Monoid m => (a -> m) -> Pair a -> m)
    -> (forall a b. (a -> b -> b) -> b -> Pair a -> b)
    -> (forall a b. (a -> b -> b) -> b -> Pair a -> b)
    -> (forall b a. (b -> a -> b) -> b -> Pair a -> b)
    -> (forall b a. (b -> a -> b) -> b -> Pair a -> b)
    -> (forall a. (a -> a -> a) -> Pair a -> a)
    -> (forall a. (a -> a -> a) -> Pair a -> a)
    -> (forall a. Pair a -> [a])
    -> (forall a. Pair a -> Bool)
    -> (forall a. Pair a -> Int)
    -> (forall a. Eq a => a -> Pair a -> Bool)
    -> (forall a. Ord a => Pair a -> a)
    -> (forall a. Ord a => Pair a -> a)
    -> (forall a. Num a => Pair a -> a)
    -> (forall a. Num a => Pair a -> a)
    -> Foldable Pair
    forall a. Eq a => a -> Pair a -> Bool
    forall a. Num a => Pair a -> a
    forall a. Ord a => Pair a -> a
    forall m. Monoid m => Pair m -> m
    forall a. Pair a -> Bool
    forall a. Pair a -> Int
    forall a. Pair a -> [a]
    forall a. (a -> a -> a) -> Pair a -> a
    forall m a. Monoid m => (a -> m) -> Pair a -> m
    forall b a. (b -> a -> b) -> b -> Pair a -> b
    forall a b. (a -> b -> b) -> b -> Pair 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. Monoid m => Pair m -> m
    fold :: forall m. Monoid m => Pair m -> m
    $cfoldMap :: forall m a. Monoid m => (a -> m) -> Pair a -> m
    foldMap :: forall m a. Monoid m => (a -> m) -> Pair a -> m
    $cfoldMap' :: forall m a. Monoid m => (a -> m) -> Pair a -> m
    foldMap' :: forall m a. Monoid m => (a -> m) -> Pair a -> m
    $cfoldr :: forall a b. (a -> b -> b) -> b -> Pair a -> b
    foldr :: forall a b. (a -> b -> b) -> b -> Pair a -> b
    $cfoldr' :: forall a b. (a -> b -> b) -> b -> Pair a -> b
    foldr' :: forall a b. (a -> b -> b) -> b -> Pair a -> b
    $cfoldl :: forall b a. (b -> a -> b) -> b -> Pair a -> b
    foldl :: forall b a. (b -> a -> b) -> b -> Pair a -> b
    $cfoldl' :: forall b a. (b -> a -> b) -> b -> Pair a -> b
    foldl' :: forall b a. (b -> a -> b) -> b -> Pair a -> b
    $cfoldr1 :: forall a. (a -> a -> a) -> Pair a -> a
    foldr1 :: forall a. (a -> a -> a) -> Pair a -> a
    $cfoldl1 :: forall a. (a -> a -> a) -> Pair a -> a
    foldl1 :: forall a. (a -> a -> a) -> Pair a -> a
    $ctoList :: forall a. Pair a -> [a]
    toList :: forall a. Pair a -> [a]
    $cnull :: forall a. Pair a -> Bool
    null :: forall a. Pair a -> Bool
    $clength :: forall a. Pair a -> Int
    length :: forall a. Pair a -> Int
    $celem :: forall a. Eq a => a -> Pair a -> Bool
    elem :: forall a. Eq a => a -> Pair a -> Bool
    $cmaximum :: forall a. Ord a => Pair a -> a
    maximum :: forall a. Ord a => Pair a -> a
    $cminimum :: forall a. Ord a => Pair a -> a
    minimum :: forall a. Ord a => Pair a -> a
    $csum :: forall a. Num a => Pair a -> a
    sum :: forall a. Num a => Pair a -> a
    $cproduct :: forall a. Num a => Pair a -> a
    product :: forall a. Num a => Pair a -> a
    Foldable, (forall a b. (a -> b) -> Pair a -> Pair b)
    -> (forall a b. a -> Pair b -> Pair a) -> Functor Pair
    forall a b. a -> Pair b -> Pair a
    forall a b. (a -> b) -> Pair a -> Pair b
    forall (f :: * -> *).
    (forall a b. (a -> b) -> f a -> f b)
    -> (forall a b. a -> f b -> f a) -> Functor f
    $cfmap :: forall a b. (a -> b) -> Pair a -> Pair b
    fmap :: forall a b. (a -> b) -> Pair a -> Pair b
    $c<$ :: forall a b. a -> Pair b -> Pair a
    <$ :: forall a b. a -> Pair b -> Pair a
    Functor, Functor Pair
    Foldable Pair
    (Functor Pair, Foldable Pair) =>
    (forall (f :: * -> *) a b.
     Applicative f =>
     (a -> f b) -> Pair a -> f (Pair b))
    -> (forall (f :: * -> *) a.
        Applicative f =>
        Pair (f a) -> f (Pair a))
    -> (forall (m :: * -> *) a b.
        Monad m =>
        (a -> m b) -> Pair a -> m (Pair b))
    -> (forall (m :: * -> *) a. Monad m => Pair (m a) -> m (Pair a))
    -> Traversable Pair
    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 => Pair (m a) -> m (Pair a)
    forall (f :: * -> *) a. Applicative f => Pair (f a) -> f (Pair a)
    forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> Pair a -> m (Pair b)
    forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Pair a -> f (Pair b)
    $ctraverse :: forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Pair a -> f (Pair b)
    traverse :: forall (f :: * -> *) a b.
    Applicative f =>
    (a -> f b) -> Pair a -> f (Pair b)
    $csequenceA :: forall (f :: * -> *) a. Applicative f => Pair (f a) -> f (Pair a)
    sequenceA :: forall (f :: * -> *) a. Applicative f => Pair (f a) -> f (Pair a)
    $cmapM :: forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> Pair a -> m (Pair b)
    mapM :: forall (m :: * -> *) a b.
    Monad m =>
    (a -> m b) -> Pair a -> m (Pair b)
    $csequence :: forall (m :: * -> *) a. Monad m => Pair (m a) -> m (Pair a)
    sequence :: forall (m :: * -> *) a. Monad m => Pair (m a) -> m (Pair a)
    Traversable)
    -- Note that Pair is a *unary* type constructor
    -- whereas (,) is binary

    -- The important thing about Pair is that it has a *homogeneous*
    -- Functor instance, so you can easily apply the same function
    -- to both components

    instance Applicative Pair where
      pure :: forall a. a -> Pair a
    pure a
    x = a -> a -> Pair a
    forall a. a -> a -> Pair a
    Pair a
    x a
    x
      (Pair a -> b
    f a -> b
    g) <*> :: forall a b. Pair (a -> b) -> Pair a -> Pair b
    <*> (Pair a
    x a
    y) = b -> b -> Pair b
    forall a. a -> a -> Pair a
    Pair (a -> b
    f a
    x) (a -> b
    g a
    y)

    instance Semi.Semigroup a => Semi.Semigroup (Pair a) where
      Pair a
    a1 a
    b1 <> :: Pair a -> Pair a -> Pair a
    <> Pair a
    a2 a
    b2 =  a -> a -> Pair a
    forall a. a -> a -> Pair a
    Pair (a
    a1 a -> a -> a
    forall a. Semigroup a => a -> a -> a
    Semi.<> a
    a2) (a
    b1 a -> a -> a
    forall a. Semigroup a => a -> a -> a
    Semi.<> a
    b2)

    instance (Semi.Semigroup a, Monoid a) => Monoid (Pair a) where
      mempty :: Pair a
    mempty = a -> a -> Pair a
    forall a. a -> a -> Pair a
    Pair a
    forall a. Monoid a => a
    mempty a
    forall a. Monoid a => a
    mempty
      mappend :: Pair a -> Pair a -> Pair a
    mappend = Pair a -> Pair a -> Pair a
    forall a. Semigroup a => a -> a -> a
    (Semi.<>)

    instance Outputable a => Outputable (Pair a) where
      ppr :: Pair a -> SDoc
    ppr (Pair a
    a a
    b) = a -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr a
    a SDoc -> SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc -> doc
    <+> Char -> SDoc
    forall doc. IsLine doc => Char -> doc
    char Char
    '~' SDoc -> SDoc -> SDoc
    forall doc. IsLine doc => doc -> doc -> doc
    <+> a -> SDoc
    forall a. Outputable a => a -> SDoc
    ppr a
    b

    unPair :: Pair a -> (a,a)
    unPair :: forall a. Pair a -> (a, a)
    unPair (Pair a
    x a
    y) = (a
    x,a
    y)

    toPair :: (a,a) -> Pair a
    toPair :: forall a. (a, a) -> Pair a
    toPair (a
    x,a
    y) = a -> a -> Pair a
    forall a. a -> a -> Pair a
    Pair a
    x a
    y

    swap :: Pair a -> Pair a
    swap :: forall a. Pair a -> Pair a
    swap (Pair a
    x a
    y) = a -> a -> Pair a
    forall a. a -> a -> Pair a
    Pair a
    y a
    x

    pLiftFst :: (a -> a) -> Pair a -> Pair a
    pLiftFst :: forall a. (a -> a) -> Pair a -> Pair a
    pLiftFst a -> a
    f (Pair a
    a a
    b) = a -> a -> Pair a
    forall a. a -> a -> Pair a
    Pair (a -> a
    f a
    a) a
    b

    pLiftSnd :: (a -> a) -> Pair a -> Pair a
    pLiftSnd :: forall a. (a -> a) -> Pair a -> Pair a
    pLiftSnd a -> a
    f (Pair a
    a a
    b) = a -> a -> Pair a
    forall a. a -> a -> Pair a
    Pair a
    a (a -> a
    f a
    b)

    unzipPairs :: [Pair a] -> ([a], [a])
    unzipPairs :: forall a. [Pair a] -> ([a], [a])
    unzipPairs [] = ([], [])
    unzipPairs (Pair a
    a a
    b : [Pair a]
    prs) = (a
    aa -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    as, a
    ba -> [a] -> [a]
    forall a. a -> [a] -> [a]
    :[a]
    bs)
      where
        !([a]
    as,[a]
    bs) = [Pair a] -> ([a], [a])
    forall a. [Pair a] -> ([a], [a])
    unzipPairs [Pair a]
    prs
        -- This makes the unzip work eagerly, building no thunks at
        -- the cost of doing all the work up-front.