GTALib: 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 http://www.ipl-lab.org/~emoto/ESOP2012.pdf).
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
(Test), and take the most valuable selection by
filterBy weightlimit capacity
(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.
aggregateBy maxsumsolutionWith getValue
knapsack capacity items = subsP items `filterBy` weightlimit capacity `aggregateBy` maxsumsolutionWith getValue getValue (_, v) = v getWeight (w, _) = w weightlimit w = (<=w) <.> weightsum where weightsum = joinListAlgebra times single nil --workaround for cabal's brace-eating bug x1 `times` x2 = ( x1 + x2) `min` (w+1) single i = getWeight i `min` (w+1) nil = 0
Several examples of GTA programming are found in examples directory at https://bitbucket.org/emoto/gtalib/src.
|Versions [RSS] [faq]||0.0.1, 0.0.2, 0.0.3, 0.0.4, 0.0.5, 0.0.6|
|Dependencies||base (>=4.3 && <4.6), containers (>=0.4 && <0.6), deepseq (>=1.1 && <1.4), parallel (>=3.1 && <3.3), template-haskell (>=2.5 && <2.8) [details]|
|Source repo||head: git clone https://bitbucket.org/emoto/gtalib.git|
|Uploaded||by KentoEmoto at 2012-06-07T09:43:11Z|
|Downloads||5047 total (22 in the last 30 days)|
|Rating||(no votes yet) [estimated by Bayesian average]|
Docs uploaded by user
Build status unknown [no reports yet]