Testing-Feat

Feat: Functional Enumeration of Algebraic Types

Paper accepted for the Haskell Symposium 2012
Library testing-feat available online including documentation and examples

cabal install testing-feat

Haskell Symposium talk video

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 (for any algebraic type) such that the part a value is in corresponds to the size of the value (measured in the number of constructors). We implement our ideas in a library called which is available online. Feat provides efficient "random access" to values of any desired size. The primary application is property based testing, where it can be used to define any mix of 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 pretty-printer of the Template Haskell library (uncovering several bugs).

Bibtex

 @InProceedings{duregardHaskell12Feat,
  author =	 {Dureg{\aa}rd, Jonas   and   Jansson, Patrik   and   Wang, Meng},
  title =	 {Feat: Functional Enumeration of Algebraic Types},
  longbooktitle ={Proceedings of the 2012 symposium on Haskell},
  pages =	 {61--72},
  numpages =	 12,
  booktitle =	 {Haskell'12},
  doi =		 {10.1145/2364506.2364515},
  COMMENTisbn =	 {978-1-4503-1574-6},
  COMMENTlocation ={Copenhagen, Denmark},
  year =	 2012,
  keywords =	 {enumeration, memoisation, property-based testing},
  publisher =	 {ACM}
 }