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


-- | Generic programming with systems 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, systems of mutually recursive datatypes have been
--   excluded.
--   
--   With the multirec library, we provide a mechanism to talk about fixed
--   points of systems 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 systems 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.2


-- | 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 :: (* -> *) -> (* -> *) -> * -> *) (s :: * -> *) (r :: * -> *) ix -> String
conFixity :: (Constructor c) => t c (f :: (* -> *) -> (* -> *) -> * -> *) (s :: * -> *) (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 system of datatypes: All the datatypes of the system 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 system, 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 (within the system) to recurse on.
data I :: * -> (* -> *) -> (* -> *) -> * -> *
I :: r xi -> I xi s r ix

-- | Destructor for <a>I</a>.
unI :: I xi s r ix -> r xi

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

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

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

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

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

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

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

-- | Destructor for <a>C</a>.
unC :: C c f s r ix -> f s 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 system.
type Str s ix = (PF s) s I0 ix
class Ix s ix
from_ :: (Ix s ix) => ix -> Str s ix
to_ :: (Ix s ix) => Str s ix -> ix
from :: (Ix s ix, pfs ~ (PF s)) => ix -> pfs s I0 ix
to :: (Ix s ix, pfs ~ (PF s)) => pfs s I0 ix -> ix
index :: (Ix s ix) => s 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 system 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
--   system, and the name (as string) for the pattern functor to derive,
--   generate the <a>Ix</a> 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.
deriveSystem :: Name -> [Name] -> String -> Q [Dec]

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

-- | Derive only the <a>Ix</a> instances. Not needed if <a>deriveSystem</a>
--   is used.
deriveIx :: Name -> [Name] -> Q [Dec]
instance Lift Associativity
instance Lift Fixity


-- | Generic function that returns the constructor names available in a
--   system of datatypes.
module Generics.MultiRec.ConNames
class ConNames f :: ((* -> *) -> (* -> *) -> * -> *)
hconNames :: (ConNames f) => f s r ix -> [String]
conNames :: (Ix s ix, ConNames (PF s)) => s 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 f
hmapA :: (HFunctor f, Applicative a) => (forall ix. (Ix s ix) => s ix -> r ix -> a (r' ix)) -> f s r ix -> a (f s 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 system <tt>s</tt>, the argument to <tt>hmap</tt> is
--   additionally parameterized by a witness of type <tt>s ix</tt>.
hmap :: (HFunctor f) => (forall ix. (Ix s ix) => s ix -> r ix -> r' ix) -> f s r ix -> f s r' ix

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


-- | 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 :: (pfs ~ (PF s), Ix s ix, HFunctor (PF s)) => ix -> HFix (pfs s) ix
hto :: (pfs ~ (PF s), Ix s ix, HFunctor (PF s)) => HFix (pfs s) ix -> ix


-- | 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 other folds, look at <a>Generics.MultiRec.FoldAlg</a>.</li>
--   </ul>
module Generics.MultiRec.Fold
type Algebra' s f r = forall ix. (Ix s ix) => s ix -> f s r ix -> r ix
type Algebra s r = Algebra' s (PF s) r
type AlgebraF' s f g r = forall ix. (Ix s ix) => s ix -> f s r ix -> g (r ix)
type AlgebraF s g r = AlgebraF' s (PF s) g r
fold :: (Ix s ix, HFunctor (PF s)) => Algebra s r -> ix -> r ix
foldM :: (Ix s ix, HFunctor (PF s), Monad m) => AlgebraF s m r -> ix -> m (r ix)
type CoAlgebra' s f r = forall ix. (Ix s ix) => s ix -> r ix -> f s r ix
type CoAlgebra s r = CoAlgebra' s (PF s) r
type CoAlgebraF' s f g r = forall ix. (Ix s ix) => s ix -> r ix -> g (f s r ix)
type CoAlgebraF s g r = CoAlgebraF' s (PF s) g r
unfold :: (Ix s ix, HFunctor (PF s)) => CoAlgebra s r -> r ix -> ix
unfoldM :: (Ix s ix, HFunctor (PF s), Monad m) => CoAlgebraF s m r -> r ix -> m ix
type ParaAlgebra' s f r = forall ix. (Ix s ix) => s ix -> f s r ix -> ix -> r ix
type ParaAlgebra s r = ParaAlgebra' s (PF s) r
type ParaAlgebraF' s f g r = forall ix. (Ix s ix) => s ix -> f s r ix -> ix -> g (r ix)
type ParaAlgebraF s g r = ParaAlgebraF' s (PF s) g r
para :: (Ix s ix, HFunctor (PF s)) => ParaAlgebra s r -> ix -> r ix
paraM :: (Ix s ix, HFunctor (PF s), Monad m) => ParaAlgebraF s m r -> ix -> m (r ix)
type AlgPart a s :: (* -> *) r ix = a s r ix -> r ix
type :-> f g s :: (* -> *) r :: (* -> *) ix = f s r ix -> g s r ix
(&) :: (AlgPart a :-> (AlgPart b :-> AlgPart (a :+: b))) s r ix
tag :: AlgPart a s r ix -> AlgPart (a :>: ix) s r ix'
con :: AlgPart a s r ix -> AlgPart (C c a) s r ix


-- | Variant of <a>Generics.MultiRec.Fold</a> where the result type is
--   independent of the index.
module Generics.MultiRec.FoldK
type Algebra' s f r = forall ix. (Ix s ix) => s ix -> f s (K0 r) ix -> r
type Algebra s r = Algebra' s (PF s) r
type AlgebraF' s f g r = forall ix. (Ix s ix) => s ix -> f s (K0 r) ix -> g r
type AlgebraF s g r = AlgebraF' s (PF s) g r
fold :: (Ix s ix, HFunctor (PF s)) => Algebra s r -> ix -> r
foldM :: (Ix s ix, HFunctor (PF s), Monad m) => AlgebraF s m r -> ix -> m r
type CoAlgebra' s f r = forall ix. (Ix s ix) => s ix -> r -> f s (K0 r) ix
type CoAlgebra s r = CoAlgebra' s (PF s) r
type CoAlgebraF' s f g r = forall ix. (Ix s ix) => s ix -> r -> g (f s (K0 r) ix)
type CoAlgebraF s g r = CoAlgebraF' s (PF s) g r
unfold :: (Ix s ix, HFunctor (PF s)) => CoAlgebra s r -> r -> ix
unfoldM :: (Ix s ix, HFunctor (PF s), Monad m) => CoAlgebraF s m r -> r -> m ix
type ParaAlgebra' s f r = forall ix. (Ix s ix) => s ix -> f s (K0 r) ix -> ix -> r
type ParaAlgebra s r = ParaAlgebra' s (PF s) r
type ParaAlgebraF' s f g r = forall ix. (Ix s ix) => s ix -> f s (K0 r) ix -> ix -> g r
type ParaAlgebraF s g r = ParaAlgebraF' s (PF s) g r
para :: (Ix s ix, HFunctor (PF s)) => ParaAlgebra s r -> ix -> r
paraM :: (Ix s ix, HFunctor (PF s), Monad m) => ParaAlgebraF s m r -> ix -> m r
type AlgPart a s :: (* -> *) b ix = a s (K0 b) ix -> b
type :-> f g s :: (* -> *) b ix = f s b ix -> g s b ix
(&) :: (AlgPart a :-> (AlgPart b :-> AlgPart (a :+: b))) s c ix
tag :: AlgPart a s c ix -> AlgPart (a :>: ix) s c ix'
con :: AlgPart a s b ix -> AlgPart (C c a) s 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 system. The additional witness argument is required only to make
--   GHC's typechecker happy.
type Algebra s r = forall ix. (Ix s ix) => s ix -> Alg (PF s) s 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, Ix s ix) => Alg f s r ix -> f s r ix -> r ix

-- | Variant of fold that takes an additional witness argument.
fold_ :: (Ix s ix, HFunctor (PF s), Fold (PF s)) => s ix -> Algebra s r -> ix -> r ix

-- | Fold with convenient algebras.
fold :: (Ix s ix, HFunctor (PF s), Fold (PF s)) => Algebra s r -> 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 system. The additional witness argument is required only to make
--   GHC's typechecker happy.
type Algebra s r = forall ix. (Ix s ix) => s ix -> Alg (PF s) s 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, Ix s ix) => Alg f s r -> f s (K0 r) ix -> r

-- | Variant of fold that takes an additional witness argument.
fold_ :: (Ix s ix, HFunctor (PF s), Fold (PF s)) => s ix -> Algebra s r -> ix -> r

-- | Fold with convenient algebras.
fold :: (Ix s ix, HFunctor (PF s), Fold (PF s)) => Algebra s r -> 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 :: (Ix s ix, HFunctor (PF s)) => (forall ix. (Ix s ix) => s ix -> ix -> ix) -> ix -> ix

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

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


-- | Generic equality.
module Generics.MultiRec.Eq
class HEq f
heq :: (HEq f) => s ix -> (forall ix. (Ix s ix) => s ix -> r ix -> r ix -> Bool) -> f s r ix -> f s r ix -> Bool
eq :: (Ix s ix, HEq (PF s)) => s ix -> ix -> ix -> Bool
instance (HEq f) => HEq (C c f)
instance (HEq f) => HEq (f :>: ix)
instance (HEq f, HEq g) => HEq (f :*: g)
instance (HEq f, HEq g) => HEq (f :+: g)
instance HEq U
instance (Eq x) => HEq (K x)
instance HEq (I xi)


-- | Generic show.
module Generics.MultiRec.Show
class (HFunctor f) => HShow f
hShowsPrecAlg :: (HShow f) => Algebra' s f (K0 [Int -> ShowS])

-- | A variant of the algebra that takes an extra argument to fix the
--   system s the algebra works on.
hShowsPrecAlg_ :: (HShow f) => s ix -> Algebra' s f (K0 [Int -> ShowS])
showsPrec :: (Ix s ix, HShow (PF s)) => s ix -> Int -> ix -> ShowS
show :: (Ix s ix, HShow (PF s)) => s ix -> ix -> String
spaces :: [ShowS] -> ShowS
instance (HShow f) => HShow (C c f)
instance (HShow f) => HShow (f :>: ix)
instance (HShow f, HShow g) => HShow (f :*: g)
instance (HShow f, HShow g) => HShow (f :+: g)
instance HShow U
instance (Show x) => HShow (K x)
instance HShow (I xi)


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