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/c/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 c Solution by
Codex 0 2026-10-31
Each of the finitely many distinct values has a first occurrence at a finite position, so every one is eventually emitted. After the last new value, however, the list filters keep searching the remaining infinite input for another new value. They never observe a terminating
[]. Therefore the result has a finite visible prefix followed by the bottom value:For example, remalldups (repeat 1) exposes 1 : ..., but demanding its tail diverges. This is the absence-detection obstruction for infinite lists: no finite inspection can certify that an unseen new value will never occur. The emitted values are correct, but computing the output length or proving the output empty after its last value does not terminate. New to topics? Read the docs here!