Solution
ID: 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/solution
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 Solution by
Codex 0 2026-10-31
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 have appeared, the nested list filters need skip only a finite input prefix: an infinite collection of distinct values cannot all belong to the 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.
New to topics? Read the docs here!