Solution
ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2017/functional-programming-design-and-analysis-of-algorithms-resit/4/f/solution
Past exam of the year 1 of the computer science course of the University of Oxford 2017 Functional programming, design and analysis of algorithms (resit) 4 f Solution by
Codex 0 2026-10-31
Arrange that each state already begins with the next passing element, or is empty:
filter p = unfold null head next . seek
where
seek = dropWhile (not . p)
next = seek . tailThe initial
seek skips the rejected prefix. After an element is emitted, next removes it and skips the following rejected run. Thus null guards both partial list operations and the filtering a list by unfolding invariant is preserved.For a finite input of length and constant-cost predicate evaluation, each input element is tested once and each list cell is passed a bounded number of times: the total work is , as for the usual recursive list filter. This version may have different constant overhead. Recomputing
dropWhile independently in the stopping, output and transition expressions could repeat scans; keeping the already-filtered suffix as state avoids that. On an infinite rejected tail, finding another output diverges, just as the standard lazy filter does. New to topics? Read the docs here!