GTALib-0.0.5: A library for GTA programming

GTA.Core

Description

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 http://www.ipl-lab.org/~emoto/ESOP2012.pdf).

Example of GTA program

The following code is a GTA program to solve the 0-1 Knapsack problem (http://en.wikipedia.org/wiki/Knapsack_problem). It appears to be an exponential cost proram in the number of input items, because it appears to generate all item selections by subsP items (Generate), discard those with total weight heavier than the knapsack's capacity by filterBy weightlimit capacity (Test), and take the most valuable selection by aggregateBy maxsumsolutionWith getValue (Aggregate). However, it actually runs in a linear time owing to our proposed program transformation 'Filter-embedding Semiring Fusion' implemented in the library. In addition, it runs in parallel so that you can get linear speedup. The predicate weightlimit is defined based on the join list algebra given in GTA.Data.JoinList module.

knapsack capacity items =
subsP items
`filterBy` weightlimit capacity
`aggregateBy` maxsumsolutionWith getValue

getValue (_, v) = v
getWeight (w, _) = w

weightlimit w = (<=w) <.> weightsum where
weightsum = JoinListAlgebra{..}
x1 `times` x2  = (   x1 +    x2) `min` (w+1)
single i  = getWeight i `min` (w+1)
nil = 0

Several example GTA programs are found in examples directory at https://bitbucket.org/emoto/gtalib/src.

This module provides generic functionalities in the GTA programming framework. Data-strructure-dependent definitions are found in GTA.Data.* modules.

Synopsis

Documentation

data Bag a Source

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.

Constructors

 Bag [a]

Instances

 (Eq a, Ord a) => Eq (Bag a) Ord a => Ord (Bag a) Read a => Read (Bag a) Show a => Show (Bag a) NFData a => NFData (Bag a)

Commutative monoid is an algebra of an associative, commutative binary operator with its identity.

Constructors

 CommutativeMonoid Fieldsoplus :: a -> a -> aCommutative, associative binary operator: (a `oplus` b) `oplus` c == a `oplus` (b `oplus` c) a `oplus` b == b `oplus` a identity :: aThe identity of oplus: a `oplus` identity == identity `oplus` a == a

data GenericSemiring alg a Source

A generic semiring is a combination of a commutative monoid and an algebra such that operators of the algebra distributes over oplus and identity is the zero of the operators.

For example, the usual semiring is a combination of a commutative monoid and a JoinListAlgebra, 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)
a `times` identity == identity `times` a == identity

Constructors

 GenericSemiring Fieldsmonoid :: CommutativeMonoid a algebra :: alg a

class GenericSemiringStructure alg free uniformer | alg -> free, alg -> uniformer whereSource

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.

Methods

freeAlgebra :: alg freeSource

The free algebra (i.e., an algebra whose operators are the constructors).

pairAlgebra :: alg a -> alg b -> alg (a, b)Source

This simply tuples two algebras.

makeAlgebra :: CommutativeMonoid m -> alg a -> (m -> [a]) -> (a -> m) -> alg mSource

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.

foldingAlgebra :: (a -> a -> a) -> a -> uniformer a -> alg aSource

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.

hom :: alg a -> free -> aSource

The homomorphism from the free algrba, i.e., the catamorphism (used in inefficient impl.).

freeSemiring :: GenericSemiring alg (Bag free)Source

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.

liftedSemiring :: Ord c => GenericSemiring alg a -> alg c -> GenericSemiring alg (Map c a)Source

The most important function to build lifted generic semiring from another generic semiring and an algebra, used in the filter-embedding transformation.

pairSemiring :: GenericSemiring alg a -> GenericSemiring alg b -> GenericSemiring alg (a, b)Source

This simply tuples two generic semirings.

shom :: GenericSemiring alg a -> Bag free -> aSource

Homomorphism of a generic semiring (used in inefficient impl.).

Instances

 GenericSemiringStructure (LVTreeAlgebra b) (LVTree b) (LVTreeMapFs b) GenericSemiringStructure (JoinListAlgebra b) (JoinList b) (JoinListMapFs b) Instance declaration of GTA.Data.GenericSemiringStructure for join lists. The implementation is quite straightforward. This can be generated automatically by genAllDecl ''JoinList. GenericSemiringStructure (ConsListAlgebra b) (ConsList b) (ConsListMapFs b) GenericSemiringStructure (BinTreeAlgebra n l) (BinTree n l) (BinTreeMapFs n l)

bag :: forall a. [a] -> Bag aSource

Makes a bag that contains the given memebrs.

(>==) :: forall alg free uniformer c b k. (GenericSemiringStructure alg free uniformer, Ord c) => (GenericSemiring alg (Map c b) -> Map k b) -> (k -> Bool, alg c) -> GenericSemiring alg b -> bSource

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.

(>=>) :: forall alg free uniformer b k. GenericSemiringStructure alg free uniformer => (GenericSemiring alg b -> b) -> GenericSemiring alg b -> bSource

Combinator for connecting a generator and an aggregator to get the result. An aggregator is represented by a generic semiring.

(>=<) :: forall alg free uniformer alg' free' uniformer' c. (GenericSemiringStructure alg free uniformer, GenericSemiringStructure alg' free' uniformer') => (GenericSemiring alg' c -> c) -> (GenericSemiring alg c -> GenericSemiring alg' c) -> GenericSemiring alg c -> cSource

Combinator for transforming a generator by a transformer. A transformer is an aggregator polymorphic over another generic semiring.

(>##) :: GenericSemiringStructure alg free uniformer => (GenericSemiring alg (Bag free) -> Bag free) -> (b -> Bool, alg b) -> GenericSemiring alg (Bag free) -> Bag freeSource

Inefficient version of >== (i.e., it does not do optimziation at all).

(>#>) :: GenericSemiringStructure alg free uniformer => (GenericSemiring alg (Bag free) -> Bag free) -> GenericSemiring alg a -> aSource

Inefficient version of >=> (i.e., it does not do optimziation at all).

(<.>) :: forall alg a b. (b -> Bool) -> alg b -> (b -> Bool, alg b)Source

Operator to build a pair of a judgement function and an algebra, which represents a Tester.

items :: Bag a -> [a]Source

Extracts members from a bag. The order of members is undecidable.

revOrd :: forall a. a -> RevOrd aSource

Reverses the order of the argument, so that we can use aggregators maxXXX to take the minimum XXX.

data RevOrd a Source

Reverses the order of a given type.

Constructors

 RevOrd a

Instances

 Eq a => Eq (RevOrd a) Num a => Num (RevOrd a) Ord a => Ord (RevOrd a) Read a => Read (RevOrd a) Show a => Show (RevOrd a)

maxsumBy :: forall free uniformer alg a. (GenericSemiringStructure alg free uniformer, Ord a, Num a) => uniformer (AddIdentity a) -> GenericSemiring alg (AddIdentity a)Source

The aggregator to the maximum sum after map.

maxsumKBy :: forall a free uniformer alg. (GenericSemiringStructure alg free uniformer, Ord a, Num a) => Int -> uniformer (AddIdentity a) -> GenericSemiring alg [AddIdentity a]Source

The best-k extension of maxsumBy.

maxsumsolutionXKBy :: forall a free uniformer b alg. (GenericSemiringStructure alg free uniformer, Ord a, Num a) => GenericSemiring alg b -> Int -> uniformer (AddIdentity a) -> GenericSemiring alg [(AddIdentity a, b)]Source

The best-k extension of maxsumsolutionXBy.

maxsumsolutionXBy :: forall free uniformer a t alg. (GenericSemiringStructure alg free uniformer, Ord a, Num a) => GenericSemiring alg t -> uniformer (AddIdentity a) -> GenericSemiring alg (AddIdentity a, t)Source

An instance of maxMonoSumsolutionXBy with the usual summation.

maxsumsolutionBy :: forall a alg free uniformer. (GenericSemiringStructure alg free uniformer, Ord a, Num a) => uniformer (AddIdentity a) -> GenericSemiring alg (AddIdentity a, Bag free)Source

An instance of maxMonoSumsolutionBy with the usual summation.

maxsumsolutionKBy :: forall a alg free uniformer. (GenericSemiringStructure alg free uniformer, Ord a, Num a) => Int -> uniformer (AddIdentity a) -> GenericSemiring alg [(AddIdentity a, Bag free)]Source

The best-k extension of maxsumsolutionBy.

maxprodBy :: forall free uniformer alg a. (GenericSemiringStructure alg free uniformer, Ord a, Num a) => uniformer (AddIdentity a) -> GenericSemiring alg (AddIdentity a)Source

The aggregator to take the maximum product on non-negative numbers.

maxprodKBy :: forall a free uniformer alg. (GenericSemiringStructure alg free uniformer, Ord a, Num a) => Int -> uniformer (AddIdentity a) -> GenericSemiring alg [AddIdentity a]Source

The best-k extension of maxprodBy

maxprodsolutionXKBy :: forall a free uniformer b alg. (GenericSemiringStructure alg free uniformer, Ord a, Num a) => GenericSemiring alg b -> Int -> uniformer (AddIdentity a) -> GenericSemiring alg [(AddIdentity a, b)]Source

The best-k extension of maxprodsolutionXBy

maxprodsolutionXBy :: forall free uniformer a t alg. (GenericSemiringStructure alg free uniformer, Ord a, Num a) => GenericSemiring alg t -> uniformer (AddIdentity a) -> GenericSemiring alg (AddIdentity a, t)Source

The tupling of maxprodsolutionBy and a given generic semiring. The second component of the result is the aggregation of the best items by the given generic emiring.

maxprodsolutionBy :: forall a alg free uniformer. (GenericSemiringStructure alg free uniformer, Ord a, Num a) => uniformer (AddIdentity a) -> GenericSemiring alg (AddIdentity a, Bag free)Source

The aggregator to find the items with the maximum product on non-negative numbers.

maxprodsolutionKBy :: forall a alg free uniformer. (GenericSemiringStructure alg free uniformer, Ord a, Num a) => Int -> uniformer (AddIdentity a) -> GenericSemiring alg [(AddIdentity a, Bag free)]Source

The best-k extension of maxprodsolutionBy

maxMonoSumBy :: forall free uniformer alg a. (GenericSemiringStructure alg free uniformer, Ord a) => (a -> a -> a) -> a -> uniformer (AddIdentity a) -> GenericSemiring alg (AddIdentity a)Source

The aggregator to take the maximum items under a given monotonic sum mplus with its identity mid after map.

c == a `max` b   =>   d `mplus` (a `max` b) == (d `mplus` a) `max` (d `mplus` b)

maxMonoSumsolutionXBy :: forall free uniformer a t alg. (GenericSemiringStructure alg free uniformer, Ord a) => (a -> a -> a) -> a -> GenericSemiring alg t -> uniformer (AddIdentity a) -> GenericSemiring alg (AddIdentity a, t)Source

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.

maxMonoSumKBy :: forall a free uniformer alg. (GenericSemiringStructure alg free uniformer, Ord a) => (a -> a -> a) -> a -> Int -> uniformer (AddIdentity a) -> GenericSemiring alg [AddIdentity a]Source

The aggregator to find the best k maximum items under a given monotonic sum. An extension of maxMonoSumBy.

maxMonoSumsolutionXKBy :: forall a free uniformer b alg. (GenericSemiringStructure alg free uniformer, Ord a) => (a -> a -> a) -> a -> GenericSemiring alg b -> Int -> uniformer (AddIdentity a) -> GenericSemiring alg [(AddIdentity a, b)]Source

The best-k extension of maxMonoSumsolutionXBy.

addIdentity :: forall a. a -> AddIdentity aSource

Introduces an identity.

data AddIdentity a Source

Introduces an identity Identity to a given type.

Constructors

Instances

 Eq a => Eq (AddIdentity a) Ord a => Ord (AddIdentity a) Read a => Read (AddIdentity a) Show a => Show (AddIdentity a) NFData a => NFData (AddIdentity a)

sumproductBy :: forall free uniformer alg a. (GenericSemiringStructure alg free uniformer, Num a) => uniformer a -> GenericSemiring alg aSource

The aggregator to compute a sum of products. Each product is of all values in the data structure after map.

result :: forall alg free uniformer. GenericSemiringStructure alg free uniformer => GenericSemiring alg (Bag free)Source

The aggregator to extract all items generated by a generator.

filterBy :: forall alg free uniformer c b k. (GenericSemiringStructure alg free uniformer, Ord c) => (GenericSemiring alg (Map c b) -> Map k b) -> (k -> Bool, alg c) -> GenericSemiring alg b -> bSource

The same as >==

aggregateBy :: forall alg free uniformer b k. GenericSemiringStructure alg free uniformer => (GenericSemiring alg b -> b) -> GenericSemiring alg b -> bSource

The same as >=>

transformBy :: forall alg free uniformer alg' free' uniformer' c. (GenericSemiringStructure alg free uniformer, GenericSemiringStructure alg' free' uniformer') => (GenericSemiring alg' c -> c) -> (GenericSemiring alg c -> GenericSemiring alg' c) -> GenericSemiring alg c -> cSource

The same as >=<