= Filtering a list by unfolding
For a <predicate> $p$, normalize the state to the first remaining passing element with `seek = dropWhile (not . p)`. Stop on an empty state, otherwise emit its head and continue from `seek (tail state)`. The invariant is that every nonempty state starts with a passing element. An initial `seek` establishes it; removing the emitted head and seeking again preserves it. Each rejected run is traversed once, giving <linear time> in the examined input prefix under constant-cost predicate tests.
Back to article page
