Pruning and Memoization Bring Bottom-Up Enumeration to miniKanren

Towards Bottom-Up Enumeration in miniKanren via Pruning and Memoization

We present two small library combinators for miniKanren that bring bottom-up enumeration with observational deduplication, a standard tool in non-relational program-by-example synthesizers, into the relational setting. The prune combinator deduplicates answer streams by user-supplied keys, while defrel/bank memoizes relations against canonical fresh variables, enabling a single pruned stream to be built bottom-up and replayed at call sites. A weighted variant, defrel/bank-w, recovers best-first enumeration when the natural depth-first order misses compact representatives. On preliminary benchmarks, defrel/bank substantially outperforms depth-bounded baselines on most deep targets, though it loses on a small family where the canonical order is suboptimal.