GTA.Core

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 = homJ' times single nil
   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.

Documentation

data Bag 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.

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)

data CommutativeMonoid a

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

Constructors

CommutativeMonoid

Fields

oplus :: a -> a -> a

identity :: a

data GenericSemiring alg a

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

Fields

monoid :: CommutativeMonoid a

algebra :: alg a

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

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 free

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

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

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

hom :: alg a -> free -> a

freeSemiring :: GenericSemiring alg (Bag free)

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

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

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

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 a

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

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

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

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 free

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

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

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

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

items :: Bag a -> [a]

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

revOrd :: forall a. a -> RevOrd a

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

data RevOrd a

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)

NFData a => NFData (RevOrd a)

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

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]

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

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)

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)

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

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)

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]

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

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)

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)

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

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)

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)

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]

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

The best-k extension of maxMonoSumsolutionXBy.

addIdentity :: forall a. a -> AddIdentity a

Introduces an identity.

data AddIdentity a

Introduces an identity Identity to a given type.

Constructors

AddIdentity a

Identity

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 a

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)

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

The same as >==

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

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

The same as >=<