Compositional data types
Compositional data types
复制标题
组合数据类型
DOI：
10.1145/2036918.2036930
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Tom Hvitved
中科院分区：
文献类型：
--
作者：
P. Bahr;Tom Hvitved
基于Wouter Swierstra的数据类型，我们提出了一个适合实际应用的组合数据类型的综合Haskell库。在这个框架中，数据类型和函数可以以模块化的方式定义。我们扩展了现有的工作，实现了广泛的递归方案，包括一元计算。最重要的是，我们将递归数据类型推广到上下文，这使我们能够描述一种特殊但频繁的蜕变。由此建立的术语同态的概念允许灵活的重用，并使捷径融合风格的森林砍伐产生相当大的加速。我们证明了我们的框架中的编译器建设的设置，此外，我们比较组合数据类型与通用编程技术，并表明，两者都是可比的运行时性能和表现力，而我们的方法允许更严格的类型。我们通过将组合数据类型提升到递归数据类型和广义代数数据类型来证实这一结论。最后，我们比较了我们的技术与传统的实现代数数据类型的运行时性能。结果出奇的好。
Building on Wouter Swierstra's Data types à la carte, we present a comprehensive Haskell library of compositional data types suitable for practical applications. In this framework, data types and functions on them can be defined in a modular fashion. We extend the existing work by implementing a wide array of recursion schemes including monadic computations. Above all, we generalise recursive data types to contexts, which allow us to characterise a special yet frequent kind of catamorphisms. The thus established notion of term homomorphisms allows for flexible reuse and enables short-cut fusion style deforestation which yields considerable speedups. We demonstrate our framework in the setting of compiler construction, and moreover, we compare compositional data types with generic programming techniques and show that both are comparable in run-time performance and expressivity while our approach allows for stricter types. We substantiate this conclusion by lifting compositional data types to recursive data types and generalised algebraic data types. Lastly, we compare the run-time performance of our techniques with traditional implementations over algebraic data types. The results are surprisingly good.