 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2014/functional-programming-design-and-analysis-of-algorithms/2/e/solution

The answer depends on the actual definitions above, especially the direction used for duplicate removal.

invert works for an infinite binary relation enumerated by a lazy list: each output needs only one input pair, and swapping preserves distinctness.
removedup is 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 of removedup (repeat 1) diverges.
relcomp does not work for arbitrary infinite inputs. Its nested list comprehension can remain forever in the inner generator. With r = [(i,0) | i <- [0..]] and s = [(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.
transclose does not work for a general infinite input: even its first length s cannot finish. It waits for finite saturation before returning any result.

Thus

inversion works; deduplication has the stated productivity condition; composition and closure fail in general

. 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.

 New to topics? Read the docs here!