Library

Module

Module type

Parameter

Class

Class type

sectionYPositions = computeSectionYPositions($el), 10)" x-init="setTimeout(() => sectionYPositions = computeSectionYPositions($el), 10)">

On This Page

Legend:

Library

Module

Module type

Parameter

Class

Class type

Library

Module

Module type

Parameter

Class

Class type

Module defining trees which is the main data-structure behind shrinking used by the `Gen`

. This module shoul be used only when defining a new runner for a new Test framework.

This module encodes a non-bounded branching tree. Values are generated lazily via the module `Seq`

.

`type 'a tree = 'a t`

Convenient alias if `'a t`

is shadowed.

`make f root`

returns a tree with root `root`

and the children are recursively produced (lazily) with `f`

.

`of_seq seq root`

returns a tree whose root is `root`

and the children are generated via `seq`

. Hence, if `seq`

is not empty, the depth of the tree is `1`

.

`val root : 'a t -> 'a`

`root tree`

returns the root of the tree.

`map f tree`

maps `f`

to all the elements of the tree. The merge function is reset to `Seq.append`

. There is no automatic way to preserve the merge behavior with `map`

. However, you can save the previous behavior with `get_merge`

and set a new behavior with `with_merge`

.

`binary_search ~initial ~origin`

implements a binary search enumerating elements. Elements are guaranteed to be in the interval `origin;initial`

.

Note: If `initial < origin`

, it returns a tree with the single node `origin`

.

```
val fractional_search :
?exhaustive_search_digits:int ->
?precision_digits:int ->
initial:float ->
origin:float ->
unit ->
float t
```

```
fractional_search ?exhaustive_search_digits ?precision_digits
~initial ~origin ()
```

returns a tree of depth one where the root is `initial`

and children are ordered by the prefix ordering (modulo float representations) starting with `origin`

. The children are always float between `origin`

and `initial`

starting with floats with few digits.

`linear_search`

returns a tree of depth 1 whose `root`

is `initial`

and children are the number from `origin`

included to `initial`

excluded.

`val return : 'a -> 'a t`

`return value`

returns a tree containing a single node with `value`

.

`bind tree f`

returns a tree where `f`

is applied (lazily) to all the values of `tree`

. Since `f`

returns itself a tree, `bind`

must be able to merge values of `tree`

with the ones produced by `f`

. This can be done via the merging process specified by the tree returned by `f`

.

`module Syntax : sig ... end`

By using `bind`

, one needs to be able to merge sequences of trees. To understand why, let's give an informal definition of `bind`

:

```
let rec bind tree f =
let {root;children=left} = tree in
(* children : 'a t Seq.t *)
let {root; children=right} f root in
(* How should we combine the sequence of trees denotes by [left] and [right]? *)
```

A natural way to merging them as denoted by the variable names is to use `Seq.append`

. However, this is an arbitrary choice. Libraries using this module may redefine the default merging procedure to enable more complex behaviors.

Even though `Seq.append`

is arbitrary, in practice it leads to predictable and easy to unerstand behaviors.

Notice that in the definition above, there are two trees, hence maybe two different merging behaviors. However, by typing, only one is allowed: the one resulting of the application of `f root`

.

The type of the `merge`

prevents `'a t`

to be an applicative functor.

`with_merge ~merge tree`

sets the merging behavior as `merge`

.

`get_merge tree`

returns the merge function for this tree.

`module Forest : sig ... end`

A forest can be considered as a non-empty sequence of trees. The functions declared in this module transposed naturally the functions provided on `tree`

.

`shrink tree f`

returns a value `a`

that has the following specification:

`f a = Error _`

`path(a,tree.root) = true`

- forall v, if
`v \in path(a, tree.root)`

then`f v = Error _`

- if
`v' = Left(v)`

and`v \in path(a, tree.root)`

then`f v = Ok _`

Assuming that `f tree.root`

is `Error _`

.

On This Page