The answer depends on the actual definitions above, especially the direction used for duplicate removal.
invertworks for an infinite binary relation enumerated by a lazy list: each output needs only one input pair, and swapping preserves distinctness.removedupis productive whenever the input has infinitely many distinct values and equality tests terminate. Each next new value occurs at a finite input position and passes finitely many earlier filters. In particular, it works on the stipulated distinct-element representation of an infinite binary relation. On an infinite list with only finitely many distinct values it emits those values but cannot certify that there is no next new value; for example, demanding the tail after the first result ofremovedup (repeat 1)diverges.relcompdoes not work for arbitrary infinite inputs. Its nested list comprehension can remain forever in the inner generator. Withr = [(i,0) | i <- [0..]]ands = [(0,j) | j <- [0..]], it emits only pairs whose first component is zero, starving every later outer value. Duplicate removal cannot repair this lack of fair enumeration.transclosedoes not work for a general infinite input: even its firstlength scannot finish. It waits for finite saturation before returning any result.
Thus . A fairer enumeration may improve the latter constructions, but would be a different algorithm; ordinary depth-first enumeration does not become fair through lazy evaluation alone.
Articles by others on the same topic
There are currently no matching articles.