-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Generic programming for families of recursive datatypes
--   
--   Many generic programs require information about the recursive
--   positions of a datatype. Examples include the generic fold, generic
--   rewriting or the Zipper data structure. Several generic programming
--   systems allow to write such functions by viewing datatypes as fixed
--   points of a pattern functor. Traditionally, this view has been limited
--   to so-called regular datatypes such as lists and binary trees. In
--   particular, families of mutually recursive datatypes have been
--   excluded.
--   
--   With the multirec library, we provide a mechanism to talk about fixed
--   points of families of datatypes that may be mutually recursive. On top
--   of this representations, generic functions such as the fold or the
--   Zipper can then be defined.
--   
--   We expect that the library will be especially interesting for compiler
--   writers, because ASTs are typically families of mutually recursive
--   datatypes, and with multirec it becomes easy to write generic
--   functions on ASTs.
--   
--   The library is based on ideas described in the paper:
--   
--   <ul>
--   <li>Alexey Rodriguez, Stefan Holdermans, Andres Löh, Johan Jeuring.
--   <i>Generic programming with fixed points for mutually recursive
--   datatypes</i>. ICFP 2009.</li>
--   </ul>
@package multirec
@version 0.7


-- | Type-level equality. This module is currently provided by the multirec
--   library, even though it is more general and does not really belong
--   here.
module Generics.MultiRec.TEq
data (:=:) :: * -> * -> *
Refl :: a :=: a
cast :: a :=: b -> a -> b


-- | This module contains a class for datatypes that represent data
--   constructors.
module Generics.MultiRec.Constructor

-- | Class for datatypes that represent data constructors. For non-symbolic
--   constructors, only <a>conName</a> has to be defined. The weird
--   argument is supposed to be instantiated with <tt>C</tt> from base,
--   hence the complex kind.
class Constructor c
conName :: Constructor c => t c (f :: (* -> *) -> * -> *) (r :: * -> *) ix -> String
conFixity :: Constructor c => t c (f :: (* -> *) -> * -> *) (r :: * -> *) ix -> Fixity

-- | Datatype to represent the fixity of a constructor. An infix
--   declaration directly corresponds to an application of <a>Infix</a>.
data Fixity
Prefix :: Fixity
Infix :: Associativity -> Int -> Fixity
data Associativity
LeftAssociative :: Associativity
RightAssociative :: Associativity
NotAssociative :: Associativity
instance Eq Associativity
instance Show Associativity
instance Ord Associativity
instance Read Associativity
instance Eq Fixity
instance Show Fixity
instance Ord Fixity
instance Read Fixity


-- | This module is the base of the multirec library. It defines the view
--   of a family of datatypes: All the datatypes of the family are
--   represented as indexed functors that are built up from the structure
--   types defined in this module. Furthermore, in order to use the library
--   for a family, conversion functions have to be defined between the
--   original datatypes and their representation. The type class that holds
--   these conversion functions are also defined here.
module Generics.MultiRec.Base

-- | Represents recursive positions. The first argument indicates which
--   type to recurse on.
data I xi r :: (* -> *) ix
I :: r xi -> I xi ix
unI :: I xi ix -> r xi

-- | Represents constant types that do not belong to the family.
data K a r :: (* -> *) ix
K :: a -> K a ix
unK :: K a ix -> a

-- | Represents constructors without fields.
data U r :: (* -> *) ix
U :: U ix

-- | Represents sums (choices between constructors).
data (:+:) f g r :: (* -> *) ix
L :: (f r ix) -> :+: f g ix
R :: (g r ix) -> :+: f g ix

-- | Represents products (sequences of fields of a constructor).
data (:*:) f g r :: (* -> *) ix
(:*:) :: f r ix -> g r ix -> :*: f g ix

-- | Is used to indicate the type that a particular constructor injects to.
data (:>:) f ix :: (* -> *) -> * -> *
Tag :: f r ix -> (f :>: ix) r ix

-- | Destructor for '(:&gt;:)'.
unTag :: (f :>: ix) r ix -> f r ix

-- | Represents composition with functors of kind * -&gt; *.
data (:.:) f g r :: (* -> *) ix
D :: f (g r ix) -> :.: f g ix
unD :: :.: f g ix -> f (g r ix)

-- | Represents constructors.
data C c f r :: (* -> *) ix
C :: f r ix -> C c f r ix

-- | Destructor for <a>C</a>.
unC :: C c f r ix -> f r ix

-- | Unlifted version of <a>I</a>.
newtype I0 a
I0 :: a -> I0 a
unI0 :: I0 a -> a

-- | Unlifted version of <a>K</a>.
newtype K0 a b
K0 :: a -> K0 a b
unK0 :: K0 a b -> a

-- | Type family describing the pattern functor of a family.

-- | Class for the members of a family.
class El phi ix
proof :: El phi ix => phi ix

-- | Class that contains the shallow conversion functions for a family.
class Fam phi
from :: Fam phi => phi ix -> ix -> PF phi I0 ix
to :: Fam phi => phi ix -> PF phi I0 ix -> ix

-- | For backwards-compatibility: a synonym for <a>proof</a>.
index :: El phi ix => phi ix

-- | Semi-decidable equality for types of a family.
class EqS phi
eqS :: EqS phi => phi ix -> phi ix' -> Maybe (ix :=: ix')
instance Functor (K0 a)
instance Applicative I0
instance Functor I0


-- | The definition of functorial map.
module Generics.MultiRec.HFunctor
class HFunctor phi f
hmapA :: (HFunctor phi f, Applicative a) => (forall ix. phi ix -> r ix -> a (r' ix)) -> phi ix -> f r ix -> a (f r' ix)

-- | The function <a>hmap</a> takes a functor <tt>f</tt>. All the recursive
--   instances in that functor are wrapped by an application of <tt>r</tt>.
--   The argument to <a>hmap</a> takes a function that transformes
--   <tt>r</tt> occurrences into <tt>r'</tt> occurrences, for every
--   <tt>ix</tt>. In order to associate the index <tt>ix</tt> with the
--   correct family <tt>phi</tt>, the argument to <tt>hmap</tt> is
--   additionally parameterized by a witness of type <tt>phi ix</tt>.
hmap :: HFunctor phi f => (forall ix. phi ix -> r ix -> r' ix) -> phi ix -> f r ix -> f r' ix

-- | Monadic version of <a>hmap</a>.
hmapM :: (HFunctor phi f, Monad m) => (forall ix. phi ix -> r ix -> m (r' ix)) -> phi ix -> f r ix -> m (f r' ix)
instance (Constructor c, HFunctor phi f) => HFunctor phi (C c f)
instance (Traversable f, HFunctor phi g) => HFunctor phi (f :.: g)
instance HFunctor phi f => HFunctor phi (f :>: ix)
instance (HFunctor phi f, HFunctor phi g) => HFunctor phi (f :*: g)
instance (HFunctor phi f, HFunctor phi g) => HFunctor phi (f :+: g)
instance HFunctor phi U
instance HFunctor phi (K x)
instance El phi xi => HFunctor phi (I xi)


-- | The definition of generic fold, unfold, paramorphisms. In addition,
--   some combinators that facilitate the construction of algebras.
--   
--   There are several variants of fold in other modules that are probably
--   easier to use:
--   
--   <ul>
--   <li>for folds with constant return type, look at
--   <a>Generics.MultiRec.FoldAlgK</a> (or
--   <a>Generics.MultiRec.FoldK</a>),</li>
--   <li>for folds with convenient algebras, look at
--   <a>Generics.MultiRec.FoldAlg</a>.</li>
--   </ul>
module Generics.MultiRec.Fold
type Algebra' phi f r = forall ix. phi ix -> f r ix -> r ix
type Algebra phi r = Algebra' phi (PF phi) r
type AlgebraF' phi f g r = forall ix. phi ix -> f r ix -> g (r ix)
type AlgebraF phi g r = AlgebraF' phi (PF phi) g r
fold :: (Fam phi, HFunctor phi (PF phi)) => Algebra phi r -> phi ix -> ix -> r ix
foldM :: (Fam phi, HFunctor phi (PF phi), Monad m) => AlgebraF phi m r -> phi ix -> ix -> m (r ix)
type CoAlgebra' phi f r = forall ix. phi ix -> r ix -> f r ix
type CoAlgebra phi r = CoAlgebra' phi (PF phi) r
type CoAlgebraF' phi f g r = forall ix. phi ix -> r ix -> g (f r ix)
type CoAlgebraF phi g r = CoAlgebraF' phi (PF phi) g r
unfold :: (Fam phi, HFunctor phi (PF phi)) => CoAlgebra phi r -> phi ix -> r ix -> ix
unfoldM :: (Fam phi, HFunctor phi (PF phi), Monad m) => CoAlgebraF phi m r -> phi ix -> r ix -> m ix
type ParaAlgebra' phi f r = forall ix. phi ix -> f r ix -> ix -> r ix
type ParaAlgebra phi r = ParaAlgebra' phi (PF phi) r
type ParaAlgebraF' phi f g r = forall ix. phi ix -> f r ix -> ix -> g (r ix)
type ParaAlgebraF phi g r = ParaAlgebraF' phi (PF phi) g r
para :: (Fam phi, HFunctor phi (PF phi)) => ParaAlgebra phi r -> phi ix -> ix -> r ix
paraM :: (Fam phi, HFunctor phi (PF phi), Monad m) => ParaAlgebraF phi m r -> phi ix -> ix -> m (r ix)
type AlgPart f r ix = f r ix -> r ix
type :-> f g r :: (* -> *) ix = f r ix -> g r ix
(&) :: (AlgPart a :-> (AlgPart b :-> AlgPart (a :+: b))) r ix
tag :: AlgPart a r ix -> AlgPart (a :>: ix) r ix'
con :: AlgPart a r ix -> AlgPart (C c a) r ix


-- | The compos operator, inspired by
--   
--   B. Bringert and A. Ranta A pattern for almost compositional functions
--   ICFP 2006
module Generics.MultiRec.Compos

-- | Normal version.
compos :: (Fam phi, HFunctor phi (PF phi)) => (forall ix. phi ix -> ix -> ix) -> phi ix -> ix -> ix

-- | Monadic version of <a>compos</a>.
composM :: (Fam phi, HFunctor phi (PF phi), Monad m) => (forall ix. phi ix -> ix -> m ix) -> phi ix -> ix -> m ix

-- | Applicative version of <a>compos</a>.
composA :: (Fam phi, HFunctor phi (PF phi), Applicative a) => (forall ix. phi ix -> ix -> a ix) -> phi ix -> ix -> a ix


-- | Generic equality.
module Generics.MultiRec.Eq
class HEq phi f
heq :: HEq phi f => (forall ix. phi ix -> r ix -> r ix -> Bool) -> phi ix -> f r ix -> f r ix -> Bool
class Eq1 f
eq1 :: Eq1 f => (a -> a -> Bool) -> f a -> f a -> Bool
eq :: (Fam phi, HEq phi (PF phi)) => phi ix -> ix -> ix -> Bool
instance (Constructor c, HEq phi f) => HEq phi (C c f)
instance HEq phi f => HEq phi (f :>: ix)
instance (Eq1 f, HEq phi g) => HEq phi (f :.: g)
instance (HEq phi f, HEq phi g) => HEq phi (f :*: g)
instance (HEq phi f, HEq phi g) => HEq phi (f :+: g)
instance HEq phi U
instance Eq a => HEq phi (K a)
instance El phi xi => HEq phi (I xi)
instance Eq1 Maybe
instance Eq1 []


-- | Higher-order fixed point operator as well as conversion functions. It
--   is rarely necessary to use <a>HFix</a>. Generic functions usually
--   convert between the original datatype and the functor directly.
module Generics.MultiRec.HFix
data HFix h :: ((* -> *) -> * -> *) ix
HIn :: h (HFix h) ix -> HFix ix
hout :: HFix ix -> h (HFix h) ix
hfrom :: (Fam phi, HFunctor phi (PF phi)) => phi ix -> ix -> HFix (PF phi) ix
hto :: (Fam phi, HFunctor phi (PF phi)) => phi ix -> HFix (PF phi) ix -> ix


-- | This module contains Template Haskell code that can be used to
--   automatically generate the boilerplate code for the multirec library.
--   The constructor information can be generated per datatype, the rest
--   per family of datatypes.
module Generics.MultiRec.TH

-- | Given the name of the family index GADT, derive everything.
deriveAll :: Name -> Q [Dec]

-- | Given a list of datatype names, derive datatypes and instances of
--   class <a>Constructor</a>. Not needed if <a>deriveAll</a> is used.
deriveConstructors :: [Name] -> Q [Dec]

-- | Compatibility. Use <a>deriveAll</a> instead.
--   
--   Given the name of the index GADT, the names of the types in the
--   family, and the name (as string) for the pattern functor to derive,
--   generate the <tt>Ix</tt> and <a>PF</a> instances. <i>IMPORTANT</i>: It
--   is assumed that the constructors of the GADT have the same names as
--   the datatypes in the family.
deriveFamily :: Name -> [Name] -> String -> Q [Dec]

-- | Compatibility. Use <a>deriveAll</a> instead.
deriveSystem :: Name -> [Name] -> String -> Q [Dec]

-- | Derive only the <a>PF</a> instance. Not needed if <a>deriveAll</a> is
--   used.
derivePF :: String -> [Name] -> Q [Dec]

-- | Derive only the <a>El</a> instances. Not needed if <a>deriveAll</a> is
--   used.
deriveEl :: Name -> [Name] -> Q [Dec]

-- | Derive only the <a>Fam</a> instance. Not needed if <a>deriveAll</a> is
--   used.
deriveFam :: Name -> [Name] -> Q [Dec]

-- | Derive only the <a>EqS</a> instance. Not needed if <a>deriveAll</a> is
--   used.
deriveEqS :: Name -> [Name] -> Q [Dec]


-- | Generic function that returns the constructor names available in a
--   family of datatypes.
module Generics.MultiRec.ConNames
class ConNames f :: ((* -> *) -> * -> *)
hconNames :: ConNames f => f r ix -> [String]
conNames :: ConNames (PF phi) => phi ix -> [String]
instance ConNames f => ConNames (f :>: ix)
instance ConNames (I a)
instance ConNames (f :.: g)
instance ConNames (f :*: g)
instance ConNames U
instance ConNames (K x)
instance (ConNames f, ConNames g) => ConNames (f :+: g)
instance Constructor c => ConNames (C c f)


-- | Variant of <a>Generics.MultiRec.Fold</a> where the result type is
--   independent of the index.
module Generics.MultiRec.FoldK
type Algebra' phi f r = forall ix. phi ix -> f (K0 r) ix -> r
type Algebra phi r = Algebra' phi (PF phi) r
type AlgebraF' phi f g r = forall ix. phi ix -> f (K0 r) ix -> g r
type AlgebraF phi g r = AlgebraF' phi (PF phi) g r
fold :: (Fam phi, HFunctor phi (PF phi)) => Algebra phi r -> phi ix -> ix -> r
foldM :: (Fam phi, HFunctor phi (PF phi), Monad m) => AlgebraF phi m r -> phi ix -> ix -> m r
type CoAlgebra' phi f r = forall ix. phi ix -> r -> f (K0 r) ix
type CoAlgebra phi r = CoAlgebra' phi (PF phi) r
type CoAlgebraF' phi f g r = forall ix. phi ix -> r -> g (f (K0 r) ix)
type CoAlgebraF phi g r = CoAlgebraF' phi (PF phi) g r
unfold :: (Fam phi, HFunctor phi (PF phi)) => CoAlgebra phi r -> phi ix -> r -> ix
unfoldM :: (Fam phi, HFunctor phi (PF phi), Monad m) => CoAlgebraF phi m r -> phi ix -> r -> m ix
type ParaAlgebra' phi f r = forall ix. phi ix -> f (K0 r) ix -> ix -> r
type ParaAlgebra phi r = ParaAlgebra' phi (PF phi) r
type ParaAlgebraF' phi f g r = forall ix. phi ix -> f (K0 r) ix -> ix -> g r
type ParaAlgebraF phi g r = ParaAlgebraF' phi (PF phi) g r
para :: (Fam phi, HFunctor phi (PF phi)) => ParaAlgebra phi r -> phi ix -> ix -> r
paraM :: (Fam phi, HFunctor phi (PF phi), Monad m) => ParaAlgebraF phi m r -> phi ix -> ix -> m r
type AlgPart f b ix = f (K0 b) ix -> b
type :-> f g b ix = f b ix -> g b ix
(&) :: (AlgPart a :-> (AlgPart b :-> AlgPart (a :+: b))) c ix
tag :: AlgPart a c ix -> AlgPart (a :>: ix) c ix'
con :: AlgPart a b ix -> AlgPart (C c a) b ix


-- | Generic show.
module Generics.MultiRec.Show

-- | The list in the result type allows us to get at the fields of a
--   constructor individually, which in turn allows us to insert additional
--   stuff in between if record notation is used.
class HFunctor phi f => HShow phi f
hShowsPrecAlg :: HShow phi f => Algebra' phi f [Int -> ShowS]
class Show1 f
show1 :: Show1 f => f [Int -> ShowS] -> Int -> ShowS
showsPrec :: (Fam phi, HShow phi (PF phi)) => phi ix -> Int -> ix -> ShowS
show :: (Fam phi, HShow phi (PF phi)) => phi ix -> ix -> String
spaces :: [ShowS] -> ShowS
commas :: [ShowS] -> ShowS
intersperse :: String -> [ShowS] -> ShowS
instance Show1 []
instance Show1 Maybe
instance (Constructor c, HShow phi f) => HShow phi (C c f)
instance (Show1 f, Traversable f, HShow phi g) => HShow phi (f :.: g)
instance HShow phi f => HShow phi (f :>: ix)
instance (HShow phi f, HShow phi g) => HShow phi (f :*: g)
instance (HShow phi f, HShow phi g) => HShow phi (f :+: g)
instance HShow phi U
instance Show a => HShow phi (K a)
instance El phi xi => HShow phi (I xi)


-- | A variant of fold that allows the specification of the algebra in a
--   convenient way.
module Generics.MultiRec.FoldAlg

-- | The type family we use to describe the convenient algebras.

-- | The algebras passed to the fold have to work for all index types in
--   the family. The additional witness argument is required only to make
--   GHC's typechecker happy.
type Algebra phi r = forall ix. phi ix -> Alg (PF phi) r ix

-- | The class fold explains how to convert a convenient algebra <a>Alg</a>
--   back into a function from functor to result, as required by the
--   standard fold function.
class Fold f :: ((* -> *) -> * -> *)
alg :: Fold f => Alg f r ix -> f r ix -> r ix

-- | Fold with convenient algebras.
fold :: (Fam phi, HFunctor phi (PF phi), Fold (PF phi)) => Algebra phi r -> phi ix -> ix -> r ix

-- | For constructing algebras that are made of nested pairs rather than
--   n-ary tuples, it is helpful to use this pairing combinator.
(&) :: a -> b -> (a, b)
instance Fold f => Fold (C c f)
instance Fold f => Fold (f :>: xi)
instance Fold g => Fold (I xi :*: g)
instance Fold g => Fold (K a :*: g)
instance (Fold f, Fold g) => Fold (f :+: g)
instance Functor f => Fold (f :.: I xi)
instance Fold (I xi)
instance Fold U
instance Fold (K a)


-- | A variant of fold that allows the specification of the algebra in a
--   convenient way, and that fixes the result type to a constant.
module Generics.MultiRec.FoldAlgK

-- | The type family we use to describe the convenient algebras.

-- | The algebras passed to the fold have to work for all index types in
--   the family. The additional witness argument is required only to make
--   GHC's typechecker happy.
type Algebra phi r = forall ix. phi ix -> Alg (PF phi) r

-- | The class fold explains how to convert a convenient algebra <a>Alg</a>
--   back into a function from functor to result, as required by the
--   standard fold function.
class Fold f :: ((* -> *) -> * -> *)
alg :: Fold f => Alg f r -> f (K0 r) ix -> r

-- | Fold with convenient algebras.
fold :: (Fam phi, HFunctor phi (PF phi), Fold (PF phi)) => Algebra phi r -> phi ix -> ix -> r

-- | For constructing algebras that are made of nested pairs rather than
--   n-ary tuples, it is helpful to use this pairing combinator.
(&) :: a -> b -> (a, b)
instance Fold f => Fold (C c f)
instance Fold f => Fold (f :>: xi)
instance Fold g => Fold (I xi :*: g)
instance Fold g => Fold (K a :*: g)
instance (Fold f, Fold g) => Fold (f :+: g)
instance Fold (I xi)
instance Fold U
instance Fold (K a)


-- | Generic read.
module Generics.MultiRec.Read
class CountAtoms f :: ((* -> *) -> * -> *)
countatoms :: CountAtoms f => f r ix -> Int
class HReadPrec phi :: (* -> *) f :: ((* -> *) -> * -> *)
hreader :: HReadPrec phi f => phi ix -> (forall ix1. phi ix1 -> ReadPrec (I0 ix1)) -> ReadPrec (f I0 ix)
class Read1 f
read1 :: Read1 f => ReadPrec (g I0 ix) -> ReadPrec (f (g I0 ix))
readCons :: Constructor c => ReadPrec (f I0 ix) -> ReadPrec (C c f I0 ix)
readPrefixCons :: ReadPrec (f I0 ix) -> Bool -> String -> ReadPrec (f I0 ix)
readInfixCons :: (HReadPrec phi f, HReadPrec phi g) => phi ix -> (forall ix1. phi ix1 -> ReadPrec (I0 ix1)) -> (Associativity, Int, Bool) -> String -> ReadPrec ((f :*: g) I0 ix)
readNoArgsCons :: String -> ReadPrec (U I0 ix)
appPrec :: Int
readPrec :: (Fam phi, HReadPrec phi (PF phi)) => phi ix -> ReadPrec ix
readsPrec :: (Fam phi, HReadPrec phi (PF phi)) => phi ix -> Int -> ReadS ix
read :: (Fam phi, HReadPrec phi (PF phi)) => phi ix -> String -> ix
instance (Constructor c, CountAtoms (f :*: g), HReadPrec phi f, HReadPrec phi g) => HReadPrec phi (C c (f :*: g))
instance (Constructor c, HReadPrec phi (f :.: g)) => HReadPrec phi (C c (f :.: g))
instance (Constructor c, HReadPrec phi (K a)) => HReadPrec phi (C c (K a))
instance (Constructor c, HReadPrec phi (I xi)) => HReadPrec phi (C c (I xi))
instance Constructor c => HReadPrec phi (C c U)
instance Read1 Maybe
instance Read1 []
instance (Read1 f, HReadPrec phi g) => HReadPrec phi (f :.: g)
instance (HReadPrec phi f, EqS phi, El phi ix) => HReadPrec phi (f :>: ix)
instance (HReadPrec phi f, HReadPrec phi g) => HReadPrec phi (f :*: g)
instance (HReadPrec phi f, HReadPrec phi g) => HReadPrec phi (f :+: g)
instance El phi xi => HReadPrec phi (I xi)
instance Read a => HReadPrec phi (K a)
instance HReadPrec phi U
instance (CountAtoms f, CountAtoms g) => CountAtoms (f :*: g)
instance CountAtoms (I xi)
instance CountAtoms (K a)


-- | multirec -- generic programming for families of recursive datatypes
--   
--   This top-level module re-exports most modules of the library.
module Generics.MultiRec