среда, 7 мая 2014 г.

Паттерн Итератор

Пред. паттерн: Паттерн Посредник

Назначение: представляет доступ ко всем элементам составного объекта, не раскрывая его внутреннего представления.

Подробнее – Iterator on Wiki

Мотивация

Практически любое приложение в той или иной мере работает с коллекциями данных. Мы постоянно используем векторы, списки, деревья и хеш-таблицы. В некоторых случаях для обработки данных коллекции мы используем специфический API конкретных коллекций, но в большинстве случаев мы получаем доступ к их внутренностям за счет специального абстрактного слоя – итераторов.

Итераторы предоставляют абстрактный интерфейс для доступа к содержимому составных объектов, не раскрывая клиентам их внутреннюю структуру. В результате получается четкое разделение ответственностей: клиенты получают возможность работать с разными коллекциями унифицированным образом, и классы-коллекций становятся проще за счет того, что ответственность за перебор ее элементов отводится отдельной сущности.

Итераторы настолько укоренились в большинстве языков и платформ, что их поддержка появилась даже на уровне языков программирования: foreach в C#, range-for в C++ 11, for в Java 5+ и даже в консервативном Eiffel появилась аналогичная конструкция – across. Более того, многие языки поддерживают не только «потребление итераторов» с помощью циклов foreach, но еще и их создание за счет блоков итераторов (Iterator Block в C# и VB) или так называемых Sequence Comprehension (доступных в F#, Scala, Phyton и многих других языках).

Примеры в .NET Framework

В .NET Framework итераторы представлены парами интерфейсов:

  • IEnumerable/IEnumerator для работы с необобщенными коллекциями (составными объектами);
  • IEnumerable<T>/IEnumerator<T> для работы с обобщенными коллекциями (составными объектами)
  • IObservable<T>/IObserver<T> для работы с «реактивными» (или push-based) коллекциями.

Использование итераторов в языке C# осуществляется с помощью цикла foreach, а создание итераторов упрощается за счет блоков итераторов (Iterator Block).

Обсуждение

Паттерн Итератор – это один из немногих паттернов, который пришел в .NET Framework из книги банды четырех практически в неизменном виде. Если взять исходную диаграмму классов из книги “Design Patterns”, заменить Aggregate на IEnumerable<T>, Iterator на IEnumerator<T> и немного изменить методы класса Iterator, то мы получим очень похожую картину:

clip_image002

Рисунок 1 – Классическая диаграмма паттерна Итератор

clip_image004

Рисунок 2 – Паттерн Итератор в .NET Framework

Итераторы в .NET являются однонаправленными итераторами только для чтения. При этом для получения итератора используется метод GetEnumerator интерфейса IEnumerable, который каждый раз возвращает новый экземпляр итератора.

Интерфейс IEnumerator также довольно прост:

  • MoveNext – переход на следующий элемент агрегата. Возвращает false, если достигнут конец последовательности.
  • Current – возвращает текущий элемент.
  • Reset – возвращает итератор к началу агрегата. Реализуется не всегда.

Сразу после создания, итератор указывает на -1-й элемент, поэтому для перехода к первому элементу нужно вызвать MoveNext как минимум один раз.

Итераторы в .NET могут показаться довольно примитивными, особенно по сравнению с итераторами в С++. Стандарт С++ определяет несколько разных типов итераторов: Input <- Forward <- Bidirectional <- Random Access. В С++ есть даже Output Iterator, т.е. итератор для вывода данных.

Платформа .NET поддерживает два типа итераторов: необобщенные и обобщенные итераторы. Первые появились с первой версии платформы .NET, а вторые были добавлены со второй версии вместе с обобщениями (generics) и блоками итераторов (iterator blocks).

clip_image006

Рисунок 3 – Обобщенные и необобщенные итераторы.

Особенности итераторов в C#/.NET
Контракт итераторов

У любого класса или интерфейса есть контракт. Иногда контракт бывает явным, и тогда он описывается с помощью соответствующих инструментов, таких как Code Contracts. Иногда он является неявным, тогда для понимания принципов использования, предусловий, постусловий и инвариантов, нужно обратиться к документации, внимательно прочитать секцию “remarks”, а часто еще и вникнуть в детали реализации.

При установки библиотеки Code Contracts в нашем распоряжении появляются контракты всех типов BCL. Однако встроенные контракты интерфейсов IEnumerable/IEnumerator не слишком хороши, поэтому давайте выведем их самостоятельно.

Нас будут интересовать контракты лишь методов MoveNext и свойства Current:

public T Current
{
   
get
    {
       
Contract.Requires(!Disposed, "Iterator should not be disposed."
);
       
Contract.
Requires(IteratorPointsToCorrectValue,
           
"MoveNext() should be called and return 'true'."
);

       
Contract.Ensures(true, "Returns current value from the Aggregate."
);
       
return default(T
);
    }
}

public bool
MoveNext()
{
   
Contract.Requires(!Disposed, "Iterator should not be disposed."
);
   
Contract.Requires(Valid, "Iterator should  be valid."
);

   
// Если итератор еще не дошел до конца агрегата,
    // то он будет перемещен на следующий элемент
    Contract.Ensures(Finished() ||
                InternalIndex == Contract.OldValue(InternalIndex) + 1
);
   
Contract.Ensures(Contract.Result<bool>() ==
                        (InternalIndex ==
InternalLength));
   
return default(bool);
}

ПРИМЕЧАНИЕ
Обращаю внимание, что это не настоящие контракты итератора, это лишь мое представление того, каким они могли бы быть! Настоящий контракт итератора, определенный в mscorlib.Contracts.dll не содержит всех этих вещей.

Контракт свойства Current:

Предусловие:

  • Итератор не должен быть освобожден с помощью вызова Dispose.
  • Итератор должен указывать на корректное значение: пользовательский код должен вызвать метод MoveNext, который должен вернуть true.

Постусловие:

  • Свойство Current вернет значение, на которое «указывает» итератор.
    Итератор не налагает ограничений, вернет ли это свойство null или нет.

Контракт метода MoveNext:

Предусловие:

  • Итератор не должен быть освобожден с помощью вызова Dispose.
  • Итератор должен быть валидным (коллекция не должна быть изменена после получения текущего итератора).

Постусловие:

  • Если итератор не дошел до конца коллекции, то итератор перейдет на следующий элемент и метод вернет true, в противном случае, метод вернет false.

Тут есть несколько интересных моментов. Во-первых, предусловие свойства Current слабее предусловия метода MoveNext. На самом деле у свойства Current вообще нет предусловий: мы можем обратиться к свойству Current после вызова Dispose и до вызова MoveNext и не получим исключений! Я же добавил эти требования в контракт, поскольку никто в здравом уме не должен обращаться к свойству Current без выполнения этих условий.

И еще один момент, связанный с методом MoveNext: вам никто не запрещает вызывать MoveNext на завершенном итераторе. В этом случае метод MoveNext просто вернет false! Вот это более валидное требование, поскольку оно позволяет заново проходить по завершенному итератору, а также свободно использовать итератор пустой коллекции (который можно рассматривать как завершенный).

Блоки итераторов

Использование итераторов в блоке foreach мы рассмотрим в следующем разделе, а пока рассмотрим процесс создания итераторов.

Процесс создания итераторов вручную является достаточно утомительным занятием, которое включает управление состоянием, и перемещением по элементам коллекции при вызове MoveNext. С помощью блока итераторов реализовать итератор существенно проще:

public static IEnumerator<int> CustomArrayIterator(this int[] array)
{
   
foreach (var n in array) { yield return n; }
}

(Пример создания итератора вручную рассмотрен в заметке “Итераторы в C#. Часть 1”)

С помощью блока итераторов мы можем создавать итераторы для своих коллекций, существующих коллекций или вообще для внешних ресурсов, таких как файлы. Для этого достаточно открыть файл в начале метода и возвращать прочитанные блоки данных с помощью yield return. Кроме того, мы можем генерировать данные бесконечным образом, о чем мы поговорим в разделе «Итераторы и генераторы».

ПРИМЕЧАНИЕ
Теперь должно быть понятно, почему метод Reset в контракте итератора является необязательным. Представьте себе, что итератор возвращает данные, пришедшие по сети. Как в этом случае мы сможем реализовать метод Reset?

Блок итераторов преобразуется компилятором языка C# в конечный автомат с несколькими состояниями, соответствующие начальному положению итератора (когда он указывает на -1-й элемент), конечному положению (когда итератор прошел все элементы) и «среднему» положению, при котором он указывает на определенный элемент. При этом блок итераторов представляет собой некую форму корутин, которые продолжают исполнение с предыдущего места благодаря методу MoveNext.

«Ленивость» итераторов

Итераторы, полученные с помощью блока итераторов являются ленивыми: их тело исполняется не в момент вызова метода, а при переборе элементов с помощью метода MoveNext. Это приводит к некоторым особенностям обработки ошибок, ведь даже валидация аргументов метода, возвращающего итератор, будет производиться уже в момент «потребления» итератора.

public static IEnumerable<string> ReadFromFile(string path)
{
   
if (path == null) throw new ArgumentNullException("path"
);
   
foreach(string line in File.
ReadLines(path))
    {
       
yield return
line;
    }
}


// Где будет ошибка?
var result = ReadFromFile(null); //1
foreach (var l in
result)
{
   
Console.WriteLine(l); //2
}

На этом же принципе построена большая часть методов LINQ (Language Integrated Query), что позволяет получать сложные запросы без лишних накладных расходов.

Подробнее об итераторах в языке C#, а также о деталях реализации блоков итераторов смотрите в статьях: Итераторы в C# - Часть 1, Часть 2, Часть 3.

Использование итераторов в цикле foreach

Цикл foreach является универсальным инструментом для обработки коллекций/последовательностей. Способ его преобразования компилятором зависит от типа перебираемой коллекции (обобщенная/необобщенная) и представляет простой цикл while. Пример обхода необобщенной коллекции выглядит таким образом:

public static void ForEachIEnumerable(IEnumerable sequence)
{
   
// foreach(var e in sequence) {Console.WriteLine(e);}
    IEnumerator enumerator = sequence.
GetEnumerator();
   
object current = null
;
   
try
    {
       
while (enumerator.
MoveNext())
        {
            current
= enumerator.
Current;
           
Console.
WriteLine(current);
        }
    }
   
finally
    {
       
IDisposable disposable = enumerator as IDisposable
;
       
if (disposable != null
)
        {
            disposable
.Dispose();
        }
    }
}

ПРИМЕЧАНИЕ
Для поддержки цикла foreach не обязательно наличие интерфейса IEnumerable/IEnumerable<T>. На самом деле, достаточно, чтобы класс коллекции содержал метод GetEnumerator, который будет возвращать тип, с методом bool MoveNext() и свойством Current.
Подробнее об этом можно почитать в статье: “Duck typing или “так ли прост старина foreach”.
Также стоит обратить внимание, что реализация блока foreach изменилась в C# 5.0, начиная с которого переменная “current” внесена во внутреннюю область видимости. Подробности: Замыкания на переменных цикла в C# 5.0

Интересный вопрос заключается в том, зачем нужна проверка во время исполнения того, реализует ли итератор интерфейс IDisposable с последующим вызовом метода Dispose? Можете подумать минутку самостоятельноJ

Давайте рассмотрим следующий совершенно корректный код:

public IEnumerable CrazyMethod(string path)
{
   
var file = File.
OpenText(path);
   
try
    {
       
yield return file.
ReadLine();
       
yield return int.Parse(file.
ReadLine());
    }
   
finally
    {
        file
.Close();
    }
}

Любой типизированный итератор реализует интерфейс IDisposable, поскольку сам интерфейс IEnumerator<T> наследует IDisposable. Причина этого в том, что итераторы, полученные с помощью блока итераторов легко могут содержать ресурсы, которые освобождаются в блоке finally, вызов которого как раз и осуществляется путем вызова Dispose итератора. Но дело все в том, что блок итераторов может возвращать не только типизированный итератор, но и его предшественников: IEnumerable/IEnumerator, которые не реализуют интерфейс IDisposable.

Итераторы или генераторы

Блок итераторов может использоваться для создания итераторов, т.е. для обхода некоторого агрегата в памяти (коллекции) или за ее пределами (итератор содержимого файла). Но помимо этого блок итераторов может использоваться для создания генераторов.

Вот пример простого бесконечного генератора чисел Фибоначчи:

public static IEnumerable<int> GenerateFibonaci()
{
   
int prev = 0
;
   
int current = 1
;

   
while (true
)
    {
       
yield return
current;

       
int tmp =
current;
        current
= prev +
current;
        prev
= tmp;
    }
}

В этом плане, блок итераторов в C# напоминает более общие концепции из других языков программирования, такие как List Comprehension, предназначенные для создания последовательностей и коллекций.

Валидность итераторов

В некоторых языках, таких как С++, понятие инвалидации итераторов (когда итератор коллекции становится недействительным) определено в спецификации языка, в разделе, посвященном конкретной коллекции. Так, например, не для всех контейнеров операция добавления элемента делает итератор недействительным: добавление элемента в двусвязный список вполне допустима, а добавление элемента в вектор – нет.

Подобные правила, хотя и не столь формальные, существуют и для коллекций .NET Framework. Точнее, есть лишь одно правило и оно не привязано к конкретному типу коллекции: при изменении коллекции все ранее полученные итераторы становятся недейсвтительными. Так, в обоих случаях ниже мы получим InvalidOperationException:

var list = new List<int> { 42, 12 };
var listIter = list.
GetEnumerator();
listIter
.
MoveNext();

list
.RemoveAt(1);
Console.WriteLine(listIter.Current); // Ok
listIter.MoveNext(); // InvalidOperationException

var linked = new LinkedList<int
>();
linked
.AddLast(42);
var linkedIter = linked.
GetEnumerator();
linkedIter
.
MoveNext();

linked
.AddLast(12);
Console.WriteLine(linkedIter.Current); // Ok
linkedIter.MoveNext();
// InvalidOperationException

Это поведение коренным образом отличаются от правил коллекций языка С++, поскольку в случае std::vector и std::list обе приведенные операции были бы допустимыми.

Итераторы и структуры

Итераторы всех коллекций .NET Framework являются изменяемыми структурами. Это избавляет от дополнительного выделения памяти в управляемой куче при проходе по коллекции, а с другой стороны, может привести к неожиданному результату:

var x = new {Items = new List<int> {1, 2, 3}.GetEnumerator()};
while (x.Items.
MoveNext())
{
   
Console.WriteLine(x.Items);
}

Но несмотря на потенциальную опасность, итераторы любой широко используемой коллекции должен быть структурой. Более того, в некоторых случаях есть правила, запрещающие использовать коллекции с классами-итераторами. Хорошим примером является правило участия в проекте Roslyn, которое запрещает использовать классы-итераторы в критических участках кода! (см. Roslyn. How to Contribute, раздел Coding Conventions)

ПРИМЕЧАНИЕ
Подробнее о проблемах с изменяемыми значимыми типами читайте в заметках: “О вреде изменяемых значимых типов” и “О вреде изменяемых значимых типов. Часть 2”, а еще один пример проблемы изменяемых итераторов рассмотрен в заметке: “Observable.Generate и перечисление списков”.

Push-based итераторы

Мало кто обратил внимание, что в книге Банды четырех определены два вида итераторов: внешний и внутренний, в зависимости от того, кто управляет итерацией – клиент или сам итератор.

Внешний итератор – это классический (pull-based) итератор, когда процессом обхода явно управляет клиент путем вызова метода Next или ему подобного. Внутренний итератор – это push-based итератор, которому передается метод обратного вызова и он сам уведомляет клиента о «посещении» следующего элемента.

Несложно догадаться, что ранее мы рассмотрели внешний итератор, а внутренний итератор в .NET представлен библиотекой Reactive Extensions и парой интерфейсов: IObserver<T>/IObservable<T>. Да, эта пара интерфейсов больше напоминают наблюдатель, а не итератор, но пример все расставит по местам:

var list = new List<int> {1, 2, 3};
IObservable<int> observable = list.
ToObservable();
observable
.
Subscribe(
    onNext: n
=> Console.WriteLine("Processing: {0}"
, n),
    onCompleted: ()
=> Console.WriteLine("Sequece finished"));

Данный пример не имеет особого смысла, но, например, преобразование в «наблюдаемую» коллекцию объекта SqlDataReader, который также реализует IEnumerable вполне имело бы смысл.

ПРИМЕЧАНИЕ
Подробнее познакомиться с «реактивными расширениями» можно в серии статей Ли Кэмпбелла (Lee Campbell) – Introduction to Rx.

Применимость

По своему определению, итератор применяется для доступа к содержимому составных объектов, типичным примером которых являются коллекции. Но стоит ли делать «итерируемыми» бизнес объекты?

Давайте вернемся к вопросу анализа паттернов проектирования. У нас может быть класс PatternsDetector который вполне может реализовывать интерфейс IEnumerable<DesignPattern>, что позволит его клиентам «перебирать» полученные паттерны проектирования. Но вопрос, насколько это отношение корректно?

Я обычно отношусь настороженно к такому подходу. Во-первых, детектор паттернов НЕ ЯВЛЯЕТСЯ коллекцией паттернов. Во-вторых, не вполне понятно, когда именно будет происходить анализ: в конструкторе класса или непосредственно в момент перебора элементов?

Именно поэтому я предпочитаю реализовывать интерфейсы IEnumerable<T> только классами, которые по своей природе являются коллекциями элементами, а во всех других случаях делать свойство или метод, которые предоставят доступ к коллекции элементов:

class PatternsAnalyzer
{
   
public PatternsAnalyzer(string
source)
    { }

   
public IEnumerable<DesignPattern
> Analyze()
    {
}
}

ПРИМЕЧАНИЕ
Недавно Эрик Липперт дает похожий совет на StackOverflow.com в ответе на вопрос: “Why not inherit from List<T>”, поясняя, должен ли класс FootballTeam наследовать от List<Player>. Эрик советовал аналогичным образом: футбольная команда НЕ ЯВЛЯЕТСЯ списком игроков, поэтому не класс FootballTeam не должен наследовать List<Player>. В этом случае гораздо лучше подходит отношение ИМЕЕТ, а значит команда должна содержать список игроков.

Дополнительные ссылки

  1. Programming Stuff. Итераторы в C#. Часть 1.
  2. Programming Stuff. Итераторы в C#. Часть 2.
  3. Programming Stuff. Итераторы в C#. Часть 3.
  4. Programming Stuff. Duck typing или ”так ли прост старина foreach?”.
  5. Programming Stuff. Замыкания на переменных цикла в C# 5.0.
  6. Programming Stuff. Контракты на платформе .NET.
  7. Jon Skeet. Iterator block implementation details.
  8. Eric Lippert. Iterator Block, Part One.
  9. Eric Lippert. Iterator Block, Part Two: Why no ref or out parameters?

--------------------

Понравилась статья? Вы же знаете, что ею можно поделиться с друзьями/коллегами;) Вам не сложно, а мне будет приятно.

21 комментарий:

  1. > "Совмещает роли методов Next и IsDone"
    Нарушая тем самым CQS, отчего Бертран Мейер негодуе. Интересно, зачем авторы так поступили.

    ОтветитьУдалить
    Ответы
    1. Да, меня это тоже напрягает. Попробуй сделать Merge последовательностей, представленных двумя итераторами. Там очень нужно знать его текущее состояние (завершен или нет), не пытаясь при этом перейти на другой элемент, если итератор еще не достиг конца последовательности.

      А вот почему так сделано: хз. Решили, что так будет проще. Одним шагом убить два зайца.

      Удалить
  2. Этот комментарий был удален автором.

    ОтветитьУдалить
  3. "При этом для получения итератора используется метод GetEnumerator интерфейса IEnumerator"
    Наверное, имелось в виду IEnumerable?

    ОтветитьУдалить
  4. Сергей, реквестирую статью по Rx, раз уж вы их затронули. Было бы интересно почитать ваше мнение

    ОтветитьУдалить
    Ответы
    1. Vlad, у меня есть небольшая статья по Rx-ам - "Реактивные расширения и асинхронные операции">. Можно и подробнее как-нить описать будет. Но если кратко, то мне идея (да и реализация тоже) очень даже симпатична. А тот факт, что реактивное программирование - это скорее парадигма, а не конкретная библиотека, то в Rx-ы вполне можно инвестировать свое время, ведь полученные знания можно будет использовать в F#, Scala, Haskell и многих других языках и средах.

      Удалить
  5. У вас в контрактах для MoveNext второй Ensures кидает исключение для всех коллекций размером больше единицы. Условие нужно заменить на <=

    ОтветитьУдалить
    Ответы
    1. По идее, его нужно поменять на "<". Т.е. результат должен быть True до тех пор, пока текущий внутренний индекс итератора не дошел до конца коллекции (т.е. еще меньше Length).

      Удалить
    2. Этот комментарий был удален автором.

      Удалить
  6. Да, судя по тому, что в предыдущем постусловии проверяется Finished, то <

    ОтветитьУдалить
  7. 1. Спасибо за, как всегда, интересную статью!
    2. Имхо, причислять IObservable к итераторам - несколько смелое решение.
    Конечно, Erik Meijer, бла-бла, стрелки назад, вывернем итератор наизнанку и получим наблюдателя и т.п. Но различий между ними хватило, чтобы GoF посчитали их разными паттернами и, поэтому, нужны хотя бы оговорки.

    ОтветитьУдалить
    Ответы
    1. Мне кажется, что аналогично смелым решением считать IObserver/IObservable классическим наблюдателем. Ну и я же обосновал, почему можно считать IObserver/IObservable вывернутым итератором: поскольку это ни что иное, как внешний итератор, описанный бандой четырех. В этом плане, я ничего не придумывал:))

      Удалить
    2. Этот комментарий был удален автором.

      Удалить
    3. Не буду утверждать, что он классический. Но то, что он слегка усовершенствованный - буду. :)
      http://en.wikipedia.org/wiki/Observer_pattern
      Выделяем из Subject интерфейс, делая его генериком, параметризованным типом параметра метода notify, называем IObservable.
      Вместо пары registerObserver/unregisterObserver делаем один метод Subscribe, возвращающий объект, через который можно произвести отписку (возвращаем IDisposable с методом Dispose); метод notifyObservers оставляем деталью реализации Subject (т.е. не выносим в интерфейс).
      Observer делаем интерфейсом IObserver[T]. Разбиваем notify на три разных метода (OnNext, OnError, OnCompleted) - чтобы явно разделить виды оповещений.

      Удалить
    4. Подозреваю, что понятие push-коллекция было придумано, чтобы "from ... in ... select ..." не взрывало мозг, когда применялось для IObservable.
      А синтаксис "from ... in ... select ..." и названия методов Select с SelectMany были выбраны намеренно, чтобы было похоже на SQL и никто бы не заподозрил, что мимо проходил Эрик и намонадил тут... :)
      Но мы-то знаем! ;)

      Удалить
    5. Полагаю, второе, что пришло в голову прожженому хаскелисту Эрику (после реализации аналога монады list на основе интерфейса IEnumerable) - это реализовать монаду continuation или ее аналог. Но возникли две трудности:
      1. При классической реализации continuation monad ничто не спасет от разрыва мозга, когда для нее будет применяться sql-подобный linq-синтаксис, поэтому нужно как-то за уши притянуть некую коллекционность.
      2. Хотелось бы предотвратить лишние итерации головного мозга у среднестатистических ООПшников и, в идеале, использовать что-то знакомое им.

      Монада continuation позволяет:
      1. Выполнить переданную лямбду более одного раза.
      2. Запомнить переданную лямбду и выполнить ее позже.
      Если соблюдены оба условия, то (о удача!) получим штуку, очень похожую на знакомый ООПшникам паттерн Наблюдатель. Осталось только слегка обобщить его и придумать телегу про "Итератор, вывернутый наизнанку", чтобы он мыслился как "источник последовательности событий" и, тем самым, придать ему вышеупомянутую коллекционность.

      Моя версия истории возникновения IObservable/IObserver. :D

      Удалить
    6. @artelk: спасибо за параллели и исторический экскурс:) Но моя аналогия итератора с парой интерфейсов IObserver/IObservable следующая: (цитата из GoF, стр. 252, раздел "Реализация" паттерна Итератор):

      Какой участник управляет итерацией. Важнейший вопрос состоит в том, что управляет итерацией: сам итератор или клиент, который им пользуется. Если итерацией управляет клиент, то итератор называется внешним, в противном случае - внутренним(*). Клиенты, применяющие внешний итератор, должны явно запрашивать у итератора следующий элемент, чтобы двигаться дальше по агрегату. Напротив, в случае внутреннего итератора клиент передает итератору некоторую операцию, а итератор уже сам применяет эту операцию к каждому посещенному во время обхода элементу агрегата.
      Внешние итераторы обладают большей гибкостью, чем внутренние. Например, сравнивать две коллекции на равенство с помощью внешнего итератора очень легко, а с помощью внутреннего - практически невозможно. Слабые стороны внутренних итераторов наиболее отчетливо проявляются в таких языках, как С++, где нет анонимных функций, замыканий (closure) и продолжений (continuation), как в Smalltalk или CLOS. НО, с другой стороны, внутренние итераторы проще в использовании, поскольку они вместо вас определяют логику обхода.

      ----
      (*) Грейди Буч (Grady Booch) называет внешние и внутренние итераторы соответственно активным и пассивным. Термины "активный" и "пассивный" относятся к роли клиента, а не к действиям, выполняемым итератором.

      Итого, что мы видим: идея внутренных (push-based или active) итераторов зародилась задолго до Эрика, но он очень удачно сгладил границы между двумя типами итераторов, сделав "API потребления" одинаковым.

      Т.е. для меня важна здесь историческая составляющая, а не то, как именно Эрик пришел к дуальности (возможно он черпал идеи не только в трудах по ФП, но и в трудах по ООП).

      Удалить
    7. Хмм... ишь ты. :)
      Только факт прибитости классического патерна Итератор к коллекции (или другой структуре, лежащей в памяти, например AST) нам как бы намекает, что под внутренним итератором имеется ввиду что-то типа List.ForEach или
      myCollection.GetForEachIterator().ForEach(Console.WriteLine)
      или может
      new ForEachIterator(myCollection).ForEach(Console.WriteLine)
      Т.е. делается синхронный обход по подлежащей структуре.
      В то время как IObservable/IObserver нацелен, в первую очередь, на асинхронные события и оповещения о них, т.к. обход произвольных коллекций уже решен за счет IEnumerable и linq to objects. Более того, поскольку IEnumerable штука более обобщенная, чем классический итератор и за ней может скрываться генератор, то и обход синхронных "как-бы событий" тоже решен.
      Если бы под внутренним итератором авторы держали в голове, что переданная лямбда может быть выполнена позже, по наступлению некоего события, и неоднократно, то им было бы очевидно, что паттерн Наблюдатель - это частный случай этого самого "внутреннего" Итератора. Однако в книге они даже не указали о родственности этих паттернов (см. раздел "Родственные паттерны").
      А про уведомления/оповещения там поётся именно в песне "Паттерн Наблюдатель".
      Короче, возражаю. :)

      Удалить
    8. Ну смотри, во-первых, твой пример:
      myCollection.GetForEachIterator().ForEach(Console.WriteLIne);

      Абсолютно аналогичен Rx-ам:

      myCollection.ToObservable().Subscribe(Console.WriteLine);

      Да, я согласен, что классический итератор говорит об обходе агрегата и обычно разделяется от генератора. С другой стороны, их можно и объединять (как это сделано в подавляющем большинстве платформ). И в этом случае асинхронный обход внешнего итератора тоже выглядит логичным, ведь связь между синхронным и асинхронным внешним итератором аналогична разделению между итератором и генератором.

      К тому же, это нормально, что об оповещении поется именно в "Итераторе", но ведь здесь явно сказано, что внутренний итератор принимает callback, а это уже есть форма наблюдателя.
      И еще: далеко не все паттерны проектирования находятся на одном уровне абстракции. Например, посредник может быть реализован на основе наблюдателя; аналогично внутренний итератор может быть реализован на основе наблюдателя. В этом не будет криминала: паттерны - они же на то и паттерны, чтобы не задавать жестких ограничений.

      Поэтому если смотреть на проблему шире (а паттерны - это и есть попытка обобщения решений конкретных задач), то вполне можно считать IObserver/IObservable одной из возможных реализаций внешних итераторов для платформы .NET:)

      Удалить
    9. Можно, ровно на столько, на сколько Наблюдатель можно считать частным случаем внутреннего Итератора или наоборот: внутренний Итератор - частным случаем Наблюдателя (когда коллекция "как бы событий" передается в конструктор Наблюдателя и запоминается, а при подписке мы всю эту пачку поэлементно и синхронно заталкиваем в переданную лямбду). :)

      Удалить