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


-- | Pointless Haskell library
--   
--   Pointless Haskell is library for point-free programming with recursion
--   patterns defined as hylomorphisms, inspired in ideas from the PolyP
--   library. Generic recursion patterns can be expressed for recursive
--   types and no support for mutually recursive types or nested data types
--   is provided. The library also features the visualization of the
--   intermediate data structure of hylomorphisms with GHood
--   (<a>http://hackage.haskell.org/cgi-bin/hackage-scripts/package/GHood</a>).
@package pointless-haskell
@version 0.0.3


-- | Pointless Haskell: point-free programming with recursion patterns as
--   hylomorphisms
--   
--   This module defines many standard combinators used for point-free
--   programming.
module Generics.Pointless.Combinators

-- | The bottom value for any type. It is many times used just for type
--   annotations.
_L :: a

-- | The final object. The only possible value of type <a>One</a> is
--   <a>_L</a>.
data One

-- | Creates a point to the terminal object.
bang :: a -> One

-- | Converts elements into points.
pnt :: a -> One -> a

-- | The infix split combinator.
(/\) :: (a -> b) -> (a -> c) -> a -> (b, c)
(><) :: (a -> b) -> (c -> d) -> (a, c) -> (b, d)

-- | Injects a value to the left of a sum.
inl :: a -> Either a b

-- | Injects a value to the right of a sum.
inr :: b -> Either a b

-- | The infix either combinator.
(\/) :: (b -> a) -> (c -> a) -> Either b c -> a

-- | The infix sum combinator.
(-|-) :: (a -> b) -> (c -> d) -> Either a c -> Either b d

-- | Alias for the infix sum combinator.
(<>) :: (a -> b) -> (c -> d) -> Either a c -> Either b d

-- | The application combinator.
app :: (a -> b, a) -> b

-- | The left exponentiation combinator.
lexp :: (a -> b) -> (b -> c) -> (a -> c)

-- | The right exponentiation combinator.
rexp :: (b -> c) -> (a -> b) -> (a -> c)

-- | The infix combinator for a constant point.
(!) :: a -> b -> a

-- | Guard combinator that operates on Haskell booleans.
grd :: (a -> Bool) -> a -> Either a a

-- | Infix guarc combinator that simulates the postfix syntax.
(?) :: (a -> Bool) -> a -> Either a a

-- | The uncurried split combinator.
split :: (a -> b, a -> c) -> (a -> (b, c))

-- | The uncurried either combinator.
eithr :: (a -> c, b -> c) -> Either a b -> c

-- | The uncurried composition combinator.
comp :: (b -> c, a -> b) -> (a -> c)

-- | Binary <tt>or</tt> of boolean functions.
orf :: (a -> Bool, a -> Bool) -> (a -> Bool)

-- | Binary <tt>and</tt> of boolean functions.
andf :: (a -> Bool, a -> Bool) -> (a -> Bool)

-- | Binary <tt>or</tt> point-free combinator.
or :: (Bool, Bool) -> Bool

-- | Binary <tt>and</tt> point-free combinator.
and :: (Bool, Bool) -> Bool

-- | Binary equality point-free combinator.
eq :: (Eq a) => (a, a) -> Bool

-- | Binary inequality point-free combinator.
neq :: (Eq a) => (a, a) -> Bool

-- | Swap the elements of a product.
swap :: (a, b) -> (b, a)

-- | Swap the elements of a sum.
coswap :: Either a b -> Either b a

-- | Distribute products over the left of sums.
distl :: (Either a b, c) -> Either (a, c) (b, c)

-- | Distribute sums over the left of products.
undistl :: Either (a, c) (b, c) -> (Either a b, c)

-- | Distribute products over the right of sums.
distr :: (c, Either a b) -> Either (c, a) (c, b)

-- | Distribute sums over the right of products.
undistr :: Either (c, a) (c, b) -> (c, Either a b)

-- | Associate nested products to the left.
assocl :: (a, (b, c)) -> ((a, b), c)

-- | Associates nested products to the right.
assocr :: ((a, b), c) -> (a, (b, c))

-- | Associates nested sums to the left.
coassocl :: Either a (Either b c) -> Either (Either a b) c

-- | Associates nested sums to the right.
coassocr :: Either (Either a b) c -> Either a (Either b c)
instance Eq One
instance Show One


-- | Pointless Haskell: point-free programming with recursion patterns as
--   hylomorphisms
--   
--   This module defines data types as fixed points of functor. Pointless
--   Haskell works on a view of data types as fixed points of functors, in
--   the same style as the PolyP
--   (<a>http://www.cse.chalmers.se/~patrikj/poly/polyp/</a>) library.
--   Instead of using an explicit fixpoint operator, a type function is
--   used to relate the data types with their equivalent functor
--   representations.
module Generics.Pointless.Functors

-- | Identity functor.
newtype Id x
Id :: x -> Id x
unId :: Id x -> x

-- | Constant functor.
newtype Const t x
Cons :: t -> Const t x
unCons :: Const t x -> t

-- | Sum of functors.
data (:+:) g h x
Inl :: (g x) -> :+: g h x
Inr :: (h x) -> :+: g h x

-- | Product of functors.
data (:*:) g h x
Prod :: (g x) -> (h x) -> :*: g h x

-- | Composition of functors.
newtype (:@:) g h x
Comp :: g (h x) -> :@: g h x
unComp :: :@: g h x -> g (h x)

-- | Explicit fixpoint operator.
newtype Fix f
Fix :: Rep f (Fix f) -> Fix f

-- | The unfolding of the fixpoint of a functor is the functor applied to
--   its fixpoint.
--   
--   <a>unFix</a> is specialized with the application of <a>Rep</a> in
--   order to subsume functor application
unFix :: Fix f -> Rep f (Fix f)

-- | Family of patterns functors of data types.
--   
--   The type function is not necessarily injective, this is, different
--   data types can have the same base functor.
--   
--   Semantically, we can say that <tt>a = <a>Fix</a> f</tt>.

-- | Family of functor representations.
--   
--   The <a>Rep</a> family implements the implicit coercion between the
--   application of a functor and the structurally equivalent sum of
--   products.
--   
--   Functors applied to types can be represented as sums of products.

-- | Polytypic <tt>Prelude.Functor</tt> class for functor representations
class Functor f :: (* -> *)
fmap :: (Functor f) => Fix f -> (x -> y) -> Rep f x -> Rep f y

-- | Short alias to express the structurally equivalent sum of products for
--   some data type
type F a x = Rep (PF a) x

-- | Polytypic map function
pmap :: (Functor (PF a)) => a -> (x -> y) -> F a x -> F a y

-- | The <a>Mu</a> class provides the value-level translation between data
--   types and their sum of products representations
class Mu a
inn :: (Mu a) => F a a -> a
out :: (Mu a) => a -> F a a

-- | In order to simplify type-level composition of functors, we can create
--   fixpoint combinators that implicitely assume fixpoint application.
--   
--   Semantically, we can say that <tt><a>I</a> = <a>Fix</a>
--   <a>Id</a></tt>.
data I
FixId :: I

-- | Semantically, we can say that <tt><a>K</a> t = <a>Fix</a>
--   (<a>Const</a> t)</tt>.
data K a
FixConst :: a -> K a
unFixConst :: K a -> a

-- | Semantically, we can say that <tt><a>Fix</a> f :+!: <a>Fix</a> g =
--   <a>Fix</a> (f :+: g)</tt>.
data (:+!:) a b
FixSum :: F (a :+!: b) (a :+!: b) -> :+!: a b
unFixSum :: :+!: a b -> F (a :+!: b) (a :+!: b)

-- | Semantically, we can say that <tt><a>Fix</a> f :*!: <a>Fix</a> g =
--   <a>Fix</a> (f :*: g)</tt>.
data (:*!:) a b
FixProd :: F (a :*!: b) (a :*!: b) -> :*!: a b
unFixProd :: :*!: a b -> F (a :*!: b) (a :*!: b)

-- | Semantically, we can say that <tt><a>Fix</a> f :@!: <a>Fix</a> g =
--   <a>Fix</a> (f ':@: g)</tt>.
data (:@!:) a b
FixComp :: F (a :@!: b) (a :@!: b) -> :@!: a b
unFixComp :: :@!: a b -> F (a :@!: b) (a :@!: b)
nil :: One -> [a]
cons :: (a, [a]) -> [a]
data Nat
Zero :: Nat
Succ :: Nat -> Nat
zero :: One -> Int
suck :: Int -> Int
true :: One -> Bool
false :: One -> Bool
maybe2bool :: Maybe a -> Bool
instance Eq Nat
instance Show Nat
instance Mu (Maybe a)
instance Mu Bool
instance Mu Int
instance Mu Nat
instance Mu [a]
instance Mu (a :@!: b)
instance Mu (a :*!: b)
instance Mu (a :+!: b)
instance Mu (K a)
instance Mu I
instance Mu (Fix f)
instance Functor []
instance (Functor g, Functor h) => Functor (g :@: h)
instance (Functor g, Functor h) => Functor (g :*: h)
instance (Functor g, Functor h) => Functor (g :+: h)
instance Functor (Const t)
instance Functor Id
instance (Show (Rep f (Fix f))) => Show (Fix f)


-- | Pointless Haskell: point-free programming with recursion patterns as
--   hylomorphisms
--   
--   This module defines recursion patterns as hylomorphisms.
--   
--   Recursion patterns can be seen as high-order functions that
--   encapsulate typical forms of recursion. The hylomorphism recursion
--   pattern was first defined in
--   <a>http://research.microsoft.com/~emeijer/Papers/CWIReport.pdf</a>,
--   along with its relation with derived more specific recursion patterns
--   such as catamorphisms, anamorphisms and paramorphisms.
--   
--   The seminal paper that introduced point-free programming and defined
--   many of the laws for catamorphisms and anamorphisms can be found in
--   <a>http://eprints.eemcs.utwente.nl/7281/01/db-utwente-40501F46.pdf</a>.
--   
--   More complex and exotic recursion patterns have been discovered later,
--   such as accumulations, apomorphisms, zygomorphisms, histomorphisms,
--   futumorphisms, dynamorphisms or chronomorphisms.
module Generics.Pointless.RecursionPatterns

-- | Definition of an hylomorphism
hylo :: (Functor (PF b)) => b -> (F b c -> c) -> (a -> F b a) -> a -> c

-- | Definition of a catamorphism as an hylomorphism.
--   
--   Catamorphisms model the fundamental pattern of iteration, where
--   constructors for recursive datatypes are repeatedly consumed by
--   arbitrary functions. They are usually called folds.
cata :: (Mu a, Functor (PF a)) => a -> (F a b -> b) -> a -> b

-- | Recursive definition of a catamorphism.
cataRec :: (Mu a, Functor (PF a)) => a -> (F a b -> b) -> a -> b

-- | Definition of an anamorphism as an hylomorphism.
--   
--   Anamorphisms resembles the dual of iteration and, hence, dene the
--   inverse of catamorphisms. Instead of consuming recursive types, they
--   produce values of those types.
ana :: (Mu b, Functor (PF b)) => b -> (a -> F b a) -> a -> b

-- | Recursive definition of an anamorphism.
anaRec :: (Mu b, Functor (PF b)) => b -> (a -> F b a) -> a -> b

-- | The functor of the intermediate type of a paramorphism is the functor
--   of the consumed type <tt>a</tt> extended with an extra annotation to
--   itself in recursive definitions.
type Para a = a :@!: (I :*!: K a)

-- | Definition of a paramorphism.
--   
--   Paramorphisms supply the gene of a catamorphism with a recursively
--   computed copy of the input.
--   
--   The first introduction to paramorphisms is reported in
--   <a>http://www.cs.uu.nl/research/techreps/repo/CS-1990/1990-04.pdf</a>.
para :: (Mu a, Functor (PF a)) => a -> (F a (b, a) -> b) -> a -> b

-- | Recursive definition of a paramorphism.
paraRec :: (Mu a, Functor (PF a)) => a -> (F a (b, a) -> b) -> a -> b

-- | The functor of the intermediate type of an apomorphism is the functor
--   of the generated type <tt>b</tt> with an alternative annotation to
--   itself in recursive definitions.
type Apo b = b :@!: (I :+!: K b)

-- | Definition of an apomorphism as an hylomorphism.
--   
--   Apomorphisms are the dual recursion patterns of paramorphisms, and
--   therefore they can express functions defined by primitive corecursion.
--   
--   They were introduced independently in
--   <a>http://www.cs.ut.ee/~varmo/papers/nwpt97.ps.gz</a> and <i>Program
--   Construction and Generation Based on Recursive Types, MSc thesis</i>.
apo :: (Mu b, Functor (PF b)) => b -> (a -> F b (Either a b)) -> a -> b

-- | Recursive definition of an apomorphism.
apoRec :: (Mu b, Functor (PF b)) => b -> (a -> F b (Either a b)) -> a -> b

-- | In zygomorphisms we extend the recursive occurences in the base
--   functor functor of type <tt>a</tt> with an extra annotation
--   <tt>b</tt>.
type Zygo a b = a :@!: (I :*!: K b)

-- | Definition of a zygomorphism as an hylomorphism.
--   
--   Zygomorphisms were introduced in
--   <a>http://dissertations.ub.rug.nl/faculties/science/1990/g.r.malcolm/</a>.
--   
--   They can be seen as the asymmetric form of mutual iteration, where
--   both a data consumer and an auxiliary function are defined
--   (<a>http://www.fing.edu.uy/~pardo/papers/njc01.ps.gz</a>).
zygo :: (Mu a, Functor (PF a), (F a (a, b)) ~ (F (Zygo a b) a)) => a -> (F a b -> b) -> (F (Zygo a b) b -> b) -> a -> b

-- | In accumulations we add an extra annotation <tt>b</tt> to the base
--   functor of type <tt>a</tt>.
type Accum a b = a :*!: K b

-- | Definition of an accumulation as an hylomorphism.
--   
--   Accumulations <a>http://www.fing.edu.uy/~pardo/papers/wcgp02.ps.gz</a>
--   are binary functions that use the second parameter to store
--   intermediate results.
--   
--   The so called <a>accumulation technique</a> is tipically used in
--   functional programming to derive efficient implementations of some
--   recursive functions.
accum :: (Mu a, Functor (PF a)) => a -> (F (Accum a b) c -> c) -> ((F a a, b) -> F a (a, b)) -> (a, b) -> c

-- | In histomorphisms we add an extra annotation <tt>c</tt> to the base
--   functor of type <tt>a</tt>.
type Histo a c = K c :*!: a

-- | Definition of an histomorphism as an hylomorphism (as long as the
--   catamorphism is defined as an hylomorphism).
--   
--   Histomorphisms (<a>http://cs.ioc.ee/~tarmo/papers/inf.ps.gz</a>)
--   capture the powerfull schemes of course-of-value iteration, and differ
--   from catamorphisms for being able to apply the gene function at a
--   deeper depth of recursion. In other words, they allow to reuse sub-sub
--   constructor results.
histo :: (Mu a, Functor (PF a)) => a -> (F a (Histo a c) -> c) -> a -> c

-- | The combinator <a>outl</a> unpacks the functor of an histomorphism and
--   selects the annotation.
outl :: Histo a c -> c

-- | The combinator <a>outr</a> unpacks the functor of an histomorphism and
--   discards the annotation.
outr :: Histo a c -> F a (Histo a c)

-- | In futumorphisms we add an alternative annotation <tt>c</tt> to the
--   base functor of type <tt>b</tt>.
type Futu b c = K c :+!: b

-- | Definition of a futumorphism as an hylomorphism (as long as the
--   anamorphism is defined as an hylomorphism).
--   
--   Futumorphisms are the dual of histomorphisms and are proposed as
--   'cocourse-of-argument' coiterators by their creators
--   (<a>http://cs.ioc.ee/~tarmo/papers/inf.ps.gz</a>).
--   
--   In the same fashion as histomorphisms, it allows to seed the gene with
--   multiple levels of depth instead of having to do 'all at once' with an
--   anamorphism.
futu :: (Mu b, Functor (PF b)) => b -> (a -> F b (Futu b a)) -> a -> b

-- | The combinator <a>innl</a> packs the functor of a futumorphism from
--   the base functor.
innl :: c -> Futu b c

-- | The combinator <a>innr</a> packs the functor of an futumorphism from
--   an annotation.
innr :: F b (Futu b c) -> Futu b c

-- | Definition of a dynamorphism as an hylomorphisms.
--   
--   Dynamorphisms
--   (<a>http://math.ut.ee/~eugene/kabanov-vene-mpc-06.pdf</a>) are a more
--   general form of histomorphisms for capturing dynaming programming
--   constructions.
--   
--   Instead of following the recursion pattern of the input via structural
--   recursion (as in histomorphisms), dynamorphisms allow us to reuse the
--   annotated structure in a bottom-up approach and avoiding rebuilding it
--   every time an annotation is needed, what provides a more efficient
--   dynamic algorithm.
dyna :: (Mu b, Functor (PF b)) => b -> (F b (Histo b c) -> c) -> (a -> F b a) -> a -> c

-- | Definition of a chronomorphism as an hylomorphism.
--   
--   This recursion pattern subsumes histomorphisms, futumorphisms and
--   dynamorphisms and can be seen as the natural hylomorphism
--   generalization from composing an histomorphism after a futumorphism.
--   Therefore, chronomorphisms can 'look back' when consuming a type and
--   'jump forward' when generating one, via it's fold/unfold operations,
--   respectively.
--   
--   The notion of chronomorphism is a recent recursion pattern (at least
--   known as such). The first and single reference available is
--   <a>http://comonad.com/reader/2008/time-for-chronomorphisms/</a>.
chrono :: (Mu c, Functor (PF c)) => c -> (F c (Histo c b) -> b) -> (a -> F c (Futu c a)) -> a -> b

-- | The Fixpoint combinator as an hylomorphism.
--   
--   <a>fix</a> is a fixpoint combinator if <tt><a>fix</a> = <a>app</a>
--   <a>.</a> (<a>id</a> <a>/\</a> <a>fix</a>)</tt>.
--   
--   After expanding the denitions of <a>.</a>, <a>/\</a> and <a>app</a>
--   we see that this corresponds to the expected pointwise equation
--   <tt><a>fix</a> f = f (<a>fix</a> f)</tt>.
fix :: (a -> a) -> a


-- | Pointless Haskell: point-free programming with recursion patterns as
--   hylomorphisms
--   
--   This module defines generic GHood observations for user-defined data
--   types.
module Generics.Pointless.Observe.Functors

-- | Class for mapping observations over functor representations.
class FunctorO f
functorOf :: (FunctorO f) => Fix f -> String
watch :: (FunctorO f) => Fix f -> x -> Rep f x -> String
fmapO :: (FunctorO f) => Fix f -> (x -> ObserverM y) -> Rep f x -> ObserverM (Rep f y)

-- | Polytypic mapping of observations.
omap :: (FunctorO (PF a)) => a -> (x -> ObserverM y) -> F a x -> ObserverM (F a y)
instance (Functor f, FunctorO f) => Observable (Fix f)
instance (FunctorO (PF a), FunctorO (PF b)) => Observable (a :@!: b)
instance (FunctorO (PF a), FunctorO (PF b)) => Observable (a :*!: b)
instance (FunctorO (PF a), FunctorO (PF b)) => Observable (a :+!: b)
instance (Typeable a, Observable a) => Observable (K a)
instance Observable I
instance Observable One
instance (FunctorO g, FunctorO h) => FunctorO (g :@: h)
instance (FunctorO f, FunctorO g) => FunctorO (f :*: g)
instance (FunctorO f, FunctorO g) => FunctorO (f :+: g)
instance (Typeable a, Observable a) => FunctorO (Const a)
instance FunctorO Id
instance Typeable One


-- | Pointless Haskell: point-free programming with recursion patterns as
--   hylomorphisms
--   
--   This module redefines recursion patterns with support for GHood
--   observation of intermediate data structures.
module Generics.Pointless.Observe.RecursionPatterns

-- | Redefinition of hylomorphisms with observation of the intermediate
--   data type.
hyloO :: (Mu b, Functor (PF b), FunctorO (PF b)) => b -> (F b c -> c) -> (a -> F b a) -> a -> c

-- | Redefinition of catamorphisms as observable hylomorphisms.
cataO :: (Mu a, Functor (PF a), FunctorO (PF a)) => a -> (F a b -> b) -> a -> b

-- | Redefinition of anamorphisms as observable hylomorphisms.
anaO :: (Mu b, Functor (PF b), FunctorO (PF b)) => b -> (a -> F b a) -> a -> b

-- | Redefinition of paramorphisms as observable hylomorphisms.
paraO :: (Mu a, Functor (PF a), FunctorO (PF a), Observable a, Typeable a) => a -> (F a (b, a) -> b) -> a -> b

-- | Redefinition of apomorphisms as observable hylomorphisms.
apoO :: (Mu b, Functor (PF b), FunctorO (PF b), Observable b, Typeable b) => b -> (a -> F b (Either a b)) -> a -> b

-- | Redefinition of zygomorphisms as observable hylomorphisms.
zygoO :: (Mu a, Functor (PF a), FunctorO (PF a), Observable b, Typeable b, (F a (a, b)) ~ (F (Zygo a b) a)) => a -> (F a b -> b) -> (F (Zygo a b) b -> b) -> a -> b

-- | Redefinition of accumulations as observable hylomorphisms.
accumO :: (Mu a, Functor (PF d), FunctorO (PF d), Observable b, Typeable b) => d -> ((F a a, b) -> F d (a, b)) -> (F (Accum d b) c -> c) -> (a, b) -> c

-- | Redefinition of histomorphisms as observable hylomorphisms.
histoO :: (Mu a, Functor (PF a), FunctorO (PF a), Observable a) => a -> (F a (Histo a c) -> c) -> a -> c

-- | Redefinition of futumorphisms as observable hylomorphisms.
futuO :: (Mu b, Functor (PF b), FunctorO (PF b), Observable b) => b -> (a -> F b (Futu b a)) -> a -> b

-- | Redefinition of dynamorphisms as observable hylomorphisms.
dynaO :: (Mu b, Functor (PF b), FunctorO (PF b), Observable b) => b -> (F b (Histo b c) -> c) -> (a -> F b a) -> a -> c

-- | Redefinition of chronomorphisms as observable hylomorphisms.
chronoO :: (Mu c, Functor (PF c), FunctorO (PF c)) => c -> (F c (Histo c b) -> b) -> (a -> F c (Futu c a)) -> a -> b


-- | Pointless Haskell: point-free programming with recursion patterns as
--   hylomorphisms
--   
--   This module provides examples, examples and more examples.
module Generics.Pointless.Examples.Examples

-- | Pre-defined algebraic addition.
add :: (Int, Int) -> Int

-- | Definition of algebraic addition as an anamorphism in the point-wise
--   style.
addAnaPW :: (Int, Int) -> Int

-- | Defition of algebraic addition as an anamorphism.
addAna :: (Int, Int) -> Int

-- | The fixpoint of the functor that is either a constant or defined
--   recursively.
type From a = K a :+!: I

-- | Definition of algebraic addition as an hylomorphism.
addHylo :: (Int, Int) -> Int

-- | Definition of algebraic addition as an accumulation.
addAccum :: (Int, Int) -> Int
addApoPW :: (Int, Int) -> Int

-- | Definition of algebraic addition as an apomorphism.
addApo :: (Int, Int) -> Int

-- | Pre-defined algebraic product.
prod :: (Int, Int) -> Int

-- | Definition of algebraic product as an hylomorphism
prodHylo :: (Int, Int) -> Int

-- | Pre-defined 'greater than' comparison.
gt :: (Ord a) => (a, a) -> Bool

-- | Definition of 'greater than' as an hylomorphism.
gtHylo :: (Int, Int) -> Bool

-- | Native recursive definition of the factorial function.
fact :: Int -> Int

-- | Recursive definition of the factorial function in the point-free
--   style.
factPF :: Int -> Int

-- | Recursive definition of the factorial function in the point-free style
--   with structural recursion.
factPF' :: Int -> Int

-- | Definition of the factorial function as an hylomorphism.
factHylo :: Int -> Int

-- | Definition of the factorial function as a paramorphism.
factPara :: Int -> Int

-- | Definition of the factorial function as a zygomorphism.
factZygo :: Int -> Int

-- | Native recursive definition of the fibonacci function.
fib :: Int -> Int

-- | Recursive definition of the fibonacci function in the point-free
--   style.
fibPF :: Int -> Int

-- | Recursive definition of the fibonacci function in the point-free style
--   with structural recursion.
fibPF' :: Int -> Int

-- | The fixpoint of the functor for a binary shape tree.
type BSTree = K One :+!: (K One :+!: (I :*!: I))

-- | Definition of the fibonacci function as an hylomorphism.
fibHylo :: Int -> Int

-- | Definition of the fibonacci function as an histomorphism.
fibHisto :: Int -> Int

-- | Definition of the fibonacci function as a dynamorphism.
fibDyna :: Int -> Int

-- | Native recursive definition for the binary partitions of a number.
--   
--   The number of binary partitions for a number n is the number of unique
--   ways to partition this number (ignoring the order) into powers of 2. |
--   Definition of the binary partitioning of a number as an hylomorphism.
bp :: Int -> Int

-- | The fixpoint of the functor representing trees with maximal branching
--   factor of two.
type BTree = K One :+!: (I :+!: (I :*!: I))

-- | Definition of the binary partitioning of a number as an hylomorphism.
bpHylo :: Int -> Int

-- | Definition of the binary partitioning of a number as a dynamorphism.
bpDyna :: Int -> Int

-- | Recursive definition of the average of a set of integers.
average :: [Int] -> Int

-- | Definition of the average of a set of integers as a catamorphism.
averageCata :: [Int] -> Int

-- | Pre-defined wrapping of an element into a list.
wrap :: a -> [a]

-- | Definition of wrapping in the point-free style.
wrapPF :: a -> [a]

-- | Definition of the tail of a list as a total function.
tail :: [a] -> [a]

-- | Definition of the tail of a list in the point-free style.
tailPF :: [a] -> [a]

-- | Definition of the tail of a list as an anamorphism.
tailCata :: [a] -> [a]

-- | Definition of the tail of a list as a paramorphism.
tailPara :: [a] -> [a]

-- | Native recursion definition of list length.
length :: [a] -> Int

-- | Recursive definition of list length in the point-free style.
lengthPF :: [a] -> Int

-- | Recursive definition of list length in the point-free style with
--   structural recursion.
lengthPF' :: [a] -> Int

-- | Definition of list length as an hylomorphism.
lengthHylo :: [a] -> Int

-- | Definition of list length as an anamorphism.
lengthAna :: [a] -> Int

-- | Definition of list length as a catamorphism.
lengthCata :: [a] -> Int

-- | Native recursive definition of list filtering.
filter :: (a -> Bool) -> [a] -> [a]

-- | Definition of list filtering as an catamorphism.
filterCata :: (a -> Bool) -> [a] -> [a]

-- | Generation of infinite lists as an anamorphism.
repeatAna :: a -> [a]

-- | Finite replication of an element as an anamorphism.
replicateAna :: (Int, a) -> [a]

-- | Generation of a downwards list as an anamorphism.
downtoAna :: Int -> [Int]

-- | Ordered list insertion as an apomorphism.
insertApo :: (Ord a) => (a, [a]) -> [a]

-- | Ordered list insertion as a paramorphism.
insertPara :: (Ord a) => (a, [a]) -> [a]

-- | Append an element to the end of a list as an hylomorphism.
snoc :: (a, [a]) -> [a]

-- | Append an element to the end of a list as an apomorphism.
snocApo :: (a, [a]) -> [a]

-- | Creates a bubble from a list. Used in the bubble sort algorithm.
bubble :: (Ord a) => [a] -> Either One (a, [a])

-- | Extraction of a number of elements from a list as an anamorphism.
takeAna :: (Int, [a]) -> [a]

-- | Native recursive definition for partitioning a list at a specified
--   element.
partition :: (Ord a) => (a, [a]) -> ([a], [a])

-- | Definition for partitioning a list at a specified element as an
--   hylomorphism.
partitionHylo :: (Ord a) => (a, [a]) -> ([a], [a])

-- | Incremental summation as a catamorphism.
isum :: [Int] -> [Int]

-- | Incrementation the elements of a list by a specified value a
--   catamorphism.
fisum :: [Int] -> Int -> [Int]

-- | Definition of list mapping as a catamorphism.
mapCata :: [a] -> (a -> b) -> [b]

-- | Definition of list reversion as a catamorphism.
reverseAna :: [a] -> [a]

-- | Definition of the quicksort algorithm as an hylomorphism.
qsort :: (Ord a) => [a] -> [a]

-- | Definition of the bubble sort algorithm as an anamorphism.
bsort :: (Ord a) => [a] -> [a]

-- | Definition of the insertion sort algorithm as a catamorphism.
isort :: (Ord a) => [a] -> [a]
msplit :: [a] -> ([a], [a])
msort :: (Ord a) => [a] -> [a]

-- | Definition of the heap sort algorithm as an hylomorphism.
hsort :: (Ord a) => [a] -> [a]
hsplit :: (Ord a) => [a] -> (a, ([a], [a]))

-- | Malcolm downwards accumulations on lists.
malcolm :: ((b, a) -> a) -> a -> [b] -> [a]

-- | Malcom downwards accumulations on lists as an anamorphism.
malcolmAna :: ((b, a) -> a) -> a -> [b] -> [a]

-- | Uncurried version of Malcom downwards accumulations on lists as an
--   anamorphism.
malcolmAna' :: ((b, a) -> a) -> ([b], a) -> [a]

-- | Definition of the zip for lists of pairs as an anamorphism.
zipAna :: ([a], [b]) -> [(a, b)]

-- | Definition of the subsequences of a list as a catamorphism.
subsequences :: (Eq a) => [a] -> [[a]]

-- | Pre-defined list concatenation.
cat :: ([a], [a]) -> [a]

-- | List concatenation as a catamorphism.
catCata :: [a] -> [a] -> [a]

-- | The fixpoint of the list functor with a specific terminal element.
type NeList a b = K a :+!: (K b :*!: I)

-- | List concatenation as an hylomorphism.
catHylo :: ([a], [a]) -> [a]

-- | Native recursive definition of lists-of-lists concatenation.
concat :: [[a]] -> [a]

-- | Definition of lists-of-lists concatenation as an anamorphism.
concatCata :: [[a]] -> [a]

-- | Sorted concatenation of two lists as an hylomorphism.
merge :: (Ord a) => ([a], [a]) -> [a]

-- | Definition of inter addition as a catamorphism.
sumCata :: [Int] -> Int

-- | Native recursive definition of integer multiplication.
mult :: [Int] -> Int

-- | Definition of integer multiplication as a catamorphism.
multCata :: [Int] -> Int
sorted :: (Ord a) => [a] -> Bool

-- | Native recursive definition of the edit distance algorithm.
--   
--   Edit distance is a classical dynamic programming algorithm that
--   calculates a measure of distance or dierence between lists with
--   comparable elements.
editdist :: (Eq a) => ([a], [a]) -> Int

-- | The fixpoint of the functor that represents a virtual matrix used to
--   accumulate and look up values for the edit distance algorithm.
--   
--   Since matrixes are not inductive types, a walk-through of a matrix is
--   used, consisting in a list of values from the matrix ordered
--   predictability.
--   
--   For a more detailed explanation, please refer to
--   <a>http://math.ut.ee/~eugene/kabanov-vene-mpc-06.pdf</a>.
type EditDist a = K [a] :+!: ((K a :*!: K a) :*!: (I :*!: (I :*!: I)))
type EditDistL a = (K [a] :*!: K [a]) :*!: (K One :+!: I)

-- | The edit distance algorithm as an hylomorphism.
editdistHylo :: (Eq a) => ([a], [a]) -> Int

-- | The edit distance algorithm as a dynamorphism.
editDistDyna :: (Eq a) => ([a], [a]) -> Int

-- | The fixpoint of the functor of streams.
type Stream a = K a :*!: I

-- | Stream head.
headS :: Stream a -> a

-- | Stream tail.
tailS :: Stream a -> Stream a

-- | Definition of a stream sequence generator as an anamorphism.
generate :: Int -> Stream Int

-- | Identity o streams as an anamorphism.
idStream :: Stream a -> Stream a

-- | Mapping over streams as an anamorphism.
mapStream :: (a -> b) -> Stream a -> Stream b

-- | Malcolm downwards accumulations on streams.
malcolmS :: ((b, a) -> a) -> a -> Stream b -> Stream a

-- | Malcom downwards accumulations on streams as an anamorphism.
malcolmSAna :: ((b, a) -> a) -> a -> Stream b -> Stream a

-- | Uncurried version of Malcom downwards accumulations on streams as an
--   anamorphism.
malcolmSAna' :: ((b, a) -> a) -> (Stream b, a) -> Stream a

-- | Promotes streams elements to streams of singleton elements.
inits :: Stream a -> Stream [a]

-- | Definition of parwise exchange on streams as a futumorphism.
exchFutu :: Stream a -> Stream a

-- | Datatype declaration of a binary tree.
data Tree a
Empty :: Tree a
Node :: a -> (Tree a) -> (Tree a) -> Tree a

-- | Counting the number of leaves in a binary tree as a catamorphism.
nleaves :: Tree a -> Int

-- | Counting the number of nodes in a binary tree as a catamorphism.
nnodes :: Tree a -> Int

-- | Generation of a binary tree with a specified height as an anamorphism.
genTree :: Int -> Tree Int

-- | The preorder traversal on binary trees as a catamorphism.
preTree :: Tree a -> [a]

-- | The postorder traversal on binary trees as a catamorphism.
postTree :: Tree a -> [a]

-- | Datatype declaration of a leaf tree.
data LTree a
Leaf :: a -> LTree a
Branch :: (LTree a) -> (LTree a) -> LTree a

-- | Extract the leaves of a leaf tree as a catamorphism.
leaves :: LTree a -> [a]

-- | Generation of a leaft tree of a specified height as an anamorphism.
genLTree :: Int -> LTree Int

-- | Calculate the height of a leaf tree as a catamorphism.
height :: LTree a -> Int

-- | Datatype declaration of a rose tree.
data Rose a
Forest :: a -> [Rose a] -> Rose a
preRose :: Rose a -> [a]

-- | The postorder traversal on rose trees as a catamorphism.
postRose :: Rose a -> [a]

-- | Generation of a rose tree of a specified height as an anamorphism.
genRose :: Int -> Rose Int
instance (Show a) => Show (Rose a)
instance (Show a) => Show (Tree a)
instance Mu (Rose a)
instance Mu (LTree a)
instance Mu (Tree a)


-- | Pointless Haskell: point-free programming with recursion patterns as
--   hylomorphisms
--   
--   This module provides the same examples, but with support for GHood
--   observations.
module Generics.Pointless.Examples.Observe

-- | Definition of the observable length function as an hylomorphism.
lengthHyloO :: (Observable a) => [a] -> Int

-- | Definition of the observable length function as an anamorphism.
lengthAnaO :: (Observable a) => [a] -> Int

-- | Definition of the observable length function as a catamorphism.
lengthCataO :: (Typeable a, Observable a) => [a] -> Int

-- | Definition of the observable factorial function as an hylomorphism.
factHyloO :: Int -> Int

-- | Definition of the observable factorial function as a paramorphism.
factParaO :: Int -> Int

-- | Definition of the observable factorial function as a zygomorphism.
factZygoO :: Int -> Int

-- | Definition of the observable fibonacci function as an hylomorphism.
fibHyloO :: Int -> Int

-- | Definition of the observable fibonacci function as an histomorphism.
fibHistoO :: Int -> Int

-- | Definition of the observable fibonacci function as a dynamorphism.
fibDynaO :: Int -> Int

-- | Definition of the observable quicksort function as an hylomorphism.
qsortHyloO :: (Typeable a, Observable a, Ord a) => [a] -> [a]

-- | Definition of the observable tail function as a paramorphism.
tailParaO :: (Typeable a, Observable a) => [a] -> [a]

-- | Definition of the observable add function as an accumulation.
addAccumO :: (Int, Int) -> Int


-- | Pointless Haskell: point-free programming with recursion patterns as
--   hylomorphisms
--   
--   This module defines a class of representable functors.
module Generics.Pointless.Fctrable

-- | Functor GADT for polytypic recursive functions. At the moment it does
--   not rely on a <tt>Typeable</tt> instance for constants.
data Fctr f :: (* -> *)
I :: Fctr Id
K :: Fctr (Const c)
(:*!:) :: Fctr f -> Fctr g -> Fctr (f :*: g)
(:+!:) :: Fctr f -> Fctr g -> Fctr (f :+: g)
(:@!:) :: Fctr f -> Fctr g -> Fctr (f :@: g)

-- | Class of representable functors.
class (Functor f) => Fctrable f :: (* -> *)
fctr :: (Fctrable f) => Fctr f

-- | The fixpoint of a representable functor.
fixF :: Fctr f -> Fix f

-- | The representation of the fixpoint of a representable functor.
fctrF :: (Fctrable f) => Fix f -> Fctr f
instance (Functor f, Fctrable f, Functor g, Fctrable g) => Fctrable (f :@: g)
instance (Functor f, Fctrable f, Functor g, Fctrable g) => Fctrable (f :+: g)
instance (Functor f, Fctrable f, Functor g, Fctrable g) => Fctrable (f :*: g)
instance Fctrable (Const c)
instance Fctrable Id


-- | Pointless Haskell: point-free programming with recursion patterns as
--   hylomorphisms
--   
--   This module lifts many standard combinators used for point-free
--   programming to combinators over monads.
module Generics.Pointless.MonadCombinators

-- | The left-to-right monadic binding combinator.
(<<=) :: (Monad m) => (a -> m b) -> m a -> m b

-- | Higher-order monadic binding.
bind :: (Monad m) => (a -> m b, m a) -> m b

-- | The monadic left exponentiation combinator.
mlexp :: (Monad m) => (a -> m b) -> (b -> m c) -> (a -> m c)

-- | The monadic right exponentiation combinator.
mrexp :: (Monad m) => (b -> m c) -> (a -> m b) -> (a -> m c)

-- | The monadic sum combinator.
(-||-) :: (Monad m) => (a -> m b) -> (c -> m d) -> (Either a c -> m (Either b d))

-- | The strength combinator for strong monads. In Haskell, every monad is
--   a strong monad: <a>http://comonad.
--   com/reader/2008/deriving-strength-from-laziness/</a>.
mstrength :: (Monad m) => (b, m a) -> m (b, a)

-- | The monadic fusion combinator. Performs left-to-right distribution of
--   a strong monad over a product.
mfuse :: (Monad m) => (m a, m b) -> m (a, b)

-- | The monadic split combinator.
(/|\) :: (Monad m) => (a -> m b) -> (a -> m c) -> a -> m (b, c)

-- | The monadic product combinator.
(>|<) :: (Monad m) => (a -> m c) -> (b -> m d) -> (a, b) -> m (c, d)


-- | Pointless Haskell: point-free programming with recursion patterns as
--   hylomorphisms
--   
--   This module defines polymorphic data types as fixed points of
--   bifunctor. Pointless Haskell works on a view of data types as fixed
--   points of functors, in the same style as the PolyP
--   (<a>http://www.cse.chalmers.se/~patrikj/poly/polyp/</a>) library.
--   Instead of using an explicit fixpoint operator, a type function is
--   used to relate the data types with their equivalent functor
--   representations.
module Generics.Pointless.Bifunctors
newtype BId a x
BId :: x -> BId a x
unBId :: BId a x -> x
newtype BConst t a x
BConst :: t -> BConst t a x
unBConst :: BConst t a x -> t
newtype BPar a x
Par :: a -> BPar a x
unPar :: BPar a x -> a
data (:+|) g h a x
BInl :: (g a x) -> :+| g h a x
BInr :: (h a x) -> :+| g h a x
data (:*|) g h a x
BProd :: (g a x) -> (h a x) -> :*| g h a x
newtype (:@|) g h a x
BComp :: g a (h a x) -> :@| g h a x
unBComp :: :@| g h a x -> g a (h a x)
newtype BFix f
BFix :: f (BFix f) (BFix f) -> BFix f
unBFix :: BFix f -> f (BFix f) (BFix f)
class Bifunctor f :: (* -> * -> *)
bmap :: (Bifunctor f) => BFix f -> (a -> b) -> (x -> y) -> Rep (BRep f a) x -> Rep (BRep f b) y
type B d a x = Rep (BRep (BF d) a) x
class Bimu d
binn :: (Bimu d) => B d a (d a) -> d a
bout :: (Bimu d) => d a -> B d a (d a)
pbmap :: (Bifunctor (BF d)) => d a -> (a -> b) -> (x -> y) -> B d a x -> B d b y
data BI x
FixBId :: BI x
data BK a x
FixBConst :: a -> BK a x
unFixBConst :: BK a x -> a
data (:+!|) a :: (* -> *) b :: (* -> *) x
FixBSum :: B (a :+!| b) x ((a :+!| b) x) -> :+!| x
unFixBSum :: :+!| x -> B (a :+!| b) x ((a :+!| b) x)
data (:*!|) a :: (* -> *) b :: (* -> *) x
FixBProd :: B (a :*!| b) x ((a :*!| b) x) -> :*!| x
unFixBProd :: :*!| x -> B (a :*!| b) x ((a :*!| b) x)
data (:@!|) a :: (* -> *) b :: (* -> *) x
FixBComp :: B (a :@!| b) x ((a :@!| b) x) -> :@!| x
unFixBComp :: :@!| x -> B (a :@!| b) x ((a :@!| b) x)
instance Bimu []
instance Bimu (a :@!| b)
instance Bimu (a :*!| b)
instance Bimu (a :+!| b)
instance Bimu (BK a)
instance Bimu BI
instance (Bifunctor g, Bifunctor h) => Bifunctor (g :@| h)
instance (Bifunctor g, Bifunctor h) => Bifunctor (g :*| h)
instance (Bifunctor g, Bifunctor h) => Bifunctor (g :+| h)
instance Bifunctor BPar
instance Bifunctor (BConst t)
instance Bifunctor BId


-- | Pointless Haskell: point-free programming with recursion patterns as
--   hylomorphisms
--   
--   This module defines a class of representable bifunctors.
module Generics.Pointless.Bifctrable

-- | Functor GADT for polytypic recursive bifunctions. At the moment it
--   does not rely on a <tt>Typeable</tt> instance for constants.
data Bifctr f :: (* -> * -> *)
BI :: Bifctr BId
BK :: Bifctr (BConst c)
BP :: Bifctr BPar
(:*!|) :: Bifctr f -> Bifctr g -> Bifctr (f :*| g)
(:+!|) :: Bifctr f -> Bifctr g -> Bifctr (f :+| g)
(:@!|) :: Bifctr f -> Bifctr g -> Bifctr (f :@| g)

-- | Class of representable bifunctors.
class (Bifunctor f) => Bifctrable f :: (* -> * -> *)
bctr :: (Bifctrable f) => Bifctr f

-- | The fixpoint of a representable bifunctor.
fixB :: Bifctr f -> BFix f

-- | The representation of the fixpoint of a representable functor.
fctrB :: (Bifctrable f) => BFix f -> Bifctr f
instance (Bifunctor f, Bifctrable f, Bifunctor g, Bifctrable g) => Bifctrable (f :+| g)
instance (Bifunctor f, Bifctrable f, Bifunctor g, Bifctrable g) => Bifctrable (f :*| g)
instance Bifctrable BPar
instance Bifctrable (BConst c)
instance Bifctrable BId