{-# LANGUAGE CPP #-}
#if __GLASGOW_HASKELL__ >= 702
{-# LANGUAGE Safe #-}
{-# LANGUAGE DeriveGeneric #-}
#endif
#if __GLASGOW_HASKELL__ >= 706
{-# LANGUAGE PolyKinds #-}
#endif
#if __GLASGOW_HASKELL__ >= 710 && __GLASGOW_HASKELL__ < 802
{-# LANGUAGE AutoDeriveTypeable #-}
#endif
-----------------------------------------------------------------------------
-- |
-- Module      :  Data.Functor.Reverse
-- Copyright   :  (c) Russell O'Connor 2009
-- License     :  BSD-style (see the file LICENSE)
--
-- Maintainer  :  R.Paterson@city.ac.uk
-- Stability   :  experimental
-- Portability :  portable
--
-- Making functors whose elements are notionally in the reverse order
-- from the original functor.
-----------------------------------------------------------------------------

module Data.Functor.Reverse (
    Reverse(..),
  ) where

import Control.Applicative.Backwards
#if MIN_VERSION_base(4,18,0)
import Data.Foldable1 (Foldable1(foldMap1))
#endif
import Data.Functor.Classes
#if MIN_VERSION_base(4,12,0)
import Data.Functor.Contravariant
#endif

import Prelude hiding (foldr, foldr1, foldl, foldl1, null, length)
import Control.Applicative
import Control.Monad
#if MIN_VERSION_base(4,9,0)
import qualified Control.Monad.Fail as Fail
#endif
import Data.Foldable
#if !(MIN_VERSION_base(4,8,0))
import Data.Traversable (Traversable(traverse))
#endif
import Data.Monoid
#if __GLASGOW_HASKELL__ >= 704
import GHC.Generics
#endif

-- | The same functor, but with 'Foldable' and 'Traversable' instances
-- that process the elements in the reverse order.
newtype Reverse f a = Reverse { forall {k} (f :: k -> *) (a :: k). Reverse f a -> f a
getReverse :: f a }
#if __GLASGOW_HASKELL__ >= 710
    deriving (forall a.
(forall x. a -> Rep a x) -> (forall x. Rep a x -> a) -> Generic a
forall k (f :: k -> *) (a :: k) x.
Rep (Reverse f a) x -> Reverse f a
forall k (f :: k -> *) (a :: k) x.
Reverse f a -> Rep (Reverse f a) x
$cto :: forall k (f :: k -> *) (a :: k) x.
Rep (Reverse f a) x -> Reverse f a
$cfrom :: forall k (f :: k -> *) (a :: k) x.
Reverse f a -> Rep (Reverse f a) x
Generic, forall k (f :: k -> *).
(forall (a :: k). f a -> Rep1 f a)
-> (forall (a :: k). Rep1 f a -> f a) -> Generic1 f
forall k (f :: k -> *) (a :: k). Rep1 (Reverse f) a -> Reverse f a
forall k (f :: k -> *) (a :: k). Reverse f a -> Rep1 (Reverse f) a
$cto1 :: forall k (f :: k -> *) (a :: k). Rep1 (Reverse f) a -> Reverse f a
$cfrom1 :: forall k (f :: k -> *) (a :: k). Reverse f a -> Rep1 (Reverse f) a
Generic1)
#elif __GLASGOW_HASKELL__ >= 704
    deriving (Generic)
#endif

instance (Eq1 f) => Eq1 (Reverse f) where
    liftEq :: forall a b. (a -> b -> Bool) -> Reverse f a -> Reverse f b -> Bool
liftEq a -> b -> Bool
eq (Reverse f a
x) (Reverse f b
y) = forall (f :: * -> *) a b.
Eq1 f =>
(a -> b -> Bool) -> f a -> f b -> Bool
liftEq a -> b -> Bool
eq f a
x f b
y
    {-# INLINE liftEq #-}

instance (Ord1 f) => Ord1 (Reverse f) where
    liftCompare :: forall a b.
(a -> b -> Ordering) -> Reverse f a -> Reverse f b -> Ordering
liftCompare a -> b -> Ordering
comp (Reverse f a
x) (Reverse f b
y) = forall (f :: * -> *) a b.
Ord1 f =>
(a -> b -> Ordering) -> f a -> f b -> Ordering
liftCompare a -> b -> Ordering
comp f a
x f b
y
    {-# INLINE liftCompare #-}

instance (Read1 f) => Read1 (Reverse f) where
    liftReadsPrec :: forall a.
(Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (Reverse f a)
liftReadsPrec Int -> ReadS a
rp ReadS [a]
rl = forall a. (String -> ReadS a) -> Int -> ReadS a
readsData forall a b. (a -> b) -> a -> b
$
        forall a t.
(Int -> ReadS a) -> String -> (a -> t) -> String -> ReadS t
readsUnaryWith (forall (f :: * -> *) a.
Read1 f =>
(Int -> ReadS a) -> ReadS [a] -> Int -> ReadS (f a)
liftReadsPrec Int -> ReadS a
rp ReadS [a]
rl) String
"Reverse" forall {k} (f :: k -> *) (a :: k). f a -> Reverse f a
Reverse

instance (Show1 f) => Show1 (Reverse f) where
    liftShowsPrec :: forall a.
(Int -> a -> ShowS)
-> ([a] -> ShowS) -> Int -> Reverse f a -> ShowS
liftShowsPrec Int -> a -> ShowS
sp [a] -> ShowS
sl Int
d (Reverse f a
x) =
        forall a. (Int -> a -> ShowS) -> String -> Int -> a -> ShowS
showsUnaryWith (forall (f :: * -> *) a.
Show1 f =>
(Int -> a -> ShowS) -> ([a] -> ShowS) -> Int -> f a -> ShowS
liftShowsPrec Int -> a -> ShowS
sp [a] -> ShowS
sl) String
"Reverse" Int
d f a
x

instance (Eq1 f, Eq a) => Eq (Reverse f a) where == :: Reverse f a -> Reverse f a -> Bool
(==) = forall (f :: * -> *) a. (Eq1 f, Eq a) => f a -> f a -> Bool
eq1
instance (Ord1 f, Ord a) => Ord (Reverse f a) where compare :: Reverse f a -> Reverse f a -> Ordering
compare = forall (f :: * -> *) a. (Ord1 f, Ord a) => f a -> f a -> Ordering
compare1
instance (Read1 f, Read a) => Read (Reverse f a) where readsPrec :: Int -> ReadS (Reverse f a)
readsPrec = forall (f :: * -> *) a. (Read1 f, Read a) => Int -> ReadS (f a)
readsPrec1
instance (Show1 f, Show a) => Show (Reverse f a) where showsPrec :: Int -> Reverse f a -> ShowS
showsPrec = forall (f :: * -> *) a. (Show1 f, Show a) => Int -> f a -> ShowS
showsPrec1

-- | Derived instance.
instance (Functor f) => Functor (Reverse f) where
    fmap :: forall a b. (a -> b) -> Reverse f a -> Reverse f b
fmap a -> b
f (Reverse f a
a) = forall {k} (f :: k -> *) (a :: k). f a -> Reverse f a
Reverse (forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap a -> b
f f a
a)
    {-# INLINE fmap #-}

-- | Derived instance.
instance (Applicative f) => Applicative (Reverse f) where
    pure :: forall a. a -> Reverse f a
pure a
a = forall {k} (f :: k -> *) (a :: k). f a -> Reverse f a
Reverse (forall (f :: * -> *) a. Applicative f => a -> f a
pure a
a)
    {-# INLINE pure #-}
    Reverse f (a -> b)
f <*> :: forall a b. Reverse f (a -> b) -> Reverse f a -> Reverse f b
<*> Reverse f a
a = forall {k} (f :: k -> *) (a :: k). f a -> Reverse f a
Reverse (f (a -> b)
f forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> f a
a)
    {-# INLINE (<*>) #-}

-- | Derived instance.
instance (Alternative f) => Alternative (Reverse f) where
    empty :: forall a. Reverse f a
empty = forall {k} (f :: k -> *) (a :: k). f a -> Reverse f a
Reverse forall (f :: * -> *) a. Alternative f => f a
empty
    {-# INLINE empty #-}
    Reverse f a
x <|> :: forall a. Reverse f a -> Reverse f a -> Reverse f a
<|> Reverse f a
y = forall {k} (f :: k -> *) (a :: k). f a -> Reverse f a
Reverse (f a
x forall (f :: * -> *) a. Alternative f => f a -> f a -> f a
<|> f a
y)
    {-# INLINE (<|>) #-}

-- | Derived instance.
instance (Monad m) => Monad (Reverse m) where
#if !(MIN_VERSION_base(4,8,0))
    return a = Reverse (return a)
    {-# INLINE return #-}
#endif
    Reverse m a
m >>= :: forall a b. Reverse m a -> (a -> Reverse m b) -> Reverse m b
>>= a -> Reverse m b
f = forall {k} (f :: k -> *) (a :: k). f a -> Reverse f a
Reverse (forall {k} (f :: k -> *) (a :: k). Reverse f a -> f a
getReverse Reverse m a
m forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= forall {k} (f :: k -> *) (a :: k). Reverse f a -> f a
getReverse forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> Reverse m b
f)
    {-# INLINE (>>=) #-}
#if !(MIN_VERSION_base(4,13,0))
    fail msg = Reverse (fail msg)
    {-# INLINE fail #-}
#endif

#if MIN_VERSION_base(4,9,0)
instance (Fail.MonadFail m) => Fail.MonadFail (Reverse m) where
    fail :: forall a. String -> Reverse m a
fail String
msg = forall {k} (f :: k -> *) (a :: k). f a -> Reverse f a
Reverse (forall (m :: * -> *) a. MonadFail m => String -> m a
Fail.fail String
msg)
    {-# INLINE fail #-}
#endif

-- | Derived instance.
instance (MonadPlus m) => MonadPlus (Reverse m) where
    mzero :: forall a. Reverse m a
mzero = forall {k} (f :: k -> *) (a :: k). f a -> Reverse f a
Reverse forall (m :: * -> *) a. MonadPlus m => m a
mzero
    {-# INLINE mzero #-}
    Reverse m a
x mplus :: forall a. Reverse m a -> Reverse m a -> Reverse m a
`mplus` Reverse m a
y = forall {k} (f :: k -> *) (a :: k). f a -> Reverse f a
Reverse (m a
x forall (m :: * -> *) a. MonadPlus m => m a -> m a -> m a
`mplus` m a
y)
    {-# INLINE mplus #-}

-- | Fold from right to left.
instance (Foldable f) => Foldable (Reverse f) where
    foldMap :: forall m a. Monoid m => (a -> m) -> Reverse f a -> m
foldMap a -> m
f (Reverse f a
t) = forall a. Dual a -> a
getDual (forall (t :: * -> *) m a.
(Foldable t, Monoid m) =>
(a -> m) -> t a -> m
foldMap (forall a. a -> Dual a
Dual forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> m
f) f a
t)
    {-# INLINE foldMap #-}
    foldr :: forall a b. (a -> b -> b) -> b -> Reverse f a -> b
foldr a -> b -> b
f b
z (Reverse f a
t) = forall (t :: * -> *) b a.
Foldable t =>
(b -> a -> b) -> b -> t a -> b
foldl (forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> b -> b
f) b
z f a
t
    {-# INLINE foldr #-}
    foldl :: forall b a. (b -> a -> b) -> b -> Reverse f a -> b
foldl b -> a -> b
f b
z (Reverse f a
t) = forall (t :: * -> *) a b.
Foldable t =>
(a -> b -> b) -> b -> t a -> b
foldr (forall a b c. (a -> b -> c) -> b -> a -> c
flip b -> a -> b
f) b
z f a
t
    {-# INLINE foldl #-}
    foldr1 :: forall a. (a -> a -> a) -> Reverse f a -> a
foldr1 a -> a -> a
f (Reverse f a
t) = forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
foldl1 (forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> a -> a
f) f a
t
    {-# INLINE foldr1 #-}
    foldl1 :: forall a. (a -> a -> a) -> Reverse f a -> a
foldl1 a -> a -> a
f (Reverse f a
t) = forall (t :: * -> *) a. Foldable t => (a -> a -> a) -> t a -> a
foldr1 (forall a b c. (a -> b -> c) -> b -> a -> c
flip a -> a -> a
f) f a
t
    {-# INLINE foldl1 #-}
#if MIN_VERSION_base(4,8,0)
    null :: forall a. Reverse f a -> Bool
null (Reverse f a
t) = forall (t :: * -> *) a. Foldable t => t a -> Bool
null f a
t
    length :: forall a. Reverse f a -> Int
length (Reverse f a
t) = forall (t :: * -> *) a. Foldable t => t a -> Int
length f a
t
#endif

#if MIN_VERSION_base(4,18,0)
-- | Fold from right to left.
instance (Foldable1 f) => Foldable1 (Reverse f) where
    foldMap1 f (Reverse t) = getDual (foldMap1 (Dual . f) t)
#endif

-- | Traverse from right to left.
instance (Traversable f) => Traversable (Reverse f) where
    traverse :: forall (f :: * -> *) a b.
Applicative f =>
(a -> f b) -> Reverse f a -> f (Reverse f b)
traverse a -> f b
f (Reverse f a
t) =
        forall (f :: * -> *) a b. Functor f => (a -> b) -> f a -> f b
fmap forall {k} (f :: k -> *) (a :: k). f a -> Reverse f a
Reverse forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall {k} (f :: k -> *) (a :: k). Backwards f a -> f a
forwards forall a b. (a -> b) -> a -> b
$ forall (t :: * -> *) (f :: * -> *) a b.
(Traversable t, Applicative f) =>
(a -> f b) -> t a -> f (t b)
traverse (forall {k} (f :: k -> *) (a :: k). f a -> Backwards f a
Backwards forall b c a. (b -> c) -> (a -> b) -> a -> c
. a -> f b
f) f a
t
    {-# INLINE traverse #-}

#if MIN_VERSION_base(4,12,0)
-- | Derived instance.
instance (Contravariant f) => Contravariant (Reverse f) where
    contramap :: forall a' a. (a' -> a) -> Reverse f a -> Reverse f a'
contramap a' -> a
f = forall {k} (f :: k -> *) (a :: k). f a -> Reverse f a
Reverse forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall (f :: * -> *) a' a.
Contravariant f =>
(a' -> a) -> f a -> f a'
contramap a' -> a
f forall b c a. (b -> c) -> (a -> b) -> a -> c
. forall {k} (f :: k -> *) (a :: k). Reverse f a -> f a
getReverse
    {-# INLINE contramap #-}
#endif