A Lightweight Optimization Technique for Data Types à la Carte
Data types a la carte (DTC) is a technique to modularly add new variants to data types. A drawback of DTC compared to simple variant types,which is the common way to define data types in functional programming language, is runtime inefficiency in destruction of these values. In this paper we propose a lightweight optimization technique for functions that destruct the values of DTC data types. It makes run as efficiently as their non-DTC counterparts by just (1) deriving non-extensible algebraic datatypes isomorphic to extensible data types defined in DTC fashion (2) using them within the type annotations that specify concrete data types using the composition operator given in DTC. The approach is based on our insight on the functions: they never depend on any concrete data types but merely constrain them. We implement functions that take an extensible data type defined in DTC fashion and derive an isomorphic non-extensible algebraic data type using Template Haskell. Our experimental results show that using our approach DTC functions run as efficient as their non-DTC counterparts and avoid performance slowdown even if the data types are extended multiple times.
Tue 15 Mar
|14:00 - 14:05|
|14:05 - 14:40|
|14:40 - 15:00|
Bastian Kruck, Stefan Lehmann, Christoph Kessler, Jakob Reschke, Tim Felgentreff, Jens Lincke, Robert HirschfeldDOI Pre-print Media Attached