{-# LANGUAGE RankNTypes, ScopedTypeVariables, CPP #-}
-----------------------------------------------------------------------------
-- |
-- Module      :  Data.Generics.Twins
-- Copyright   :  (c) The University of Glasgow, CWI 2001--2004
-- License     :  BSD-style (see the LICENSE file)
--
-- Maintainer  :  generics@haskell.org
-- Stability   :  experimental
-- Portability :  non-portable (local universal quantification)
--
-- \"Scrap your boilerplate\" --- Generic programming in Haskell
-- See <http://www.cs.uu.nl/wiki/GenericProgramming/SYB>. The present module
-- provides support for multi-parameter traversal, which is also
-- demonstrated with generic operations like equality.
--
-----------------------------------------------------------------------------

module Data.Generics.Twins (

        -- * Generic folds and maps that also accumulate
        gfoldlAccum,
        gmapAccumT,
        gmapAccumM,
        gmapAccumQl,
        gmapAccumQr,
        gmapAccumQ,
        gmapAccumA,

        -- * Mapping combinators for twin traversal
        gzipWithT,
        gzipWithM,
        gzipWithQ,

        -- * Typical twin traversals
        geq,
        gzip,
        gcompare

  ) where


------------------------------------------------------------------------------

#ifdef __HADDOCK__
import Prelude
#endif
import Data.Data
import Data.Generics.Aliases

#ifdef __GLASGOW_HASKELL__
import Prelude hiding ( GT )
#endif

#if __GLASGOW_HASKELL__ < 709
import Control.Applicative (Applicative(..))
import Data.Monoid         ( mappend, mconcat )
#endif

------------------------------------------------------------------------------


------------------------------------------------------------------------------
--
--      Generic folds and maps that also accumulate
--
------------------------------------------------------------------------------

{--------------------------------------------------------------

A list map can be elaborated to perform accumulation.
In the same sense, we can elaborate generic maps over terms.

We recall the type of map:
map :: (a -> b) -> [a] -> [b]

We recall the type of an accumulating map (see Data.List):
mapAccumL :: (a -> b -> (a,c)) -> a -> [b] -> (a,[c])

Applying the same scheme we obtain an accumulating gfoldl.

--------------------------------------------------------------}

-- | gfoldl with accumulation

gfoldlAccum :: Data d
            => (forall e r. Data e => a -> c (e -> r) -> e -> (a, c r))
            -> (forall g. a -> g -> (a, c g))
            -> a -> d -> (a, c d)

gfoldlAccum :: forall d a (c :: * -> *).
Data d =>
(forall e r. Data e => a -> c (e -> r) -> e -> (a, c r))
-> (forall g. a -> g -> (a, c g)) -> a -> d -> (a, c d)
gfoldlAccum forall e r. Data e => a -> c (e -> r) -> e -> (a, c r)
k forall g. a -> g -> (a, c g)
z a
a0 d
d = forall a (c :: * -> *) d. A a c d -> a -> (a, c d)
unA (forall a (c :: * -> *).
Data a =>
(forall d b. Data d => c (d -> b) -> d -> c b)
-> (forall g. g -> c g) -> a -> c a
gfoldl forall {e} {d}. Data e => A a c (e -> d) -> e -> A a c d
k' forall {d}. d -> A a c d
z' d
d) a
a0
 where
  k' :: A a c (e -> d) -> e -> A a c d
k' A a c (e -> d)
c e
y = forall a (c :: * -> *) d. (a -> (a, c d)) -> A a c d
A (\a
a -> let (a
a', c (e -> d)
c') = forall a (c :: * -> *) d. A a c d -> a -> (a, c d)
unA A a c (e -> d)
c a
a in forall e r. Data e => a -> c (e -> r) -> e -> (a, c r)
k a
a' c (e -> d)
c' e
y)
  z' :: d -> A a c d
z' d
f   = forall a (c :: * -> *) d. (a -> (a, c d)) -> A a c d
A (\a
a -> forall g. a -> g -> (a, c g)
z a
a d
f)


-- | A type constructor for accumulation
newtype A a c d = A { forall a (c :: * -> *) d. A a c d -> a -> (a, c d)
unA :: a -> (a, c d) }


-- | gmapT with accumulation
gmapAccumT :: Data d
           => (forall e. Data e => a -> e -> (a,e))
           -> a -> d -> (a, d)
gmapAccumT :: forall d a.
Data d =>
(forall e. Data e => a -> e -> (a, e)) -> a -> d -> (a, d)
gmapAccumT forall e. Data e => a -> e -> (a, e)
f a
a0 d
d0 = let (a
a1, ID d
d1) = forall d a (c :: * -> *).
Data d =>
(forall e r. Data e => a -> c (e -> r) -> e -> (a, c r))
-> (forall g. a -> g -> (a, c g)) -> a -> d -> (a, c d)
gfoldlAccum forall {t} {x}. Data t => a -> ID (t -> x) -> t -> (a, ID x)
k forall {a} {x}. a -> x -> (a, ID x)
z a
a0 d
d0
                     in (a
a1, forall x. ID x -> x
unID ID d
d1)
 where
  k :: a -> ID (t -> x) -> t -> (a, ID x)
k a
a (ID t -> x
c) t
d = let (a
a',t
d') = forall e. Data e => a -> e -> (a, e)
f a
a t
d
                  in (a
a', forall x. x -> ID x
ID (t -> x
c t
d'))
  z :: a -> x -> (a, ID x)
z a
a x
x = (a
a, forall x. x -> ID x
ID x
x)


-- | Applicative version
gmapAccumA :: forall b d a. (Data d, Applicative a)
           => (forall e. Data e => b -> e -> (b, a e))
           -> b -> d -> (b, a d)
gmapAccumA :: forall b d (a :: * -> *).
(Data d, Applicative a) =>
(forall e. Data e => b -> e -> (b, a e)) -> b -> d -> (b, a d)
gmapAccumA forall e. Data e => b -> e -> (b, a e)
f b
a0 d
d0 = forall d a (c :: * -> *).
Data d =>
(forall e r. Data e => a -> c (e -> r) -> e -> (a, c r))
-> (forall g. a -> g -> (a, c g)) -> a -> d -> (a, c d)
gfoldlAccum forall d' e. Data d' => b -> a (d' -> e) -> d' -> (b, a e)
k forall t c (a' :: * -> *). Applicative a' => t -> c -> (t, a' c)
z b
a0 d
d0
    where
      k :: forall d' e. (Data d') =>
           b -> a (d' -> e) -> d' -> (b, a e)
      k :: forall d' e. Data d' => b -> a (d' -> e) -> d' -> (b, a e)
k b
a a (d' -> e)
c d'
d = let (b
a',a d'
d') = forall e. Data e => b -> e -> (b, a e)
f b
a d'
d
                    c' :: a e
c' = a (d' -> e)
c forall (f :: * -> *) a b. Applicative f => f (a -> b) -> f a -> f b
<*> a d'
d'
                in (b
a', a e
c')
      z :: forall t c a'. (Applicative a') =>
           t -> c -> (t, a' c)
      z :: forall t c (a' :: * -> *). Applicative a' => t -> c -> (t, a' c)
z t
a c
x = (t
a, forall (f :: * -> *) a. Applicative f => a -> f a
pure c
x)


-- | gmapM with accumulation
gmapAccumM :: (Data d, Monad m)
           => (forall e. Data e => a -> e -> (a, m e))
           -> a -> d -> (a, m d)
gmapAccumM :: forall d (m :: * -> *) a.
(Data d, Monad m) =>
(forall e. Data e => a -> e -> (a, m e)) -> a -> d -> (a, m d)
gmapAccumM forall e. Data e => a -> e -> (a, m e)
f = forall d a (c :: * -> *).
Data d =>
(forall e r. Data e => a -> c (e -> r) -> e -> (a, c r))
-> (forall g. a -> g -> (a, c g)) -> a -> d -> (a, c d)
gfoldlAccum forall {t} {b}. Data t => a -> m (t -> b) -> t -> (a, m b)
k forall {m :: * -> *} {a} {a}. Monad m => a -> a -> (a, m a)
z
 where
  k :: a -> m (t -> b) -> t -> (a, m b)
k a
a m (t -> b)
c t
d = let (a
a',m t
d') = forall e. Data e => a -> e -> (a, m e)
f a
a t
d
             in (a
a', m t
d' forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \t
d'' -> m (t -> b)
c forall (m :: * -> *) a b. Monad m => m a -> (a -> m b) -> m b
>>= \t -> b
c' -> forall (m :: * -> *) a. Monad m => a -> m a
return (t -> b
c' t
d''))
  z :: a -> a -> (a, m a)
z a
a a
x = (a
a, forall (m :: * -> *) a. Monad m => a -> m a
return a
x)


-- | gmapQl with accumulation
gmapAccumQl :: Data d
            => (r -> r' -> r)
            -> r
            -> (forall e. Data e => a -> e -> (a,r'))
            -> a -> d -> (a, r)
gmapAccumQl :: forall d r r' a.
Data d =>
(r -> r' -> r)
-> r -> (forall e. Data e => a -> e -> (a, r')) -> a -> d -> (a, r)
gmapAccumQl r -> r' -> r
o r
r0 forall e. Data e => a -> e -> (a, r')
f a
a0 d
d0 = let (a
a1, CONST r d
r1) = forall d a (c :: * -> *).
Data d =>
(forall e r. Data e => a -> c (e -> r) -> e -> (a, c r))
-> (forall g. a -> g -> (a, c g)) -> a -> d -> (a, c d)
gfoldlAccum forall {p} {a} {a}. Data p => a -> CONST r a -> p -> (a, CONST r a)
k forall {a} {p} {a}. a -> p -> (a, CONST r a)
z a
a0 d
d0
                           in (a
a1, forall c a. CONST c a -> c
unCONST CONST r d
r1)
 where
  k :: a -> CONST r a -> p -> (a, CONST r a)
k a
a (CONST r
c) p
d = let (a
a', r'
r) = forall e. Data e => a -> e -> (a, r')
f a
a p
d
                     in (a
a', forall c a. c -> CONST c a
CONST (r
c r -> r' -> r
`o` r'
r))
  z :: a -> p -> (a, CONST r a)
z a
a p
_ = (a
a, forall c a. c -> CONST c a
CONST r
r0)


-- | gmapQr with accumulation
gmapAccumQr :: Data d
            => (r' -> r -> r)
            -> r
            -> (forall e. Data e => a -> e -> (a,r'))
            -> a -> d -> (a, r)
gmapAccumQr :: forall d r' r a.
Data d =>
(r' -> r -> r)
-> r -> (forall e. Data e => a -> e -> (a, r')) -> a -> d -> (a, r)
gmapAccumQr r' -> r -> r
o r
r0 forall e. Data e => a -> e -> (a, r')
f a
a0 d
d0 = let (a
a1, Qr r d
l) = forall d a (c :: * -> *).
Data d =>
(forall e r. Data e => a -> c (e -> r) -> e -> (a, c r))
-> (forall g. a -> g -> (a, c g)) -> a -> d -> (a, c d)
gfoldlAccum forall {p} {a} {a}. Data p => a -> Qr r a -> p -> (a, Qr r a)
k forall {a} {p} {r} {a}. a -> p -> (a, Qr r a)
z a
a0 d
d0
                           in (a
a1, forall r a. Qr r a -> r -> r
unQr Qr r d
l r
r0)
 where
  k :: a -> Qr r a -> p -> (a, Qr r a)
k a
a (Qr r -> r
c) p
d = let (a
a',r'
r') = forall e. Data e => a -> e -> (a, r')
f a
a p
d
                  in (a
a', forall r a. (r -> r) -> Qr r a
Qr (\r
r -> r -> r
c (r'
r' r' -> r -> r
`o` r
r)))
  z :: a -> p -> (a, Qr r a)
z a
a p
_ = (a
a, forall r a. (r -> r) -> Qr r a
Qr forall a. a -> a
id)


-- | gmapQ with accumulation
gmapAccumQ :: Data d
           => (forall e. Data e => a -> e -> (a,q))
           -> a -> d -> (a, [q])
gmapAccumQ :: forall d a q.
Data d =>
(forall e. Data e => a -> e -> (a, q)) -> a -> d -> (a, [q])
gmapAccumQ forall e. Data e => a -> e -> (a, q)
f = forall d r' r a.
Data d =>
(r' -> r -> r)
-> r -> (forall e. Data e => a -> e -> (a, r')) -> a -> d -> (a, r)
gmapAccumQr (:) [] forall e. Data e => a -> e -> (a, q)
f



------------------------------------------------------------------------------
--
--      Helper type constructors
--
------------------------------------------------------------------------------


-- | The identity type constructor needed for the definition of gmapAccumT
newtype ID x = ID { forall x. ID x -> x
unID :: x }


-- | The constant type constructor needed for the definition of gmapAccumQl
newtype CONST c a = CONST { forall c a. CONST c a -> c
unCONST :: c }


-- | The type constructor needed for the definition of gmapAccumQr
newtype Qr r a = Qr { forall r a. Qr r a -> r -> r
unQr  :: r -> r }



------------------------------------------------------------------------------
--
--      Mapping combinators for twin traversal
--
------------------------------------------------------------------------------


-- | Twin map for transformation
gzipWithT :: GenericQ (GenericT) -> GenericQ (GenericT)
gzipWithT :: GenericQ GenericT -> GenericQ GenericT
gzipWithT GenericQ GenericT
f a
x a
y = case forall d a.
Data d =>
(forall e. Data e => a -> e -> (a, e)) -> a -> d -> (a, d)
gmapAccumT forall {b}. Data b => [GenericT'] -> b -> ([GenericT'], b)
perkid [GenericT']
funs a
y of
                    ([], a
c) -> a
c
                    ([GenericT'], a)
_       -> forall a. HasCallStack => [Char] -> a
error [Char]
"gzipWithT"
 where
  perkid :: [GenericT'] -> b -> ([GenericT'], b)
perkid [GenericT']
a b
d = (forall a. [a] -> [a]
tail [GenericT']
a, GenericT' -> GenericT
unGT (forall a. [a] -> a
head [GenericT']
a) b
d)
  funs :: [GenericT']
funs = forall a u. Data a => (forall d. Data d => d -> u) -> a -> [u]
gmapQ (\d
k -> GenericT -> GenericT'
GT (GenericQ GenericT
f d
k)) a
x



-- | Twin map for monadic transformation
gzipWithM :: Monad m => GenericQ (GenericM m) -> GenericQ (GenericM m)
gzipWithM :: forall (m :: * -> *).
Monad m =>
GenericQ (GenericM m) -> GenericQ (GenericM m)
gzipWithM GenericQ (GenericM m)
f a
x a
y = case forall d (m :: * -> *) a.
(Data d, Monad m) =>
(forall e. Data e => a -> e -> (a, m e)) -> a -> d -> (a, m d)
gmapAccumM forall {a} {m :: * -> *}.
Data a =>
[GenericM' m] -> a -> ([GenericM' m], m a)
perkid [GenericM' m]
funs a
y of
                    ([], m a
c) -> m a
c
                    ([GenericM' m], m a)
_       -> forall a. HasCallStack => [Char] -> a
error [Char]
"gzipWithM"
 where
  perkid :: [GenericM' m] -> a -> ([GenericM' m], m a)
perkid [GenericM' m]
a a
d = (forall a. [a] -> [a]
tail [GenericM' m]
a, forall (m :: * -> *). GenericM' m -> forall a. Data a => a -> m a
unGM (forall a. [a] -> a
head [GenericM' m]
a) a
d)
  funs :: [GenericM' m]
funs = forall a u. Data a => (forall d. Data d => d -> u) -> a -> [u]
gmapQ (\d
k -> forall (m :: * -> *). (forall a. Data a => a -> m a) -> GenericM' m
GM (GenericQ (GenericM m)
f d
k)) a
x


-- | Twin map for queries
gzipWithQ :: GenericQ (GenericQ r) -> GenericQ (GenericQ [r])
gzipWithQ :: forall r. GenericQ (GenericQ r) -> GenericQ (GenericQ [r])
gzipWithQ GenericQ (GenericQ r)
f a
x a
y = case forall d a q.
Data d =>
(forall e. Data e => a -> e -> (a, q)) -> a -> d -> (a, [q])
gmapAccumQ forall {a} {b}. Data a => [GenericQ' b] -> a -> ([GenericQ' b], b)
perkid [GenericQ' r]
funs a
y of
                   ([], [r]
r) -> [r]
r
                   ([GenericQ' r], [r])
_       -> forall a. HasCallStack => [Char] -> a
error [Char]
"gzipWithQ"
 where
  perkid :: [GenericQ' b] -> a -> ([GenericQ' b], b)
perkid [GenericQ' b]
a a
d = (forall a. [a] -> [a]
tail [GenericQ' b]
a, forall r. GenericQ' r -> GenericQ r
unGQ (forall a. [a] -> a
head [GenericQ' b]
a) a
d)
  funs :: [GenericQ' r]
funs = forall a u. Data a => (forall d. Data d => d -> u) -> a -> [u]
gmapQ (\d
k -> forall r. GenericQ r -> GenericQ' r
GQ (GenericQ (GenericQ r)
f d
k)) a
x



------------------------------------------------------------------------------
--
--      Typical twin traversals
--
------------------------------------------------------------------------------

-- | Generic equality: an alternative to \"deriving Eq\"
geq :: Data a => a -> a -> Bool

{-

Testing for equality of two terms goes like this. Firstly, we
establish the equality of the two top-level datatype
constructors. Secondly, we use a twin gmap combinator, namely tgmapQ,
to compare the two lists of immediate subterms.

(Note for the experts: the type of the worker geq' is rather general
but precision is recovered via the restrictive type of the top-level
operation geq. The imprecision of geq' is caused by the type system's
unability to express the type equivalence for the corresponding
couples of immediate subterms from the two given input terms.)

-}

geq :: forall a. Data a => a -> a -> Bool
geq a
x0 a
y0 = GenericQ (GenericQ Bool)
geq' a
x0 a
y0
  where
    geq' :: GenericQ (GenericQ Bool)
    geq' :: GenericQ (GenericQ Bool)
geq' a
x a
y =     (forall a. Data a => a -> Constr
toConstr a
x forall a. Eq a => a -> a -> Bool
== forall a. Data a => a -> Constr
toConstr a
y)
                Bool -> Bool -> Bool
&& forall (t :: * -> *). Foldable t => t Bool -> Bool
and (forall r. GenericQ (GenericQ r) -> GenericQ (GenericQ [r])
gzipWithQ GenericQ (GenericQ Bool)
geq' a
x a
y)


-- | Generic zip controlled by a function with type-specific branches
gzip :: GenericQ (GenericM Maybe) -> GenericQ (GenericM Maybe)
-- See testsuite/.../Generics/gzip.hs for an illustration
gzip :: GenericQ (GenericM Maybe) -> GenericQ (GenericM Maybe)
gzip GenericQ (GenericM Maybe)
f = GenericQ (GenericM Maybe)
go
  where
    go :: GenericQ (GenericM Maybe)
    go :: GenericQ (GenericM Maybe)
go a
x a
y =
      GenericQ (GenericM Maybe)
f a
x a
y
      forall a. Maybe a -> Maybe a -> Maybe a
`orElse`
      if forall a. Data a => a -> Constr
toConstr a
x forall a. Eq a => a -> a -> Bool
== forall a. Data a => a -> Constr
toConstr a
y
        then forall (m :: * -> *).
Monad m =>
GenericQ (GenericM m) -> GenericQ (GenericM m)
gzipWithM GenericQ (GenericM Maybe)
go a
x a
y
        else forall a. Maybe a
Nothing

-- | Generic comparison: an alternative to \"deriving Ord\"
gcompare :: Data a => a -> a -> Ordering
gcompare :: forall a. Data a => a -> a -> Ordering
gcompare = forall a b. (Data a, Data b) => a -> b -> Ordering
gcompare'
  where
    gcompare' :: (Data a, Data b) => a -> b -> Ordering
    gcompare' :: forall a b. (Data a, Data b) => a -> b -> Ordering
gcompare' a
x b
y
      = let repX :: ConstrRep
repX = Constr -> ConstrRep
constrRep forall a b. (a -> b) -> a -> b
$ forall a. Data a => a -> Constr
toConstr a
x
            repY :: ConstrRep
repY = Constr -> ConstrRep
constrRep forall a b. (a -> b) -> a -> b
$ forall a. Data a => a -> Constr
toConstr b
y
        in
        case (ConstrRep
repX, ConstrRep
repY) of
          (AlgConstr ConIndex
nX,   AlgConstr ConIndex
nY)   ->
            ConIndex
nX forall a. Ord a => a -> a -> Ordering
`compare` ConIndex
nY forall a. Monoid a => a -> a -> a
`mappend` forall a. Monoid a => [a] -> a
mconcat (forall r. GenericQ (GenericQ r) -> GenericQ (GenericQ [r])
gzipWithQ (\a
a -> forall a b. (Data a, Data b) => a -> b -> Ordering
gcompare' a
a) a
x b
y)
          (IntConstr Integer
iX,   IntConstr Integer
iY)   -> Integer
iX forall a. Ord a => a -> a -> Ordering
`compare` Integer
iY
          (FloatConstr Rational
rX, FloatConstr Rational
rY) -> Rational
rX forall a. Ord a => a -> a -> Ordering
`compare` Rational
rY
          (CharConstr Char
cX,  CharConstr Char
cY)  -> Char
cX forall a. Ord a => a -> a -> Ordering
`compare` Char
cY
          (ConstrRep, ConstrRep)
_ -> forall a. HasCallStack => [Char] -> a
error [Char]
"type incompatibility in gcompare"