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


-- | Generic programming library for regular datatypes.
--   
--   This package provides generic functionality for regular datatypes.
--   Regular datatypes are recursive datatypes such as lists, binary trees,
--   etc. This library cannot be used with mutually recursive datatypes or
--   with nested datatypes. The multirec library [1] can deal with mutually
--   recursive datatypes.
--   
--   This library has been described in the paper:
--   
--   <ul>
--   <li><i>A Lightweight Approach to Datatype-Generic Rewriting.</i>
--   Thomas van Noort, Alexey Rodriguez, Stefan Holdermans, Johan Jeuring,
--   Bastiaan Heeren. ACM SIGPLAN Workshop on Generic Programming
--   2008.</li>
--   </ul>
--   
--   More information about this library can be found at
--   <a>http://www.cs.uu.nl/wiki/GenericProgramming/Regular</a>.
--   
--   [1] <a>http://hackage.haskell.org/package/multirec</a>
@package regular
@version 0.2.2


-- | Summary: Representation for record selectors.
module Generics.Regular.Selector
class Selector s
selName :: (Selector s) => t s (f :: * -> *) r -> String


-- | Summary: Representation for constructors.
module Generics.Regular.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 -> String
conFixity :: (Constructor c) => t c (f :: * -> *) r -> Fixity
conIsRecord :: (Constructor c) => t c (f :: * -> *) r -> Bool

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


-- | Summary: Types for structural representation.
module Generics.Regular.Base

-- | Structure type for constant values.
newtype K a r
K :: a -> K a r
unK :: K a r -> a

-- | Structure type for recursive values.
newtype I r
I :: r -> I r
unI :: I r -> r

-- | Structure type for empty constructors.
data U r
U :: U r

-- | Structure type for alternatives in a type.
data (:+:) f g r
L :: (f r) -> :+: f g r
R :: (g r) -> :+: f g r

-- | Structure type for fields of a constructor.
data (:*:) f g r
(:*:) :: f r -> g r -> :*: f g r

-- | Structure type to store the name of a constructor.
data C c f r
C :: f r -> C c f r
unC :: C c f r -> f r

-- | Structure type to store the name of a record selector.
data S l f r
S :: f r -> S l f r
unS :: S l f r -> f r

-- | 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 -> String
conFixity :: (Constructor c) => t c (f :: * -> *) r -> Fixity
conIsRecord :: (Constructor c) => t c (f :: * -> *) r -> Bool

-- | 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
class Selector s
selName :: (Selector s) => t s (f :: * -> *) r -> String

-- | The well-known fixed-point type.
newtype Fix f
In :: f (Fix f) -> Fix f
out :: Fix f -> f (Fix f)

-- | The type class <tt>Regular</tt> captures the structural representation
--   of a type and the corresponding embedding-projection pairs.
--   
--   To be able to use the generic functions, the user is required to
--   provide an instance of this type class.
class Regular a
from :: (Regular a) => a -> PF a a
to :: (Regular a) => PF a a -> a

-- | The type family <tt>PF</tt> represents the pattern functor of a
--   datatype.
--   
--   To be able to use the generic functions, the user is required to
--   provide an instance of this type family.
instance (Functor f) => Functor (S c f)
instance (Functor f) => Functor (C c f)
instance (Functor f, Functor g) => Functor (f :*: g)
instance (Functor f, Functor g) => Functor (f :+: g)
instance Functor U
instance Functor (K a)
instance Functor I


-- | This module contains Template Haskell code that can be used to
--   automatically generate the boilerplate code for the regular library.
module Generics.Regular.TH

-- | Given the type and the name (as string) for the pattern functor to
--   derive, generate the Constructor' instances, the Selector' instances
--   and the <a>Regular</a> instance.
deriveAll :: Name -> String -> Q [Dec]

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

-- | Given a datatype name, derive datatypes and instances of class
--   <a>Selector</a>.
deriveSelectors :: Name -> Q [Dec]

-- | Given the type and the name (as string) for the pattern functor to
--   derive, generate the <a>Regular</a> instance.
deriveRegular :: Name -> String -> Q [Dec]

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


-- | Summary: Return the name of all the constructors of a type.
module Generics.Regular.Functions.ConNames
class ConNames f
hconNames :: (ConNames f) => f a -> [String]

-- | Return the name of all the constructors of the type of the given term.
conNames :: (Regular a, ConNames (PF a)) => a -> [String]
instance ConNames (K a)
instance ConNames U
instance ConNames I
instance (ConNames f, ConNames g) => ConNames (f :*: g)
instance (ConNames f, Constructor c) => ConNames (C c f)
instance (ConNames f, ConNames g) => ConNames (f :+: g)


-- | Summary: Generic crush.
module Generics.Regular.Functions.Crush

-- | The <tt>Crush</tt> class defines a right-associative crush on
--   functorial values.
class Crush f
crush :: (Crush f) => Assoc -> (a -> b -> b) -> b -> f a -> b

-- | Flatten a structure by collecting all the elements present.
flattenl :: (Crush f) => f a -> [a]
flattenr :: (Crush f) => f a -> [a]
crushr :: (Crush f) => (a -> b -> b) -> b -> f a -> b
crushl :: (Crush f) => (a -> b -> b) -> b -> f a -> b
instance (Crush f) => Crush (S s f)
instance (Crush f) => Crush (C c f)
instance (Crush f, Crush g) => Crush (f :*: g)
instance (Crush f, Crush g) => Crush (f :+: g)
instance Crush U
instance Crush (K a)
instance Crush I


-- | Summary: Generic folding and unfolding.
module Generics.Regular.Functions.Fold
type Algebra a r = Alg (PF a) r

-- | The class fold explains how to convert an algebra <a>Alg</a> into a
--   function from functor to result.
class Fold f :: (* -> *)
alg :: (Fold f) => Alg f r -> f r -> r

-- | Fold with convenient algebras.
fold :: (Regular a, Fold (PF a), Functor (PF a)) => Algebra a r -> a -> r
type CoAlgebra a s = s -> CoAlg (PF a) s

-- | The class unfold explains how to convert a coalgebra <a>CoAlg</a> and
--   a seed into a representation.
class Unfold f :: (* -> *)
coalg :: (Unfold f) => (s -> a) -> CoAlg f s -> f a
unfold :: (Unfold (PF a), Regular a) => CoAlgebra a s -> s -> a

-- | For constructing algebras it is helpful to use this pairing
--   combinator.
(&) :: a -> b -> (a, b)
instance (Unfold f) => Unfold (S s f)
instance (Unfold f) => Unfold (C c f)
instance (Unfold f, Unfold g) => Unfold (f :*: g)
instance (Unfold f, Unfold g) => Unfold (f :+: g)
instance Unfold U
instance Unfold I
instance Unfold (K a)
instance (Fold f) => Fold (S s f)
instance (Fold f) => Fold (C c f)
instance (Fold g) => Fold (I :*: g)
instance (Fold g) => Fold (K a :*: g)
instance (Fold f, Fold g) => Fold (f :+: g)
instance Fold I
instance Fold U
instance Fold (K a)


-- | Summary: Monadic generic map.
module Generics.Regular.Functions.GMap

-- | The <a>Functor</a> class is used for types that can be mapped over.
--   Instances of <a>Functor</a> should satisfy the following laws:
--   
--   <tt> fmap id == id fmap (f . g) == fmap f . fmap g </tt>
--   
--   The instances of <a>Functor</a> for lists, Data.Maybe.Maybe and
--   System.IO.IO defined in the <a>Prelude</a> satisfy these laws.
class Functor f :: (* -> *)
fmap :: (Functor f) => (a -> b) -> f a -> f b

-- | The <tt>GMap</tt> class defines a monadic functorial map.
class GMap f
fmapM :: (GMap f, Monad m) => (a -> m b) -> f a -> m (f b)
instance (GMap f) => GMap (S s f)
instance (GMap f) => GMap (C c f)
instance (GMap f, GMap g) => GMap (f :*: g)
instance (GMap f, GMap g) => GMap (f :+: g)
instance GMap U
instance GMap (K a)
instance GMap I


-- | Summary: Generic functionality for regular dataypes: mapM, flatten,
--   zip, equality, show, value generation and fold.
module Generics.Regular.Functions.LR

-- | The <tt>LRBase</tt> class defines two functions, <tt>leftb</tt> and
--   <tt>rightb</tt>, which should produce different values.
class LRBase a
leftb :: (LRBase a) => a
rightb :: (LRBase a) => a

-- | The <tt>LR</tt> class defines two functions, <tt>leftf</tt> and
--   <tt>rightf</tt>, which should produce different functorial values.
class LR f
leftf :: (LR f) => a -> f a
rightf :: (LR f) => a -> f a

-- | Produces a value which should be different from the value returned by
--   <tt>right</tt>.
left :: (Regular a, LR (PF a)) => a

-- | Produces a value which should be different from the value returned by
--   <tt>left</tt>.
right :: (Regular a, LR (PF a)) => a
instance (LR f) => LR (S s f)
instance (LR f) => LR (C c f)
instance (LR f, LR g) => LR (f :*: g)
instance (LR f, LR g) => LR (f :+: g)
instance LR U
instance (LRBase a) => LR (K a)
instance LR I
instance (LRBase a) => LRBase [a]
instance LRBase Char
instance LRBase Integer
instance LRBase Int


-- | Summary: Deep generic seq. Used to fully evaluate a term.
module Generics.Regular.Functions.Seq

-- | A general class for expressing deep seq. It is used in the <a>K</a>
--   case for the generic seq.
--   
--   We do not give an instance of the form <tt>instance (Regular a, Seq
--   (PF a)) =&gt; DeepSeq a where dseq = gdseq</tt> because this requires
--   undecidable instances. However, any type for which there is a generic
--   instance can be given a trivial instance of <a>DeepSeq</a> by using
--   <a>gdseq</a>.
class DeepSeq a
dseq :: (DeepSeq a) => a -> b -> b

-- | The class for generic deep seq.
class Seq f
gseq :: (Seq f) => (a -> b -> b) -> f a -> b -> b

-- | Deep, generic version of seq.
gdseq :: (Regular a, Seq (PF a)) => a -> b -> b
instance (DeepSeq a, DeepSeq b) => DeepSeq (Either a b)
instance (DeepSeq a) => DeepSeq (Maybe a)
instance (DeepSeq a) => DeepSeq [a]
instance DeepSeq ()
instance DeepSeq Double
instance DeepSeq Float
instance DeepSeq Char
instance DeepSeq Integer
instance DeepSeq Int
instance (Seq f) => Seq (S s f)
instance (Seq f) => Seq (C c f)
instance (Seq f, Seq g) => Seq (f :*: g)
instance (Seq f, Seq g) => Seq (f :+: g)
instance Seq U
instance (DeepSeq a) => Seq (K a)
instance Seq I


-- | Summary: Generic zip.
module Generics.Regular.Functions.Zip

-- | The <tt>Zip</tt> class defines a monadic zip on functorial values.
class Zip f
fzipM :: (Zip f, Monad m) => (a -> b -> m c) -> f a -> f b -> m (f c)

-- | Functorial zip with a non-monadic function, resulting in a monadic
--   value.
fzip :: (Zip f, Monad m) => (a -> b -> c) -> f a -> f b -> m (f c)

-- | Partial functorial zip with a non-monadic function.
fzip' :: (Zip f) => (a -> b -> c) -> f a -> f b -> f c
instance (Zip f) => Zip (S s f)
instance (Zip f) => Zip (C c f)
instance (Zip f, Zip g) => Zip (f :*: g)
instance (Zip f, Zip g) => Zip (f :+: g)
instance Zip U
instance (Eq a) => Zip (K a)
instance Zip I


-- | Summary: All of the generic functionality for regular dataypes: mapM,
--   flatten, zip, equality, value generation, fold and unfold. Generic
--   show (<a>Generics.Regular.Functions.Show</a>), generic read
--   (<a>Generics.Regular.Functions.Read</a>) and generic equality
--   (<a>Generics.Regular.Functions.Eq</a>) are not exported to prevent
--   clashes with <tt>Prelude</tt>.
module Generics.Regular.Functions


-- | Summary: Generic equality.
module Generics.Regular.Functions.Eq
class Eq f
eqf :: (Eq f) => (a -> a -> Bool) -> f a -> f a -> Bool
eq :: (Regular a, Eq (PF a)) => a -> a -> Bool
instance (Eq f) => Eq (C c f)
instance (Eq f, Eq g) => Eq (f :*: g)
instance (Eq f, Eq g) => Eq (f :+: g)
instance Eq U
instance (Eq a) => Eq (K a)
instance Eq I


-- | Summary: Generic read. This module is not exported by
--   <a>Generics.Regular.Functions</a> to avoid clashes with
--   <a>Prelude</a>.
module Generics.Regular.Functions.Read
class Read f
hreader :: (Read f) => ReadPrec a -> Bool -> ReadPrec (f a)
read :: (Regular a, Read (PF a)) => String -> a
readPrec :: (Regular a, Read (PF a)) => ReadPrec a
readsPrec :: (Regular a, Read (PF a)) => Int -> ReadS a
instance (Selector s, Read f) => Read (S s f)
instance (Constructor c, CountAtoms (f :*: g), Read f, Read g) => Read (C c (f :*: g))
instance (Constructor c, Read (S s f)) => Read (C c (S s f))
instance (Constructor c, Read (K a)) => Read (C c (K a))
instance (Constructor c, Read I) => Read (C c I)
instance (Constructor c) => Read (C c U)
instance (Read f, Read g) => Read (f :*: g)
instance (Read f, Read g) => Read (f :+: g)
instance Read I
instance (Read a) => Read (K a)
instance Read U
instance (CountAtoms f) => CountAtoms (S s f)
instance (CountAtoms f, CountAtoms g) => CountAtoms (f :*: g)
instance CountAtoms I
instance CountAtoms (K a)


-- | Summary: Generic show. This module is not exported by
--   <a>Generics.Regular.Functions</a> to avoid clashes with
--   <a>Prelude</a>.
module Generics.Regular.Functions.Show

-- | The <tt>Show</tt> class defines a show on values.
class Show f
hshowsPrec :: (Show f) => (Int -> a -> ShowS) -> Bool -> Int -> f a -> ShowS
show :: (Regular a, Show (PF a)) => a -> String
shows :: (Regular a, Show (PF a)) => a -> ShowS
instance (Selector s, Show f) => Show (S s f)
instance (Constructor c, Show f) => Show (C c f)
instance (Show f, Show g) => Show (f :*: g)
instance (Show f, Show g) => Show (f :+: g)
instance Show U
instance (Show a) => Show (K a)
instance Show I


-- | Summary: Top-level module for this library. By importing this module,
--   the user is able to use all the generic functionality. The user is
--   only required to provide an instance of <tt>Regular</tt> for the
--   datatype.
--   
--   Consider a datatype representing logical expressions:
--   
--   <pre>
--   data Logic = Var String
--              | Logic :-&gt;:  Logic  -- implication
--              | Logic :&lt;-&gt;: Logic  -- equivalence
--              | Logic :&amp;&amp;:  Logic  -- and (conjunction)
--              | Logic :||:  Logic  -- or (disjunction)
--              | Not Logic          -- not
--              | T                  -- true
--              | F                  -- false
--   </pre>
--   
--   First we import the relevant modules:
--   
--   <pre>
--   import Generics.Regular
--   import Generics.Regular.Functions
--   import qualified Generics.Regular.Functions.Show as G
--   import qualified Generics.Regular.Functions.Read as G
--   </pre>
--   
--   An instance of <tt>Regular</tt> can be derived automatically with TH
--   by invoking:
--   
--   <pre>
--   $(deriveAll ''Logic "PFLogic")
--   type instance PF Logic = PFLogic
--   </pre>
--   
--   We define some logic expressions:
--   
--   <pre>
--   l1, l2, l3 :: Logic
--   l1 = Var "p"
--   l2 = Not l1
--   l3 = l1 :-&gt;: l2
--   </pre>
--   
--   And now we can use all of the generic functions. Flattening:
--   
--   <pre>
--   ex0 :: [Logic]
--   ex0 = flattenr (from l3)
--   
--   &gt; [Var "p",Not (Var "p")]
--   </pre>
--   
--   Generic equality:
--   
--   <pre>
--   ex1, ex2 :: Bool
--   ex1 = eq l3 l3
--   
--   &gt; True
--   
--   
--   ex2 = eq l3 l2
--   
--   &gt; False
--   </pre>
--   
--   Generic show:
--   
--   <pre>
--   ex3 :: String
--   ex3 = G.show l3
--   
--   &gt; "((:-&gt;:) (Var \"p\") (Not (Var \"p\")))"
--   </pre>
--   
--   Generic read:
--   
--   <pre>
--   ex4 :: Logic
--   ex4 = G.read ex3
--   
--   &gt; Var "p" :-&gt;: Not (Var "p")
--   </pre>
--   
--   Value generation:
--   
--   <pre>
--   ex5, ex6 :: Logic
--   ex5 = left
--   
--   &gt; Var ""
--   
--   
--   ex6 = right
--   
--   &gt; F
--   </pre>
--   
--   Folding:
--   
--   <pre>
--   ex7 :: Bool
--   ex7 = fold (alg (\_ -&gt; False)) l3 where
--     alg env = (env &amp; impl &amp; (==) &amp; (&amp;&amp;) &amp; (||) &amp; not &amp; True &amp; False)
--     impl p q = not p || q
--   
--   &gt; True
--   </pre>
--   
--   Unfolding:
--   
--   <pre>
--   ex8 :: Logic
--   ex8 = unfold alg 8 where
--     alg :: CoAlgebra Logic Int
--     alg n | odd n || n &lt;= 0 = Left ""
--           | even n          = Right (Left (n-1,n-2))
--   
--   &gt; Var "" :-&gt;: (Var "" :-&gt;: (Var "" :-&gt;: (Var "" :-&gt;: Var "")))
--   </pre>
--   
--   Constructor names:
--   
--   <pre>
--   ex9 = conNames (undefined :: Logic)
--   
--   &gt; ["Var",":-&gt;:",":&lt;-&gt;:",":&amp;&amp;:",":||:","Not","T","F"]
--   </pre>
--   
--   Deep seq:
--   
--   <pre>
--   ex10 = gdseq (Not (T :-&gt;: (error "deep seq works"))) ()
--   
--   &gt; *** Exception: deep seq works
--   </pre>
module Generics.Regular