Duregard, Jonas and Jansson, Patrik and Wang, Meng (2012) Feat: Functional Enumeration of Algebraic Types. In: Proceedings of the 2012 Haskell Symposium. ICFP International Conference on Functional Programming . ACM, New York, USA, pp. 6172. ISBN 9781450315746. (doi:10.1145/2364506.2364515) (KAR id:47486)
PDF
Publisher pdf
Language: English 

Download (259kB)
Preview

Preview 
This file may not be suitable for users of assistive technology.
Request an accessible format


Official URL: http://dx.doi.org/10.1145/2364506.2364515 
Abstract
In mathematics, an enumeration of a set S is a bijective function from (an initial segment of) the natural numbers to S. We define "functional enumerations" as efficiently computable such bijections. This paper describes a theory of functional enumeration and provides an algebra of enumerations closed under sums, products, guarded recursion and bijections. We partition each enumerated set into numbered, finite subsets.
We provide a generic enumeration such that the number of each part corresponds to the size of its values (measured in the number of constructors). We implement our ideas in a Haskell library called testingfeat, and make the source code freely available. Feat provides efficient "random access" to enumerated values. The primary application is propertybased testing, where it is used to define both random sampling (for example QuickCheck generators) and exhaustive enumeration (in the style of SmallCheck). We claim that functional enumeration is the best option for automatically generating test cases from large groups of mutually recursive syntax tree types. As a case study we use Feat to test the prettyprinter of the Template Haskell library (uncovering several bugs).
Item Type:  Book section 

DOI/Identification number:  10.1145/2364506.2364515 
Uncontrolled keywords:  Enumeration, Propertybased testing, Memoisation 
Subjects: 
Q Science > QA Mathematics (inc Computing science) > QA 75 Electronic computers. Computer science Q Science > QA Mathematics (inc Computing science) > QA 76 Software, computer programming, 
Divisions:  Divisions > Division of Computing, Engineering and Mathematical Sciences > School of Computing 
Depositing User:  Meng Wang 
Date Deposited:  01 Mar 2015 00:56 UTC 
Last Modified:  16 Nov 2021 10:19 UTC 
Resource URI:  https://kar.kent.ac.uk/id/eprint/47486 (The current URI for this page, for reference purposes) 
 Link to SensusAccess
 Export to:
 RefWorks
 EPrints3 XML
 BibTeX
 CSV
 Depositors only (login required):