July 25, 2007

Being lazy

Много всякого говорят про ленивые вычисления, то есть, когда какой-то код выполняется только в том случае, когда его результат действительно нужен, а не "впрок". Не буду сильно углубляться в описание того, что же это такое, ленивые вычисления, про это много уже написано. Последним, что я встретил на эту тему, был рассказ об itertools в Python.

Отличная, надо сказать, штука, эти "вычисления по запросу". В приведённой выше статье про itertools много хорошего говорится об их пользе в качестве средства обработки коллекций. И правда! Замечательная идея, взять коллекцию и пробегать её только тогда, когда это необходимо. Или не пробегать, а генерировать следующий элемент, как в классическом примере про бесконечную последовательность Чисел Фибоначчи, которая упоминается почти везде, где разговор идёт о правильности ленивых вычислений. Особенно любят это дело (бесконечные последовательности и ленивые вычисления) сторонники Haskell. Нигде я не встречал так часто слова "lazy" как в литературе по этому замечательнм языку.

Сам я, к сожалению, пока что не познал премудростей Haskell'а, и моим рабочим языком программирования по прежнему является старый добрый C#. В своей 2.0 версии C# получил от разработчиков замечатльную возможность, называемую итераторами. То есть, нет, итераторы там были и раньше, но был добавлен новый способ их реализации. Если раньше для того, чтобы вернуть коллекцию (лучше, наверное, сказать "последовательность"), надо было писать свою собственную реализацию IEnumerator, то теперь достаточно выучить волшебное слово "yield" (кстати, знакомое всем Python и Ruby разработчикам, но действующее, как обычно, несколько по-своему), а точнее фразу "yield return", которая совершенно незаметно сделает всю грязную работу. Есть, правда, некотороые ограничения на код с использванием yield return, но это не столь важно в контексте нашего разговора.

Итак. В C# 2.0 возможна реализация итераторов, которые позволяют пробегать коллекцию "ленивым" способом, то есть только по надобности. Ну и, конечно, если есть инструмент типа "молоток", то, в процессе забивания гвоздей, можно смело ожидать удара по любимой руке. Так и с итераторами. Для наглядности приведу код.

using System;
using System.Collections.Generic;

namespace Foo {
public static class Bar{

public static IEnumerable<int> Map(IEnumerable<int> items){
foreach(int i in items){
Console.WriteLine(string.Format("inside Map: {0}", i));
yield return i;
}
}

public static void JustDoIt(IEnumerable<int> ints){
foreach(int i in ints){
Console.WriteLine(string.Format("inside JustDoIt: {0}", i));
}
}

public static void Main(string[] args){
List<int> ints = new List<int>();
ints.AddRange(new int[]{1, 2, 3});
IEnumerable<int> afterMap = Map(ints);
try{
ints.Add(123);
ints.RemoveAt(1);
JustDoIt(ints);
}
catch(Exception ex){
Console.WriteLine(ex.ToString());
}
}
}

Простенький итератор представлен методом Map, который не делает ровным счётом ничего, кроме того, что "лениво" пробегает исходную коллекцию, выводя по дороге элементы коллекции на печать. Простой метод JustDoIt имитирует метод-потребитель итератора. Ну и собственно, метод Main. В нём создаётся коллекция [1, 2, 3], после этого создаётся тот самый итератор. Затем коллекция изменяется, и лишь вслед за этим вызывается метод-потребитель.


Поведение ожидаемое (если, конечно, понимать суть). В JustDoIt была обработана не та коллекция, которая передавалась в Map, а её изменённая версия, хотя сам Map был вызван до модификации, и вроде бы ints и afterMap ссылаются на разные объекты.


А теперь собственно о том, как можно "ударить молотком по пальцу". Придумаем более сложный пример. Есть TreeView, в нодах которого присутствует Tag, в котором в свою очередь хранится какое-то очень важное значение. И вот в один прекрасный момент нам надо получить все значения Tag для выбранных элементов дерева с приведением к конкретному типу.



public static IEnumerable<Output> Map<Input, Output>(
Converter<Input, Output> convert, IEnumerable<Input> container) {
foreach(Input item in container) {
yield return convert(item);
}

При помощи вот такого простенького Map'а я могу применять почти любое действие к почти любой коллекции. Например, могу написать метод, возвращающий значение Tag для узла дерева, и передать этот метод в Map вместе с коллекцией выбранных узлов дерева. И на выходе из Map у меня будет требуемая "коллекция". Казалось бы, ровно то, что и требовалось. Однако, всё не так просто. Как стало ясно из предыдущего примера, на выходе из Map'а получается не коллекция (я намеренно так назвал её и поставил кавычки) а итератор, который по натуре своей создание ленивое и не станет делать ничего до тех пор, пока его об этом явно не попросят. А попросить его о чём-то могут уже после того, как список выбранных узлов в дереве изменится. Вот Вам и грабли. Так что, ко всякому умному инструменту надо подходить с пониманием, даже если это простой и до боли знакомый итератор.


This page is powered by Blogger. Isn't yours?