Name: compdata
Version: 0.1
Synopsis: Compositional Data Types
Description:
Based on Wouter Swierstra's Functional Pearl /Data types à la carte/
(Journal of Functional Programming, 18(4):423-436, 2008),
this package provides a framework for defining recursive
data types in a compositional manner. The fundamental idea of
compositional data types is to separate the signature of a data type
from the fixed point construction that produces its recursive
structure. By allowing to compose and decompose signatures,
/compositional data types/ enable to combine data types in a flexible
way. The key point of Wouter Swierstra's original work is to define
functions on /compositional data types/ in a compositional manner as
well by leveraging Haskell's type class machinery.
.
Building on that foundation, this library provides additional
extensions and (run-time) optimisations which makes compositional data types
usable for practical implementations. In particular, it
provides an excellent framework for manipulating and analysing
abstract syntax trees in a type-safe manner. Thus, it is perfectly
suited for programming language implementations, especially, in an environment
consisting of a family of tightly interwoven /domain-specific languages/.
.
In concrete terms, this package provides the following features:
.
* Compositional data types in the style of Wouter Swierstra's
Functional Pearl /Data types à la carte/.
.
* Modular definition of function on compositional data types through
catamorphisms and anamorphisms as well as more structured
recursion schemes such as primitive recursion and co-recursion,
and course-of-value iteration and co-iteration.
.
* Support for monadic computations via monadic variants of all
recursion schemes.
.
* Support of a succinct programming style over compositional data types
via generic programming combinators that allow various forms of
generic transformations and generic queries.
.
* Generalisation of compositional data types (terms) to
compositional data types \"with holes\" (contexts). This allows
flexible reuse of a wide variety of catamorphisms (called
/term homomorphisms/) as well as an efficient composition of them.
.
* Operations on signatures, for example, to add and remove
annotations of abstract syntax trees. This includes combinators to
propagate annotations fully automatically through certain
term homomorphisms.
.
* Optimisation of the implementation of recursion schemes. This
includes /short-cut fusion/ style optimisation rules which yield a
performance boost of up to factor six.
.
* Efficient implementation of catamorphisms on non-polynomial
signatures that contain function types. This allows to represent
/higher-order abstract syntax/ with compositional data types.
.
* Automatic derivation of instances of all relevant type classes for
using compositional data types via /Template Haskell/. This includes
instances of 'Prelude.Eq', 'Prelude.Ord' and 'Prelude.Show' that are
derived via instances for functorial variants of them. Additionally,
also /smart constructors/, which allow to easily construct inhabitants
of compositional data types, are automatically generated.
.
* /Mutually recursive data types/. All of the above is also lifted to
families of mutually recursive data types.
.
For examples illustrating the use of compositional data types, consult
"Data.Comp" resp. "Data.Comp.Multi" for mutually recursive data types.
Category: Generics
License: BSD3
License-file: LICENSE
Author: Patrick Bahr, Tom Hvitved
Maintainer: paba@diku.dk
Build-Type: Custom
Cabal-Version: >=1.8.0.6
extra-source-files:
-- test files
testsuite/tests/Data_Test.hs,
testsuite/tests/Data/Comp_Test.hs,
testsuite/tests/Data/Comp/Equality_Test.hs,
testsuite/tests/Test/Utils.hs
-- benchmark files
benchmark/Benchmark.hs
benchmark/DataTypes.hs
benchmark/Functions.hs
benchmark/DataTypes/Comp.hs
benchmark/DataTypes/Transform.hs
benchmark/DataTypes/Standard.hs
benchmark/Multi/DataTypes/Comp.hs
benchmark/Multi/Functions/Comp/Eval.hs
benchmark/Multi/Functions/Comp/Desugar.hs
benchmark/Transformations.hs
benchmark/Functions/Comp.hs
benchmark/Functions/Comp/Eval.hs
benchmark/Functions/Comp/Desugar.hs
benchmark/Functions/Comp/FreeVars.hs
benchmark/Functions/Comp/Inference.hs
benchmark/Functions/Standard/Eval.hs
benchmark/Functions/Standard/Desugar.hs
benchmark/Functions/Standard/FreeVars.hs
benchmark/Functions/Standard/Inference.hs
benchmark/Functions/Standard.hs
flag test
description: Build test executable.
default: False
flag benchmark
description: Build benchmark executable.
default: False
library
Exposed-Modules: Data.Comp, Data.Comp.Product, Data.Comp.Sum,
Data.Comp.Term, Data.Comp.Algebra, Data.Comp.Equality,
Data.Comp.Ordering, Data.Comp.DeepSeq, Data.Comp.Generic
Data.Comp.TermRewriting, Data.Comp.Automata,
Data.Comp.Arbitrary, Data.Comp.Show, Data.Comp.Variables,
Data.Comp.Decompose, Data.Comp.Unification,
Data.Comp.Derive, Data.Comp.Matching, Data.Comp.Multi,
Data.Comp.Multi.Term, Data.Comp.Multi.Sum,
Data.Comp.Multi.Functor, Data.Comp.Multi.ExpFunctor,
Data.Comp.Multi.Foldable, Data.Comp.Multi.Traversable,
Data.Comp.Multi.Algebra,
Data.Comp.Multi.Product, Data.Comp.Multi.Show,
Data.Comp.Multi.Equality, Data.Comp.Multi.Variables,
Data.Comp.Multi.Ops, Data.Comp.Ops, Data.Comp.ExpFunctor
Other-Modules: Data.Comp.Derive.Utils, Data.Comp.Derive.Equality,
Data.Comp.Derive.Ordering, Data.Comp.Derive.Arbitrary,
Data.Comp.Derive.Show, Data.Comp.Derive.DeepSeq,
Data.Comp.Derive.SmartConstructors,
Data.Comp.Derive.Foldable, Data.Comp.Derive.ExpFunctor,
Data.Comp.Derive.Traversable,
Data.Comp.Derive.Multi.Functor,
Data.Comp.Derive.Multi.Foldable,
Data.Comp.Derive.Multi.Traversable,
Data.Comp.Derive.Multi.Equality,
Data.Comp.Derive.Multi.Show,
Data.Comp.Derive.Multi.ExpFunctor,
Data.Comp.Derive.Multi.SmartConstructors
Build-Depends: base == 4.*, template-haskell, containers, mtl, QuickCheck >= 2, derive, deepseq, th-expand-syns
hs-source-dirs: src
ghc-options: -W
Executable test
Main-is: Data_Test.hs
Build-Depends: base == 4.*, template-haskell, containers, mtl, QuickCheck >= 2, test-framework, test-framework-quickcheck2, derive, th-expand-syns, deepseq
hs-source-dirs: src testsuite/tests
ghc-options: -fhpc
if !flag(test)
buildable: False
Executable benchmark
Main-is: Benchmark.hs
Build-Depends: base == 4.*, template-haskell, containers, mtl, QuickCheck >= 2, derive, deepseq, criterion, random, uniplate, th-expand-syns
hs-source-dirs: src benchmark
ghc-options: -W -O2
-- Disable short-cut fusion rules in order to compare optimised and unoptimised code.
cpp-options: -DNO_RULES
if !flag(benchmark)
buildable: False