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


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

-- | 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 Applicative I0
instance Functor I0


-- | 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 (f :>: ix)
instance (HFunctor f, HFunctor g) => HFunctor (f :*: g)
instance (HFunctor f, HFunctor g) => HFunctor (f :+: g)
instance HFunctor (K x)
instance HFunctor (I xi)


-- | The definition of generic fold.
module Generics.MultiRec.Fold
type Algebra s r = forall ix. (Ix s ix) => s ix -> PF s s r ix -> r ix
fold :: (Ix s ix, HFunctor (PF s)) => Algebra s r -> ix -> r ix
type CoAlgebra s r = forall ix. (Ix s ix) => s ix -> r ix -> PF s s r ix
unfold :: (Ix s ix, HFunctor (PF s)) => CoAlgebra s r -> r ix -> ix
type ParaAlgebra s r = forall ix. (Ix s ix) => s ix -> PF s s r ix -> ix -> r ix
para :: (Ix s ix, HFunctor (PF s)) => ParaAlgebra s r -> ix -> 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'


-- | 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 (f :>: ix)
instance (HEq f, HEq g) => HEq (f :*: g)
instance (HEq f, HEq g) => HEq (f :+: g)
instance (Eq x) => HEq (K x)
instance HEq (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