package exenum

  1. Overview
  2. Docs
package exenum
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source

Module ExEnum

Build efficient enumerations for datatypes

The exenum library offers constructors to build enumerations for datatypes, that is, functions from (arbitrarily large) integers to values. Such enumerations are very useful for unit testing.

The library is efficient: the n-th element of an enumeration is returned without having computed the (n-1) previous elements. Complexity is in log(n), except for some pathological datatypes.

See the homepage for details: http://exenum.forge.ocamlcore.org/

Inspired by Feat: Functional Enumeration of Algebraic Types, by Duregard, Jansson, Wang, Chalmers University.

Contact: D. Le Botlan (lebotlan atat users.forge.ocamlcore.org)

Example

As an example, consider the following familiar datatype:

 type term = Var of string | App of term * term | Lambda of string * term

Using exenum, one may easily generate zillions of different lambda-terms. For this example, we limit ourselves to four variable names : x, y, u, and v. Then, one may compute for instance term number 2000000000000, which happens to be

((((x v) (fun u -> y)) ((fun u -> y) (fun y -> y))) (((x v) (fun u -> v)) (fun u -> y)))

Efficiency: computing lambda-term number 1E200 (1 followed by 200 zeros) is instantaneous on an antique Intel Centrino.

Building an enumeration from a datatype is straightforward. For instance, the enumeration corresponding to type term is built as follows:

(* We restrict ourselves to four variable names. *)
let e_vars = from_list ~name:"variables" ["x" ; "y" ; "u" ; "v"]

(* Type term is recursive, hence we need a lazy enumeration first. *)
let rec e_term = lazy
  begin
    (* In order to use the enumeration recursively, we need to "pay" a cost. *)
    let r_term = pay e_term in
   
    (* Now, this is the direct translation of the datatype definition. *)
    union 
      [ map e_vars (fun x -> Var x) ;
        map (pair r_term r_term) (fun (t1, t2) -> App (t1, t2)) ;
        map (pair e_vars r_term) (fun (x, t) -> Lambda (x, t))  ] 
  end

(* Here is the enumeration for lambda-terms. *)
let e_term = Lazy.force e_term
type 'a enum

The type of exhaustive enumerations of values of type 'a.

type 'a t = 'a enum

Basics

val from_list : ?name:string -> 'a list -> 'a t

Builds an enumeration from a finite set of values. The name is used for nicer debugging.

val single : ?name:string -> 'a -> 'a t

Enumeration of a single value (derived from from_list).

val cardinal : 'a t -> Big_int.big_int option

Returns the cardinality of type 'a. None means infinity.

val get : 'a t -> Big_int.big_int -> 'a

Returns the nth value of type 'a, starting at 0.

  • raises Failure

    if the index is greater or equal than the cardinality of 'a t.

Finite enumerations for ground types

val e_unit : unit t

One element: ().

val e_bool : bool t

Two elements: true, false

val e_char : char t

Contains 256 elements: from '\000' to '\255'.

val e_pchar : char t

Printable characters (from 32 to 125).

val e_biginterval : Big_int.big_int -> Big_int.big_int -> Big_int.big_int t

Enumeration of a big-integer interval.

val e_interval : int -> int -> int t

Enumeration of an integer interval.

val sub : max:Big_int.big_int -> 'a t -> 'a t

Restrict an enumeration to the given number of elements.

Infinite enumerations for ground types

val e_bigpos : Big_int.big_int t

Strictly positive numbers: [1, +infty[

val e_bignat : Big_int.big_int t

Natural numbers: [0, +infty[

val e_bigint : Big_int.big_int t

All numbers: ] -infty, +infty [ This enumeration starts from 0 and alternates between positive and negative values.

val e_nat : int t

Natural integers: [0, max_int] as an infinite enumeration (hence, non-injective).

val e_pos : int t

Strictly positive integers: [1, max_int] as an infinite enumeration (hence, non-injective).

val e_int : int t

All integers: [min_int, max_int]. This enumeration starts from 0 and alternates between positive and negative values. This enumeration is infinite, hence non-injective.

val e_string : string t

Strings, built only with printable characters.

val e_rstring : char list -> string t

Strings, built only with the given characters.

Composition

val union : 'a t list -> 'a t

Builds an enumeration from a union of enumerations. The enumerations given in the list must be disjoint, otherwise injectivity of the resulting enumeration is not guaranteed.

val product : 'a t list -> 'a list t

Builds an enumeration from a cartesian product of enumerations.

val pair : 'a t -> 'b t -> ('a * 'b) t

Convenience function to build an enumeration of pairs from two enumerations (derived from product and projection functions).

val triple : 'a t -> 'b t -> 'c t -> ('a * 'b * 'c) t
val tuple2 : 'a t -> 'b t -> ('a * 'b) t

Generic names for pair and triple.

val tuple3 : 'a t -> 'b t -> 'c t -> ('a * 'b * 'c) t
val tuple4 : 'a t -> 'b t -> 'c t -> 'd t -> ('a * 'b * 'c * 'd) t
val tuple5 : 'a t -> 'b t -> 'c t -> 'd t -> 'e t -> ('a * 'b * 'c * 'd * 'e) t
val tuple6 : 'a t -> 'b t -> 'c t -> 'd t -> 'e t -> 'f t -> ('a * 'b * 'c * 'd * 'e * 'f) t
val e_list : 'a t -> 'a list t

Enumerations of lists of arbitrary size, starting from the empty list.

val e_array : 'a t -> 'a array t

Enumerations of arrays.

val e_option : 'a t -> 'a option t

Recursion, map

val pay : 'a t Lazy.t -> 'a t

An enumeration is a possibly-infinite set of finite parts. Recursive, infinite enumerations must be built by increasing the cost of each part. The enumeration given in argument must be infinite (which is usually the case when building a recursive enumeration). See examples to understand how to use pay.

val map : 'a t -> ('a -> 'b) -> 'b t

Builds an enumeration by mapping an existing enumeration.

Helper functions

val show : 'a t -> ('a -> string) -> int -> int -> unit

show enum to_string index len outputs values of the given enumeration, using the to_string conversion function, from index index to index (index + len - 1).

val bigshow : 'a t -> ('a -> string) -> Big_int.big_int -> int -> unit

bigshow enum to_string index len is similar to show, except that index is a big_int.

val tester : 'a t -> ?from:Big_int.big_int -> ?upto:Big_int.big_int -> ?verbose_period:int -> len:int -> ('a -> unit) -> unit

tester enum ~len f applies f in sequence to different values of the enumeration. First, len values are taken starting at 0 (or starting from from, if specified). Then, the current index is multiplied by 2 (that is, we start at 2*len) and again len values are considered. This is repeated forever (or while the current index is lower than the upper bound upto).

If verbose_period is strictly positive, a message giving the current index is printed on stdout every verbose_period tests.

Typical usage is: tester enum ~len:10000 f, where f is a testing function.

val get_exen : 'a enum -> 'a Exenum_internals.Exen.t