= Solution
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 \b[$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.
Back to article page
