You picked an especially bad pattern for your proof. Iterators aren't inherently functional. In the imperative world they needlessly maintain state and are by n

You picked an especially bad pattern for your proof. Iterators aren't inherently functional. In the imperative world they needlessly maintain state and are by nature one giant side effect. Data abstraction doesn't even require an iterator "pattern" to achieve iteration, that's the whole point of data abstraction that a "pattern" isn't required but merely a "concept". In Clojure, for example, the concept is a sequence which has stateless traversal. That paper you quote even makes the distinction between the separate approaches taken from functional versus imperative.