Up

Module type Observer

Signature

type 'a t

An 'a Quickcheck.Observer.t represents observations that can be made to distinguish values of type 'a. An observer maps values of type 'a to disjoint subsets ("buckets") using a finite number of observations.

Observers are used to construct distributions of random functions; see Quickcheck.Generator.fn.

One constructs an observer by breaking down an input into basic type constituents that can be individually observed. Use built-in observers for basic types when possible. Use either or the variant* observers to distinguish clauses of variants. Use the tuple* observers to get at individual fields of tuples or records. When you have a custom type with no built-in observer, construct an observer for an equivalent type, then use unmap. Use recursive to build observers for recursive types. See the below example for a binary search tree:


        type 'a bst = Leaf | Node of 'a bst * 'a * 'a bst

        let bst_obs key_obs =
          recursive (fun bst_of_key_obs ->
            unmap (Either.obs Unit.obs (tuple3 bst_of_key_obs key_obs bst_of_key_obs))
              ~f:(function
                | Leaf           -> First ()
                | Node (l, k, r) -> Second (l, k, r))
              ~f_sexp:(fun () -> Sexp.Atom "either_of_bst"))
type 'a gen
val doubleton : ('a -> bool) -> f_sexp:(unit -> Sexp.t) -> 'a t

doubleton f ~f_sexp maps values to two "buckets" (as described in t above), depending on whether they satisfy f. f_sexp should describe f.

val enum : int -> f:('a -> int) -> f_sexp:(unit -> Sexp.t) -> 'a t

enum n ~f maps values to n buckets, where f produces the index for a bucket from 0 to n-1 for each value.

val of_list : 'a list -> equal:('a -> 'a -> bool) -> sexp_of_elt:('a -> Sexp.t) -> 'a t

of_list list ~equal maps values in list to separate buckets, and compares observed values to the elements of list using equal.

val recursive : ('a t -> 'a t) -> 'a t

Fixed point observer; use recursive to create observers for recursive types. For example:


        let sexp_obs =
          recursive (fun sexp_t ->
            unmap (variant2 string (list sexp_t))
              ~f:(function
                | Sexp.Atom atom -> `A atom
                | Sexp.List list -> `B list)
              ~f_sexp:(fun () -> Sexp.Atom "variant_of_sexp"))
val variant3 : 'a t -> 'b t -> 'c t -> [
| `A of 'a
| `B of 'b
| `C of 'c
] t
val variant4 : 'a t -> 'b t -> 'c t -> 'd t -> [
| `A of 'a
| `B of 'b
| `C of 'c
| `D of 'd
] t
val variant5 : 'a t -> 'b t -> 'c t -> 'd t -> 'e t -> [
| `A of 'a
| `B of 'b
| `C of 'c
| `D of 'd
| `E of 'e
] t
val variant6 : 'a t -> 'b t -> 'c t -> 'd t -> 'e t -> 'f t -> [
| `A of 'a
| `B of 'b
| `C of 'c
| `D of 'd
| `E of 'e
| `F of 'f
] t
val of_predicate : 'a t -> 'a t -> f:('a -> bool) -> f_sexp:(unit -> Sexp.t) -> 'a t

of_predicate t1 t2 ~f combines t1 and t2, where t1 observes values that satisfy f and t2 observes values that do not satisfy f.

val comparison : compare:('a -> 'a -> int) -> eq:'a -> lt:'a t -> gt:'a t -> compare_sexp:(unit -> Sexp.t) -> sexp_of_eq:('a -> Sexp.t) -> 'a t

comparison ~compare ~eq ~lt ~gt combines observers lt and gt, where lt observes values less than eq according to compare, and gt observes values greater than eq according to compare.

val branching_factor : _ t -> int

branching_factor t produces the number of nodes in the decision tree of t, or one less than the number of buckets in t. This value is artificially capped at 2^15-1 in order to avoid intractable function generators and overflow in arithmetic. The result may be an overapproximation for observers constructed with fn or of_fun.

val observe : 'a t -> 'b gen -> sexp_of_rng:('b -> Sexp.t) -> branching_factor:int -> (('a -> 'b) * (unit -> Sexp.t)) gen

observe t gen ~sexp_of_rng ~branching_factor constructs a generator for a function type using t to observe the domain and gen to generate the range. Each generated function also comes with a (lazy, unmemoized) sexp describing it. The size of the function's decision tree is determined by branching_factor and the sexps of its return values are constructed by sexp_of_rng.

The functions in the resulting generator will all be intensionally unique: no two will make the same set of decisions in the same order. However, as two such functions may make the same set of decisions in a different order, they will not be extensionally unique. While it would be nice to have distributions of extensionally unique functions, implementing such a generator is quite difficult, and likely not worth the effort.

val singleton : unit -> _ t

maps all values to a single bucket.

val unmap : 'a t -> f:('b -> 'a) -> f_sexp:(unit -> Sexp.t) -> 'b t

unmap t ~f ~f_sexp applies f to values before observing them using t.

val weighted_union : (float * 'a t) list -> 'a t

Nondeterministic observer. Presents a weighted choice of multiple observers. When observe builds a decision tree, it randomly chooses nodes from any of these observers with probability proportional to the given weights. All weights must be finite and non-negative.

val variant2 : 'a t -> 'b t -> [
| `A of 'a
| `B of 'b
] t
val tuple2 : 'a t -> 'b t -> ('a * 'b) t
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 fn : ?p:float -> 'a gen -> 'b t -> sexp_of_dom:('a -> Sexp.t) -> ('a -> 'b) t

Observer for function type. fn ~p gen t ~sexp_of_dom observes a function by generating random inputs from gen, applying the function, and observing the output using t.

When observe builds a single random decision tree node from the result of fn, it chooses between generating a new input and observing a previously generated input. It does the former with probability p and the latter with probability 1. -. p.

p defaults to 0.25, and must be between 0 and 1 (both inclusive).

val of_fun : (unit -> 'a t) -> 'a t

of_fun f produces an observer that lazily applies f.

It is recommended that f should not do a lot of expensive work and should not be memoized. Instead, spread out the work of generating an observer over many of_fun calls combined with, e.g., variant or tuple. This allows lazily generated observers to be garbage collected after each test and the relevant portions cheaply recomputed in subsequent tests, rather than accumulating without bound over time.