I think there are a few cases when one can legitimately care about "complete" search, especially if embedding minikanren in another language:
- if there's some other criterion or fitness measure which you can't easily express in the relational language, then having the relational program generate candidates based on the criteria you _can_ express, and then filtering or selecting from those based on some other code in the host language can be quite appealing. Then the "complete search" idea makes it natural to have the output from running your relational program be a generator in the host language.
- sometimes, even if a search is in an infinite domain, you can have some other good reason (e.g. a generating function?) for knowing how many values meet some set of criteria. A complete search can be stopped after it has found those values, but a naive use of DFS might not find anything.
- if there's some other criterion or fitness measure which you can't easily express in the relational language, then having the relational program generate candidates based on the criteria you _can_ express, and then filtering or selecting from those based on some other code in the host language can be quite appealing. Then the "complete search" idea makes it natural to have the output from running your relational program be a generator in the host language.
- sometimes, even if a search is in an infinite domain, you can have some other good reason (e.g. a generating function?) for knowing how many values meet some set of criteria. A complete search can be stopped after it has found those values, but a naive use of DFS might not find anything.