Recursive & Lazy Arbitraries

fast-check provides powerful tools for generating recursive data structures, which are essential for testing algorithms that operate on inputs like trees, linked lists, or nested JSON objects. The primary mechanisms for this are "lazy" arbitraries, which defer their definition until they are needed, preventing infinite loops during setup. The two main functions for this purpose are fc.letrec and fc.memo. These helpers allow for the definition of complex, self-referential data generators in a declarative and safe manner.

Sources: examples/README.md

fc.letrec: The Core of Recursive Generation

The fc.letrec function is the foundation for creating mutually recursive arbitraries. It accepts a builder function that receives a tie function as its argument. This tie function acts as a lazy-loaded placeholder, allowing you to reference arbitraries that are defined within the same letrec scope before they are fully constructed.

The builder function must return a dictionary where keys are the names of the arbitraries and values are their definitions. These arbitraries can then be accessed from the object returned by fc.letrec.

Sources: packages/fast-check/src/arbitrary/letrec.ts

High-Level Flow

The following diagram illustrates how fc.letrec uses the tie function to resolve lazy dependencies between arbitraries.

fc.memo: Optimizing Generation with Memoization

The fc.memo function is a helper used to memoize an arbitrary's definition. It takes a builder function () => Arbitrary<T> and ensures this function is executed only once. Subsequent calls will return the cached arbitrary instance.

In the context of recursive structures, fc.memo is critical. When used with fc.letrec, it guarantees that every call to tie('myArbitrary') resolves to the exact same arbitrary instance. This is crucial for performance and for the shrinking process to work correctly, as it avoids re-creating and re-evaluating the same complex arbitrary multiple times.

Sources: packages/fast-check/src/arbitrary/memo.ts, examples/002-recursive/isSearchTree/main.spec.ts:13-14

Practical Implementation: Binary Search Tree Example

A common use case for lazy and recursive arbitraries is generating tree structures. The following example demonstrates how to create an arbitrary for a binary tree using fc.memo and fc.letrec.

Sources: examples/002-recursive/isSearchTree/main.spec.ts

Arbitrary Definition

The binaryTree arbitrary is defined to be either a leaf (a node with no children) or a node (a node with left and right children, which are themselves binary trees).

// examples/002-recursive/isSearchTree/main.spec.ts:13-23
const binaryTree = fc.memo<Tree>((tie) =>
  fc.letrec((tie) => ({
    tree: fc.oneof(tie('leaf'), tie('node')),
    node: fc.record({
      value: fc.nat(),
      left: tie('tree'),
      right: tie('tree'),
    }),
    leaf: fc.record({ value: fc.nat(), left: fc.constant(null), right: fc.constant(null) }),
  })).tree,
);

Generated Data Structure

The code above generates objects that conform to the following structure, where a Tree can be either a Leaf or a Node.

Key Considerations and Best Practices

When building recursive arbitraries, several factors are crucial for ensuring correctness and performance.

Sources: packages/fast-check/MIGRATION_2.X_TO_3.X.md

For example, the following is the correct way to structure the oneof call to ensure the generator can easily produce leaves and terminate recursion:

// Correct: Base case first
const { tree } = fc.letrec((tie) => ({
  tree: fc.oneof(tie('leaf'), tie('node')), 
  // ...
}));

An incorrect implementation would be to place the recursive node case first, which would bias the generator towards deeper trees and could have performance implications.

// Incorrect: Recursive case first
const { tree } = fc.letrec((tie) => ({
  tree: fc.oneof(tie('node'), tie('leaf')), // BAD!!!
  // ...
}));

Sources: packages/fast-check/MIGRATION_2.X_TO_3.X.md

Evolution of letrec

The letrec arbitrary has been subject to refinement and refactoring, indicating its importance in the fast-check ecosystem.

• Self-Referencing Capability: A circular option was briefly added to fc.letrec but was later reverted. This suggests careful consideration is being given to the API design for handling different types of recursive definitions.
• Refactoring: Several internal refactorings have been performed to factorize letrec implementations and extract the logic for building lazy arbitraries. This improves maintainability and consistency.

Sources: website/blog/2025-12-15-whats-new-in-fast-check-4-4-0/index.md

Conclusion

Recursive and lazy arbitraries, primarily through fc.letrec and fc.memo, are indispensable features of fast-check for property-based testing of algorithms that handle complex, self-referential data structures. By allowing for the deferred and memoized definition of arbitraries, fast-check provides a safe, declarative, and performant way to generate valid recursive inputs like trees. Understanding how to correctly structure these arbitraries, particularly by prioritizing base cases, is key to leveraging their full potential.