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


-- | A library for GTA programming
--   
--   This package provides the core functionalities of the GTA (Generate,
--   Test, and Aggregate) programming framework on Haskell (c.f., Kento
--   Emoto, Sebastian Fischer, Zhenjiang Hu: Generate, Test, and Aggregate
--   - A Calculation-based Framework for Systematic Parallel Programming
--   with MapReduce. ESOP 2012: 254-273. The authors' version is available
--   at <a>http://www.ipl-lab.org/~emoto/ESOP2012.pdf</a>).
--   
--   <i>Example</i>
--   
--   The following code is a GTA program to solve the 0-1 Knapsack problem
--   (<a>http://en.wikipedia.org/wiki/Knapsack_problem</a>). It <i>appears
--   to be an exponential cost</i> proram in the number of input items,
--   because it appears to generate all item selections by <tt>subsP
--   items</tt> (<i>Generate</i>), discard those with total weight heavier
--   than the knapsack's capacity by <tt><a>filterBy</a> weightlimit
--   capacity</tt> (<i>Test</i>), and take the most valuable selection by
--   <tt><a>aggregateBy</a> maxsumsolutionWith getValue</tt>
--   (<i>Aggregate</i>). However, it <i>actually runs in a linear time</i>
--   owing to our proposed program transformation 'Filter-embedding
--   Semiring Fusion' implemented in the library. In addition, it runs in
--   <i>parallel</i> so that you can get linear speedup.
--   
--   <pre>
--   knapsack capacity items =
--    subsP items
--    `filterBy` weightlimit capacity
--    `aggregateBy` maxsumsolutionWith getValue
--   
--   getValue (_, v) = v
--   getWeight (w, _) = w
--   
--   weightlimit w = (&lt;=w) &lt;.&gt; weightsum where
--     weightsum = homJ' times single nil
--     x1 `times` x2  = (   x1 +    x2) `min` (w+1)
--     single i  = getWeight i `min` (w+1)
--     nil = 0
--   </pre>
--   
--   Several examples of GTA programming are found in <i>examples</i>
--   directory at <a>https://bitbucket.org/emoto/gtalib/src</a>.
@package GTALib
@version 0.0.6


-- | Copied from
--   <a>http://haskell.1045720.n5.nabble.com/Deriving-Read-with-Template-Haskell-Re-automatic-instances-for-pretty-printing-and-parsing-td3197647.html</a>,
--   and modified a bit.
--   
--   Observing a structure of a datatype in a uniform way no matter whether
--   it was defined in infix, prefix or record form.
--   
--   This code is based on the <tt>Derive</tt> module from the SYB3 code
--   distribution, (C) 2005, Ralf Laemmel and Simon Peyton Jones, see
--   <a>http://homepages.cwi.nl/~ralf/syb3/code.html</a>.
module GTA.Util.TypeInfo

-- | The first part is the name, the second - a list of type parameters,
--   the third - a list of constructors. For each constructor we have a
--   name and a list describing constructor fields.
--   
--   type TypeInfo = (Name, [Name], [(Name, [(Maybe Name, Type)])])
type TypeInfo = (Name, [TyVarBndr], [(Name, [(Maybe Name, Type)])])

-- | Returns type information of a given type.
typeInfo :: Name -> Q TypeInfo

-- | Apply <a>nameBase</a> to the name.
simpleName :: Name -> Name


-- | This module provides a mechanism for automatic generation of
--   data-structure-dependent definitions necessary for the GTA framework
--   (namely, an instance of <a>GenericSemiringStructure</a> as well as
--   definitions of algebras and structures for map functions).
module GTA.Util.GenericSemiringStructureTemplate

-- | This function generates a definition of the algebra of a given data
--   structure. For example, given a data structure defined below,
--   
--   <pre>
--   data BinTree n l = BinNode n (BinTree n l) (BinTree n l)
--                    | BinLeaf l
--   </pre>
--   
--   the following definition of the algebra is generated by
--   <tt>genAlgebraDecl ''BinTree</tt>.
--   
--   <pre>
--   data BinTreeAlgebra n l a = BinTreeAlgebra {
--         binNode :: n -&gt; a -&gt; a -&gt; a,
--         binLeaf :: l -&gt; a
--       }
--   </pre>
genAlgebraDecl :: Name -> Q [Dec]

-- | This function generates a definition of a record holding functions to
--   be mapped to values in a given data structure. For example, given a
--   data structure defined below,
--   
--   <pre>
--   data BinTree n l = BinNode n (BinTree n l) (BinTree n l)
--                    | BinLeaf l
--   </pre>
--   
--   the following record is generated by <tt>genMapFunctionsDecl
--   ''BinTree</tt>.
--   
--   <pre>
--   data BinTreeMapFs n l b' = BinTreeMapFs {
--         binNodeF :: n -&gt; b',
--         binLeafF :: l -&gt; b'
--       }
--   </pre>
genMapFunctionsDecl :: Name -> Q [Dec]

-- | This function generates an instance of <a>GenericSemiringStructure</a>
--   for a given data structure. For example, given a data structure
--   defined below,
--   
--   <pre>
--   data BinTree n l = BinNode n (BinTree n l) (BinTree n l)
--                    | BinLeaf l
--   </pre>
--   
--   the following record is generated by
--   <tt>genInstanceDecl''BinTree</tt>.
--   
--   <pre>
--   instance GenericSemiringStructure (BinTreeAlgebra n l) (BinTree n l) (BinTreeMapFs n l) where
--     freeAlgebra = BinTreeAlgebra {..} where
--         binNode = BinNode
--         binLeaf = BinLeaf
--     pairAlgebra lvta1 lvta2 = BinTreeAlgebra {..} where
--         binNode a (l1, l2) (r1, r2) = (binNode1 a l1 r1, binNode2 a l2 r2)
--         binLeaf a                   = (binLeaf1 a, binLeaf2 a)
--         (binNode1, binLeaf1) = let BinTreeAlgebra {..} = lvta1 in (binNode, binLeaf)
--         (binNode2, binLeaf2) = let BinTreeAlgebra {..} = lvta2 in (binNode, binLeaf)
--     makeAlgebra (CommutativeMonoid {..}) lvta frec fsingle = BinTreeAlgebra {..} where  
--         binNode a l r = foldr oplus identity [fsingle (binNode' a l' r') | l' &lt;- frec l, r' &lt;- frec r]
--         binLeaf a     = fsingle (binLeaf' a)
--         (binNode', binLeaf') = let BinTreeAlgebra {..} = lvta in (binNode, binLeaf)
--     foldingAlgebra op iop (BinTreeMapFs {..}) = BinTreeAlgebra {..} where
--         binNode a l r = binNodeF a `op` l `op` r
--         binLeaf a     = binLeafF a
--     hom (BinTreeAlgebra {..}) = h where
--         h (BinNode a l r) = binNode a (h l) (h r)
--         h (BinLeaf a)     = binLeaf a
--   
--   </pre>
genInstanceDecl :: Name -> Q [Dec]

-- | Given a data structure, this function generates a definition of its
--   algebra (by <tt>genAlgebraDecl</tt>), a record of map functions (by
--   <tt>genMapFunctionsDecl</tt>), and an instance of
--   <a>GenericSemiringStructure</a> (by <tt>genInstanceDecl</tt>). Usage:
--   <tt>genAllDecl ''BinTree</tt>.
genAllDecl :: Name -> Q [Dec]


-- | This module provides the core functionalities of the GTA (Generate,
--   Test, and Aggregate) programming framework on Haskell (c.f., Kento
--   Emoto, Sebastian Fischer, Zhenjiang Hu: Generate, Test, and Aggregate
--   - A Calculation-based Framework for Systematic Parallel Programming
--   with MapReduce. ESOP 2012: 254-273. The authors' version is available
--   at <a>http://www.ipl-lab.org/~emoto/ESOP2012.pdf</a>).
--   
--   <i>Example of GTA program</i>
--   
--   The following code is a GTA program to solve the 0-1 Knapsack problem
--   (<a>http://en.wikipedia.org/wiki/Knapsack_problem</a>). It <i>appears
--   to be an exponential cost</i> proram in the number of input items,
--   because it appears to generate all item selections by <tt>subsP
--   items</tt> (<i>Generate</i>), discard those with total weight heavier
--   than the knapsack's capacity by <tt><a>filterBy</a> weightlimit
--   capacity</tt> (<i>Test</i>), and take the most valuable selection by
--   <tt><a>aggregateBy</a> maxsumsolutionWith getValue</tt>
--   (<i>Aggregate</i>). However, it <i>actually runs in a linear time</i>
--   owing to our proposed program transformation 'Filter-embedding
--   Semiring Fusion' implemented in the library. In addition, it runs in
--   <i>parallel</i> so that you can get linear speedup. The predicate
--   <tt>weightlimit</tt> is defined based on the join list algebra given
--   in <a>GTA.Data.JoinList</a> module.
--   
--   <pre>
--   knapsack capacity items = 
--    subsP items 
--    `filterBy` weightlimit capacity
--    `aggregateBy` maxsumsolutionWith getValue
--   
--   getValue (_, v) = v
--   getWeight (w, _) = w
--   
--   weightlimit w = (&lt;=w) &lt;.&gt; weightsum where
--     weightsum = homJ' times single nil
--     x1 `times` x2  = (   x1 +    x2) `min` (w+1)
--     single i  = getWeight i `min` (w+1)
--     nil = 0
--   </pre>
--   
--   Several example GTA programs are found in <i>examples</i> directory at
--   <a>https://bitbucket.org/emoto/gtalib/src</a>.
--   
--   This module provides generic functionalities in the GTA programming
--   framework. Data-strructure-dependent definitions are found in
--   GTA.Data.* modules.
module GTA.Core

-- | A bag is a multiset, i.e., a set in which members are allowed to
--   appear more than one. The order of memebrs is ignored: e.g., <tt>Bag
--   [1,2] == Bag [2,1]</tt> is True.
data Bag a
Bag :: [a] -> Bag a

-- | Commutative monoid is an algebra of an associative, commutative binary
--   operator with its identity.
data CommutativeMonoid a
CommutativeMonoid :: (a -> a -> a) -> a -> CommutativeMonoid a
oplus :: CommutativeMonoid a -> a -> a -> a
identity :: CommutativeMonoid a -> a

-- | A generic semiring is a combination of a commutative monoid and an
--   algebra such that operators of the algebra distributes over
--   <a>oplus</a> and <a>identity</a> is the zero of the operators.
--   
--   For example, the usual semiring is a combination of a commutative
--   monoid and a <a>JoinListAlgebra</a>, in which we have the
--   distributivity and the zeroness:
--   
--   <pre>
--   a `times` (b `oplus` c) == (a `times` b) `oplus` (a `times` c)
--   (a `oplus` b) `times` c == (a `times` c) `oplus` (b `times` c)
--   a `times` identity == identity `times` a == identity
--   </pre>
data GenericSemiring alg a
GenericSemiring :: CommutativeMonoid a -> alg a -> GenericSemiring alg a
monoid :: GenericSemiring alg a -> CommutativeMonoid a
algebra :: GenericSemiring alg a -> alg a

-- | Collection of data-structure-dependent definitions necessary for the
--   GTA framework, including the free algebra, lifting of a generic
--   semirig with an algebra, construction of useful algebras, etc.
class GenericSemiringStructure alg free uniformer | alg -> free, alg -> uniformer where freeSemiring = GenericSemiring {..} where monoid = bagMonoid algebra = makeAlgebra bagMonoid freeAlgebra items singletonBag liftedSemiring s a = GenericSemiring {monoid = monoid', algebra = algebra'} where monoid' = let GenericSemiring {..} = s in mapMonoid monoid algebra' = makeAlgebra (mapMonoid (monoid s)) (pairAlgebra a (algebra s)) assocs (uncurry singleton) shom (GenericSemiring {..}) = sh where CommutativeMonoid {..} = monoid sh (Bag b) = foldr oplus identity (map (hom algebra) b) pairSemiring s1 s2 = GenericSemiring {monoid = monoid', algebra = algebra'} where monoid' = pairMonoid (monoid s1) (monoid s2) algebra' = pairAlgebra (algebra s1) (algebra s2)
freeAlgebra :: GenericSemiringStructure alg free uniformer => alg free
pairAlgebra :: GenericSemiringStructure alg free uniformer => alg a -> alg b -> alg (a, b)
makeAlgebra :: GenericSemiringStructure alg free uniformer => (CommutativeMonoid m) -> (alg a) -> (m -> [a]) -> (a -> m) -> alg m
foldingAlgebra :: GenericSemiringStructure alg free uniformer => (a -> a -> a) -> a -> uniformer a -> alg a
hom :: GenericSemiringStructure alg free uniformer => alg a -> free -> a
freeSemiring :: GenericSemiringStructure alg free uniformer => GenericSemiring alg (Bag free)
liftedSemiring :: (GenericSemiringStructure alg free uniformer, Ord c) => GenericSemiring alg a -> alg c -> GenericSemiring alg (Map c a)
pairSemiring :: GenericSemiringStructure alg free uniformer => GenericSemiring alg a -> GenericSemiring alg b -> GenericSemiring alg (a, b)
shom :: GenericSemiringStructure alg free uniformer => GenericSemiring alg a -> Bag free -> a

-- | Makes a bag that contains the given memebrs.
bag :: [a] -> Bag a

-- | Combinator for connecting a generator and a filter to build another
--   generator. A fitler is represented by a pair of a judgement function
--   and an algebra.
(>==) :: (GenericSemiringStructure alg free uniformer, Ord c) => (GenericSemiring alg (Map c b) -> Map k b) -> (k -> Bool, alg c) -> GenericSemiring alg b -> b

-- | Combinator for connecting a generator and an aggregator to get the
--   result. An aggregator is represented by a generic semiring.
(>=>) :: GenericSemiringStructure alg free uniformer => (GenericSemiring alg b -> b) -> GenericSemiring alg b -> b

-- | Combinator for transforming a generator by a transformer. A
--   transformer is an aggregator polymorphic over another generic
--   semiring.
(>=<) :: (GenericSemiringStructure alg free uniformer, GenericSemiringStructure alg' free' uniformer') => (GenericSemiring alg' c -> c) -> (GenericSemiring alg c -> GenericSemiring alg' c) -> GenericSemiring alg c -> c

-- | Inefficient version of <a>&gt;==</a> (i.e., it does not do
--   optimziation at all).
(>##) :: GenericSemiringStructure alg free uniformer => (GenericSemiring alg (Bag free) -> Bag free) -> (b -> Bool, alg b) -> GenericSemiring alg (Bag free) -> Bag free

-- | Inefficient version of <a>&gt;=&gt;</a> (i.e., it does not do
--   optimziation at all).
(>#>) :: GenericSemiringStructure alg free uniformer => (GenericSemiring alg (Bag free) -> Bag free) -> GenericSemiring alg a -> a

-- | Operator to build a pair of a judgement function and an algebra, which
--   represents a Tester.
(<.>) :: (b -> Bool) -> alg b -> (b -> Bool, alg b)

-- | Extracts members from a bag. The order of members is undecidable.
items :: Bag a -> [a]

-- | Reverses the order of the argument, so that we can use aggregators
--   maxXXX to take the minimum XXX.
revOrd :: a -> RevOrd a

-- | Reverses the order of a given type.
data RevOrd a
RevOrd :: a -> RevOrd a

-- | The aggregator to the maximum sum after <i>map</i>.
maxsumBy :: (GenericSemiringStructure alg free uniformer, Ord a, Num a) => uniformer (AddIdentity a) -> GenericSemiring alg (AddIdentity a)

-- | The <i>best-k</i> extension of <a>maxsumBy</a>.
maxsumKBy :: (GenericSemiringStructure alg free uniformer, Ord a, Num a) => Int -> uniformer (AddIdentity a) -> GenericSemiring alg [AddIdentity a]

-- | The <i>best-k</i> extension of <a>maxsumsolutionXBy</a>.
maxsumsolutionXKBy :: (GenericSemiringStructure alg free uniformer, Ord a, Num a) => GenericSemiring alg b -> Int -> uniformer (AddIdentity a) -> GenericSemiring alg [(AddIdentity a, b)]

-- | An instance of <a>maxMonoSumsolutionXBy</a> with the usual summation.
maxsumsolutionXBy :: (GenericSemiringStructure alg free uniformer, Ord a, Num a) => GenericSemiring alg t -> uniformer (AddIdentity a) -> GenericSemiring alg (AddIdentity a, t)

-- | An instance of <tt>maxMonoSumsolutionBy</tt> with the usual summation.
maxsumsolutionBy :: (GenericSemiringStructure alg free uniformer, Ord a, Num a) => uniformer (AddIdentity a) -> GenericSemiring alg (AddIdentity a, Bag free)

-- | The <i>best-k</i> extension of <a>maxsumsolutionBy</a>.
maxsumsolutionKBy :: (GenericSemiringStructure alg free uniformer, Ord a, Num a) => Int -> uniformer (AddIdentity a) -> GenericSemiring alg [(AddIdentity a, Bag free)]

-- | The aggregator to take the maximum product on <i>non-negative</i>
--   numbers.
maxprodBy :: (GenericSemiringStructure alg free uniformer, Ord a, Num a) => uniformer (AddIdentity a) -> GenericSemiring alg (AddIdentity a)

-- | The <i>best-k</i> extension of <a>maxprodBy</a>
maxprodKBy :: (GenericSemiringStructure alg free uniformer, Ord a, Num a) => Int -> uniformer (AddIdentity a) -> GenericSemiring alg [AddIdentity a]

-- | The <i>best-k</i> extension of <a>maxprodsolutionXBy</a>
maxprodsolutionXKBy :: (GenericSemiringStructure alg free uniformer, Ord a, Num a) => GenericSemiring alg b -> Int -> uniformer (AddIdentity a) -> GenericSemiring alg [(AddIdentity a, b)]

-- | The tupling of <a>maxprodsolutionBy</a> and a given generic semiring.
--   The second component of the result is the aggregation of the best
--   items by the given generic emiring.
maxprodsolutionXBy :: (GenericSemiringStructure alg free uniformer, Ord a, Num a) => GenericSemiring alg t -> uniformer (AddIdentity a) -> GenericSemiring alg (AddIdentity a, t)

-- | The aggregator to find the items with the maximum product on
--   <i>non-negative</i> numbers.
maxprodsolutionBy :: (GenericSemiringStructure alg free uniformer, Ord a, Num a) => uniformer (AddIdentity a) -> GenericSemiring alg (AddIdentity a, Bag free)

-- | The <i>best-k</i> extension of <a>maxprodsolutionBy</a>
maxprodsolutionKBy :: (GenericSemiringStructure alg free uniformer, Ord a, Num a) => Int -> uniformer (AddIdentity a) -> GenericSemiring alg [(AddIdentity a, Bag free)]

-- | The aggregator to take the maximum items under a given monotonic sum
--   <tt>mplus</tt> with its identity <tt>mid</tt> after <i>map</i>.
--   
--   <pre>
--   c == a `max` b   =&gt;   d `mplus` (a `max` b) == (d `mplus` a) `max` (d `mplus` b)
--   </pre>
maxMonoSumBy :: (GenericSemiringStructure alg free uniformer, Ord a) => (a -> a -> a) -> a -> uniformer (AddIdentity a) -> GenericSemiring alg (AddIdentity a)

-- | The tupling of maxMonoSumBy and a given generic semiring. The second
--   component of the result is the aggregation of the maximum items by the
--   given generaic semiring.
maxMonoSumsolutionXBy :: (GenericSemiringStructure alg free uniformer, Ord a) => (a -> a -> a) -> a -> GenericSemiring alg t -> uniformer (AddIdentity a) -> GenericSemiring alg (AddIdentity a, t)

-- | The aggregator to find the best k maximum items under a given
--   monotonic sum. An extension of <a>maxMonoSumBy</a>.
maxMonoSumKBy :: (GenericSemiringStructure alg free uniformer, Ord a) => (a -> a -> a) -> a -> Int -> uniformer (AddIdentity a) -> GenericSemiring alg [AddIdentity a]

-- | The <i>best-k</i> extension of <a>maxMonoSumsolutionXBy</a>.
maxMonoSumsolutionXKBy :: (GenericSemiringStructure alg free uniformer, Ord a) => (a -> a -> a) -> a -> GenericSemiring alg b -> Int -> uniformer (AddIdentity a) -> GenericSemiring alg [(AddIdentity a, b)]

-- | Introduces an identity.
addIdentity :: a -> AddIdentity a

-- | Introduces an identity <a>Identity</a> to a given type.
data AddIdentity a
AddIdentity :: a -> AddIdentity a
Identity :: AddIdentity a

-- | The aggregator to compute a sum of products. Each product is of all
--   values in the data structure after <i>map</i>.
sumproductBy :: (GenericSemiringStructure alg free uniformer, Num a) => uniformer a -> GenericSemiring alg a

-- | The aggregator to extract all items generated by a generator.
result :: GenericSemiringStructure alg free uniformer => GenericSemiring alg (Bag free)

-- | The same as <a>&gt;==</a>
filterBy :: (GenericSemiringStructure alg free uniformer, Ord c) => (GenericSemiring alg (Map c b) -> Map k b) -> (k -> Bool, alg c) -> GenericSemiring alg b -> b

-- | The same as <a>&gt;=&gt;</a>
aggregateBy :: GenericSemiringStructure alg free uniformer => (GenericSemiring alg b -> b) -> GenericSemiring alg b -> b

-- | The same as <a>&gt;=&lt;</a>
transformBy :: (GenericSemiringStructure alg free uniformer, GenericSemiringStructure alg' free' uniformer') => (GenericSemiring alg' c -> c) -> (GenericSemiring alg c -> GenericSemiring alg' c) -> GenericSemiring alg c -> c
instance [overlap ok] Show a => Show (Bag a)
instance [overlap ok] Ord a => Ord (Bag a)
instance [overlap ok] Read a => Read (Bag a)
instance [overlap ok] Show a => Show (AddIdentity a)
instance [overlap ok] Eq a => Eq (AddIdentity a)
instance [overlap ok] Read a => Read (AddIdentity a)
instance [overlap ok] Eq a => Eq (RevOrd a)
instance [overlap ok] Show a => Show (RevOrd a)
instance [overlap ok] Read a => Read (RevOrd a)
instance [overlap ok] NFData a => NFData (RevOrd a)
instance [overlap ok] Ord a => Ord (RevOrd a)
instance [overlap ok] Num a => Num (RevOrd a)
instance [overlap ok] NFData a => NFData (AddIdentity a)
instance [overlap ok] Ord a => Ord (AddIdentity a)
instance [overlap ok] (Eq a, Ord a) => Eq (Bag a)
instance [overlap ok] NFData a => NFData (Bag a)


-- | This module provides the GTA framework on binary (and leaf-valued)
--   trees, such as definitions of the data structures and their algebras,
--   generators, aggregators, etc.
module GTA.Data.BinTree
data LVTree a
NodeLV :: (LVTree a) -> (LVTree a) -> LVTree a
LeafLV :: a -> LVTree a
data LVTreeAlgebra b a
LVTreeAlgebra :: (a -> a -> a) -> (b -> a) -> LVTreeAlgebra b a
nodeLV :: LVTreeAlgebra b a -> a -> a -> a
leafLV :: LVTreeAlgebra b a -> b -> a
data LVTreeMapFs b b'
LVTreeMapFs :: (b -> b') -> LVTreeMapFs b b'
leafLVF :: LVTreeMapFs b b' -> b -> b'
data BinTree n l
BinNode :: n -> (BinTree n l) -> (BinTree n l) -> BinTree n l
BinLeaf :: l -> BinTree n l
data BinTreeAlgebra n l a
BinTreeAlgebra :: (n -> a -> a -> a) -> (l -> a) -> BinTreeAlgebra n l a
binNode :: BinTreeAlgebra n l a -> n -> a -> a -> a
binLeaf :: BinTreeAlgebra n l a -> l -> a
data BinTreeMapFs n l b'
BinTreeMapFs :: (n -> b') -> (l -> b') -> BinTreeMapFs n l b'
binNodeF :: BinTreeMapFs n l b' -> n -> b'
binLeafF :: BinTreeMapFs n l b' -> l -> b'
lvtrees :: [a] -> LVTreeSemiring a s -> s
subtreeSelectsWithRoot :: BinTree n l -> BinTreeSemiring (Bool, n) (Bool, l) a -> a
subtreeSelects :: BinTree n l -> BinTreeSemiring (Bool, n) (Bool, l) a -> a
selects :: BinTree n l -> BinTreeSemiring (Bool, n) (Bool, l) a -> a
assignTrans :: [b] -> [c] -> BinTreeSemiring c (b, a) s -> LVTreeSemiring a s
assignTrees :: [b] -> [c] -> [a] -> BinTreeSemiring c (b, a) s -> s
count :: Num a => BinTreeSemiring n l a
maxsum :: (Num a, Ord a) => BinTreeSemiring (Bool, a) (Bool, a) (AddIdentity a)
maxsumsolution :: (Num a, Ord a) => BinTreeSemiring (Bool, a) (Bool, a) (AddIdentity a, Bag (BinTree (Bool, a) (Bool, a)))
type LVTreeSemiring a s = GenericSemiring (LVTreeAlgebra a) s
type BinTreeSemiring n l a = GenericSemiring (BinTreeAlgebra n l) a
instance [overlap ok] Eq a => Eq (LVTree a)
instance [overlap ok] Ord a => Ord (LVTree a)
instance [overlap ok] Read a => Read (LVTree a)
instance [overlap ok] (Eq n, Eq l) => Eq (BinTree n l)
instance [overlap ok] (Ord n, Ord l) => Ord (BinTree n l)
instance [overlap ok] (Read n, Read l) => Read (BinTree n l)
instance [overlap ok] Show RtStClass
instance [overlap ok] Eq RtStClass
instance [overlap ok] Ord RtStClass
instance [overlap ok] Read RtStClass
instance [overlap ok] Show StClass
instance [overlap ok] Eq StClass
instance [overlap ok] Ord StClass
instance [overlap ok] Read StClass
instance [overlap ok] GenericSemiringStructure (BinTreeAlgebra n l) (BinTree n l) (BinTreeMapFs n l)
instance [overlap ok] GenericSemiringStructure (LVTreeAlgebra b) (LVTree b) (LVTreeMapFs b)


-- | This module provides the GTA framework on join lists, such as
--   definitions of the data structure and its algebra, parallel/serial
--   generators, aggregators, etc.
module GTA.Data.JoinList

-- | Join lists.
--   
--   <pre>
--   x ++ y ==&gt; x `Times` y
--   [a]    ==&gt; Single a
--   []     ==&gt; Nil
--   </pre>
--   
--   We assume that <a>Times</a> is associative and <a>Nil</a> is its
--   identity:
--   
--   <pre>
--   x `Times` (y `Times` z) == (x `Times` y) `Times` z
--   x `Times` Nil == Nil `Times` x == x
--   </pre>
data JoinList a
Times :: (JoinList a) -> (JoinList a) -> JoinList a
Single :: a -> JoinList a
Nil :: JoinList a

-- | The algebra of join lists.
--   
--   We assume that <a>times</a> is associative and <a>nil</a> is its
--   identity, inheriting those of <a>Times</a> and <a>Nil</a>:
--   
--   <pre>
--   x `times` (y `times` z) == (x `times` y) `times` z
--   x `times` nil == nil `times` x == x
--   </pre>
--   
--   This can be generated automatically by <tt>genAllDecl ''JoinList</tt>.
data JoinListAlgebra b a
JoinListAlgebra :: (a -> a -> a) -> (b -> a) -> a -> JoinListAlgebra b a
times :: JoinListAlgebra b a -> a -> a -> a
single :: JoinListAlgebra b a -> b -> a
nil :: JoinListAlgebra b a -> a

-- | Conversion from a usual list to a join list.
joinize :: [a] -> JoinList a

-- | Conversion from a join list to a usual list.
dejoinize :: JoinList a -> [a]

-- | This generates all segments (continuous subsequences) of a given list.
--   
--   For example,
--   
--   <pre>
--   &gt;&gt;&gt; segs [1,2,3] `aggregateBy` result
--   Bag [[1],[2],[3],[2,3],[1,2],[1,2,3],[]]
--   </pre>
segs :: [a] -> Semiring a s -> s

-- | This generates all prefixes of a given list.
--   
--   For example,
--   
--   <pre>
--   &gt;&gt;&gt; inits [1,2,3] `aggregateBy` result
--   Bag [[],[1],[1,2],[1,2,3]]
--   </pre>
inits :: [a] -> Semiring a s -> s

-- | This generates all suffixes of a given list.
--   
--   For example,
--   
--   <pre>
--   &gt;&gt;&gt; tails [1,2,3] `aggregateBy` result
--   Bag [[1,2,3],[2,3],[3],[]]
--   </pre>
tails :: [a] -> Semiring a s -> s

-- | This generates all subsequences of a given list.
--   
--   For example,
--   
--   <pre>
--   &gt;&gt;&gt; subs [1,2,3] `aggregateBy` result
--   Bag [[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
--   </pre>
subs :: [a] -> Semiring a s -> s

-- | This generates all assignments of elements of the first list to
--   elements of the second list.
--   
--   For example,
--   
--   <pre>
--   &gt;&gt;&gt; assigns [True,False] [1,2,3] `aggregateBy` result
--   Bag [[(True,1),(True,2),(True,3)],[(True,1),(True,2),(False,3)],[(True,1),(False,2),(True,3)],[(True,1),(False,2),(False,3)],[(False,1),(True,2),(True,3)],[(False,1),(True,2),(False,3)],[(False,1),(False,2),(True,3)],[(False,1),(False,2),(False,3)]]
--   </pre>
assigns :: [m] -> [a] -> Semiring (m, a) s -> s

-- | This generates all paths from the root to leaves of a given binary
--   tree.
--   
--   For example,
--   
--   <pre>
--   &gt;&gt;&gt; *Main GTA.Data.BinTree&gt; paths (BinNode 1 (BinLeaf 2) (BinNode 3 (BinLeaf 4) (BinLeaf 5))) `aggregateBy` result
--   Bag [[1,2],[1,3,4],[1,3,5]]
--   </pre>
paths :: BinTree a a -> Semiring a s -> s

-- | This is a generalization of <a>assigns</a>: the values to be assigned
--   is dependent of the target.
--   
--   For example,
--   
--   <pre>
--   &gt;&gt;&gt; assignsBy (\a -&gt; if odd a then [True, False] else [True]) [1,2,3] `aggregateBy` result
--   Bag [[(True,1),(True,2),(True,3)],[(True,1),(True,2),(False,3)],[(False,1),(True,2),(True,3)],[(False,1),(True,2),(False,3)]]
--   </pre>
assignsBy :: (a -> [m]) -> [a] -> Semiring (m, a) s -> s

-- | Wrapper for <a>JoinListMapFs</a>.
mapJ :: (b -> a) -> JoinListMapFs b a

-- | The aggregator to count the number of items in a generated bag.
count :: Num a => Semiring b a

-- | The aggregator to take the maximum sum.
maxsum :: (Ord a, Num a) => Semiring a (AddIdentity a)

-- | The aggregator to find items with the maximum sum.
maxsumsolution :: (Ord a, Num a) => Semiring a (AddIdentity a, Bag (JoinList a))

-- | The aggregator to take the maximum sum after <tt>map f</tt>.
maxsumWith :: (Ord a, Num a) => (b -> a) -> Semiring b (AddIdentity a)

-- | The <i>best-k</i> extension of <a>maxsumWith</a>.
maxsumKWith :: (Ord a, Num a) => Int -> (b -> a) -> Semiring b ([AddIdentity a])

-- | The <i>best-k</i> extension of <a>maxsumsolutionXWith</a>.
maxsumsolutionXKWith :: (Ord a, Num a) => Semiring c b -> Int -> (c -> a) -> Semiring c [(AddIdentity a, b)]

-- | The tupling of maxsumsolution and a given semiring. The second
--   component is the aggregation of the maximum items by the given
--   semiring.
maxsumsolutionXWith :: (Ord a, Num a) => Semiring c b -> (c -> a) -> Semiring c (AddIdentity a, b)

-- | The aggregator to find items with the maximum sum after <tt>map
--   f</tt>.
maxsumsolutionWith :: (Ord a, Num a) => (b -> a) -> Semiring b (AddIdentity a, Bag (JoinList b))

-- | The <i>best-k</i> extension of <a>maxsumsolutionWith</a>.
maxsumsolutionKWith :: (Ord a, Num a) => Int -> (b -> a) -> Semiring b [(AddIdentity a, Bag (JoinList b))]

-- | The aggregator to take the maximum product of <i>non-negative</i>
--   numbers after <tt>map f</tt>.
maxprodWith :: (Ord a, Num a) => (b -> a) -> Semiring b (AddIdentity a)

-- | The <i>best-k</i> extension of <a>maxprodWith</a>.
maxprodKWith :: (Ord a, Num a) => Int -> (b -> a) -> Semiring b ([AddIdentity a])

-- | The <i>best-k</i> extension of <a>maxprodsolutionXWith</a>.
maxprodsolutionXKWith :: (Ord a, Num a) => Semiring c b -> Int -> (c -> a) -> Semiring c [(AddIdentity a, b)]

-- | The tupling of maxprodsolution and a given semiring. The second
--   component is the aggregation of the maximum items by the given
--   semiring.
maxprodsolutionXWith :: (Ord a, Num a) => Semiring c b -> (c -> a) -> Semiring c (AddIdentity a, b)

-- | The aggregator to find items with the maximum product. The numbers
--   have to be <i>non-negative</i>.
maxprodsolutionWith :: (Ord a, Num a) => (b -> a) -> Semiring b (AddIdentity a, Bag (JoinList b))

-- | The <i>best-k</i> extension of <a>maxprodsolutionWith</a>.
maxprodsolutionKWith :: (Ord a, Num a) => Int -> (b -> a) -> Semiring b [(AddIdentity a, Bag (JoinList b))]

-- | Parallel version of <a>segs</a>.
segsP :: NFData s => [a] -> Semiring a s -> s

-- | Parallel version of <a>inits</a>.
initsP :: NFData s => [a] -> Semiring a s -> s

-- | Parallel version of <a>tails</a>.
tailsP :: NFData s => [a] -> Semiring a s -> s

-- | Parallel version of <a>subs</a>.
subsP :: NFData s => [a] -> Semiring a s -> s

-- | Parallel version of <a>assigns</a>.
assignsP :: NFData s => [m] -> [a] -> Semiring (m, a) s -> s

-- | Parallel version of <a>assignsBy</a>.
assignsByP :: NFData s => (a -> [m]) -> [a] -> Semiring (m, a) s -> s

-- | Constructor of a bag of join lists.
--   
--   For example,
--   
--   <pre>
--   &gt;&gt;&gt; (bag (map joinize [[1,2], [3]])) `crossConcat` (bag (map joinize [[4,5], [6]]))
--   Bag [[1,2,4,5],[1,2,6],[3,4,5],[3,6]]
--   </pre>
crossConcat :: Bag (JoinList a) -> Bag (JoinList a) -> Bag (JoinList a)

-- | Constructor of a bag of join lists.
--   
--   For example,
--   
--   <pre>
--   &gt;&gt;&gt; bagOfSingleton 1
--   Bag [[1]]
--   </pre>
bagOfSingleton :: a -> Bag (JoinList a)

-- | Constructor of a bag of join lists.
--   
--   For example,
--   
--   <pre>
--   &gt;&gt;&gt; emptyBag
--   Bag []
--   </pre>
emptyBag :: Bag (JoinList a)

-- | Constructor of a bag of join lists.
--   
--   For example,
--   
--   <pre>
--   &gt;&gt;&gt; bagOfNil
--   Bag [[]]
--   </pre>
bagOfNil :: Bag (JoinList a)

-- | Constructor of a bag of join lists.
--   
--   For example,
--   
--   <pre>
--   &gt;&gt;&gt; (bag (map joinize [[1,2], [3]])) `bagUnion` (bag (map joinize [[4,5], [6]]))
--   Bag [[1,2],[3],[4,5],[6]]
--   </pre>
bagUnion :: Bag (JoinList a) -> Bag (JoinList a) -> Bag (JoinList a)

-- | The usual semiring is a generic semiring of join lists:
--   
--   <pre>
--   a `times` (b `oplus` c) == (a `times` b) `oplus` (a `times` c)
--   (a `oplus` b) `times` c == (a `times` c) `oplus` (b `times` c)
--   a `times` identity == identity `times` a == identity
--   </pre>
type Semiring a s = GenericSemiring (JoinListAlgebra a) s

-- | Property of <a>times</a> of a JoinListAlgebra:
--   
--   <pre>
--   x `times` (y `times` z) == (x `times` y) `times` z
--   </pre>
prop_Associativity :: Eq b => JoinListAlgebra a b -> (b, b, b) -> Bool

-- | Property of <a>times</a> and <a>nil</a> of a JoinListAlgebra:
--   
--   <pre>
--   (x `times` nil == x) &amp;&amp; (nil `times` x == x)
--   </pre>
prop_Identity :: Eq b => JoinListAlgebra a b -> b -> Bool

-- | A record to hold a function to be applied to elements of a list.
--   
--   This can be generated automatically by <tt>genAllDecl ''JoinList</tt>.
data JoinListMapFs b b'

-- | A wrapper function for JoinList homomorphism.
homJ :: (a -> a -> a) -> (b -> a) -> a -> JoinList b -> a

-- | A fake function of homJ to build <a>JoinListAlgebra</a> instead of
--   executing the homomorphism with it.
homJ' :: (a -> a -> a) -> (b -> a) -> a -> JoinListAlgebra b a

-- | A transfomer that applies given function to every element in every
--   list in a given bag.
mapMap :: (b -> b') -> GenericSemiring (JoinListAlgebra b') a -> GenericSemiring (JoinListAlgebra b) a

-- | This generates all permutations of a given list.
--   
--   For example,
--   
--   <pre>
--   &gt;&gt;&gt; perms "hoge" `aggregateBy` result
--   Bag ["hoge","hoeg","ohge","oheg","hgoe","hgeo","ghoe","gheo","heog","hego","ehog","ehgo","oghe","ogeh","gohe","goeh","oehg","oegh","eohg","eogh","geho","geoh","egho","egoh"]
--   </pre>
perms :: [a] -> Semiring a s -> s

-- | Parallel version of <a>perms</a>.
permsP :: NFData s => [a] -> Semiring a s -> s
instance [overlap ok] Ord a => Ord (JoinList a)
instance [overlap ok] Eq a => Eq (JoinList a)
instance [overlap ok] Read a => Read (JoinList a)
instance [overlap ok] Show a => Show (JoinList a)
instance [overlap ok] NFData a => NFData (JoinList a)
instance [overlap ok] GenericSemiringStructure (JoinListAlgebra b) (JoinList b) (JoinListMapFs b)


-- | This module provides the GTA framework on cons lists, such as
--   definitions of the data structure and its algebra, generators,
--   aggregators, etc.
module GTA.Data.ConsList
data ConsList a
Cons :: a -> (ConsList a) -> ConsList a
Nil :: ConsList a
data ConsListAlgebra b a
ConsListAlgebra :: (b -> a -> a) -> a -> ConsListAlgebra b a
cons :: ConsListAlgebra b a -> b -> a -> a
nil :: ConsListAlgebra b a -> a
consize :: [a] -> ConsList a
deconsize :: ConsList a -> [a]
segs :: [a] -> ConsSemiring a s -> s
inits :: [a] -> ConsSemiring a s -> s
tails :: [a] -> ConsSemiring a s -> s
subs :: [a] -> ConsSemiring a s -> s
assigns :: [m] -> [a] -> ConsSemiring (m, a) s -> s
assignsBy :: (a -> [m]) -> [a] -> ConsSemiring (m, a) s -> s
paths :: BinTree a a -> ConsSemiring a s -> s
mapC :: (b -> a) -> ConsListMapFs b a
count :: Num a => ConsSemiring b a
maxsum :: (Ord a, Num a) => ConsSemiring a (AddIdentity a)
maxsumsolution :: (Ord a, Num a) => ConsSemiring a (AddIdentity a, Bag (ConsList a))
maxsumWith :: (Ord a, Num a) => (b -> a) -> ConsSemiring b (AddIdentity a)
maxsumKWith :: (Ord a, Num a) => Int -> (b -> a) -> ConsSemiring b ([AddIdentity a])
maxsumsolutionXKWith :: (Ord a, Num a) => ConsSemiring c b -> Int -> (c -> a) -> ConsSemiring c [(AddIdentity a, b)]
maxsumsolutionXWith :: (Ord a, Num a) => ConsSemiring c b -> (c -> a) -> ConsSemiring c (AddIdentity a, b)
maxsumsolutionWith :: (Ord a, Num a) => (b -> a) -> ConsSemiring b (AddIdentity a, Bag (ConsList b))
maxsumsolutionKWith :: (Ord a, Num a) => Int -> (b -> a) -> ConsSemiring b [(AddIdentity a, Bag (ConsList b))]
maxprodWith :: (Ord a, Num a) => (b -> a) -> ConsSemiring b (AddIdentity a)
maxprodKWith :: (Ord a, Num a) => Int -> (b -> a) -> ConsSemiring b ([AddIdentity a])
maxprodsolutionXKWith :: (Ord a, Num a) => ConsSemiring c b -> Int -> (c -> a) -> ConsSemiring c [(AddIdentity a, b)]
maxprodsolutionXWith :: (Ord a, Num a) => ConsSemiring c b -> (c -> a) -> ConsSemiring c (AddIdentity a, b)
maxprodsolutionWith :: (Ord a, Num a) => (b -> a) -> ConsSemiring b (AddIdentity a, Bag (ConsList b))
maxprodsolutionKWith :: (Ord a, Num a) => Int -> (b -> a) -> ConsSemiring b [(AddIdentity a, Bag (ConsList b))]
crossCons :: a -> Bag (ConsList a) -> Bag (ConsList a)
emptyBag :: Bag (ConsList a)
bagOfNil :: Bag (ConsList a)
bagUnion :: Bag (ConsList a) -> Bag (ConsList a) -> Bag (ConsList a)
type ConsSemiring a s = GenericSemiring (ConsListAlgebra a) s
foldr' :: (a -> s -> s) -> s -> ConsListAlgebra a s
data ConsListMapFs b b'
mapMap :: (b -> b') -> GenericSemiring (ConsListAlgebra b') a -> GenericSemiring (ConsListAlgebra b) a
perms :: [a] -> ConsSemiring a s -> s
instance [overlap ok] Ord a => Ord (ConsList a)
instance [overlap ok] Eq a => Eq (ConsList a)
instance [overlap ok] Read a => Read (ConsList a)
instance [overlap ok] Show a => Show (ConsList a)
instance [overlap ok] GenericSemiringStructure (ConsListAlgebra b) (ConsList b) (ConsListMapFs b)