Past exam of the year 1 of the computer science course of the University of Oxford / 2005 / Functional programming, data structures and algorithms, procedural programming, and digital hardware / 3 / b

Assume a proper lazy list with defined elements and terminating equality tests. If infinitely many distinct values occur, first-occurrence duplicate removal produces an infinite list of distinct values, in first-occurrence order. To produce the next new value after $k$ have appeared, the nested list filters need skip only a finite input prefix: an infinite collection of distinct values cannot all belong to the $k$ already seen. The next new value therefore occurs at a finite position and is reached in finite work. ConsequentlyThis is a stream productivity claim, not a bounded-delay claim: arbitrarily long runs of repetitions can make successive delays arbitrarily large. Undefined elements or diverging equality tests invalidate the stated assumptions.