The correctness-first Ichor.Backtrack engine: a solution is a plain
thunk, (-> :empty | {:solution, value, rest}) -- a manually-unfolded
lazy list (a "search tree," hence the name), not backed by any
process/agent or Elixir Stream machinery. Each combinator forces
exactly one step of whatever it's combining, which is what makes
once/1 genuinely stop exploring rather than compute everything and
discard all but the first result, and what makes an infinite Prolog
recursion still yield its first solutions instead of hanging forever
building a list.
Kept intentionally simple over "fair" interleaving search (the way
microKanren's own mplus/bind alternate between branches):
disjunction/2 exhausts its first argument before touching its
second, depth-first, left-to-right -- exactly Prolog's own clause-order
backtracking, not a design gap. A future WAM-grade engine implementing
the same Ichor.Backtrack behaviour could still choose differently.
Summary
Functions
Every solution of a, then every solution of b -- disjunction/2's own primitive.
The empty solution sequence -- a goal that never succeeds reduces to this.
Every solution of solutions, each fed through fun (itself producing a lazy sequence) and concatenated in order -- conjunction/2's own primitive.
A single solution followed by nothing else.
The first n solutions, computed lazily -- once/1's own primitive (n = 1).
Eagerly pulls every solution into a plain list -- for tests/finite searches only; never call this on a search that might not terminate.
Types
Functions
Every solution of a, then every solution of b -- disjunction/2's own primitive.
@spec empty() :: t()
The empty solution sequence -- a goal that never succeeds reduces to this.
Every solution of solutions, each fed through fun (itself producing a lazy sequence) and concatenated in order -- conjunction/2's own primitive.
A single solution followed by nothing else.
@spec take(t(), non_neg_integer()) :: t()
The first n solutions, computed lazily -- once/1's own primitive (n = 1).
Eagerly pulls every solution into a plain list -- for tests/finite searches only; never call this on a search that might not terminate.