-- 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>. Technical Report, Universiteit Utrecht
--   (<a>http://www.cs.uu.nl/research/techreps/repo/CS-2008/2008-019.pdf</a>).</li>
--   </ul>
@package multirec
@version 0.3


-- | 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 C 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 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


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

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

-- | 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 Ix 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 deriveFamily instead.
deriveSystem :: Name -> [Name] -> String -> Q [Dec]

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

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

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

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


-- | 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 U
instance ConNames (K x)
instance (ConNames f, ConNames g) => ConNames (f :+: g)
instance (Constructor c) => ConNames (C c f)


-- | 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)) -> 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) -> 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)) -> f r ix -> m (f r' ix)
instance (Constructor c, HFunctor phi f) => HFunctor phi (C c f)
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


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


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


-- | 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 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)


-- | 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
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 (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)


-- | Generic show.
module Generics.MultiRec.Show
class (HFunctor phi f) => HShow phi f
hShowsPrecAlg :: (HShow phi f) => Algebra' phi f [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
instance (Constructor c, HShow phi f) => HShow phi (C c f)
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)


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