{-
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.