Name: compdata Version: 0.6.1.3 Synopsis: Compositional Data Types Description: Based on Wouter Swierstra's Functional Pearl /Data types a 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/ (Workshop on Generic Programming, 83-94, 2011, ) 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 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 package provides the following features: . * Compositional data types in the style of Wouter Swierstra's Functional Pearl /Data types a la carte/. . * 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". . * /Parametric compositional data types/ (Workshop on Mathematically Structured Functional Programming, 3-24, 2012, ). All of the above is also lifted to parametric data types, which enables support for parametric higher-order abstract syntax (PHOAS). This extension resides in the module "Data.Comp.Param". . * /Generalised parametric compositional data types/. All of the above is also lifted to generalised parametric data types, which enables support for typed parametric higher-order abstract syntax (PHOAS). This extension resides in the module "Data.Comp.MultiParam". . * Advanced recursion schemes derived from tree automata. These recursion schemes allow for a higher degree of modularity and make it possible to apply fusion. See /Modular Tree Automata/ (Mathematics of Program Construction, 263-299, 2012, ). . Examples of using (generalised) (parametric) compositional data types are bundled with the package in the libray @examples@. Category: Generics License: BSD3 License-file: LICENSE Author: Patrick Bahr, Tom Hvitved Maintainer: paba@diku.dk Build-Type: Simple Cabal-Version: >=1.9.2 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/Data/Comp/Variables_Test.hs, testsuite/tests/Data/Comp/Multi_Test.hs, testsuite/tests/Data/Comp/Multi/Variables_Test.hs, testsuite/tests/Data/Comp/Examples_Test.hs, testsuite/tests/Data/Comp/Examples/Comp.hs, testsuite/tests/Data/Comp/Examples/Multi.hs, testsuite/tests/Data/Comp/Examples/Param.hs, testsuite/tests/Data/Comp/Examples/MultiParam.hs, testsuite/tests/Test/Utils.hs -- benchmark files benchmark/Test.hs 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 -- example files examples/Examples/Common.hs examples/Examples/Eval.hs examples/Examples/EvalM.hs examples/Examples/Desugar.hs examples/Examples/Automata/Compiler.hs, examples/Examples/Multi/Common.hs examples/Examples/Multi/Eval.hs examples/Examples/Multi/EvalI.hs examples/Examples/Multi/EvalM.hs examples/Examples/Multi/Desugar.hs examples/Examples/Param/Lambda.hs examples/Examples/Param/Names.hs examples/Examples/Param/Graph.hs examples/Examples/MultiParam/Lambda.hs examples/Examples/MultiParam/FOL.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.Variables, Data.Comp.Decompose, Data.Comp.Unification, Data.Comp.Derive, Data.Comp.Matching, Data.Comp.Desugar, Data.Comp.Automata, Data.Comp.Automata.Product, Data.Comp.Number, 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.Number, Data.Comp.Multi.Derive Data.Comp.Multi.Generic, Data.Comp.Multi.Desugar, Data.Comp.Param, Data.Comp.Param.Term, Data.Comp.Param.FreshM, Data.Comp.Param.Sum, Data.Comp.Param.Difunctor, Data.Comp.Param.Ditraversable, Data.Comp.Param.Algebra, Data.Comp.Param.Annotation, Data.Comp.Param.Ops Data.Comp.Param.Equality Data.Comp.Param.Ordering Data.Comp.Param.Show Data.Comp.Param.Derive, Data.Comp.Param.Desugar Data.Comp.Param.Thunk Data.Comp.MultiParam, Data.Comp.MultiParam.Term, Data.Comp.MultiParam.FreshM, Data.Comp.MultiParam.Sum, Data.Comp.MultiParam.HDifunctor, Data.Comp.MultiParam.HDitraversable, Data.Comp.MultiParam.Algebra, Data.Comp.MultiParam.Annotation, Data.Comp.MultiParam.Ops Data.Comp.MultiParam.Equality Data.Comp.MultiParam.Ordering Data.Comp.MultiParam.Show Data.Comp.MultiParam.Derive, Data.Comp.MultiParam.Desugar 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.SmartAConstructors, Data.Comp.Derive.Foldable, Data.Comp.Derive.Traversable, Data.Comp.Derive.Injections, Data.Comp.Derive.Projections, Data.Comp.Derive.HaskellStrict, Data.Comp.Automata.Product.Derive, 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 Data.Comp.Multi.Derive.Injections, Data.Comp.Multi.Derive.Projections, Data.Comp.Param.Derive.Difunctor, Data.Comp.Param.Derive.Ditraversable, Data.Comp.Param.Derive.Equality, Data.Comp.Param.Derive.Ordering, Data.Comp.Param.Derive.Show, Data.Comp.Param.Derive.SmartConstructors, Data.Comp.Param.Derive.SmartAConstructors, Data.Comp.Param.Derive.Injections, Data.Comp.Param.Derive.Projections, Data.Comp.MultiParam.Derive.HDifunctor, Data.Comp.MultiParam.Derive.Equality, Data.Comp.MultiParam.Derive.Ordering, Data.Comp.MultiParam.Derive.Show, Data.Comp.MultiParam.Derive.SmartConstructors, Data.Comp.MultiParam.Derive.SmartAConstructors, Data.Comp.MultiParam.Derive.Injections, Data.Comp.MultiParam.Derive.Projections Build-Depends: base == 4.*, template-haskell, containers, mtl, QuickCheck >= 2, derive, deepseq, th-expand-syns, transformers hs-source-dirs: src ghc-options: -W Test-Suite test Type: exitcode-stdio-1.0 Main-is: Data_Test.hs hs-source-dirs: src testsuite/tests examples Build-Depends: base == 4.*, 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.*, template-haskell, containers, mtl, QuickCheck >= 2, derive, deepseq, criterion, random, uniplate, th-expand-syns, transformers source-repository head type: hg location: https://bitbucket.org/paba/compdata