Name: compdata
Version: 0.9
Synopsis: Compositional Data Types
Description:
This library implements the ideas of /Data types a la carte/
(Journal of Functional Programming, 18(4):423-436, 2008,
) as outlined in the
paper /Compositional data types/ (Workshop on Generic Programming,
83-94, 2011, ). The
purpose of this library is to allow the programmer to construct data
types -- as well as the functions defined on them -- in a modular
fashion. The underlying idea is to separate the signature of a data
type from the fixed point construction that produces its recursive
structure. Signatures can then be composed and decomposed freely.
.
Building on that foundation, this library provides additional
extensions and (run-time) optimisations which make 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 library provides the following features:
.
* Compositional data types in the style of Wouter Swierstra's
Functional Pearl /Data types a la carte/. The implementation of
signature subsumption is based on the paper
/Composing and Decomposing Data Types/ (Workshop on Generic
Programming, 2014, to appear), which makes signature composition more
flexible.
.
* Modular definition of functions 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.
.
* 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/ and
/generalised algebraic data types (GADTs)/. All of the above is also lifted
to families of mutually recursive data types and (more generally) GADTs.
This extension resides in the module "Data.Comp.Multi".
.
Examples of using (generalised) compositional data types are bundled
with the package in the folder @examples@.
.
There are some supplementary packages, some of which were included
in previous versions of this package:
.
* @compdata-param@
: a parametric
variant of compositional data types to deal with variable binders
in a systematic way.
.
* @compdata-automata@
: advanced
recursion schemes derived from tree automata that allow for a
higher degree of modularity and make it possible to apply fusion.
.
* @compdata-dags@
: recursion
schemes on directed acyclic graphs.
Category: Generics
License: BSD3
License-file: LICENSE
Author: Patrick Bahr, Tom Hvitved
Maintainer: paba@diku.dk
Build-Type: Simple
Cabal-Version: >=1.9.2
bug-reports: https://github.com/pa-ba/compdata/issues
extra-source-files:
-- test files
testsuite/tests/*.hs
testsuite/tests/Data/*.hs
testsuite/tests/Data/Comp/*.hs
testsuite/tests/Data/Comp/Multi/*.hs
testsuite/tests/Data/Comp/Examples/*.hs
testsuite/tests/Test/Utils.hs
-- benchmark files
benchmark/*.hs
benchmark/DataTypes/*.hs
benchmark/Functions/*.hs
benchmark/Functions/Comp/*.hs
benchmark/Functions/Standard/*.hs
benchmark/Multi/DataTypes/*.hs
benchmark/Multi/Functions/Comp/*.hs
-- example files
examples/Examples/*.hs
examples/Examples/Multi/*.hs
library
Exposed-Modules: Data.Comp
Data.Comp.Annotation
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.Arbitrary
Data.Comp.Show
Data.Comp.Render
Data.Comp.Variables
Data.Comp.Decompose
Data.Comp.Unification
Data.Comp.Derive
Data.Comp.Derive.Utils
Data.Comp.Matching
Data.Comp.Desugar
Data.Comp.Mapping
Data.Comp.Thunk
Data.Comp.Ops
Data.Comp.Multi
Data.Comp.Multi.Term
Data.Comp.Multi.Sum
Data.Comp.Multi.HFunctor
Data.Comp.Multi.HFoldable
Data.Comp.Multi.HTraversable
Data.Comp.Multi.Algebra
Data.Comp.Multi.Annotation
Data.Comp.Multi.Show
Data.Comp.Multi.Equality
Data.Comp.Multi.Ordering
Data.Comp.Multi.Variables
Data.Comp.Multi.Ops
Data.Comp.Multi.Mapping
Data.Comp.Multi.Derive
Data.Comp.Multi.Generic
Data.Comp.Multi.Desugar
Other-Modules: Data.Comp.SubsumeCommon
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.SmartAConstructors
Data.Comp.Derive.Foldable
Data.Comp.Derive.Traversable
Data.Comp.Derive.HaskellStrict
Data.Comp.Multi.Derive.HFunctor
Data.Comp.Multi.Derive.HFoldable
Data.Comp.Multi.Derive.HTraversable
Data.Comp.Multi.Derive.Equality
Data.Comp.Multi.Derive.Ordering
Data.Comp.Multi.Derive.Show
Data.Comp.Multi.Derive.SmartConstructors
Data.Comp.Multi.Derive.SmartAConstructors
Build-Depends: base >= 4.7, base < 5, template-haskell, containers, mtl, QuickCheck >= 2, derive,
deepseq, th-expand-syns, transformers, tree-view
hs-source-dirs: src
ghc-options: -W
Test-Suite test
Type: exitcode-stdio-1.0
Main-is: Data_Test.hs
hs-source-dirs: testsuite/tests examples src
Build-Depends: base >= 4.7, base < 5, template-haskell, containers, mtl, QuickCheck >= 2,
HUnit, test-framework, test-framework-hunit, test-framework-quickcheck2, derive,
th-expand-syns, deepseq, transformers
Benchmark algebra
Type: exitcode-stdio-1.0
Main-is: Benchmark.hs
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
Build-Depends: base >= 4.7, base < 5, template-haskell, containers, mtl, QuickCheck >= 2, derive, deepseq, criterion, random, uniplate, th-expand-syns, transformers
source-repository head
type: git
location: https://github.com/pa-ba/compdata