Итератор: внутрь и наружу.

[_winnie]

Два способа реализации итерации по последовательности:

1) internal iteration, "callback": программист передаёт в функцию типа foreach свой callback
2) external iteration, "iterator interface": программист зовёт у объекта функцию GetNext() и HasMore()

Недостатки callback видно на примере "а попробуй перечислить две последовательности через один (interleave([A1,A2,...], [B1,B2,...]) -> A1,B1,A2,B2,...)".
В случае iterator interface всё очевидно: зовём GetNext() у одного итератора, затем у другого. А если foreach зовёт callback для всех элементов - не получится.

Недостатки второго, iterator interface - видно на примере "а попробуй написать итератор для дерева". Сделать первым способом очень легко, простая рекурсивная функция

for-each(node, callback) {
if (node) {
for-each(node->left, callback);
callback(node->value);
for-each(node->right, callback);
}
}
А сделать итератор для хождения по дереву, в котором хранить своё состояние и положение в дереве - гораздо сложнее, занудный алгоритм в котором легко сделать опечатку.

Итого, internal iterator - это иногда большая боль для пользователя библиотеки, а external iterator - иногда большая боль для писателя библиотеки.

В языках с yield, continuation и "зелёными потоками" - можно совместить преимущества обоих способов. Алгоритм (типа обхода дерева) выплевывает в какой-то "канал" текущее значение, а пользователь с другой стороны "канала" использует обычные методы GetNext() и HasMore(), интегрированые с for. Задача инструмента - реализовать этот канал. Такое встроено в Ruby, Go, Erlang. В bash с Unix-процессами. В Haskell с ленивыми списками может повезти, и вы не сделаете случайную незаметную утечку памяти (копию списка или список thunk-функций размером с входные данные).
В Питоне есть такое, но на 50%, нужна ручная работа и менять все промежуточные функции - при вызове каждой под-функции каждый раз писать цикл с yield. Python 3.3 экономит на строчке с for (yield from), но проблема "все функции переделать на генераторы" остаётся. Тем не менее, простые функции-генераторы - пишутся легко.

Источник: http://journal.stuffwithstuff.com/2013/01/13/iteration-inside-and-out/