Feat

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.

Two packages, feat and feat-num, offer the same API. feat relies on the big integer library zarith, whereas feat-num relies on the library num. Both packages offer the same API: the main module (named Feat or FeatNum) offers three submodules named Num, IFSeq, and Enum.

• The submodule Num implements a small set of operations on big integers.

• The submodule IFSeq implements the signature IFSEQ_EXTENDED of (implicit, finite) sequences.

  These sequences are implicit, which means that they are not explicitly epresented in memory as an actual sequence of elements; instead, they are 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.

• The submodule Enum implements the signature ENUM of enumerations. An enumeration of type 'a enum is a function of a size s to a sequence of elements of size s.
• The external library Fix comes in handy when building enumerations of recursive algebraic data types: see the demo.