úÎÛÅŅGš      !"#$%&'()*+,-./0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~€‚ƒ„…†‡ˆ‰Š‹ŒŽ‘’“”•–—˜™š›œžŸ ĄĒĢĪĨĶ§ĻĐŠŦŽ­ŪŊ°ąēģīĩķ·ļđ Safe-InferedDThe first part is the name, the second - a list of type parameters, J the third - a list of constructors. For each constructor we have a name , and a list describing constructor fields. *Returns type information of a given type. Apply š to the name. None‚This function generates a definition of the algebra of a given data structure. For example, given a data structure defined below,  : data BinTree n l = BinNode n (BinTree n l) (BinTree n l)  | BinLeaf l 8the following definition of the algebra is generated by genAlgebraDecl ''BinTree. . data BinTreeAlgebra n l a = BinTreeAlgebra { $ binNode :: n -> a -> a -> a,  binLeaf :: l -> a  } Ļ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,  : data BinTree n l = BinNode n (BinTree n l) (BinTree n l)  | BinLeaf l %the following record is generated by genMapFunctionsDecl ''BinTree. + data BinTreeMapFs n l b' = BinTreeMapFs {  binNodeF :: n -> b',  binLeafF :: l -> b'  } 'This function generates an instance of P for a given data structure. For example, given a data structure defined below,  : data BinTree n l = BinNode n (BinTree n l) (BinTree n l)  | BinLeaf l %the following record is generated by genInstanceDecl''BinTree. _ instance GenericSemiringStructure (BinTreeAlgebra n l) (BinTree n l) (BinTreeMapFs n l) where + freeAlgebra = BinTreeAlgebra {..} where  binNode = BinNode  binLeaf = BinLeaf 7 pairAlgebra lvta1 lvta2 = BinTreeAlgebra {..} where J binNode a (l1, l2) (r1, r2) = (binNode1 a l1 r1, binNode2 a l2 r2) > binLeaf a = (binLeaf1 a, binLeaf2 a) T (binNode1, binLeaf1) = let BinTreeAlgebra {..} = lvta1 in (binNode, binLeaf) T (binNode2, binLeaf2) = let BinTreeAlgebra {..} = lvta2 in (binNode, binLeaf) X makeAlgebra (CommutativeMonoid {..}) lvta frec fsingle = BinTreeAlgebra {..} where f binNode a l r = foldr oplus identity [fsingle (binNode' a l' r') | l' <- frec l, r' <- frec r] , binLeaf a = fsingle (binLeaf' a) S (binNode', binLeaf') = let BinTreeAlgebra {..} = lvta in (binNode, binLeaf) I foldingAlgebra op iop (BinTreeMapFs {..}) = BinTreeAlgebra {..} where 0 binNode a l r = binNodeF a `op` l `op` r " binLeaf a = binLeafF a ' hom (BinTreeAlgebra {..}) = h where 1 h (BinNode a l r) = binNode a (h l) (h r) % h (BinLeaf a) = binLeaf a  PGiven a data structure, this function generates a definition of its algebra (by genAlgebraDecl!), a record of map functions (by genMapFunctionsDecl), and an instance of  (by genInstanceDecl ). Usage:  genAllDecl ''BinTree. None0%Reverses the order of a given type. Introduces an identity   to a given type. Å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. KThe free algebra (i.e., an algebra whose operators are the constructors). "This simply tuples two algebras. žThis is used to lift a given algebra to the same level as a given monoid so that the combination of the lifted algebra and the monoid is a generic semiring. —This is used to make an algebra from a usual binary operator; every operator in the algebra simply combines its operand by the given binary operator. \The homomorphism from the free algrba, i.e., the catamorphism (used in inefficient impl.). ĐFree generic semiring to build a bag of given data structures (such as lists, binary trees, etc.). This is a combination of the bag monoid and the lifted free algebra. ™The most important function to build lifted generic semiring from another generic semiring and an algebra, used in the filter-embedding transformation. +This simply tuples two generic semirings. AHomomorphism of a generic semiring (used in inefficient impl.). A generic semiring is a combination of a commutative monoid and an algebra such that operators of the algebra distributes over  and  is the zero of the operators. OFor example, the usual semiring is a combination of a commutative monoid and a  8, in which we have the distributivity and the zeroness: @ a `times` (b `oplus` c) == (a `times` b) `oplus` (a `times` c) @ (a `oplus` b) `times` c == (a `times` c) `oplus` (b `times` c) 6 a `times` identity == identity `times` a == identity dCommutative monoid is an algebra of an associative, commutative binary operator with its identity. +Commutative, associative binary operator: 4 (a `oplus` b) `oplus` c == a `oplus` (b `oplus` c)  a `oplus` b == b `oplus` a The identity of : / a `oplus` identity == identity `oplus` a == a ~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., Bag [1,2] == Bag [2,1] is True. CExtracts members from a bag. The order of members is undecidable. !.Makes a bag that contains the given memebrs. "š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. #€Combinator for connecting a generator and an aggregator to get the result. An aggregator is represented by a generic semiring. $…Combinator for transforming a generator by a transformer. A transformer is an aggregator polymorphic over another generic semiring. % The same as " & The same as # ' The same as $ (Inefficient version of ". (i.e., it does not do optimziation at all). )Inefficient version of #. (i.e., it does not do optimziation at all). *]Operator to build a pair of a judgement function and an algebra, which represents a Tester. +?The aggregator to extract all items generated by a generator. ,gThe aggregator to compute a sum of products. Each product is of all values in the data structure after map. -Introduces an identity. .EThe aggregator to take the maximum items under a given monotonic sum mplus with its identity mid after map. R c == a `max` b => d `mplus` (a `max` b) == (d `mplus` a) `max` (d `mplus` b) /Ĩ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. 0]The aggregator to find the best k maximum items under a given monotonic sum. An extension of .. 1The best-k extension of /. 2(The aggregator to the maximum sum after map. 3The best-k extension of 2. 4The best-k extension of 5. 5An instance of / with the usual summation. 6An instance of maxMonoSumsolutionBy with the usual summation. 7The best-k extension of 6. 8.The aggregator to take the maximum product on  non-negative numbers. 9The best-k extension of 8 :The best-k extension of ; ;The tupling of <… and a given generic semiring. The second component of the result is the aggregation of the best items by the given generic emiring. <=The aggregator to find the items with the maximum product on  non-negative numbers. =The best-k extension of < >dReverses the order of the argument, so that we can use aggregators maxXXX to take the minimum XXX. >  !"#$%&'()*+,-./0123456789:;<=>ŧž―ūŋĀ8  !"#$%&'()*+,-./0123456789:;<=>8 !"#$()* >23456789:;<=./01- ,+%&'+   !"#$%&'()*+,-./0123456789:;<=>ŧž―ūŋĀNone"?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^Á ?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^ SUTOPQRLMNHJIDEFG@ABCV]^\Z[WXYK??@ABCDEFGHJIKLMNOPQRSUTVWXYZ[\]^ÁÂNone,_8The usual semiring is a generic semiring of join lists: @ a `times` (b `oplus` c) == (a `times` b) `oplus` (a `times` c) @ (a `oplus` b) `times` c == (a `times` c) `oplus` (b `times` c) 6 a `times` identity == identity `times` a == identity `AA record to hold a function to be applied to elements of a list. 'This can be generated automatically by  genAllDecl ''JoinList. bThe algebra of join lists. We assume that d is associative and f& is its identity, inheriting those of j and h:  4 x `times` (y `times` z) == (x `times` y) `times` z % x `times` nil == nil `times` x == x 'This can be generated automatically by  genAllDecl ''JoinList. g Join lists.   x ++ y ==> x `Times` y  [a] ==> Single a  [] ==> Nil We assume that j is associative and h is its identity: 4 x `Times` (y `Times` z) == (x `Times` y) `Times` z % x `Times` Nil == Nil `Times` x == x kA wrapper function for record b* . (I needed this as a workaround of cabal's brace-eating bug.) l Property of d of a JoinListAlgebra: 4 x `times` (y `times` z) == (x `times` y) `times` z m Property of d and f of a JoinListAlgebra: . (x `times` nil == x) && (nil `times` x == x) n.Conversion from a usual list to a join list. o.Conversion from a join list to a usual list. pHThis generates all segments (continuous subsequences) of a given list. For example, !segs [1,2,3] `aggregateBy` result(Bag [[1],[2],[3],[2,3],[1,2],[1,2,3],[]]q.This generates all prefixes of a given list. For example, "inits [1,2,3] `aggregateBy` resultBag [[],[1],[1,2],[1,2,3]]r.This generates all suffixes of a given list. For example, "tails [1,2,3] `aggregateBy` resultBag [[1,2,3],[2,3],[3],[]]s2This generates all subsequences of a given list. For example, !subs [1,2,3] `aggregateBy` result.Bag [[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]t]This generates all assignments of elements of the first list to elements of the second list. For example, 1assigns [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)]]uThis is a generalization of t8: the values to be assigned is dependent of the target. For example, VassignsBy (\a -> 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)]]vIThis generates all paths from the root to leaves of a given binary tree. For example, n*Main GTA.Data.BinTree> paths (BinNode 1 (BinLeaf 2) (BinNode 3 (BinLeaf 4) (BinLeaf 5))) `aggregateBy` resultBag [[1,2],[1,3,4],[1,3,5]]w Wrapper for `. x@The aggregator to count the number of items in a generated bag. y(The aggregator to take the maximum sum. z3The aggregator to find items with the maximum sum. {-The aggregator to take the maximum sum after map f. |The best-k extension of {. }The best-k extension of ~. ~ˆThe tupling of maxsumsolution and a given semiring. The second component is the aggregation of the maximum items by the given semiring. 8The aggregator to find items with the maximum sum after map f. €The best-k extension of . .The aggregator to take the maximum product of  non-negative numbers after map f. ‚The best-k extension of . ƒThe best-k extension of „. „‰The tupling of maxprodsolution and a given semiring. The second component is the aggregation of the maximum items by the given semiring. …NThe aggregator to find items with the maximum product. The numbers have to be  non-negative. †The best-k extension of …. ‡Parallel version of p. ˆParallel version of q. ‰Parallel version of r. ŠParallel version of s. ‹Parallel version of t. ŒParallel version of u. $Constructor of a bag of join lists.  For example, O(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]]Ž$Constructor of a bag of join lists.  For example, bagOfSingleton 1 Bag [[1]]$Constructor of a bag of join lists.  For example, bagOfNilBag [[]]$Constructor of a bag of join lists.  For example, emptyBagBag []‘$Constructor of a bag of join lists.  For example, L(bag (map joinize [[1,2], [3]])) `bagUnion` (bag (map joinize [[4,5], [6]]))Bag [[1,2],[3],[4,5],[6]]ÃwInstance declaration of GTA.Data.GenericSemiringStructure for join lists. The implementation is quite straightforward. 'This can be generated automatically by  genAllDecl ''JoinList. 9_`abcdefghijklmnopqrstuvwxyz{|}~€‚ƒ„…†‡ˆ‰Š‹ŒŽ‘ÄÅÆĮČÃ3_`abcdefghijklmnopqrstuvwxyz{|}~€‚ƒ„…†‡ˆ‰Š‹ŒŽ‘3gjihbcdefnopqrstvuwxyz{|}~€‚ƒ„…†‡ˆ‰Š‹ŒŽ‘_lmk`a1_`abcdefgjihklmnopqrstuvwxyz{|}~€‚ƒ„…†‡ˆ‰Š‹ŒŽ‘ÄÅÆĮČÃNone-’“”•–—˜™š›œžŸ ĄĒĢĪĨĶ§ĻĐŠŦŽ­ŪŊ°ąēģīĩķ·ļđÉĘËĖÍ(’“”•–—˜™š›œžŸ ĄĒĢĪĨĶ§ĻĐŠŦŽ­ŪŊ°ąēģīĩķ·ļđ(™›š•–—˜œŸ ĄĒĢĪĨĶ§ĻĐŠŦŽ­ŪŊ°ąēģīĩķļ·đ’ž“”'’“”•–—˜™›šœžŸ ĄĒĢĪĨĶ§ĻĐŠŦŽ­ŪŊ°ąēģīĩķ·ļđÉĘËĖÍÎ      !"##$%&'()*+,-./0123456789:;<=>?@ABCDDEFGGHIJKLMNNOPPQRSTUVWXYZ[\]^_`a  bcdefghijklmnopqrstuWXYvwxyz{|}~€‚ƒ„…†‡ˆ‰Š‹ŒŽ‘d’f“”•–nopqrst—WXYvwxyz{|}~€˜Š‹Œ™š›œžŸ ĄĒĢĪĨĶ§ĻĐŠŦŽ­ŪŊ GTALib-0.0.5GTA.Util.TypeInfo)GTA.Util.GenericSemiringStructureTemplateGTA.CoreGTA.Data.BinTreeGTA.Data.JoinListGTA.Data.ConsListGTA.DataGenericSemiringStructureJoinListAlgebraTypeInfotypeInfo simpleNamegenAlgebraDeclgenMapFunctionsDeclgenInstanceDecl genAllDeclRevOrd AddIdentityIdentity freeAlgebra pairAlgebra makeAlgebrafoldingAlgebrahom freeSemiringliftedSemiring pairSemiringshomGenericSemiringmonoidalgebraCommutativeMonoidoplusidentityBagitemsbag>==>=>>=<filterBy aggregateBy transformBy>##>#><.>result sumproductBy addIdentity maxMonoSumBymaxMonoSumsolutionXBy maxMonoSumKBymaxMonoSumsolutionXKBymaxsumBy maxsumKBymaxsumsolutionXKBymaxsumsolutionXBymaxsumsolutionBymaxsumsolutionKBy maxprodBy maxprodKBymaxprodsolutionXKBymaxprodsolutionXBymaxprodsolutionBymaxprodsolutionKByrevOrdBinTreeSemiring BinTreeMapFsbinNodeFbinLeafFBinTreeAlgebrabinNodebinLeafBinTreeBinLeafBinNodeLVTreeSemiring LVTreeMapFsleafLVF LVTreeAlgebranodeLVleafLVLVTreeLeafLVNodeLVlvtreescountmaxsummaxsumsolution assignTrans assignTreesselectssubtreeSelectsWithRootsubtreeSelectsSemiring JoinListMapFssingleFtimessinglenilJoinListNilSingleTimesjoinListAlgebraprop_Associativity prop_Identityjoinize dejoinizesegsinitstailssubsassigns assignsBypathsmapJ maxsumWith maxsumKWithmaxsumsolutionXKWithmaxsumsolutionXWithmaxsumsolutionWithmaxsumsolutionKWith maxprodWith maxprodKWithmaxprodsolutionXKWithmaxprodsolutionXWithmaxprodsolutionWithmaxprodsolutionKWithsegsPinitsPtailsPsubsPassignsP assignsByP crossConcatbagOfSingletonbagOfNilemptyBagbagUnion ConsSemiring ConsListMapFsconsFConsListAlgebraconsConsListConsconsize deconsizefoldr'mapC crossConstemplate-haskellLanguage.Haskell.TH.SyntaxnameBase $fOrdRevOrd $fNumRevOrd$fNFDataAddIdentity$fOrdAddIdentity$fEqBag $fNFDataBag;$fGenericSemiringStructureBinTreeAlgebraBinTreeBinTreeMapFs8$fGenericSemiringStructureLVTreeAlgebraLVTreeLVTreeMapFs>$fGenericSemiringStructureJoinListAlgebraJoinListJoinListMapFs $fOrdJoinList $fEqJoinList$fReadJoinList$fShowJoinList$fNFDataJoinList $fOrdConsList $fEqConsList$fReadConsList$fShowConsList>$fGenericSemiringStructureConsListAlgebraConsListConsListMapFs