Recursive Structure

Define arbitraries able to generate recursive structures.

letrec

Generate recursive structures.

Prefer fc.letrec over fc.memo. Most of the features offered by fc.memo can now be implemented with fc.letrec.

Signatures:

fc.letrec(builder)

with:

builder — builder function defining how to build the recursive structure, it answers to the signature (tie) => object with key corresponding to the name of the arbitrary and with vaue the arbitrary itself. The tie function given to builder should be used as a placeholder to handle the recursion. It takes as input the name of the arbitrary to use in the recursion.

Usages:

// Setup the tree structure:
const { tree } = fc.letrec((tie) => ({
  // Warning: In version 2.x and before, there is no automatic control over the depth of the generated data-structures.
  // As a consequence to avoid your data-structures to be too deep, it is highly recommended to add the constraint `depthFactor`
  // onto your usages of `option` and `oneof` and to put the arbitrary without recursion first.
  // In version 3.x, `depthSize` (previously `depthFactor`) and `withCrossShrink` will be enabled by default.
  tree: fc.oneof({ depthSize: 'small', withCrossShrink: true }, tie('leaf'), tie('node')),
  node: fc.record({
    left: tie('tree'),
    right: tie('tree'),
  }),
  leaf: fc.nat(),
}));
// Use the arbitrary:
tree;
// Examples of generated values:
// • 1948660480
// • {"left":2147483625,"right":28}
// • {"left":{"left":21,"right":2147483628},"right":{"left":2147483619,"right":{"left":1419355913,"right":2}}}
// • 423794071
// • 27
// • …

fc.letrec((tie) => ({
  node: fc.record({
    value: fc.nat(),
    left: fc.option(tie('node'), { maxDepth: 1, depthIdentifier: 'tree' }),
    right: fc.option(tie('node'), { maxDepth: 1, depthIdentifier: 'tree' }),
  }),
})).node;
// Note: You can limit the depth of the generated structrures by using the constraint `maxDepth` (see `option` and `oneof`).
//   On the example above we need to specify `depthIdentifier` to share the depth between left and right branches...
// Examples of generated values:
// • {"value":2147483632,"left":{"value":1485877161,"left":null,"right":null},"right":{"value":2096527253,"left":null,"right":null}}
// • {"value":1056088736,"left":null,"right":{"value":2147483623,"left":null,"right":null}}
// • {"value":1227733267,"left":{"value":21,"left":null,"right":null},"right":{"value":2147483628,"left":null,"right":null}}
// • {"value":17,"left":null,"right":{"value":12,"left":null,"right":null}}
// • {"value":17,"left":{"value":12,"left":null,"right":null},"right":{"value":1475453319,"left":null,"right":null}}
// • …

// Setup the depth identifier shared across all nodes:
const depthIdentifier = fc.createDepthIdentifier();
// Use the arbitrary:
fc.letrec((tie) => ({
  node: fc.record({
    value: fc.nat(),
    left: fc.option(tie('node'), { maxDepth: 1, depthIdentifier }),
    right: fc.option(tie('node'), { maxDepth: 1, depthIdentifier }),
  }),
})).node;
// Note: Calling `createDepthIdentifier` is another way to pass a value for `depthIdentifier`. Compared to the string-based
// version, demo-ed in the snippet above, it has the benefit to never collide with other identifiers manually specified.
// Examples of generated values:
// • {"value":2147483645,"left":{"value":9,"left":null,"right":null},"right":{"value":0,"left":null,"right":null}}
// • {"value":7,"left":null,"right":{"value":96999551,"left":null,"right":null}}
// • {"value":3,"left":{"value":1312350013,"left":null,"right":null},"right":{"value":2147483636,"left":null,"right":null}}
// • {"value":2051975271,"left":{"value":2147483645,"left":null,"right":null},"right":{"value":104175133,"left":null,"right":null}}
// • {"value":2,"left":{"value":1530374940,"left":null,"right":null},"right":{"value":3,"left":null,"right":null}}
// • …

fc.letrec((tie) => ({
  node: fc.record({
    value: fc.nat(),
    left: fc.option(tie('node'), { maxDepth: 1 }),
    right: fc.option(tie('node'), { maxDepth: 1 }),
  }),
})).node;
// ...If we don't specify it, the maximal number of right in a given path will be limited to 1, but may include intermediate left.
//    Thus the resulting trees might be deeper than 1.
// Examples of generated values:
// • {"value":14,"left":{"value":1703987241,"left":null,"right":{"value":643118365,"left":null,"right":null}},"right":null}
// • {"value":26,"left":{"value":1662273887,"left":null,"right":{"value":525337883,"left":null,"right":null}},"right":{"value":387211283,"left":{"value":213767981,"left":null,"right":null},"right":null}}
// • {"value":2121842454,"left":null,"right":{"value":1835255719,"left":{"value":1989636808,"left":null,"right":null},"right":null}}
// • {"value":1438784023,"left":{"value":24,"left":null,"right":{"value":420442369,"left":null,"right":null}},"right":{"value":2062024199,"left":{"value":2147483624,"left":null,"right":null},"right":null}}
// • {"value":1331332801,"left":null,"right":{"value":1001840875,"left":{"value":1327656949,"left":null,"right":null},"right":null}}
// • …

fc.letrec((tie) => ({
  tree: fc.oneof({ maxDepth: 2 }, { arbitrary: tie('leaf'), weight: 0 }, { arbitrary: tie('node'), weight: 1 }),
  node: fc.record({ left: tie('tree'), right: tie('tree') }),
  leaf: fc.nat(),
})).tree;
// Note: Exact depth of 2: not more not less.
// Note: If you use multiple `option` or `oneof` to define such recursive structure
//   you may want to specify a `depthIdentifier` so that they share the exact same depth.
//   See examples above for more details.
// Examples of generated values:
// • {"left":{"left":1313545969,"right":13},"right":{"left":920759934,"right":1438357599}}
// • {"left":{"left":17,"right":5},"right":{"left":1377847469,"right":2147483630}}
// • {"left":{"left":18,"right":1121202},"right":{"left":27,"right":1975057275}}
// • {"left":{"left":1542103881,"right":9},"right":{"left":27,"right":21}}
// • {"left":{"left":749002681,"right":2069272340},"right":{"left":19,"right":1584346024}}
// • …

fc.statistics(
  fc.letrec((tie) => ({
    node: fc.record({
      value: fc.nat(),
      left: fc.option(tie('node')),
      right: fc.option(tie('node')),
    }),
  })).node,
  (v) => {
    function size(n) {
      if (n === null) return 0;
      else return 1 + size(n.left) + size(n.right);
    }
    const s = size(v);
    let lower = 1;
    const next = (n) => (String(n)[0] === '1' ? n * 5 : n * 2);
    while (next(lower) <= s) {
      lower = next(lower);
    }
    return `${lower} to ${next(lower) - 1} items`;
  },
);
// Computed statistics for 10k generated values:
// For size = "xsmall":
// • 5 to 9 items....43.99%
// • 10 to 49 items..38.97%
// • 1 to 4 items....17.04%
// For size = "small":
// • 10 to 49 items..85.92%
// • 5 to 9 items.....5.12%
// • 50 to 99 items...4.60%
// • 1 to 4 items.....4.36%
// For size = "medium":
// • 100 to 499 items..82.79%
// • 50 to 99 items....10.31%
// • 1 to 4 items.......3.73%
// • 10 to 49 items.....2.95%
// • 5 to 9 items.......0.17%

fc.statistics(
  fc.letrec((tie) => ({
    node: fc.record({
      value: fc.nat(),
      children: fc.oneof(
        { depthIdentifier: 'node' },
        fc.constant([]),
        fc.array(tie('node'), { depthIdentifier: 'node' }),
      ),
    }),
  })).node,
  (v) => {
    function size(n) {
      if (n === null) return 0;
      else return 1 + n.children.reduce((acc, child) => acc + size(child), 0);
    }
    const s = size(v);
    let lower = 1;
    const next = (n) => (String(n)[0] === '1' ? n * 5 : n * 2);
    while (next(lower) <= s) {
      lower = next(lower);
    }
    return `${lower} to ${next(lower) - 1} items`;
  },
);
// Computed statistics for 10k generated values:
// For size = "xsmall":
// • 1 to 4 items..100.00%
// For size = "small":
// • 1 to 4 items....60.31%
// • 10 to 49 items..23.53%
// • 5 to 9 items....16.16%
// For size = "medium":
// • 1 to 4 items......51.33%
// • 50 to 99 items....26.34%
// • 10 to 49 items....16.25%
// • 100 to 499 items...5.89%
// • 5 to 9 items.......0.13%

Resources: API reference.
Available since 1.16.0.

memo

Generate recursive structures.

Prefer fc.letrec when feasible

Initially fc.memo has been designed to offer a higher control over the generated depth. Unfortunately it came with a cost: the arbitrary itself is costly to build. Most of the features offered by fc.memo can now be done using fc.letrec coupled with fc.option or fc.oneof. Whenever possible, we recommend using fc.letrec instead of fc.memo.