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

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

The 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 $n$ 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 $O(n)$, 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.