Functional Enumeration of Algebraic Types

feat is a library that offers support for counting, enumerating, and sampling objects of a certain kind, such as (say) the inhabitants of an algebraic data type.

Feat was inspired by the paper Feat: Functional Enumeration of Algebraic Types by Jonas Duregård, Patrik Jansson and Meng Wang (2012). It can perhaps be compared with the Haskell library testing-feat, although a detailed comparison has not been carried out.

The packages feat and feat-num offer the same API: you should use either feat or feat-num, not both. feat relies on the big integer library zarith, whereas feat-num relies on the legacy library num. Both packages offer the same API: the main module, named Feat or FeatNum, offers three submodules named Num, IFSeq, and Enum.

• Feat.Num This module implements a small set of operations on big integers.
• Feat.IFSeq This module provides an abstract data type of implicit, finite sequences. An implicit sequence is not explicitly represented in memory as an actual sequence of elements: instead, it is described by a data structure which contains enough information to produce an arbitrary element upon request. This design decision imposes some constraints on the operations that can be efficiently supported: for instance, filter is not supported.
• Feat.Enum This module offers a concrete data type 'a enum of enumerations of elements of type 'a. Suppose that every element of type 'a is implicitly assigned a certain size. Then, an enumeration is a function of an integer s to the (implicit, finite) sequence of all elements whose size is s.