feat

Facilities for enumerating and sampling algebraic data types
README

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 library is laid out as follows:

  • The module Feat.IFSeq implements
    the signature Feat.IFSEQ
    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 module Feat.Enum implements
    enumerations.
    An enumeration of type 'a enum is a function of a size s
    to a sequence of elements of size s.

  • The module Feat.Bigint
    offers a function random of type Z.t -> Z.t,
    thus repairing an unfortunate omission in the library zarith.

  • The external library
    Fix
    comes in handy when building enumerations
    of recursive algebraic data types:
    see the demo.

Install
Published
31 Dec 2020
Sources
archive.tar.gz
md5=84c4cb2a3579d6f7cb37564b47907519
sha512=9031651c9b2ce9c9d6bfa2a913e5df7ae993bccd6790cdae07768762258e2f942495033921f996fd8ed6885c177c7e3207bd24d27d25a0afbe358d82eda74fa2
Dependencies
fix
>= "20181206"
dune
>= "1.3"
ocaml
>= "4.03"
Reverse Dependencies